運(yùn)行時(shí)存儲(chǔ)空間組織.ppt

1、過(guò)程的每一次運(yùn)行(或執(zhí)行)被稱為一次活動(dòng)(activation)?；顒?dòng)是一個(gè)動(dòng)態(tài)的概念，除了設(shè)計(jì)為永不停機(jī)的過(guò)程(如操作系統(tǒng)等)，或者是因設(shè)計(jì)錯(cuò)誤而出現(xiàn)死循環(huán)的過(guò)程之外，任何過(guò)程的活動(dòng)均有有限的生存期(life time)。,第九章 運(yùn)行時(shí)存儲(chǔ)空間組織,概述：編譯程序必須在生成目標(biāo)代碼前分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間變量、常量的存放和訪問(wèn),9.1目標(biāo)程序運(yùn)行時(shí)的活動(dòng),一. 過(guò)程（procedure）的活動(dòng) 過(guò)程的概念（定義，p241）： 靜態(tài)源程序，過(guò)程體，函數(shù) 動(dòng)態(tài)目標(biāo)程序的運(yùn)行活動(dòng),過(guò)程：為討論方便，將整個(gè)程序、函數(shù)均視為過(guò)程。,過(guò)程的活動(dòng)：是指該過(guò)程的一次執(zhí)行。,過(guò)程的活動(dòng)生存期：指從該過(guò)

2、程體第一步操作到最后一步操作之間的操作序。兩個(gè)過(guò)程的活動(dòng)生存期或嵌套或不重疊。,一個(gè)標(biāo)識(shí)符說(shuō)明在程序中能起作用的范圍稱為該說(shuō)明的作用域。,生存期和作用域?qū)Q定分配目標(biāo)程序數(shù)據(jù)空間的基本策略。 ex: Fig 9.1 program,例：寫(xiě)出參數(shù)傳遞的結(jié)果 Program simple(output); var x:integer; procedure change(y:integer); begin y:=1 end; begin x:=0; change(x); write(x) End.,傳值： x=0 傳地址： x=1,二、參數(shù)傳遞 :傳地址、傳值、傳名、得結(jié)果p241,9.2 運(yùn)行時(shí)存

3、儲(chǔ)器的劃分,一、存儲(chǔ)器的劃分,程序運(yùn)行時(shí)必須由操作系統(tǒng)分配一定的存儲(chǔ)空間，編譯程序應(yīng)完成對(duì)該存儲(chǔ)空間劃分：,存放編譯時(shí)可確定大小的數(shù)據(jù)對(duì)象，如目標(biāo)代碼、如FROTRUN,過(guò)程的活動(dòng)在編譯時(shí)不確定，在運(yùn)行時(shí)當(dāng)有新過(guò)程被調(diào)用，則將該過(guò)程的相關(guān)數(shù)據(jù)放入棧中（在生存周期內(nèi)的所有對(duì)象及其相關(guān)信息）,棧的lifo特性正好對(duì)應(yīng)過(guò)程的嵌套調(diào)用,存放動(dòng)態(tài)數(shù)據(jù)（如鏈表等不符合lifo協(xié)議的動(dòng)態(tài)數(shù)據(jù)）,二. 活動(dòng)記錄,為管理過(guò)程的活動(dòng)，用一個(gè)活動(dòng)記錄（Activation Record，連續(xù)的存儲(chǔ)塊）來(lái)表示其相應(yīng)的所有信息。,活動(dòng)記錄的結(jié)構(gòu)： 1. 臨時(shí)單元（存放表達(dá)式求值等）、內(nèi)情向量、局部變量為局部數(shù)據(jù)區(qū)；,2

4、. 形式單元：存放實(shí)在參數(shù)的地址或值；,3. 靜態(tài)鏈：指向直接外層過(guò)程的最新活動(dòng)記錄，用于訪問(wèn)非局部變量；,4. 動(dòng)態(tài)鏈：指向調(diào)用本過(guò)程的最新活動(dòng)記錄的起始地址；各數(shù)據(jù)區(qū)構(gòu)成次序鏈。,作用：過(guò)程被調(diào)用時(shí)產(chǎn)生新的活動(dòng)，并將相關(guān)信息（活動(dòng)記錄），并壓入棧。,指向現(xiàn)行（最新）過(guò)程,每個(gè)活動(dòng)記錄的大小在編譯時(shí)可以確定( 除動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)外 )，因此以SP為變址器可方便的訪問(wèn)各個(gè)數(shù)據(jù)。,三. 存儲(chǔ)分配策略不同的編譯程序有不同的策略,靜態(tài)存儲(chǔ)分配：編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元（地址空間），運(yùn)行時(shí)始終不變。,棧式動(dòng)態(tài)存儲(chǔ)分配：為每個(gè)過(guò)程建立活動(dòng)記錄，運(yùn)行時(shí)每當(dāng)調(diào)用一個(gè)過(guò)程，就將活動(dòng)記錄動(dòng)態(tài)的分配于棧

