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

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

2、程體第一步操作到最后一步操作之間的操作序。兩個過程的活動生存期或嵌套或不重疊。,一個標(biāo)識符說明在程序中能起作用的范圍稱為該說明的作用域。,生存期和作用域?qū)Q定分配目標(biāo)程序數(shù)據(jù)空間的基本策略。 ex: Fig 9.1 program,例：寫出參數(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)行時存

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

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

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

6、( ) Q中的數(shù)據(jù)說明 R；,當(dāng) Main調(diào)用了Q, Q又調(diào)用了R后，其存儲空間分配如下：,TOP：始終指向已占用的棧頂單元。進(jìn)入一個過程時指向該過程創(chuàng)建的活動記錄的頂端，在分配數(shù)組之后，改指向數(shù)組區(qū)的頂端。,一. C 的活動記錄,相當(dāng)于動態(tài)鏈,SP: 總是指向現(xiàn)行過程活動記錄的起點(diǎn)，用于局部數(shù)據(jù)的訪問；,對任何局部變量或形參的引用均可表示為：XSP, X表示變量的相對地址（編譯時可確定） 相對與活動記錄的起始位置（SP）。 由于不允許嵌套，非局部變量的定義只能位于源程序的頭，并采用靜態(tài)分配。,二. C 的過程調(diào)用、過程進(jìn)入、過程返回,如前所述p200，過程調(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ù)個數(shù)） JSR P （轉(zhuǎn)子 指令，轉(zhuǎn)向p 的第一條指令）,1. 過程調(diào)用,2. 過程進(jìn)入,進(jìn)入過程后，應(yīng)執(zhí)行以下指令，為新活動記錄賦初值,SP:=TOP+1 (定義新的SP) 1SP:=返回地址 (保護(hù)返回地址) TOP:=TOP+L (定義新的top，L為活動記錄的單元 數(shù)，可在編譯時靜態(tài)計算出來) 過程段執(zhí)行語句時，對形式參數(shù)、局

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

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

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

11、態(tài)確定，故每個過程的display表的大小可以在編譯時靜態(tài)確定。,0層(主過程)的display僅含一項：0層SP；,1層的display含兩項： 0層的display+1層SP;,設(shè)過程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 項(p2為i層) 加上p2的SP即生成P2的display。,因此，非局部變量的絕對地址： 絕對地址diplay（靜態(tài)層數(shù)）相對地址 Diplay表的相對地址：位于形式單元的上

12、方，而形式單元的數(shù)目是靜態(tài)的，故display表的相對地址也是靜態(tài)可確定的。 過程運(yùn)行時棧的display表的內(nèi)容變化過程，見p263，圖9.19 0層的diplay表：只含有主程序開始工作時建立的SP值。 由此可見，使用display表比使用靜態(tài)鏈效率要高。,9.5 嵌套過程語言的棧式實現(xiàn)（PASCAL語言） 例：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; 過程調(diào)用時活動記錄的變化 end 見p260,262,9.6 堆（heep）式動態(tài)存儲分配,若源程序語言允許用戶自由地申請和退還數(shù)據(jù)空間（即不滿足lifo 原則），則應(yīng)用堆式存儲分配，其管理方式較為復(fù)雜，如圖9.21Pascal的建立new、釋放despose交替而改變堆的使用狀況。這里我們僅討論幾個主要問題。 分配原則問題：類似于磁盤空間的分配管理碎片問題、廢空間回收問題如何判斷廢空間？,一. 堆式動態(tài)存儲分配的實現(xiàn),1. 定長塊管理 存儲空間按一定長度分成若干塊，組織成鏈表，由avaiable指示，以塊為單位進(jìn)行分配、回收。類似FAT表 有申請時，從avaiable鏈表中取下若干塊分配。