運(yùn)行時的存儲組織

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

第14頁,共43頁，2024年2月25日，星期天圖10.5中描述了該程序中局部變量的靜態(tài)存儲位置：第15頁,共43頁，2024年2月25日，星期天動態(tài)存儲分配如果一個程序設(shè)計語言允許遞歸過程、可變數(shù)組或允許用戶自由申請和釋放空間，那么，就需要采用動態(tài)存儲管理技術(shù)第16頁,共43頁，2024年2月25日，星期天棧式動態(tài)存儲分配這種分配策略是將整個程序的數(shù)據(jù)空間設(shè)計為一個棧第17頁,共43頁，2024年2月25日，星期天8.3.1簡單棧式存儲分配對于沒有分程序結(jié)構(gòu)，過稱規(guī)定一不允許嵌套單允許過程遞歸調(diào)用的語言，可以采用一種簡單的棧式存儲分配策略。C語言滿足上述特點(diǎn)。臨時工作單元

內(nèi)情向量簡單變量形式單元參數(shù)個數(shù)返回地址老SP(前一活動記錄的地址)TOPSPC語言過程的活動記錄第18頁,共43頁，2024年2月25日，星期天一.簡單的棧式存儲分配的實(shí)現(xiàn)最簡單的程序設(shè)計語言結(jié)構(gòu)如圖10.7所示：

programmain;

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

//過程R的頭…

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

//過程R的尾procQ;

//過程Q的頭…

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

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

//主程序體end.(main)

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

10.8（a）對照：第24頁,共43頁，2024年2月25日，星期天二.嵌套過程語言的棧式實(shí)現(xiàn)Pascal語言程序結(jié)構(gòu)的特點(diǎn)是允許過程嵌套定義，如圖

8.11所示：第25頁,共43頁，2024年2月25日，星期天第26頁,共43頁，2024年2月25日，星期天圖8.11的Pascal程序中過程定義的嵌套情況如下：sortreadarrayexchangequicksortpartition第27頁,共43頁，2024年2月25日，星期天假如過程sort激活（調(diào)用）了過程quicksort，這時存儲棧中的情形如圖8.12所示，其中在quicksort過程活動記錄中有一存儲單元（用斜線描繪）用以記錄過程quicksort可以引用sort中定義的變量a和x。也就是說，為了解決對非局部變量的存取問題，必須設(shè)法跟蹤每個外層過程的最新活動記錄的位置第28頁,共43頁，2024年2月25日，星期天第29頁,共43頁，2024年2月25日，星期天一種跟蹤方法是：在過程活動記錄中增設(shè)存取鏈,指向包含該過程的直接外層過程的最新活動記錄的起始位置。過程活動記錄的內(nèi)容如圖8.13（a）所示。圖10.12所提到的情況可用圖8.13（b）所示：第30頁,共43頁，2024年2月25日，星期天因為PL/O的過程是無參過程，PL/O也無動態(tài)數(shù)組，所以它的過程活動記錄的內(nèi)容如圖10.14所示：第31頁,共43頁，2024年2月25日，星期天再回到圖10.11例子，如果該程序的某次執(zhí)行順序為：sort

quicksort

quicksort

partition

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

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