5、頂，過(guò)程活動(dòng)結(jié)束，則活動(dòng)記錄退出棧頂（釋放所占用的空間）。,堆式動(dòng)態(tài)存儲(chǔ)分配：運(yùn)行時(shí)將存儲(chǔ)空間組織成堆結(jié)構(gòu)，以便用戶可以隨時(shí)申請(qǐng)或釋放存儲(chǔ)空間。,一個(gè)編譯系統(tǒng)采取怎樣的分配策略，取決于源語(yǔ)言中作用域及生命期的定義規(guī)則。如： FORTRAN不允許遞歸，故用靜態(tài)策略（以下不再敘述）。 Pascal和C，運(yùn)行時(shí)難以確定遞歸激活和遞歸深度，故用棧式堆式,9.3 簡(jiǎn)單的棧式存儲(chǔ)分配,以C語(yǔ)言為例，由于不允許嵌套定義過(guò)程，但允許過(guò)程遞歸調(diào)用，因此可采用簡(jiǎn)單的棧式存儲(chǔ)分配。,例有右邊的程序結(jié)構(gòu)：,全局?jǐn)?shù)據(jù)說(shuō)明 Main( ) Main中的數(shù)據(jù)說(shuō)明 Q ； void R( ) R中的數(shù)據(jù)說(shuō)明 . void Q

6、( ) Q中的數(shù)據(jù)說(shuō)明 R；,當(dāng) Main調(diào)用了Q, Q又調(diào)用了R后，其存儲(chǔ)空間分配如下：,TOP：始終指向已占用的棧頂單元。進(jìn)入一個(gè)過(guò)程時(shí)指向該過(guò)程創(chuàng)建的活動(dòng)記錄的頂端，在分配數(shù)組之后，改指向數(shù)組區(qū)的頂端。,一. C 的活動(dòng)記錄,相當(dāng)于動(dòng)態(tài)鏈,SP: 總是指向現(xiàn)行過(guò)程活動(dòng)記錄的起點(diǎn)，用于局部數(shù)據(jù)的訪問(wèn)；,對(duì)任何局部變量或形參的引用均可表示為：XSP, X表示變量的相對(duì)地址（編譯時(shí)可確定） 相對(duì)與活動(dòng)記錄的起始位置（SP）。 由于不允許嵌套，非局部變量的定義只能位于源程序的頭，并采用靜態(tài)分配。,二. C 的過(guò)程調(diào)用、過(guò)程進(jìn)入、過(guò)程返回,如前所述p200，過(guò)程調(diào)用的四元式序列如下： TOP總是指

7、向棧頂，而形式單元和SP間的距離是3，故：,par T1 par T2 par Tn call p, n,(i+3)TOP:=Ti (傳值) 或 (i+3)TOP:=addr (Ti) (傳地址),1TOP:=SP (保存現(xiàn)行的老sp) 3TOP:=n (傳送參數(shù)個(gè)數(shù)） JSR P （轉(zhuǎn)子 指令，轉(zhuǎn)向p 的第一條指令）,1. 過(guò)程調(diào)用,2. 過(guò)程進(jìn)入,進(jìn)入過(guò)程后，應(yīng)執(zhí)行以下指令，為新活動(dòng)記錄賦初值,SP:=TOP+1 (定義新的SP) 1SP:=返回地址 (保護(hù)返回地址) TOP:=TOP+L (定義新的top，L為活動(dòng)記錄的單元 數(shù)，可在編譯時(shí)靜態(tài)計(jì)算出來(lái)) 過(guò)程段執(zhí)行語(yǔ)句時(shí)，對(duì)形式參數(shù)、局

8、部變量和數(shù)組的引用都是以SP為變址器進(jìn)行變址訪問(wèn)的。,3. 過(guò)程返回,對(duì)于以 return(E) 或 end 為結(jié)束返回的過(guò)程，應(yīng)執(zhí)行以下指令：,TOP:=SP-1 SP:=0SP X:=2TOP X為某一變 址器，返址 UJ 0X 無(wú)條件轉(zhuǎn)移,以 return(E)返回時(shí)，還應(yīng)將表達(dá)式E的值計(jì)算出來(lái)并放于臨時(shí)變量T中通過(guò)特定的寄存器傳回。然后恢復(fù)SP和TOP到進(jìn)入過(guò)程前的舊值，無(wú)條件返回到原地址，如左:,9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn) Pascal允許過(guò)程嵌套即過(guò)程定義嵌套，在討論嵌套層次時(shí)，假定主程序的嵌套層次為0。如圖，p258 圖9.15 概念：直接外層，直接內(nèi)層。層數(shù)將作為過(guò)程名的重

