運行時存儲空間組織.ppt

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

2、程體第一步操作到最后一步操作之間的操作序。兩個過程的活動生存期或嵌套或不重疊。,一個標識符說明在程序中能起作用的范圍稱為該說明的作用域。,生存期和作用域將決定分配目標程序數據空間的基本策略。 ex: Fig 9.1 program,例：寫出參數傳遞的結果 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,二、參數傳遞 :傳地址、傳值、傳名、得結果p241,9.2 運行時存

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

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

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

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

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

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

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

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

11、態(tài)確定，故每個過程的display表的大小可以在編譯時靜態(tài)確定。,0層(主過程)的display僅含一項：0層SP；,1層的display含兩項： 0層的display+1層SP;,設過程p1調用p2，則p1與p2的靜態(tài)關系如右圖所示有(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)層數）相對地址 Diplay表的相對地址：位于形式單元的上

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