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

2、作用域作用域和生存期生存期如何確定? 遞歸過程遞歸過程的數(shù)據(jù)空間的數(shù)據(jù)空間如何在運行過程中實現(xiàn)動態(tài)的分配動態(tài)的分配? 這些問題對于編譯程序是非常復(fù)雜又十分重要的。分配分配目標(biāo)程序數(shù)據(jù)空間的基本策略數(shù)據(jù)空間的基本策略:1. 靜態(tài)分配策略靜態(tài)分配策略 若一個程序語言不允許有遞歸過程不允許有遞歸過程, 不允許含可變體積的不允許含可變體積的數(shù)據(jù)項數(shù)據(jù)項或待定待定性質(zhì)的名字性質(zhì)的名字, 則在編譯時能完全確定完全確定其程序的每個數(shù)據(jù)項目的存儲空間位置, 這種策略叫靜態(tài)分配策略靜態(tài)分配策略。例如, FORTRAN語言2. 棧式動態(tài)分配策略棧式動態(tài)分配策略若程序語言允許有遞歸過程允許有遞歸過程和可變數(shù)組可變數(shù)

3、組, 則程序數(shù)據(jù)空間的分配數(shù)據(jù)空間的分配需采用動態(tài)動態(tài)策略策略, 即在程序運行時進行數(shù)據(jù)空間的分配, 此時目標(biāo)程序可用棧棧作為動態(tài)的數(shù)據(jù)空間。程序運行時運行時, 每當(dāng)進入一個子程序, 其所需的數(shù)據(jù)空間就動態(tài)地分配于棧頂分配于棧頂, 一旦該子程序運行結(jié)束運行結(jié)束, 其所占用的空間就釋釋放放, 這種方法叫棧式動態(tài)分配策略棧式動態(tài)分配策略。3. 堆式動態(tài)分配策略堆式動態(tài)分配策略若程序語言允許用戶動態(tài)地動態(tài)地申請和釋申請和釋放放存儲空間, 并且申請和釋放之間不一不一定定遵守“先申請后釋放先申請后釋放”的原則, 則必須讓運行程序擁有一個大存儲區(qū)(堆堆), 申請時從堆中分配一塊, 釋放時退還給堆, 這種方

4、法叫堆式動態(tài)分配策略堆式動態(tài)分配策略。6.1 靜態(tài)靜態(tài)存儲分配存儲分配 6.2 簡單的簡單的棧式棧式存儲分配存儲分配 6.3 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn) 6.4 堆式堆式動態(tài)存儲分配動態(tài)存儲分配 6.5 參數(shù)傳遞補遺參數(shù)傳遞補遺6.1 靜態(tài)存儲分配靜態(tài)存儲分配若編譯時編譯時能確定程序運行時所需存儲空間的大小, 則編譯編譯時時能安排好程序運行時的全部數(shù)據(jù)空間, 并能確定每個數(shù)據(jù)項的地址, 這種存儲分配方法叫做靜態(tài)分配靜態(tài)分配。FORTRAN語言不允許不允許有遞歸遞歸過程,每個數(shù)據(jù)名所需存儲空間的大小是常量(即不不允許允許含可變體積可變體積的數(shù)據(jù)), 且所有數(shù)據(jù)名的性質(zhì)是完全確定

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

6、碼后過程的目標(biāo)代碼后, 并把各數(shù)據(jù)項的存儲地址存儲地址填入相關(guān)的目標(biāo)代碼, 以便在過程運行時訪問訪問這個局部數(shù)據(jù)區(qū)。采用靜態(tài)存儲分配時, 不存在對存儲不存在對存儲區(qū)的再利用問題區(qū)的再利用問題, 目標(biāo)程序執(zhí)行時不必進行運行時存儲空間管理運行時存儲空間管理, 因此, 過程進入和退出很簡單。FORTRAN語言的靜態(tài)存儲管理特點使FORTRAN程序中各程序段可獨立程序中各程序段可獨立地進行編譯地進行編譯。在編譯過程中, 給程序中變量變量或數(shù)數(shù)組組分配存儲單元的一般方法為: 為每個變量變量(或數(shù)組數(shù)組)確定一個有序有序整數(shù)對整數(shù)對, 并把這一對整數(shù)這一對整數(shù)填入符號表相應(yīng)登記項的信息欄中。其中第一個整數(shù)

