8hh第6章運(yùn)行時存儲空間組織

1、第6章 運(yùn)行時存儲空間組織前面討論了對源程序進(jìn)行靜態(tài)分析的編譯程序的不同階段, 這些分析僅取決于源程序本身的特性, 與目標(biāo)機(jī)及目標(biāo)機(jī)的操作系統(tǒng)特性無關(guān)。但編譯程序的最終目的是把源程序翻譯成能在目標(biāo)機(jī)上運(yùn)行的目標(biāo)程序, 這就要求編譯程序不僅能生成目標(biāo)代碼, 還要在生成目標(biāo)代碼之前進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的設(shè)計和數(shù)據(jù)空間的分配。例如, 目標(biāo)程序運(yùn)行時, 源程序中各種變量、常量等如何在存儲器中存放? 如何對它們進(jìn)行訪問? 源程序中各種變量、常量的作用域和生存期如何確定? 遞歸過程的數(shù)據(jù)空間如何在運(yùn)行過程中實(shí)現(xiàn)動態(tài)的分配? 這些問題對于編譯程序是非常復(fù)雜又十分重要的。分配目標(biāo)程序數(shù)據(jù)空間的基本策略:1.

2、靜態(tài)分配策略 若一個程序語言不允許有遞歸過程, 不允許含可變體積的數(shù)據(jù)項(xiàng)或待定性質(zhì)的名字, 則在編譯時能完全確定其程序的每個數(shù)據(jù)項(xiàng)目的存儲空間位置, 這種策略叫靜態(tài)分配策略。例如, FORTRAN語言2. 棧式動態(tài)分配策略若程序語言允許有遞歸過程和可變數(shù)組, 則程序數(shù)據(jù)空間的分配需采用動態(tài)策略, 即在程序運(yùn)行時進(jìn)行數(shù)據(jù)空間的分配, 此時目標(biāo)程序可用棧作為動態(tài)的數(shù)據(jù)空間。程序運(yùn)行時, 每當(dāng)進(jìn)入一個子程序, 其所需的數(shù)據(jù)空間就動態(tài)地分配于棧頂, 一旦該子程序運(yùn)行結(jié)束, 其所占用的空間就釋放, 這種方法叫棧式動態(tài)分配策略。3. 堆式動態(tài)分配策略若程序語言允許用戶動態(tài)地申請和釋放存儲空間, 并且申請和

3、釋放之間不一定遵守“先申請后釋放”的原則, 則必須讓運(yùn)行程序擁有一個大存儲區(qū)(堆), 申請時從堆中分配一塊, 釋放時退還給堆, 這種方法叫堆式動態(tài)分配策略。6.1 靜態(tài)存儲分配 6.2 簡單的棧式存儲分配 6.3 嵌套過程語言的棧式實(shí)現(xiàn) 6.4 堆式動態(tài)存儲分配 6.5 參數(shù)傳遞補(bǔ)遺6.1 靜態(tài)存儲分配若編譯時能確定程序運(yùn)行時所需存儲空間的大小, 則編譯時能安排好程序運(yùn)行時的全部數(shù)據(jù)空間, 并能確定每個數(shù)據(jù)項(xiàng)的地址, 這種存儲分配方法叫做靜態(tài)分配。FORTRAN語言不允許有遞歸過程,每個數(shù)據(jù)名所需存儲空間的大小是常量(即不允許含可變體積的數(shù)據(jù)), 且所有數(shù)據(jù)名的性質(zhì)是完全確定的(不允許出現(xiàn)動態(tài)

4、確定其性質(zhì)的數(shù)據(jù)名)。故FORTRAN程序可靜態(tài)分配存儲空間。(1) 數(shù)組的上下界必須是常數(shù);(2) 過程調(diào)用不允許遞歸;(3)不允許采用動態(tài)數(shù)據(jù)結(jié)構(gòu), 即程序運(yùn)行過程中不允許申請和釋放存儲空間。適于靜態(tài)存儲分配的語言需滿足的條件:滿足條件的語言有FORTRAN, BASIC等。這些語言的編譯程序可完全確定程序中數(shù)據(jù)項(xiàng)所在地址(通常為相應(yīng)于各數(shù)據(jù)區(qū)起始地址的位移量)。由于過程調(diào)用不允許遞歸, 因此數(shù)據(jù)項(xiàng)的存儲地址與過程相聯(lián)系。過程調(diào)用所使用的局部數(shù)據(jù)區(qū)直接安排在過程的目標(biāo)代碼后, 并把各數(shù)據(jù)項(xiàng)的存儲地址填入相關(guān)的目標(biāo)代碼, 以便在過程運(yùn)行時訪問這個局部數(shù)據(jù)區(qū)。采用靜態(tài)存儲分配時, 不存在對存儲