9、要屬性予以登記。 層數(shù)計(jì)算： proc Begin時(shí)1 Proc End時(shí)1 9.5.1非局部名字的訪問(wèn)實(shí)現(xiàn) 一、靜態(tài)鏈和活動(dòng)記錄 結(jié)構(gòu)：,SP,TOP,為了在活動(dòng)記錄中查找非局部名字所對(duì)應(yīng)的存儲(chǔ)空間，當(dāng)前過(guò)程Q需要知道其所有外層過(guò)程的最新活動(dòng)記錄的地址，即跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄位置。 跟蹤方法：靜態(tài)鏈、顯示表。 1.靜態(tài)鏈：指向直接外層過(guò)程的最新活動(dòng)記錄，用于（允許）訪問(wèn)各外層的變量（非局部變量）。程序的每個(gè)過(guò)程的靜態(tài)結(jié)構(gòu)（嵌套層次）的確定的，故稱靜態(tài)，如 (圖9.17 (b) 程序運(yùn)行時(shí)棧的變化如：P260圖9.17SP總是指向當(dāng)前活動(dòng)過(guò)程的活動(dòng)記錄的基地址。 動(dòng)態(tài)鏈，指向調(diào)用給過(guò)

10、程前正在運(yùn)行（活動(dòng)）的過(guò)程的最新活動(dòng)記錄的基地址，即當(dāng)調(diào)用結(jié)束時(shí)，可以由動(dòng)態(tài)鏈得到調(diào)用前的過(guò)程的活動(dòng)記錄的基地址。 靜態(tài)鏈指向其靜態(tài)直接外層的活動(dòng)記錄的基地址。,二、嵌套層次顯示表（display) 和活動(dòng)記錄 為了提高訪問(wèn)非局部變量的速度，動(dòng)態(tài)地組織一個(gè)嵌套層次顯示表（display）放入活動(dòng)記錄中。 display中存有本層及各外層的活動(dòng)記錄首地址。為了快速動(dòng)態(tài)生成display表，需將調(diào)用過(guò)程的display表地址(全局display)作為連接數(shù)據(jù)傳遞，因此，活動(dòng)記錄結(jié)構(gòu)改為右圖所示： Diplay表構(gòu)成了一個(gè)小的棧結(jié)構(gòu)。 p262(a),Display表的生成過(guò)程：由于過(guò)程的層數(shù)可以靜

11、態(tài)確定，故每個(gè)過(guò)程的display表的大小可以在編譯時(shí)靜態(tài)確定。,0層(主過(guò)程)的display僅含一項(xiàng)：0層SP；,1層的display含兩項(xiàng)： 0層的display+1層SP;,設(shè)過(guò)程p1調(diào)用p2，則p1與p2的靜態(tài)關(guān)系如右圖所示有(a), (b)兩種情況：,p1是p2的外層，由p1的display加上p2的SP即生成P2的display；,(b) p1與p2同層，且有共同的外層， 由p1 display表的前 i 項(xiàng)(p2為i層) 加上p2的SP即生成P2的display。,因此，非局部變量的絕對(duì)地址： 絕對(duì)地址diplay（靜態(tài)層數(shù)）相對(duì)地址 Diplay表的相對(duì)地址：位于形式單元的上

12、方，而形式單元的數(shù)目是靜態(tài)的，故display表的相對(duì)地址也是靜態(tài)可確定的。 過(guò)程運(yùn)行時(shí)棧的display表的內(nèi)容變化過(guò)程，見(jiàn)p263，圖9.19 0層的diplay表：只含有主程序開(kāi)始工作時(shí)建立的SP值。 由此可見(jiàn)，使用display表比使用靜態(tài)鏈效率要高。,9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)（PASCAL語(yǔ)言） 例：program p; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer;var v:integer); var c,d:integer; begin if u=1 then R

13、(u+1,v) v:=(a+c)*(b-d); . end R begin . R(1,x); . end Q procedure S; var c,i:integer; begin a=1;Q(c); .end S begin a=0;S; 過(guò)程調(diào)用時(shí)活動(dòng)記錄的變化 end 見(jiàn)p260,262,9.6 堆（heep）式動(dòng)態(tài)存儲(chǔ)分配,若源程序語(yǔ)言允許用戶自由地申請(qǐng)和退還數(shù)據(jù)空間（即不滿足lifo 原則），則應(yīng)用堆式存儲(chǔ)分配，其管理方式較為復(fù)雜，如圖9.21Pascal的建立new、釋放despose交替而改變堆的使用狀況。這里我們僅討論幾個(gè)主要問(wèn)題。 分配原則問(wèn)題：類似于磁盤空間的分配管理碎片問(wèn)題、廢空間回收問(wèn)題如何判斷廢空間？,一. 堆式動(dòng)態(tài)存儲(chǔ)分配的實(shí)現(xiàn),1. 定長(zhǎng)塊管理 存儲(chǔ)空間按一定長(zhǎng)度分成若干塊，組織成鏈表，由avaiable指示，以塊為單位進(jìn)行分配、回收。類似FAT表 有申請(qǐng)時(shí)，從avaiable鏈表中取下若干塊分配。