運(yùn)行時(shí)的存儲(chǔ)組織

運(yùn)行時(shí)的存儲(chǔ)組織第一頁，共四十三頁，2022年，8月28日知識(shí)結(jié)構(gòu)第二頁，共四十三頁，2022年，8月28日8.1概述從邏輯上看，代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間的分配所謂運(yùn)行時(shí)的環(huán)境是指目標(biāo)計(jì)算機(jī)的寄存器和存儲(chǔ)器的結(jié)構(gòu)，以及用來管理存儲(chǔ)器并保存執(zhí)行過程所需要的信息。幾乎所有的程序設(shè)計(jì)語言都使用3種類型的存儲(chǔ)環(huán)境：完全靜態(tài)環(huán)境、基于棧的存儲(chǔ)環(huán)境和基于堆的存儲(chǔ)環(huán)境中的一種或幾種。第三頁，共四十三頁，2022年，8月28日8.1概述從邏輯上看，代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間的分配數(shù)據(jù)空間包括：用戶定義的各種類型的數(shù)據(jù)對(duì)象（變量和常量）所需的存儲(chǔ)空間，作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元，調(diào)用過程時(shí)所需的連接單元，組織輸入/輸出所需的緩沖區(qū)。第四頁，共四十三頁，2022年，8月28日8.1概述存儲(chǔ)管理復(fù)雜度取決于源語言本身，具體包括：允許的數(shù)據(jù)類型的多少語言中允許的數(shù)據(jù)項(xiàng)是靜態(tài)確定動(dòng)態(tài)確定程序決定名字的作用域的規(guī)則和結(jié)構(gòu)段結(jié)構(gòu)過程定義不嵌套，只允許過程遞歸調(diào)用分程序結(jié)構(gòu)分程序嵌套過程定義嵌套第五頁，共四十三頁，2022年，8月28日存儲(chǔ)區(qū)劃分成：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)、堆區(qū)：目標(biāo)代碼區(qū)用以存放目標(biāo)代碼，這是固定長(zhǎng)度的，即編譯時(shí)能確定的全程/靜態(tài)數(shù)據(jù)區(qū)用以存放編譯時(shí)能確定所占用空間的數(shù)據(jù)堆/棧區(qū)用于可變數(shù)據(jù)以及管理過程活動(dòng)的控制信息目標(biāo)代碼區(qū)全程/靜態(tài)數(shù)據(jù)區(qū)棧↑自由空間↓堆8.1運(yùn)行時(shí)存儲(chǔ)空間的劃分第六頁，共四十三頁，2022年，8月28日過程的活動(dòng)記錄過程的活動(dòng)記錄是一段連續(xù)的存儲(chǔ)區(qū)，用來存放過程的一次執(zhí)行所需要的信息。自變量（參數(shù)空間）返回地址用作局部數(shù)據(jù)的空間用作局部臨時(shí)變量的空間8.2過程活動(dòng)記錄第七頁，共四十三頁，2022年，8月28日編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是程序語言設(shè)計(jì)時(shí)對(duì)程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定在程序設(shè)計(jì)語言語義學(xué)中，使用environment表示將一個(gè)名字映射到一個(gè)存儲(chǔ)位置的函數(shù)，state表示存儲(chǔ)位置到值的映射，如圖10.2所示：第八頁，共四十三頁，2022年，8月28日數(shù)據(jù)空間的使用和管理方法分成三種：靜態(tài)存儲(chǔ)分配棧式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)分配第九頁，共四十三頁，2022年，8月28日8.2靜態(tài)存儲(chǔ)分配指在編譯時(shí)對(duì)數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)位置，運(yùn)行時(shí)始終不變。即一旦存儲(chǔ)空間的某個(gè)位置分配給了某個(gè)數(shù)據(jù)名，則在目標(biāo)程序的整個(gè)運(yùn)行過程中，此位置（地址）就屬于該數(shù)據(jù)名。由靜態(tài)存儲(chǔ)分配產(chǎn)生的數(shù)據(jù)區(qū)稱為靜態(tài)數(shù)據(jù)區(qū)。靜態(tài)存儲(chǔ)分配適用于不允許遞歸過程或遞歸調(diào)用，不允許可變體積的數(shù)據(jù)結(jié)構(gòu)的語言靜態(tài)存儲(chǔ)分配的特點(diǎn)：簡(jiǎn)單、易于實(shí)現(xiàn)例：FORTRAN語言，它所有的數(shù)據(jù)都屬于這一類。第十頁，共四十三頁，2022年，8月28日8.2靜態(tài)存儲(chǔ)分配例：FORTRAN程序主程序段

ProgramTEST

……ENDSUBROUTINELADD(A,SIZE,QMEAN)COMMONMAXSIZEINTEGERMAXSIZE,SIZEREALA(SIZE),QMEAN,TEMPINTEGERKTEMP0,0DO10K=1,SIZETEMP=TEMP+A(K)10CONTINUEQMEAN=TEMP/SIZERETURNEND

