編譯原理第8章程序運行時的存儲組織PPT課件

1、源 程 序目 標 程 序1.編 譯編 譯 程 序初 始 數(shù) 據(jù)系 統(tǒng) 子 程 序結 果2.運 行第第8 8章章 程序運行時的存儲組織及管理程序運行時的存儲組織及管理(P158)(P158)n8.1 程序運行時的存儲組織程序運行時的存儲組織n8.2 靜態(tài)存儲分配靜態(tài)存儲分配n8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配n8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配學學 習習 重重 點點n影響存儲分配策略的語言特征影響存儲分配策略的語言特征n靜態(tài)存儲分配靜態(tài)存儲分配n動態(tài)存儲分配動態(tài)存儲分配n活動記錄活動記錄n堆式存儲分配變長塊的方法堆式存儲分配變長塊的方法n影響存儲分配策略的語言特征影響存儲分配策略的語

2、言特征: : 過程能否遞歸過程能否遞歸 過程能否嵌套過程能否嵌套 過程調(diào)用時參數(shù)如何傳遞過程調(diào)用時參數(shù)如何傳遞 哪些實體可以作為參數(shù)和返回值哪些實體可以作為參數(shù)和返回值 是否允許動態(tài)的為對象分配和撤銷存儲空間是否允許動態(tài)的為對象分配和撤銷存儲空間 存儲空間是否必須顯式地釋放存儲空間是否必須顯式地釋放 第第8 8章章 程序運行時的存儲組織及管理程序運行時的存儲組織及管理n程序運行時，系統(tǒng)將為程序分配一塊存儲空間。這程序運行時，系統(tǒng)將為程序分配一塊存儲空間。這塊空間用來存儲程序的目標代碼以及目標代碼運行時塊空間用來存儲程序的目標代碼以及目標代碼運行時需要或產(chǎn)生的各種數(shù)據(jù)。從用途上看，這塊空間可分需

3、要或產(chǎn)生的各種數(shù)據(jù)。從用途上看，這塊空間可分為以下幾個部分：為以下幾個部分：1 1）目標程序區(qū)）目標程序區(qū)：用來存放目標代碼。：用來存放目標代碼。2 2）靜態(tài)數(shù)據(jù)區(qū)）靜態(tài)數(shù)據(jù)區(qū)：用來存放編譯時就能確定存儲空：用來存放編譯時就能確定存儲空間的數(shù)據(jù)。間的數(shù)據(jù)。3 3）運行棧區(qū)）運行棧區(qū)：用來存放運行時才能確定存儲空間：用來存放運行時才能確定存儲空間的數(shù)據(jù)。的數(shù)據(jù)。4 4）運行堆區(qū)）運行堆區(qū)：用來存放運行時用戶動態(tài)申請存儲：用來存放運行時用戶動態(tài)申請存儲空間的數(shù)據(jù)?？臻g的數(shù)據(jù)。8.1 8.1 程序運行時的存儲組織程序運行時的存儲組織n靜態(tài)存儲分配方式：靜態(tài)存儲分配方式：對于源程序中出現(xiàn)的各種數(shù)據(jù)對于

4、源程序中出現(xiàn)的各種數(shù)據(jù)項，如常量、簡單變量、常界數(shù)組、非變體記錄等項，如常量、簡單變量、常界數(shù)組、非變體記錄等, , 在編譯時就給它們分配固定的存儲空間，而且在目標在編譯時就給它們分配固定的存儲空間，而且在目標程序運行時，總是使用這些在編譯時就分配好的存儲程序運行時，總是使用這些在編譯時就分配好的存儲單元作為它們的數(shù)據(jù)空間。單元作為它們的數(shù)據(jù)空間。8.2 8.2 靜態(tài)存儲分配靜態(tài)存儲分配n采用靜態(tài)存儲分配的語言必須滿足下列條件：采用靜態(tài)存儲分配的語言必須滿足下列條件：1 1）不允許過程有遞歸調(diào)用。）不允許過程有遞歸調(diào)用。2 2）不允許有可變大小的數(shù)據(jù)項，如可變數(shù)組或可變）不允許有可變大小的數(shù)據(jù)