7、第一個整數(shù)指示數(shù)據(jù)區(qū)的編號編號, 第二個整數(shù)第二個整數(shù)指明該變量(或數(shù)組)所對應(yīng)的存儲起始單元存儲起始單元相應(yīng)于其所在數(shù)據(jù)區(qū)起點的位移位移。各數(shù)據(jù)區(qū)的起始地址在編譯時暫不確各數(shù)據(jù)區(qū)的起始地址在編譯時暫不確定定, 待各程序段全部編譯完后, 再由連連接裝配程序接裝配程序最終確定, 并將各程序段的目標(biāo)代碼組裝成一個完整的目標(biāo)程序。FORTRAN程序段的局部數(shù)據(jù)區(qū)局部數(shù)據(jù)區(qū)可由圖6-1所示的項目組成: 臨時變量臨時變量數(shù)組數(shù)組簡單變量簡單變量形式單元形式單元寄存器保護區(qū)寄存器保護區(qū)隱隱參參數(shù)數(shù) 返回地址返回地址圖圖6-1 一個一個FORTRAN程序段的程序段的局部數(shù)據(jù)區(qū)局部數(shù)據(jù)區(qū)隱參數(shù)隱參數(shù)指過程調(diào)用

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

9、:# 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 棧式存儲分配與活動記錄棧式存儲分配與活動記錄使用棧式存儲分配法意味著程序運行時, 每當(dāng)進入一個過程每當(dāng)進入一個過程(或函數(shù)或函數(shù))就有一就有一個相應(yīng)的活動記錄累筑于棧頂個相應(yīng)的活動記錄累筑于棧頂, 此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時

10、工作單元等。在執(zhí)行可執(zhí)行語句執(zhí)行可執(zhí)行語句之前之前, 把把局部數(shù)組局部數(shù)組所需空間所需空間累筑于棧頂累筑于棧頂, 從而形成過程工作時的完整數(shù)據(jù)區(qū)。注意: (1)每個過程的活動記錄的體積活動記錄的體積在編譯時可以靜態(tài)地確定。(2)由于允許含有可變數(shù)組可變數(shù)組, 故數(shù)組的大數(shù)組的大小小在運行時運行時才能知道。(3)由于可變數(shù)組的大小不能預(yù)先獲知, 為了擴充方便, 把數(shù)組區(qū)數(shù)組區(qū)累筑于活動記錄之上的當(dāng)前棧頂。(4)當(dāng)一個過程執(zhí)行完畢返回時, 它在棧頂?shù)臄?shù)據(jù)區(qū)(包括活動記錄活動記錄和數(shù)組區(qū)數(shù)組區(qū))隨即不復(fù)存在。由于C語言語言不含可變數(shù)組不含可變數(shù)組, 故故其活動活動記錄記錄本身包含了局部數(shù)組的空間本身

11、包含了局部數(shù)組的空間。圖6-2和圖6-3分別給出了C語言語言和含含可變數(shù)組的某簡單語言可變數(shù)組的某簡單語言程序運行時的數(shù)據(jù)空間結(jié)構(gòu), 即顯示了主程序調(diào)用了過程Q, Q調(diào)用了過程R, R投入運行投入運行后后的存儲結(jié)構(gòu)。SPTOPR的活動記錄的活動記錄Q的活動記錄的活動記錄main的活動記錄的活動記錄全局?jǐn)?shù)據(jù)區(qū)全局?jǐn)?shù)據(jù)區(qū)圖圖6-2 C語言程序語言程序的的存儲組織存儲組織 SP總是指向執(zhí)行過程活動記錄的起點, TOP始終指向棧頂單元。當(dāng)進入進入一個過程時, SP指向為此過程創(chuàng)建的活動記錄的起點, TOP指向為此過程創(chuàng)建的活動記錄的頂端。當(dāng)進入進入一個過程時, SP指向為此過程創(chuàng)建的活動記錄的起點,