5、區(qū)的再利用問題, 目標(biāo)程序執(zhí)行時不必進(jìn)行運(yùn)行時存儲空間管理, 因此, 過程進(jìn)入和退出很簡單。FORTRAN語言的靜態(tài)存儲管理特點(diǎn)使FORTRAN程序中各程序段可獨(dú)立地進(jìn)行編譯。在編譯過程中, 給程序中變量或數(shù)組分配存儲單元的一般方法為: 為每個變量(或數(shù)組)確定一個有序整數(shù)對, 并把這一對整數(shù)填入符號表相應(yīng)登記項(xiàng)的信息欄中。其中第一個整數(shù)指示數(shù)據(jù)區(qū)的編號, 第二個整數(shù)指明該變量(或數(shù)組)所對應(yīng)的存儲起始單元相應(yīng)于其所在數(shù)據(jù)區(qū)起點(diǎn)的位移。各數(shù)據(jù)區(qū)的起始地址在編譯時暫不確定, 待各程序段全部編譯完后, 再由連接裝配程序最終確定, 并將各程序段的目標(biāo)代碼組裝成一個完整的目標(biāo)程序。FORTRAN程序段

6、的局部數(shù)據(jù)區(qū)可由圖6-1所示的項(xiàng)目組成: 臨時變量數(shù)組簡單變量形式單元寄存器保護(hù)區(qū)隱參數(shù)返回地址圖6-1 一個FORTRAN程序段的局部數(shù)據(jù)區(qū)隱參數(shù)指過程調(diào)用時的連接信息, 如返回地址、寄存器保護(hù)區(qū)等; 形式單元用來存放過程調(diào)用時與形參對應(yīng)的實(shí)參地址或值。首先考慮一種簡單程序語言: 沒有分程序結(jié)構(gòu), 過程定義不允許嵌套, 但允許過程的遞歸調(diào)用, 允許過程含可變數(shù)組。C語言除了不允許含可變數(shù)組外, 就是這樣一種語言。6.2 簡單的棧式存儲分配C語言的程序結(jié)構(gòu)如下:全局?jǐn)?shù)據(jù)說明main() main中的數(shù)據(jù)說明void R() R中的數(shù)據(jù)說明 void Q( ) Q中的數(shù)據(jù)說明 計算n!的C程序的

7、執(zhí)行過程可用棧實(shí)現(xiàn):# include “stdio.h”long factorial (int n) if (n1) return (n*factorial(n-1); else return (1); main () int num; do scanf (“%d” , &num); if (num=0 & num =0);6.2.1 棧式存儲分配與活動記錄使用棧式存儲分配法意味著程序運(yùn)行時, 每當(dāng)進(jìn)入一個過程(或函數(shù))就有一個相應(yīng)的活動記錄累筑于棧頂, 此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時工作單元等。在執(zhí)行可執(zhí)行語句之前, 把局部數(shù)組所需空間累筑于棧頂, 從而形

8、成過程工作時的完整數(shù)據(jù)區(qū)。注意: 每個過程的活動記錄的體積在編譯時可以靜態(tài)地確定。由于允許含有可變數(shù)組, 故數(shù)組的大小在運(yùn)行時才能知道。由于可變數(shù)組的大小不能預(yù)先獲知, 為了擴(kuò)充方便, 把數(shù)組區(qū)累筑于活動記錄之上的當(dāng)前棧頂。當(dāng)一個過程執(zhí)行完畢返回時, 它在棧頂?shù)臄?shù)據(jù)區(qū)(包括活動記錄和數(shù)組區(qū))隨即不復(fù)存在。由于C語言不含可變數(shù)組, 故其活動記錄本身包含了局部數(shù)組的空間。圖6-2和圖6-3分別給出了C語言和含可變數(shù)組的某簡單語言程序運(yùn)行時的數(shù)據(jù)空間結(jié)構(gòu), 即顯示了主程序調(diào)用了過程Q, Q調(diào)用了過程R, R投入運(yùn)行后的存儲結(jié)構(gòu)。SPTOPR的活動記錄Q的活動記錄main的活動記錄全局?jǐn)?shù)據(jù)區(qū)圖6-2