5、項，如可變數(shù)組或可變字符串。字符串。3 3）不允許用戶動態(tài)建立數(shù)據(jù)實體。）不允許用戶動態(tài)建立數(shù)據(jù)實體。nFORTRAN語言沒有長度可變的串，也沒有動態(tài)數(shù)組，語言沒有長度可變的串，也沒有動態(tài)數(shù)組，其子程序和函數(shù)也不允許遞歸調(diào)用，所以其子程序和函數(shù)也不允許遞歸調(diào)用，所以FORTRAN語語言言采用靜態(tài)存儲分配方式。采用靜態(tài)存儲分配方式。 8.2 8.2 靜態(tài)存儲分配靜態(tài)存儲分配隱式參數(shù)隱式參數(shù) 形式參數(shù)形式參數(shù) 簡單變量、簡單變量、數(shù)組及其它數(shù)組及其它程序變量程序變量 n例例(P159) 一個一個FORTRAN程序模塊程序模塊靜態(tài)存儲分配的典靜態(tài)存儲分配的典型數(shù)據(jù)區(qū)格局如右圖所示，其中：型數(shù)據(jù)區(qū)格局

6、如右圖所示，其中：1)1)隱式參數(shù)隱式參數(shù)主要用于和主調(diào)模塊的通訊，它可以是主調(diào)主要用于和主調(diào)模塊的通訊，它可以是主調(diào)過程的返回地址，或是過程的返回地址，或是函數(shù)返回值。函數(shù)返回值。2)形式參數(shù)形式參數(shù)存放相應實在參數(shù)的地址存放相應實在參數(shù)的地址或值?；蛑怠?)程序變量部分程序變量部分將作為簡單變量、數(shù)將作為簡單變量、數(shù)組、記錄以及編譯程序所產(chǎn)生的臨時組、記錄以及編譯程序所產(chǎn)生的臨時變量的存儲空間。變量的存儲空間。8.2 8.2 靜態(tài)存儲分配靜態(tài)存儲分配n實現(xiàn)靜態(tài)存儲分配策略：實現(xiàn)靜態(tài)存儲分配策略：編譯程序對源程序進編譯程序對源程序進行處理時，對每個變量在符號表中創(chuàng)建一個記錄，行處理時，對每個

7、變量在符號表中創(chuàng)建一個記錄，保存該變量的屬性，其中包括為變量分配的存儲保存該變量的屬性，其中包括為變量分配的存儲空間地址即目標地址。由于每個變量需要的空間空間地址即目標地址。由于每個變量需要的空間大小已知大小已知,可將數(shù)據(jù)區(qū)開始位置的地址可將數(shù)據(jù)區(qū)開始位置的地址A分配給第分配給第一個變量一個變量,設第一個變量占設第一個變量占n1個字節(jié)，則個字節(jié)，則A+n1分配分配給第二個變量，設第二個變量占給第二個變量，設第二個變量占n2個字節(jié)，同理，個字節(jié)，同理， A+n1+n2分配給第三個變量等。分配給第三個變量等。n例例 char array16; int i, j ; real a, b;假設假設:數(shù)

8、據(jù)區(qū)開始位置的地址數(shù)據(jù)區(qū)開始位置的地址264字符型占字符型占2個存貯單元個存貯單元整型占整型占4個存貯單元個存貯單元實型占實型占8個存貯單元個存貯單元8.2 8.2 靜態(tài)存儲分配靜態(tài)存儲分配n目標地址可采用的地址形式：目標地址可采用的地址形式：絕對地址絕對地址 如果編寫的編譯程序是用于單任務環(huán)境，那如果編寫的編譯程序是用于單任務環(huán)境，那么，通常采用絕對地址作為目標地址。么，通常采用絕對地址作為目標地址。相對地址相對地址 如果編譯程序是在多程序任務的環(huán)境中，那如果編譯程序是在多程序任務的環(huán)境中，那么目標地址可采用相對于程序數(shù)據(jù)區(qū)的基地址的么目標地址可采用相對于程序數(shù)據(jù)區(qū)的基地址的相對地址。相對地

9、址。 若使用相對地址方式，那么程序的每一次執(zhí)若使用相對地址方式，那么程序的每一次執(zhí)行，程序及其數(shù)據(jù)區(qū)可以處在不同的存儲區(qū)內(nèi)。行，程序及其數(shù)據(jù)區(qū)可以處在不同的存儲區(qū)內(nèi)。8.2 8.2 靜態(tài)存儲分配靜態(tài)存儲分配n動態(tài)存儲分配方式：動態(tài)存儲分配方式：有些語言允許有長度可變的串、有些語言允許有長度可變的串、動態(tài)數(shù)組，并允許過程遞歸調(diào)用，那么在編譯時就無動態(tài)數(shù)組，并允許過程遞歸調(diào)用，那么在編譯時就無法確定數(shù)據(jù)空間的具體大小，故其存儲分配必須留到法確定數(shù)據(jù)空間的具體大小，故其存儲分配必須留到目標程序運行時動態(tài)地進行。目標程序運行時動態(tài)地進行。8.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配n動態(tài)存儲分配方