12、TOP指向為此過程創(chuàng)建的活動記錄的頂端; 若含有可變數(shù)組可變數(shù)組, 則分配數(shù)組區(qū)后, TOP又改為指向數(shù)組區(qū)的頂端。圖6-3 含可變數(shù)組的程序含可變數(shù)組的程序的存儲組織R的數(shù)組區(qū)的數(shù)組區(qū)R的活動記錄的活動記錄Q的數(shù)組區(qū)的數(shù)組區(qū)Q的活動記錄的活動記錄TOPSPmain的的數(shù)組區(qū)數(shù)組區(qū)main的的活動記錄活動記錄主程序全局?jǐn)?shù)據(jù)區(qū)主程序全局?jǐn)?shù)據(jù)區(qū)C的活動記錄含以下幾個區(qū)段的活動記錄含以下幾個區(qū)段:(1)連接數(shù)據(jù)連接數(shù)據(jù)(兩項): 老老SP值值和返回地址返回地址, 其中老老SP為前一活動記錄的起始地址;(2)參數(shù)個數(shù)參數(shù)個數(shù);(3)形式單元形式單元(存放實參的值或地址);(4)過程的局部變量局部變量(

13、簡單變量)、數(shù)組的數(shù)組的內(nèi)情向量內(nèi)情向量和臨時工作單元臨時工作單元。 1TOP臨時工作單元臨時工作單元內(nèi)情向量內(nèi)情向量簡單變量簡單變量形式單元形式單元參數(shù)個數(shù)參數(shù)個數(shù)返回地址返回地址老老SPSP20圖6-4 C過程的活動記錄過程的活動記錄C語言不不允許函數(shù)嵌套允許函數(shù)嵌套, 即不允許一個過程的定義出現(xiàn)在另一過程的定義之內(nèi)。因此, C語言的語言的非局部變量非局部變量僅能出僅能出現(xiàn)在源程序頭現(xiàn)在源程序頭, 非局部變量可采用靜態(tài)靜態(tài)存儲存儲并在編譯時確定它們的地址。C語言中, 過程的每個局部變量或形參每個局部變量或形參在活動記錄中的在活動記錄中的位置是確定的位置是確定的。因此, 變量和形參運行時運行

14、時在棧上的絕對地址絕對地址:絕對地址絕對地址=活動記錄基址活動記錄基址(SP)+相對地址相對地址對于當(dāng)前正在執(zhí)行的過程, 其任一局局部變量部變量或形參或形參A的引用均可表示為變址訪問XSP, 其中X代表A相對于活動記錄基址的偏移量偏移量, 這個偏移量在編譯時可完全確定下來。過程的局部數(shù)組的內(nèi)情向量局部數(shù)組的內(nèi)情向量的相對地址在編譯時同樣可完全確定下來。當(dāng)數(shù)據(jù)空間在過程中獲得分配后, 對數(shù)組元素的引用易于用變址方式訪問。6.2.2 過程的執(zhí)行過程的執(zhí)行1. 過程調(diào)用過程調(diào)用過程調(diào)用的四元式序列為: par T1 par T2 par Tn call P, n由于此時TOP指向被調(diào)過程P之前的棧頂

15、, 而P的形式單元形式單元與活動記錄起點活動記錄起點之間的距離是確定的(等于3), 因而由調(diào)用過程調(diào)用過程給被調(diào)過程被調(diào)過程P的活動記錄活動記錄(正在形成)的形式形式單元單元傳遞傳遞實參值實參值或或?qū)崊⒌刂穼崊⒌刂? 即每個par Ti(i=1, n)可直接翻譯成如下指令: (i+3)TOP=Ti /傳參數(shù)值 或 (i+3)TOP=addrTi /參數(shù)地址四元式 call P,n 翻譯成: 1TOP=SP /保護現(xiàn)行SP 3TOP=n /傳遞參數(shù)個數(shù) JSR P /轉(zhuǎn)向P過程參數(shù)個數(shù)參數(shù)個數(shù)nTOP+3SPT2T1現(xiàn)行現(xiàn)行SP值值P的活動記錄調(diào)用過程TOP43210圖6-5 調(diào)用過程P之前先構(gòu)