9、C語言程序的存儲組織 SP總是指向執(zhí)行過程活動記錄的起點(diǎn), TOP始終指向棧頂單元。當(dāng)進(jìn)入一個過程時, SP指向?yàn)榇诉^程創(chuàng)建的活動記錄的起點(diǎn), TOP指向?yàn)榇诉^程創(chuàng)建的活動記錄的頂端。當(dāng)進(jìn)入一個過程時, SP指向?yàn)榇诉^程創(chuàng)建的活動記錄的起點(diǎn), TOP指向?yàn)榇诉^程創(chuàng)建的活動記錄的頂端; 若含有可變數(shù)組, 則分配數(shù)組區(qū)后, TOP又改為指向數(shù)組區(qū)的頂端。圖6-3 含可變數(shù)組的程序的存儲組織R的數(shù)組區(qū)R的活動記錄Q的數(shù)組區(qū)Q的活動記錄TOPSPmain的數(shù)組區(qū)main的活動記錄主程序全局?jǐn)?shù)據(jù)區(qū)C的活動記錄含以下幾個區(qū)段:連接數(shù)據(jù)(兩項(xiàng)): 老SP值和返回地址, 其中老SP為前一活動記錄的起始地址;參

10、數(shù)個數(shù);形式單元(存放實(shí)參的值或地址);過程的局部變量(簡單變量)、數(shù)組的內(nèi)情向量和臨時工作單元。 1TOP臨時工作單元內(nèi)情向量簡單變量形式單元參數(shù)個數(shù)返回地址老SPSP20圖6-4 C過程的活動記錄C語言不允許函數(shù)嵌套, 即不允許一個過程的定義出現(xiàn)在另一過程的定義之內(nèi)。因此, C語言的非局部變量僅能出現(xiàn)在源程序頭, 非局部變量可采用靜態(tài)存儲并在編譯時確定它們的地址。C語言中, 過程的每個局部變量或形參在活動記錄中的位置是確定的。因此, 變量和形參運(yùn)行時在棧上的絕對地址:絕對地址=活動記錄基址(SP)+相對地址對于當(dāng)前正在執(zhí)行的過程, 其任一局部變量或形參A的引用均可表示為變址訪問XSP, 其

11、中X代表A相對于活動記錄基址的偏移量, 這個偏移量在編譯時可完全確定下來。過程的局部數(shù)組的內(nèi)情向量的相對地址在編譯時同樣可完全確定下來。當(dāng)數(shù)據(jù)空間在過程中獲得分配后, 對數(shù)組元素的引用易于用變址方式訪問。6.2.2 過程的執(zhí)行1. 過程調(diào)用過程調(diào)用的四元式序列為: par T1 par T2 par Tn call P, n由于此時TOP指向被調(diào)過程P之前的棧頂, 而P的形式單元與活動記錄起點(diǎn)之間的距離是確定的(等于3), 因而由調(diào)用過程給被調(diào)過程P的活動記錄(正在形成)的形式單元傳遞實(shí)參值或?qū)崊⒌刂? 即每個par Ti(i=1, n)可直接翻譯成如下指令: (i+3)TOP=Ti /傳參數(shù)

12、值 或 (i+3)TOP=addrTi /參數(shù)地址四元式 call P,n 翻譯成: 1TOP=SP /保護(hù)現(xiàn)行SP 3TOP=n /傳遞參數(shù)個數(shù) JSR P /轉(zhuǎn)向P過程參數(shù)個數(shù)nTOP+3SPT2T1現(xiàn)行SP值P的活動記錄調(diào)用過程TOP43210圖6-5 調(diào)用過程P之前先構(gòu)造P 的活動記錄的部分內(nèi)容2. 過程進(jìn)入轉(zhuǎn)入過程P后, 首先要做的是定義新活動記錄的SP, 保護(hù)返回地址和定義新活動記錄的TOP值, 即執(zhí)行下述指令:SP = TOP+1 /定義新SP1SP=返回地址 /保護(hù)返回地址TOP=TOP+L /定義新TOP其中L是過程P的活動記錄所需的單元數(shù), 該數(shù)在編譯時可靜態(tài)計算出。對含可