10、式的分類：動態(tài)存儲分配方式的分類：棧式分配方式：棧式分配方式：主要采用一個棧作為動態(tài)存儲分配主要采用一個棧作為動態(tài)存儲分配的存儲空間。當調(diào)用一個程序時，過程中各數(shù)據(jù)項所的存儲空間。當調(diào)用一個程序時，過程中各數(shù)據(jù)項所需的存儲空間動態(tài)地分配于棧頂，當過程結束時，就需的存儲空間動態(tài)地分配于棧頂，當過程結束時，就釋放這部分空間。釋放這部分空間。C、PASCAL等語言即采用這種存等語言即采用這種存儲分配方式。儲分配方式。堆式分配方式：堆式分配方式：主要通過給運行程序分配一個大的主要通過給運行程序分配一個大的存儲空間存儲空間(稱為堆稱為堆)，每當運行需要時，就從這片空間，每當運行需要時，就從這片空間中借用

11、一塊，用過之后再退還給堆。中借用一塊，用過之后再退還給堆。n棧式動態(tài)分配方式的實現(xiàn)：棧式動態(tài)分配方式的實現(xiàn)：1)1)申請：申請：在程序運行中，當程序模塊被調(diào)用時，就在程序運行中，當程序模塊被調(diào)用時，就從總的數(shù)據(jù)區(qū)中請求一個空間作為其數(shù)據(jù)區(qū)從總的數(shù)據(jù)區(qū)中請求一個空間作為其數(shù)據(jù)區(qū)( (即加入運即加入運行棧中行棧中) )，并保留該空間直到執(zhí)行完整個模塊為止。，并保留該空間直到執(zhí)行完整個模塊為止。2)2)釋放：釋放：當模塊執(zhí)行完畢，退出模塊時，釋放它所當模塊執(zhí)行完畢，退出模塊時，釋放它所占有的數(shù)據(jù)空間占有的數(shù)據(jù)空間( (即從運行棧中彈出即從運行棧中彈出) )。3)3)嵌套調(diào)用：嵌套調(diào)用：從模塊被調(diào)用到

12、它運行結束之間，還從模塊被調(diào)用到它運行結束之間，還可以通過過程調(diào)用或程序塊入口進入其他的模塊，此可以通過過程調(diào)用或程序塊入口進入其他的模塊，此時，也按上面所介紹的方法將這些模塊的數(shù)據(jù)區(qū)壓入時，也按上面所介紹的方法將這些模塊的數(shù)據(jù)區(qū)壓入或彈出運行棧。當嵌套的被調(diào)程序運行結束返回到主或彈出運行棧。當嵌套的被調(diào)程序運行結束返回到主調(diào)程序中的調(diào)用點時，運行棧中的格局和內(nèi)容會恢復調(diào)程序中的調(diào)用點時，運行棧中的格局和內(nèi)容會恢復到調(diào)用之前的情況。到調(diào)用之前的情況。 8.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配n例例(P160)設有如下設有如下C程序，其運行棧的變化情況如下圖所示。程序，其運行棧的變化情況

13、如下圖所示。real x; 塊塊1int m1(int ind) 塊塊2 int x; x=m2(ind+1);int m2(int j) 塊塊3 int f10; 塊塊4 bool test1; main()塊塊5 int x; x=2; printf(%dn,m1(x/5); 塊塊4數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊3數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊2數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊5數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊1數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊3數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊2數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊5數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊1數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊2數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊5數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊1數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊5數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊1數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) 塊塊1數(shù)據(jù)區(qū)數(shù)據(jù)區(qū) (a)程序剛開始程