16、造P 的活動記錄的部分內(nèi)容2. 過程進入過程進入轉(zhuǎn)入過程P后, 首先要做的是定義新活新活動記錄的動記錄的SP, 保護返回地址返回地址和定義新新活動記錄的活動記錄的TOP值值, 即執(zhí)行下述指令:SP = TOP+1 /定義新SP1SP=返回地址 /保護返回地址TOP=TOP+L /定義新TOP其中L是過程P的活動記錄所需的單元數(shù), 該數(shù)在編譯時可靜態(tài)計算出。對含可變數(shù)組含可變數(shù)組的情況, 緊接上述指令之后是對數(shù)組進行存儲分配的指令。對數(shù)組進行存儲分配的指令對數(shù)組進行存儲分配的指令是在翻譯翻譯數(shù)組說明數(shù)組說明時產(chǎn)生的, 對每個數(shù)組說明每個數(shù)組說明, 相應(yīng)的目標(biāo)指令組將做以下工作: (1)計算各維的

17、上下限; (2)調(diào)用數(shù)組空間分配子程序數(shù)組空間分配子程序。數(shù)組空間分配子程序數(shù)組空間分配子程序計算并填好內(nèi)情計算并填好內(nèi)情向量的所有信息向量的所有信息, 然后在TOP所指位置之上留出數(shù)組所需空間留出數(shù)組所需空間, 并將TOP調(diào)整為指向數(shù)組區(qū)頂端。P的數(shù)組區(qū)返回地址P的活動記錄(長度為L)1調(diào)用過程SPTOP0此后, 在執(zhí)行語句過程中, 凡引用引用形參、局部變量或數(shù)組元素都以SP為基址進行相對訪問。進入過程P后所做工作如下圖:3. 過程返回C語言及其它一些語言含return(E)形式的返回語句。假定E值值已計算出來并存放在某臨時單元T中, 則此時可將T值傳送到某個特定寄存器中(調(diào)用過程將從這個特

18、定寄存器中獲得被調(diào)過程P的結(jié)果)。剩下的工作是恢復(fù)恢復(fù)SP和TOP, 并按返返回地址回地址實行無條件轉(zhuǎn)移轉(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ù)函數(shù), 則按上述辦法傳遞結(jié)果值, 否則僅直接執(zhí)行上述返回指令序列。SPTOP返回地址老SPP空間調(diào)用過程空間圖6-7 過程P的返回示意圖6.3 嵌套過程語言的棧式實現(xiàn)嵌套過程語言的棧式實現(xiàn)在簡單程序語言實現(xiàn)中允許過程的遞允許過程的遞歸調(diào)用歸調(diào)用,

19、且過程中可含可變數(shù)組可含可變數(shù)組。現(xiàn)在再加上一種功能-允許過程的嵌套允許過程的嵌套性性, 如PASCAL。由于PASCAL含有文件和動態(tài)變量, 故它的存儲分配不能簡單地用棧式方法實現(xiàn)。考慮考慮PASCAL的一個子集的一個子集, 即去掉文件和動態(tài)變量文件和動態(tài)變量這兩種數(shù)據(jù)類型, 則可用下述方法實現(xiàn)存儲分配:6.3.1 嵌套層次顯示表和活動記錄嵌套層次顯示表和活動記錄假定主程序的層數(shù)為0。若過程Q是在層數(shù)為i的過程P內(nèi)定義的, 且P是包圍Q的最小過程, 則Q的層數(shù)為i+1。編譯程序處理過程說明時, 過程的層過程的層數(shù)數(shù)作為過程名的一個重要屬性登記在符號表中。由于過程定義是嵌套的, 因而一個過程可以引用引用包圍它的任一外層過程所定義的變量或數(shù)組, 即運行時運行時過程Q可引用它的任一外層過程P的最新活動記錄中的某些數(shù)據(jù)。因此, 過程Q運行時必須知道它的所有外層的最新活動記錄的地址。由于允許遞歸和可變數(shù)組的存在, 過程的活動記錄位置往往是變遷的, 因而必須設(shè)法跟蹤每個外層過程的最新活動記錄的位置。一種常用的跟蹤每個外層過程最新活動記錄位置的有效辦法: 每進入進入一個過程后, 在建立它的活動記錄區(qū)的同時建立一張建立