……KQMEAN返回地址TEMP3ASIZEMAXSIZETABLE(1)…(10)TEMP代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)附加過程主過程第十一頁，共四十三頁，2022年，8月28日靜態(tài)存儲(chǔ)分配：在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置8.2靜態(tài)存儲(chǔ)分配第十二頁，共四十三頁，2022年，8月28日?qǐng)D10.4給出一個(gè)FORTRAN77的程序例子：PROGRAMCNSUMECHARACTER*50BUF//程序體所擁有的靜態(tài)量BUFINTEGERNEXT//程序體所擁有的靜態(tài)量NEXTCHARACTERC,PRDUCE//程序體所擁有的靜態(tài)量CDATANEXT/1/,BUF/''/

C=PRDUCE()

BUF(NEXT:NEXT)=C

NEXT=NEXT+1

IF(C.EN.'')GOTO6

WRITE(*,'(A)')BUF(11)END第十三頁，共四十三頁，2022年，8月28日(12)CHARACTERFUNCTIONPRDUCE()CHARACTER*80BUFFER

INTEGERNEXT

SAVEBUFFER,NEXT//PRDUCE函數(shù)體所擁有的靜態(tài)量BUFFER,NEXT(16)DATANEXT/81/(17)

IF(NEXT.GT.80)THEN(18)

READ(*,'(A)')BUFFER(19)

NEXT=1(20)

ENDIF(21)

PRDUCE=BUFFER(NEXT:NEXT)(22)

NEXT=NEXT+1(23)

END

第十四頁，共四十三頁，2022年，8月28日?qǐng)D10.5中描述了該程序中局部變量的靜態(tài)存儲(chǔ)位置：第十五頁，共四十三頁，2022年，8月28日動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、可變數(shù)組或允許用戶自由申請(qǐng)和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)第十六頁，共四十三頁，2022年，8月28日棧式動(dòng)態(tài)存儲(chǔ)分配這種分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧第十七頁，共四十三頁，2022年，8月28日8.3.1簡(jiǎn)單棧式存儲(chǔ)分配對(duì)于沒有分程序結(jié)構(gòu)，過稱規(guī)定一不允許嵌套單允許過程遞歸調(diào)用的語言，可以采用一種簡(jiǎn)單的棧式存儲(chǔ)分配策略。C語言滿足上述特點(diǎn)。臨時(shí)工作單元

內(nèi)情向量簡(jiǎn)單變量形式單元參數(shù)個(gè)數(shù)返回地址老SP(前一活動(dòng)記錄的地址)TOPSPC語言過程的活動(dòng)記錄第十八頁，共四十三頁，2022年，8月28日一.簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn)最簡(jiǎn)單的程序設(shè)計(jì)語言結(jié)構(gòu)如圖10.7所示：

programmain;

//主程序頭全局變量或數(shù)組的說明；procR;

//過程R的頭…

//過程R的體end(R);

//過程R的尾procQ;

//過程Q的頭…

//過程Q的體end(Q);

//過程Q的尾主程序執(zhí)行語句

//主程序體end.(main)

//主程序尾第十九頁，共四十三頁，2022年，8月28日例如，圖10.7的程序結(jié)構(gòu)中，若主程序調(diào)用了過程Q，Q又調(diào)用了R,在R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖10.8(a)所示：若主程序調(diào)用了過程Q，Q遞歸調(diào)用自己，在Q過程第2次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖10.8(b)所示：若主程序先調(diào)用過程Q，然后主程序接著調(diào)用R，且Q過程沒有調(diào)用Q和R，這時(shí)Q和R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)分別如圖10.8(c)和10.8(d)所示：第二十頁，共四十三頁，2022年，8月28日第二十一頁，共四十三頁，2022年，8月28日常常使用兩個(gè)指針指示棧最頂端的數(shù)據(jù)區(qū)：SP：總是指向現(xiàn)行過程活動(dòng)記錄的起點(diǎn)TOP：始終指向已占用的棧頂單元第二十二頁，共四十三頁，2022年，8月28日這種語言若含有可變數(shù)組，則其過程活動(dòng)記錄的內(nèi)容如圖10.9所示：第二十三頁，共四十三頁，2022年，8月28日?qǐng)D10.10表明分配數(shù)組區(qū)之后的運(yùn)行棧情況，可以與圖

10.8（a）對(duì)照：第二十四頁，共四十三頁，2022年，8月28日二.嵌套過程語言的棧式實(shí)現(xiàn)Pascal語言程序結(jié)構(gòu)的特點(diǎn)是允許過程嵌套定義，如圖

