8hh第6章運行時存儲空間組織ppt課件

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

2、靜態(tài)分配戰(zhàn)略 假設(shè)一個程序文語不允許有遞歸過程, 不允許含可變體積的數(shù)據(jù)項或待定性質(zhì)的名字, 那么在編譯時能完全確定其程序的每個數(shù)據(jù)工程的存儲空間位置, 這種戰(zhàn)略叫靜態(tài)分配戰(zhàn)略。例如, FORTRAN言語2. 棧式動態(tài)分配戰(zhàn)略假設(shè)程序文語允許有遞歸過程和可變數(shù)組, 那么程序數(shù)據(jù)空間的分配需采用動態(tài)戰(zhàn)略, 即在程序運轉(zhuǎn)時進展數(shù)據(jù)空間的分配, 此時目的程序可用棧作為動態(tài)的數(shù)據(jù)空間。程序運轉(zhuǎn)時, 每當進入一個子程序, 其所需的數(shù)據(jù)空間就動態(tài)地分配于棧頂, 一旦該子程序運轉(zhuǎn)終了, 其所占用的空間就釋放, 這種方法叫棧式動態(tài)分配戰(zhàn)略。3. 堆式動態(tài)分配戰(zhàn)略假設(shè)程序文語允許用戶動態(tài)地懇求和釋放存儲空間,

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

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

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

6、RTRAN程序段的部分數(shù)據(jù)區(qū)可由圖6-1所示的工程組成: 暫時變量數(shù)組簡單變量方式單元存放器維護區(qū)隱參數(shù)前往地址圖6-1 一個FORTRAN程序段的部分數(shù)據(jù)區(qū)隱參數(shù)指過程調(diào)用時的銜接信息, 如前往地址、存放器維護區(qū)等; 方式單元用來存放過程調(diào)用時與形參對應的實參地址或值。首先思索一種簡單程序文語: 沒有分程序構(gòu)造, 過程定義不允許嵌套, 但允許過程的遞歸調(diào)用, 允許過程含可變數(shù)組。C言語除了不允許含可變數(shù)組外, 就是這樣一種言語。6.2 簡單的棧式存儲分配C言語的程序構(gòu)造如下:全局數(shù)聽闡明main() main中的數(shù)聽闡明void R() R中的數(shù)聽闡明 void Q( ) Q中的數(shù)聽闡明 計

7、算n!的C程序的執(zhí)行過程可用棧實現(xiàn):# include “stdio.hlong 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 棧式存儲分配與活動記錄運用棧式存儲分配法意味著程序運轉(zhuǎn)時, 每當進入一個過程(或函數(shù))就有一個相應的活動記錄累筑于棧頂, 此記錄含有銜接數(shù)據(jù)、方式單元、部分變量、部分數(shù)組的內(nèi)情向量和暫時任務(wù)單元等。在執(zhí)行可執(zhí)行語句之前, 把部分數(shù)組所需空間累筑于棧

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

9、區(qū)圖6-2 C言語程序的存儲組織 SP總是指向執(zhí)行過程活動記錄的起點, TOP一直指向棧頂單元。當進入一個過程時, SP指向為此過程創(chuàng)建的活動記錄的起點, TOP指向為此過程創(chuàng)建的活動記錄的頂端。當進入一個過程時, SP指向為此過程創(chuàng)建的活動記錄的起點, TOP指向為此過程創(chuàng)建的活動記錄的頂端; 假設(shè)含有可變數(shù)組, 那么分配數(shù)組區(qū)后, TOP又改為指向數(shù)組區(qū)的頂端。圖6-3 含可變數(shù)組的程序的存儲組織R的數(shù)組區(qū)R的活動記錄Q的數(shù)組區(qū)Q的活動記錄TOPSPmain的數(shù)組區(qū)main的活動記錄主程序全局數(shù)據(jù)區(qū)C的活動記錄含以下幾個區(qū)段:銜接數(shù)據(jù)(兩項): 老SP值和前往地址, 其中老SP為前一活動記

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

11、訪問XSP, 其中X代表A相對于活動記錄基址的偏移量, 這個偏移量在編譯時可完全確定下來。過程的部分數(shù)組的內(nèi)情向量的相對地址在編譯時同樣可完全確定下來。當數(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的方式單元與活動記錄起點之間的間隔是確定的(等于3), 因此由調(diào)用過程給被調(diào)過程P的活動記錄(正在構(gòu)成)的方式單元傳送實參值或?qū)崊⒌刂? 即每個par Ti(i=1, n)可直接翻譯成如下指令: (i+3)TOP

12、=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ù)nTOP+3SPT2T1現(xiàn)行SP值P的活動記錄調(diào)用過程TOP43210圖6-5 調(diào)用過程P之前先構(gòu)造P 的活動記錄的部分內(nèi)容2. 過程進入轉(zhuǎn)入過程P后, 首先要做的是定義新活動記錄的SP, 維護前往地址和定義新活動記錄的TOP值, 即執(zhí)行下述指令:SP = TOP+1 /定義新SP1SP=前往地址 /維護前往地址TOP=TOP+L /定義新TOP其中L是過程P的活動記錄所需的單元數(shù), 該數(shù)在編譯時可靜

13、態(tài)計算出。對含可變數(shù)組的情況, 緊接上述指令之后是對數(shù)組進展存儲分配的指令。對數(shù)組進展存儲分配的指令是在翻譯數(shù)組闡明時產(chǎn)生的, 對每個數(shù)組闡明, 相應的目的指令組將做以下任務(wù): (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為基址進展相對訪問。進入過程P后所做任務(wù)如以下圖:3. 過程前往C言語及其它一些言語含return(E)方式的

14、前往語句。假定E值已計算出來并存放在某暫時單元T中, 那么此時可將T值傳送到某個特定存放器中(調(diào)用過程將從這個特定存放器中獲得被調(diào)過程P的結(jié)果)。剩下的任務(wù)是恢復SP和TOP, 并按前往地址實行無條件轉(zhuǎn)移, 即執(zhí)行下述指令序列:TOP= SP1 /恢復調(diào)用過程的TOP值SP=0SP /恢復調(diào)用過程的SP值X=2TOP /將前往地址送XUJ 0X /無條件轉(zhuǎn)移到調(diào)用過程一個過程也可經(jīng)過它的end語句(C言語為)自動前往。假設(shè)此過程是一個函數(shù), 那么按上述方法傳送結(jié)果值, 否那么僅直接執(zhí)行上述前往指令序列。SPTOP前往地址老SPP空間調(diào)用過程空間圖6-7 過程P的前往表示圖6.3 嵌套過程言語的

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

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