13、變數(shù)組的情況, 緊接上述指令之后是對數(shù)組進(jìn)行存儲分配的指令。對數(shù)組進(jìn)行存儲分配的指令是在翻譯數(shù)組說明時產(chǎn)生的, 對每個數(shù)組說明, 相應(yīng)的目標(biāo)指令組將做以下工作: (1)計算各維的上下限; (2)調(diào)用數(shù)組空間分配子程序。數(shù)組空間分配子程序計算并填好內(nèi)情向量的所有信息, 然后在TOP所指位置之上留出數(shù)組所需空間, 并將TOP調(diào)整為指向數(shù)組區(qū)頂端。P的數(shù)組區(qū)返回地址P的活動記錄(長度為L)1調(diào)用過程SPTOP0此后, 在執(zhí)行語句過程中, 凡引用形參、局部變量或數(shù)組元素都以SP為基址進(jìn)行相對訪問。進(jìn)入過程P后所做工作如下圖:3. 過程返回C語言及其它一些語言含return(E)形式的返回語句。假定E值

14、已計算出來并存放在某臨時單元T中, 則此時可將T值傳送到某個特定寄存器中(調(diào)用過程將從這個特定寄存器中獲得被調(diào)過程P的結(jié)果)。剩下的工作是恢復(fù)SP和TOP, 并按返回地址實(shí)行無條件轉(zhuǎn)移, 即執(zhí)行下述指令序列:TOP= SP1 /恢復(fù)調(diào)用過程的TOP值SP=0SP /恢復(fù)調(diào)用過程的SP值X=2TOP /將返回地址送XUJ 0X /無條件轉(zhuǎn)移到調(diào)用過程一個過程也可通過它的end語句(C語言為)自動返回。若此過程是一個函數(shù), 則按上述辦法傳遞結(jié)果值, 否則僅直接執(zhí)行上述返回指令序列。SPTOP返回地址老SPP空間調(diào)用過程空間圖6-7 過程P的返回示意圖6.3 嵌套過程語言的棧式實(shí)現(xiàn)在簡單程序語言實(shí)現(xiàn)

15、中允許過程的遞歸調(diào)用, 且過程中可含可變數(shù)組?，F(xiàn)在再加上一種功能-允許過程的嵌套性, 如PASCAL。由于PASCAL含有文件和動態(tài)變量, 故它的存儲分配不能簡單地用棧式方法實(shí)現(xiàn)。考慮PASCAL的一個子集, 即去掉文件和動態(tài)變量這兩種數(shù)據(jù)類型, 則可用下述方法實(shí)現(xiàn)存儲分配:6.3.1 嵌套層次顯示表和活動記錄假定主程序的層數(shù)為0。若過程Q是在層數(shù)為i的過程P內(nèi)定義的, 且P是包圍Q的最小過程, 則Q的層數(shù)為i+1。編譯程序處理過程說明時, 過程的層數(shù)作為過程名的一個重要屬性登記在符號表中。由于過程定義是嵌套的, 因而一個過程可以引用包圍它的任一外層過程所定義的變量或數(shù)組, 即運(yùn)行時過程Q可引

16、用它的任一外層過程P的最新活動記錄中的某些數(shù)據(jù)。因此, 過程Q運(yùn)行時必須知道它的所有外層的最新活動記錄的地址。由于允許遞歸和可變數(shù)組的存在, 過程的活動記錄位置往往是變遷的, 因而必須設(shè)法跟蹤每個外層過程的最新活動記錄的位置。一種常用的跟蹤每個外層過程最新活動記錄位置的有效辦法: 每進(jìn)入一個過程后, 在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表DISPLAY。假定現(xiàn)在進(jìn)入的過程層數(shù)為i, 則它的DISPLAY表含有i+1個單元。DISPLAY表本身是一個棧, 自頂而下依次存放著現(xiàn)行層、直接外層第0層的最新活動記錄的起始地址。表6.1 DISPLAY表假設(shè)過程R的外層為Q, Q的外層為主程序P, 則R運(yùn)行時的DISPLAY表的內(nèi)容如表6.1所示。2R的現(xiàn)行活動記錄的起始地址(SP的現(xiàn)行值)1Q的最新活動記錄的起始地址0P的活動記錄的起始地址由于過程的層數(shù)可靜態(tài)確定, 因此每個過程的DISPLAY表的體積在編譯時即可知道。為了便于組織存儲區(qū), 把DISPLAY表作為活動記錄的一部分置于形式單元的上端。由于每個過程