8.11所示：第二十五頁，共四十三頁，2022年，8月28日第二十六頁，共四十三頁，2022年，8月28日?qǐng)D8.11的Pascal程序中過程定義的嵌套情況如下：sortreadarrayexchangequicksortpartition第二十七頁，共四十三頁，2022年，8月28日假如過程sort激活（調(diào)用）了過程quicksort，這時(shí)存儲(chǔ)棧中的情形如圖8.12所示，其中在quicksort過程活動(dòng)記錄中有一存儲(chǔ)單元（用斜線描繪）用以記錄過程quicksort可以引用sort中定義的變量a和x。也就是說，為了解決對(duì)非局部變量的存取問題，必須設(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)記錄的位置第二十八頁，共四十三頁，2022年，8月28日第二十九頁，共四十三頁，2022年，8月28日一種跟蹤方法是：在過程活動(dòng)記錄中增設(shè)存取鏈,指向包含該過程的直接外層過程的最新活動(dòng)記錄的起始位置。過程活動(dòng)記錄的內(nèi)容如圖8.13（a）所示。圖10.12所提到的情況可用圖8.13（b）所示：第三十頁，共四十三頁，2022年，8月28日因?yàn)镻L/O的過程是無參過程，PL/O也無動(dòng)態(tài)數(shù)組，所以它的過程活動(dòng)記錄的內(nèi)容如圖10.14所示：第三十一頁，共四十三頁，2022年，8月28日再回到圖10.11例子，如果該程序的某次執(zhí)行順序?yàn)椋簊ort

quicksort

quicksort

partition

exchange…圖10.15給出了進(jìn)入過程exchange之后運(yùn)行棧的示意，僅標(biāo)明存取鏈和控制鏈的值第三十二頁，共四十三頁，2022年，8月28日第三十三頁，共四十三頁，2022年，8月28日另一種跟蹤方法是：每進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表display嵌套層次：指過程定義的層數(shù)，始終假定主程序的層數(shù)為0，因此主程序稱為0層過程第三十四頁，共四十三頁，2022年，8月28日計(jì)數(shù)過程的層數(shù)用一個(gè)計(jì)數(shù)器Level，初值為0，每遇到過程說明則增1，過程說明結(jié)束則減1display是一個(gè)指針數(shù)組d，也可看做是一個(gè)小棧，自頂向下每個(gè)單元依次存放著現(xiàn)行層，直接外層，……直至最外層（0層，主程序?qū)樱┑让恳粚舆^程的最新活動(dòng)記錄的地址第三十五頁，共四十三頁，2022年，8月28日?qǐng)D10.11的程序，假定有如下四種調(diào)用情況：（a）sortquicksort…（b）sortquicksortquicksort…（c）sortquicksortquicksortpartition…（d）sort

quicksortquicksortpartitionexchange…圖10.16(a)-(d)分別說明上述四種情形的運(yùn)行棧和display第三十六頁，共四十三頁，2022年，8月28日第三十七頁，共四十三頁，2022年，8月28日display本身的體積在編譯時(shí)可確定，它作為單獨(dú)的表分配存儲(chǔ)還是作為活動(dòng)記錄的一部分，比如置于實(shí)參的上端（如圖10.17所示），則取決于編譯程序的設(shè)計(jì)者第三十八頁，共四十三頁，2022年，8月28日8.4堆式存儲(chǔ)分配假設(shè)程序運(yùn)行時(shí)有一個(gè)大的存儲(chǔ)空間，每當(dāng)需要時(shí)就從這片空間中借用一塊，不用時(shí)再退還，由于借還的時(shí)間先后不一，即不空間的使用不一定按照“先申請(qǐng)后釋放”的原則，經(jīng)一段運(yùn)行之后，程序運(yùn)行空間將被劃分成許多塊，有些占用，有些空閑。那么當(dāng)運(yùn)行程序要求一塊體積為N的空間時(shí)，需要決定應(yīng)該從哪個(gè)空閑塊得到這個(gè)空間。理論上講,應(yīng)該從比N稍大一些的空閑塊中取出N個(gè)單元，以便使大的空閑塊派更大的用場(chǎng)，但實(shí)現(xiàn)難度很大第三十九頁，共四十三頁，2022年，8月28日堆式存儲(chǔ)分配方法的基本思想是：先一個(gè)程序開始只想時(shí)有很大一塊存儲(chǔ)空間，運(yùn)行期間如果需要就從里面申請(qǐng)一塊存儲(chǔ)空間，使用完畢歸還。系統(tǒng)必須記錄所有使用情況，尤其是要記錄所有的空閑區(qū)以備后用，盡量把相連空閑區(qū)匯集成一個(gè)比較大的空閑區(qū)以免存儲(chǔ)區(qū)被分割為許多難以使用的碎片。堆式存儲(chǔ)分配方法的實(shí)現(xiàn)方法是：按定長(zhǎng)進(jìn)行分配。初始化時(shí)將堆存儲(chǔ)空間分成若干個(gè)長(zhǎng)度相等的快，按鄰塊的順序吧這些塊練成一個(gè)鏈表，每次申請(qǐng)空間從鏈表最前面的未使用節(jié)點(diǎn)開始分配，歸還時(shí)把節(jié)點(diǎn)插入鏈表，盡量保證第一個(gè)未使用的節(jié)點(diǎn)之后沒有已分配的塊。3種分配策略：（1）首次匹配法（2）最優(yōu)匹配法（3）最差匹配法第四十頁，共四十三頁，2022年，8月28日8.5