14、序剛開始 (b)運行運行main (c)運行運行m1 (d)運行運行m2 (e)運行塊運行塊4n對于對于C語言，函數(shù)是程序語言，函數(shù)是程序塊，一對花括號內(nèi)的程序即塊，一對花括號內(nèi)的程序即復合語句也可以看成是一個復合語句也可以看成是一個程序塊。程序塊。 上例說明：當這段程序剛開始運行時，其存上例說明：當這段程序剛開始運行時，其存儲分配為圖儲分配為圖(a)所示，接下來主函數(shù)所示，接下來主函數(shù)main運行，則運行，則為主函數(shù)為主函數(shù)main分配數(shù)據(jù)區(qū)，運行棧為圖分配數(shù)據(jù)區(qū)，運行棧為圖 (b)，在，在main中調(diào)用了函數(shù)中調(diào)用了函數(shù)m1，當函數(shù)，當函數(shù)m1運行時，運行運行時，運行棧為圖棧為圖 (c)，

15、在函數(shù)，在函數(shù)m1中又調(diào)用了函數(shù)中又調(diào)用了函數(shù)m2，當函，當函數(shù)數(shù)m2運行時的運行棧如圖運行時的運行棧如圖 (d)所示，由于函數(shù)所示，由于函數(shù)m2中嵌套著塊中嵌套著塊4，當運行塊，當運行塊4時，運行棧為圖時，運行棧為圖 (e)所示。所示。當塊當塊4運行完后，塊運行完后，塊4數(shù)據(jù)區(qū)出棧，運行?；謴偷綌?shù)據(jù)區(qū)出棧，運行?；謴偷綀D圖 (d)所示。當函數(shù)所示。當函數(shù)m2運行完后，運行?；謴偷竭\行完后，運行棧恢復到圖圖 (c)所示。當函數(shù)所示。當函數(shù)m1運行完后，運行棧恢復到運行完后，運行?；謴偷綀D圖 (b)所示。當所有程序運行后，運行棧為空。所示。當所有程序運行后，運行棧為空。8.3 8.3 棧式動態(tài)存

16、儲分配棧式動態(tài)存儲分配n活動記錄活動記錄：當程序運行進入一個程序模塊時，：當程序運行進入一個程序模塊時，就在運行棧的棧頂創(chuàng)建一個專用數(shù)據(jù)區(qū)，該數(shù)據(jù)就在運行棧的棧頂創(chuàng)建一個專用數(shù)據(jù)區(qū)，該數(shù)據(jù)區(qū)通常稱為活動記錄。區(qū)通常稱為活動記錄。8.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配n當程序模塊執(zhí)行結束時當程序模塊執(zhí)行結束時( (即到達模塊的出口即到達模塊的出口) )，其相應的活動記錄將從運行棧的棧頂刪除。因此其相應的活動記錄將從運行棧的棧頂刪除。因此在該模塊中所定義的變量在該模塊的外部是不存在該模塊中所定義的變量在該模塊的外部是不存在的。在的。n一個典型的活動記錄結構如右圖所示。一個典型的活動記錄結

17、構如右圖所示。1 1、 參數(shù)區(qū)參數(shù)區(qū)u1)1) 隱式參數(shù)：隱式參數(shù)：p返回地址返回地址：主調(diào)程序中調(diào)用語句的下一條可執(zhí)行語句：主調(diào)程序中調(diào)用語句的下一條可執(zhí)行語句的地址。的地址。p指向前一個活動記錄起始位置的指針指向前一個活動記錄起始位置的指針：該基地址指針：該基地址指針存放該模塊的主調(diào)模塊的活動記錄的基地址，用于確保存放該模塊的主調(diào)模塊的活動記錄的基地址，用于確?？刂品祷刂髡{(diào)過程時，能使運行環(huán)境恢復到調(diào)用前的格控制返回主調(diào)過程時，能使運行環(huán)境恢復到調(diào)用前的格局。局。p函數(shù)返回值：函數(shù)返回值：有的隱式參數(shù)區(qū)包含此項，有的不包括，有的隱式參數(shù)區(qū)包含此項，有的不包括，還有更好的處理返回值的方法還有

18、更好的處理返回值的方法 。u2) 2) 顯式參數(shù)：顯式參數(shù)：顯式參數(shù)區(qū)是形式參數(shù)的通訊區(qū)。顯式參數(shù)區(qū)是形式參數(shù)的通訊區(qū)。 形式參數(shù)的傳遞有傳值、傳地址、傳名等方法。形式參數(shù)的傳遞有傳值、傳地址、傳名等方法。局部數(shù)據(jù)局部數(shù)據(jù)區(qū)區(qū)參數(shù)區(qū)參數(shù)區(qū)display區(qū)區(qū)8.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配2、display區(qū)區(qū)(嵌套層次顯示表嵌套層次顯示表)display區(qū)區(qū)用于保存對當前正在執(zhí)行的模塊用于保存對當前正在執(zhí)行的模塊來說是全局的程序變量區(qū)的信息，它由一系列來說是全局的程序變量區(qū)的信息，它由一系列地址指針所組成，每一個指針指向一個程序塊地址指針所組成，每一個指針指向一個程序塊的活動記

19、錄的開始位置，而這個程序塊對于當?shù)幕顒佑涗浀拈_始位置，而這個程序塊對于當前正在執(zhí)行的程序塊來說是全局的。前正在執(zhí)行的程序塊來說是全局的。8.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配real x; 塊塊1int m1(int ind) 塊塊2 int x; x=m2(ind+1);int m2(int j) 塊塊3 int f10; 塊塊4 bool test1; main()塊塊5 int x; x=2; printf(%dn,m1(x/5); jOS無前記錄無前記錄 xd1abp0 x ,2d1return2abp1indx,0d1return3abp2d1d2abp3ftest1塊塊4

20、活動記錄活動記錄abp4abp4 m2活動記錄活動記錄abp3 m1活動記錄活動記錄abp2 main活動記錄活動記錄abp1abp0display區(qū)區(qū)參數(shù)區(qū)參數(shù)區(qū)局部數(shù)據(jù)局部數(shù)據(jù)區(qū)區(qū)應是應是main,m2,m1,xu構造一個構造一個display區(qū)的算法區(qū)的算法(P162)： 如果如果j=i+1(即進入一個程序塊即進入一個程序塊)，則，則復制復制i層的層的display，然后增加一個指，然后增加一個指向向i層模塊活動記錄基地址的指針。層模塊活動記錄基地址的指針。 如果如果ji(即調(diào)用對當前模塊來說是即調(diào)用對當前模塊來說是屬于全程聲明的過程模塊屬于全程聲明的過程模塊)，則來自，則來自i層模塊活

21、動記錄中的層模塊活動記錄中的display區(qū)前面區(qū)前面j-1個入口將組成個入口將組成j層模塊的層模塊的display區(qū)。區(qū)。jOS無前記錄無前記錄 xd1abp0 x d1return2abp1indxd1return3abp2d1d2abp3ftest1塊塊4活動記錄活動記錄abp4abp4 m2活動記錄活動記錄abp3 m1活動記錄活動記錄abp2 main活動記錄活動記錄abp1abp08.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配n根據(jù)變量的二元地址根據(jù)變量的二元地址(BL，ON)和和display區(qū)的區(qū)的結構可以計算出變量在運行棧中的地址，從而結構可以計算出變量在運行棧中的地址，從

22、而找到變量的值。如果所引用的變量是一個外層找到變量的值。如果所引用的變量是一個外層模塊的局部變量，則它的層次號模塊的局部變量，則它的層次號BL值必須小于值必須小于當前正在執(zhí)行的模塊的層次號。對這種情況而當前正在執(zhí)行的模塊的層次號。對這種情況而言，包含該變量單元的活動記錄能夠間接通過言，包含該變量單元的活動記錄能夠間接通過當前活動記錄中當前活動記錄中display區(qū)中的相應指針來獲取。區(qū)中的相應指針來獲取。 n給定一個要訪問的具有地址為給定一個要訪問的具有地址為(BL，ON)的變量，設該的變量，設該變量在變量在LEV 層的一個模塊中。該層的一個模塊中。該變量的地址變量的地址ADDR可按可按如下方

23、法計算如下方法計算(P163)： if BL=LEV then ADDR=abp+(BL-1)+nip+ON/局部變量局部變量 else if BLLEV then /全局變量全局變量 ADDR=displayBL+(BL-1)+nip+ON else write(“地址錯，不合法的模塊層次地址錯，不合法的模塊層次”) 在上式中，在上式中，abp是當前活動記錄基址指針值，是當前活動記錄基址指針值，displayBL指當前活動記錄中指當前活動記錄中display區(qū)中第區(qū)中第BL個元素，個元素，nip是指隱式參數(shù)的數(shù)目。是指隱式參數(shù)的數(shù)目。 注意：注意：表達式表達式(BL-1)+nip可解釋為可解

24、釋為display區(qū)的大小加隱區(qū)的大小加隱式參數(shù)區(qū)的大小。式參數(shù)區(qū)的大小。8.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配8.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配n對于具有遞歸塊程序結構的語言來說，一個對于具有遞歸塊程序結構的語言來說，一個程序模塊可以和多個活動記錄相關。當程序運程序模塊可以和多個活動記錄相關。當程序運行時，隨著遞歸函數(shù)的每一次調(diào)用，在運行棧行時，隨著遞歸函數(shù)的每一次調(diào)用，在運行棧棧頂將設置一個新的活動記錄，返回地址也與棧頂將設置一個新的活動記錄，返回地址也與每個活動記錄相聯(lián)系。每個活動記錄相聯(lián)系。地址地址 內(nèi)容內(nèi)容說明說明 abp4n,2第第3次調(diào)次調(diào)fact函數(shù)函數(shù)

25、n=2，返回，返回2給全給全局變量區(qū)的局變量區(qū)的fact單元單元abp3ret2abp0 abp3n,3第第2次調(diào)次調(diào)fact函數(shù)函數(shù)n=3，返回，返回6給全給全局變量區(qū)的局變量區(qū)的fact單元單元abp2ret2abp0 abp2n,4第第1次調(diào)次調(diào)fact函數(shù)函數(shù)n=4。返回。返回24給給全局變量區(qū)的全局變量區(qū)的fact單元單元abp1ret1abp0 abp1m,4主函數(shù)運行，主函數(shù)運行，m=4，調(diào)，調(diào)fact函數(shù)。函數(shù)。ret0是運行完是運行完main后返回的地址后返回的地址,可以是可以是OS或留空或留空abp0ret0abp0 abp0mainfact用于保存用于保存fact函數(shù)的返

26、回值，函數(shù)的返回值，開始時無值，最后開始時無值，最后fact函數(shù)返回函數(shù)返回后為后為24。fact,2,6,24無前記錄無前記錄OSn例例(P163) C程序在程序執(zhí)行期間程序在程序執(zhí)行期間其運行棧的變化情況如右圖所示。其運行棧的變化情況如右圖所示。int fact(int n) if (n3) return(n) else return(n*fact(n-1); main() int m; m=4; printf(%d!=%dn,m,fact(m); 備注：備注：返回地址返回地址ret1指示從指示從fact函函數(shù)的特定動作返回到數(shù)的特定動作返回到main函數(shù)內(nèi)函數(shù)內(nèi)部的調(diào)用點之后。返回地址部

27、的調(diào)用點之后。返回地址ret2指指示從示從fact函數(shù)的特定動作返回到函數(shù)的特定動作返回到fact函數(shù)內(nèi)部的調(diào)用點之后。函數(shù)內(nèi)部的調(diào)用點之后。 ret2ret18.3 8.3 棧式動態(tài)存儲分配棧式動態(tài)存儲分配n棧式存儲分配適合那些過程允許嵌套定義、棧式存儲分配適合那些過程允許嵌套定義、遞歸調(diào)用的語言，其過程的進入和退出具有遞歸調(diào)用的語言，其過程的進入和退出具有“后進先出后進先出”的特點。如果語言允許動態(tài)申請的特點。如果語言允許動態(tài)申請和釋放存儲空間，那么，棧式存儲分配就不適和釋放存儲空間，那么，棧式存儲分配就不適合了，這時，可以采用堆式動態(tài)存儲分配策略。合了，這時，可以采用堆式動態(tài)存儲分配策略

28、。n堆式分配策略的基本思路堆式分配策略的基本思路：假設程序運行時有一個大：假設程序運行時有一個大的連續(xù)的存儲空間（堆），當存儲管理程序接收到運行的連續(xù)的存儲空間（堆），當存儲管理程序接收到運行程序的存儲空間請求時，就從堆中分配一塊空間給運行程序的存儲空間請求時，就從堆中分配一塊空間給運行程序。當運行程序用完后再退還給堆（即釋放）。管理程序。當運行程序用完后再退還給堆（即釋放）。管理程序回收其存儲空間以備后面使用。由于每塊空間可以程序回收其存儲空間以備后面使用。由于每塊空間可以按任意順序釋放，這樣，程序經(jīng)過一段運行后，堆將被按任意順序釋放，這樣，程序經(jīng)過一段運行后，堆將被劃分成若干已用塊和空閑塊

29、。劃分成若干已用塊和空閑塊。8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配u1u3 u4u7 u8程序運行一段時間后程序運行一段時間后 程序運行初期程序運行初期 8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配n堆式存儲分配需要解決的問題：堆式存儲分配需要解決的問題：一是堆空間的分配一是堆空間的分配 當運行程序需要一塊空間時，應該分配哪當運行程序需要一塊空間時，應該分配哪一塊給它。一塊給它。二是分配空間的釋放二是分配空間的釋放 由于返回給堆的不用空間是按任意次序進由于返回給堆的不用空間是按任意次序進行的，所以需要專門研究釋放的策略。行的，所以需要專門研究釋放的策略。n 新用戶請求分配內(nèi)存時，

30、新用戶請求分配內(nèi)存時，系統(tǒng)分配空間策略系統(tǒng)分配空間策略： 系統(tǒng)繼續(xù)從高地址的空閑塊中進行分配，而不查系統(tǒng)繼續(xù)從高地址的空閑塊中進行分配，而不查看已分配給用戶的內(nèi)存區(qū)是否已空閑，直到分配看已分配給用戶的內(nèi)存區(qū)是否已空閑，直到分配無法進行無法進行(即剩余的空閑塊不能滿足分配的請求即剩余的空閑塊不能滿足分配的請求)時，時，系統(tǒng)才去回收所有用戶不再使用的空閑塊。系統(tǒng)才去回收所有用戶不再使用的空閑塊。 用戶使用一旦結束，便將所占內(nèi)存區(qū)釋放成空閑用戶使用一旦結束，便將所占內(nèi)存區(qū)釋放成空閑塊。同時，每當新的用戶請求分配內(nèi)存時，系統(tǒng)塊。同時，每當新的用戶請求分配內(nèi)存時，系統(tǒng)需要巡視整個內(nèi)存中所有空閑塊，并從中

31、找出一需要巡視整個內(nèi)存中所有空閑塊，并從中找出一個個“合適合適”的空閑塊加以分配。由此，系統(tǒng)需建的空閑塊加以分配。由此，系統(tǒng)需建立一張記錄所有空閑塊的立一張記錄所有空閑塊的“可利用空間表可利用空間表”，表，表的結構可以采用目錄表或鏈表。的結構可以采用目錄表或鏈表。 8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配0 10000 20000 30000(a)內(nèi)存狀態(tài)內(nèi)存狀態(tài) 起始地址起始地址內(nèi)存大小內(nèi)存大小 使用情況使用情況 100005000空閑空閑200003000空閑空閑300008000空閑空閑(b)可利用空間目錄表可利用空間目錄表0500020000030003000008000#10

32、000HEAD 10000 20000 30000(c)可利用空間鏈表可利用空間鏈表堆式存儲管理的可利用空間表堆式存儲管理的可利用空間表 TAGSIZELINKSPACE8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配n“可利用空間鏈表可利用空間鏈表”中結點的數(shù)據(jù)結構如下中結點的數(shù)據(jù)結構如下 TAG：標記，：標記，0表示空閑，表示空閑，1表示占用。表示占用。SIZE：記錄結點大小，指示空閑塊的存儲量。：記錄結點大小，指示空閑塊的存儲量。LINK:指向下一個結點。指向下一個結點。 SPACE：地址連續(xù)的內(nèi)存空間。：地址連續(xù)的內(nèi)存空間。 n堆式存儲管理方法：堆式存儲管理方法：1、定長塊的管理、定長

33、塊的管理 將總的可被利用的堆存儲區(qū)劃分成大小適當將總的可被利用的堆存儲區(qū)劃分成大小適當?shù)囊幌盗袎K。這些塊通過每塊中的的一系列塊。這些塊通過每塊中的LINK域連接域連接起來形成單向線性鏈表（即可利用空間鏈表）。起來形成單向線性鏈表（即可利用空間鏈表）。然后由一個分配程序來處理。然后由一個分配程序來處理。8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配n對一個存儲塊的請求，其定長塊分配程序算法如下：對一個存儲塊的請求，其定長塊分配程序算法如下：Function GET_BLOCK(HEAD)/ HEAD為指向可用存儲塊鏈表上第一個塊的指針，為指向可用存儲塊鏈表上第一個塊的指針，GET_BLOCK返

34、回一個可用塊的地址返回一個可用塊的地址p。(1) 溢出嗎溢出嗎? if HEAD=NULL then 轉錯誤處理程序；轉錯誤處理程序；(2) 分配存儲塊分配存儲塊 p=HEAD HEAD=p.LINK return(p) 由于由于各塊大小相同，故在各塊大小相同，故在分配函數(shù)中不用查找，只需將分配函數(shù)中不用查找，只需將頭指針所指的第一塊分配給申頭指針所指的第一塊分配給申請空間的程序，然后頭指針指請空間的程序，然后頭指針指向下一個空閑塊。同樣，當用向下一個空閑塊。同樣，當用戶釋放內(nèi)存時，系統(tǒng)只要將用戶釋放內(nèi)存時，系統(tǒng)只要將用戶釋放的空間塊插入到表頭即戶釋放的空間塊插入到表頭即可?？?。0800200

35、000800300000800#10000HEAD 10000 20000 30000n堆式存儲管理方法：堆式存儲管理方法：2、變長塊的管理、變長塊的管理（常用）（常用） 系統(tǒng)在運行期間分配給用戶的內(nèi)存塊的系統(tǒng)在運行期間分配給用戶的內(nèi)存塊的大小不固定，可以隨請求而變。大小不固定，可以隨請求而變。8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配n變長塊的分配策略：變長塊的分配策略：假設用戶請求一個大小為假設用戶請求一個大小為n的存儲塊，而的存儲塊，而“可利可利用空間鏈表用空間鏈表”中僅有一塊大小為中僅有一塊大小為m(mn)的空閑塊，的空閑塊，則分配時只需將大小為則分配時只需將大小為n的部分分配給

36、申請的用戶，的部分分配給申請的用戶，同時將剩余的同時將剩余的m-n部分作為一個結點留在鏈表中即部分作為一個結點留在鏈表中即可?？伞Ｈ艨衫每臻g表中有若干個大于若可利用空間表中有若干個大于n的空閑塊時，的空閑塊時，可采用首次滿足法、最優(yōu)滿足法或最差滿足法來分可采用首次滿足法、最優(yōu)滿足法或最差滿足法來分配塊。配塊。 8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配p首次滿足法：首次滿足法：從表頭指針開始查找可利用空間表，從表頭指針開始查找可利用空間表，將找到的第一個大小不小于將找到的第一個大小不小于n的空閑塊的一部分分配的空閑塊的一部分分配給用戶。可利用空間表本身既不按結點的初始地址排給用戶?？衫?/p>

37、用空間表本身既不按結點的初始地址排序，也不按結點的大小排序。在回收時，只要將釋放序，也不按結點的大小排序。在回收時，只要將釋放的空閑塊插入在鏈表的表頭即可。的空閑塊插入在鏈表的表頭即可。 8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配p最優(yōu)滿足法：最優(yōu)滿足法：系統(tǒng)在分配前首先要對可利用空間表系統(tǒng)在分配前首先要對可利用空間表從頭至尾掃描一遍，然后從中找出一塊不小于從頭至尾掃描一遍，然后從中找出一塊不小于n且最且最接近接近n空閑塊進行分配給用戶。為了提高效率，通?？臻e塊進行分配給用戶。為了提高效率，通常預先將預先將“可利用空間表可利用空間表”按空間的大小從小到大進行按空間的大小從小到大進行排序。

38、在回收時，必須將釋放的空閑塊插入到合適的排序。在回收時，必須將釋放的空閑塊插入到合適的位置上去。位置上去。p最差滿足法：最差滿足法：將可利用空間表中不小于將可利用空間表中不小于n且是鏈表且是鏈表中最大的空閑塊的一部分分配給用戶。中最大的空閑塊的一部分分配給用戶。為了減少查找為了減少查找時間，應該對時間，應該對“可利用空間表可利用空間表”按空閑塊的大小從大按空閑塊的大小從大到小排序。每次分配時無需查找，只需從鏈表中刪除到小排序。每次分配時無需查找，只需從鏈表中刪除第一個結點，并將其中一部分分配給用戶，而將剩余第一個結點，并將其中一部分分配給用戶，而將剩余部分作為一個新的結點插入到可利用空間表的適當位部分作為一個新的結點插入到可利用空間表的適當位置上。回收時也將釋放的空閑塊插入到鏈表的適當位置上?；厥諘r也將釋放的空閑塊插入到鏈表的適當位置上。置上。 8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配n在選擇變長塊的分配策略時需考慮的因素：用在選擇變長塊的分配策略時需考慮的因素：用戶的邏輯要求，請求的內(nèi)存空間的大小分布；戶的邏輯要求，請求的內(nèi)存空間的大小分布；分配和釋放的頻率以及效率對系統(tǒng)的重要性等分配和釋放的頻率以及效率對系統(tǒng)的重要性等因素。因素。8.4 8.4 堆式動態(tài)存儲分配堆式動態(tài)存儲分配