第8章 運(yùn)行時(shí)的存儲(chǔ)組織與管理

第八章運(yùn)行時(shí)的存儲(chǔ)組織與管理編譯程序需要進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間的分配，本章主要介紹下面兩個(gè)方面的內(nèi)容：（1）靜態(tài)存儲(chǔ)分配（2）棧式動(dòng)態(tài)存儲(chǔ)分配策略8.1概述在編譯程序構(gòu)造的前四個(gè)階段，不涉及目標(biāo)語言、目標(biāo)機(jī)以及目標(biāo)機(jī)的操作系統(tǒng)特性，只與源語言的特性有關(guān)。在編譯程序構(gòu)造的最后一個(gè)階段，目標(biāo)代碼生成的時(shí)候，則完全依賴于目標(biāo)機(jī)和相關(guān)的操作系統(tǒng)。這樣就要求在目標(biāo)代碼生成之前進(jìn)行運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間的分配。

所謂運(yùn)行時(shí)的環(huán)境是指目標(biāo)機(jī)的寄存器和存儲(chǔ)器的結(jié)構(gòu)，以及用來管理存儲(chǔ)器并保存執(zhí)行過程所需要的信息。實(shí)際上，幾乎所有的程序設(shè)計(jì)語言都使用以下3種類型的存儲(chǔ)環(huán)境：完全靜態(tài)環(huán)境、基于棧的存儲(chǔ)環(huán)境、基于堆的存儲(chǔ)環(huán)境中一種或幾種。

編譯程序還必須分配目標(biāo)程序運(yùn)行時(shí)所需要的存儲(chǔ)空間，包括用戶定義的各種數(shù)據(jù)類型的數(shù)據(jù)對象所需要的存儲(chǔ)空間、調(diào)用過程所需要的連接單元、組織輸入/輸出所需要的緩沖區(qū)、保留中間結(jié)果和傳遞參數(shù)所需要的臨時(shí)單元。存儲(chǔ)管理復(fù)雜程度取決于源語言本身：(1)允許的數(shù)據(jù)類型的多少(2)語言中是否允許動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)(3)標(biāo)識(shí)符的作用域的規(guī)則和結(jié)構(gòu)

段結(jié)構(gòu)

過程定義不嵌套，只允許過程遞歸調(diào)用分程序結(jié)構(gòu)*存儲(chǔ)空間通常被劃分為：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如圖8.1所示↓。圖8-1運(yùn)行時(shí)存儲(chǔ)空間的劃分

存儲(chǔ)空間分配的一個(gè)重要單元是過程的活動(dòng)記錄，它是一段連續(xù)的存儲(chǔ)區(qū)，用來存放過程的一次調(diào)用所需要的信息，包括：自變量（參數(shù)）空間；返回地址；用作局部數(shù)據(jù)的空間；用作局部臨時(shí)變量的空間。8.2靜態(tài)存儲(chǔ)分配如果在編譯時(shí)就能確定目標(biāo)程序運(yùn)行中所需要的全部數(shù)據(jù)空間的大小，則編譯時(shí)就能安排好目標(biāo)程序的全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址、存儲(chǔ)空間，這種分配方法即靜態(tài)存儲(chǔ)分配。早期的程序設(shè)計(jì)語言，如FORTRAN-77，不允許遞歸調(diào)用，每一種數(shù)據(jù)類型所需要的存儲(chǔ)空間的大小都是常量，采用的就是靜態(tài)存儲(chǔ)分配策略。8.3棧式存儲(chǔ)分配現(xiàn)代的程序設(shè)計(jì)語言都允許遞歸調(diào)用，具有可變類型數(shù)據(jù)結(jié)構(gòu)，必須采用動(dòng)態(tài)存儲(chǔ)分配策略。棧式存儲(chǔ)分配是一種動(dòng)態(tài)存儲(chǔ)分配策略，將整個(gè)存儲(chǔ)空間設(shè)計(jì)成一個(gè)棧，每當(dāng)調(diào)用一個(gè)過程時(shí)就將它的活動(dòng)記錄壓入棧中，在棧頂形成過程工作時(shí)的數(shù)據(jù)區(qū)，當(dāng)過程結(jié)束時(shí)再將其活動(dòng)記錄刪除。簡單棧式存儲(chǔ)分配對于沒有分程序結(jié)構(gòu)，過程定義不允許嵌套但允許過程遞歸調(diào)用的語言，可以采用一種簡單的棧式存儲(chǔ)分配策略。

C語言就是滿足上述特點(diǎn)的一種語言，其過程的活動(dòng)記錄一般采用如圖8-2所示的結(jié)構(gòu)。P169圖8.5

由上圖可知，過程的每一個(gè)局部變量或形參在活動(dòng)記錄中相對地址是確定的，因此可以知道程序運(yùn)行時(shí)，變量和形參在棧中的絕對地址是：

絕對地址=活動(dòng)記錄基地址SP+相對地址也就說，活動(dòng)記錄的一個(gè)重要功能就是，計(jì)算變量的地址?？紤]以下程序結(jié)構(gòu)：自習(xí)P169-170intx=2;voidp(int);Voidq(intn){…p(n);…}Voidp(intm){…if(m>1){q(m-1);x--;p(m-1);

…}…}Main(){p(x);}這段程序執(zhí)行時(shí)，存儲(chǔ)空間變化情況如圖8-3(a)(b)(c)所示。嵌套過程的棧式存儲(chǔ)分配允許嵌套過程的語言如Pascal，處理方法是在棧中增加一個(gè)嵌套層次顯示表（稱Display表），Display表用于記錄每一層活動(dòng)記錄的首地址，這樣，由一個(gè)非局部變量說明所在的靜態(tài)層數(shù)和相對于活動(dòng)記錄的相對地址就可以計(jì)算其絕對地址：

絕對地址=Display[靜態(tài)層數(shù)]+相對地址嵌套過程的棧式存儲(chǔ)分配步驟，即Display表的生成、作用；活動(dòng)記錄的填寫、刪除等內(nèi)容，請參考金成植主編，高教出版社出版。8.4堆式存儲(chǔ)分配如果一種程序設(shè)計(jì)語言允許數(shù)據(jù)對象能夠自由地分配和釋放，那么由于空間的使用不一定按照“先申請后釋放”的原則進(jìn)行，這時(shí)棧式存儲(chǔ)分配策略就不適用了，如C/C++語言。堆式存儲(chǔ)分配的基本思想是：一個(gè)程序開始執(zhí)行時(shí)有很大一塊存儲(chǔ)空間，運(yùn)行期間如果需要就從里面申請一塊存儲(chǔ)空間，使用完畢歸還。由于存儲(chǔ)空間的申請和釋放時(shí)間不一，在多次調(diào)用之后存儲(chǔ)空間可能變成如下形式：

其中各區(qū)域的長度不一定相等。此時(shí)系統(tǒng)必須記錄所有的使用情況，尤其是要記錄所有的空閑區(qū)以備后用。此外還應(yīng)該盡可能地把相連空閑區(qū)匯集成一個(gè)比較大的空閑區(qū)以免存儲(chǔ)區(qū)被分割成為許多難以合作的碎片。以下作簡要介紹。

堆式存儲(chǔ)分配最簡單的實(shí)現(xiàn)方法是按定長進(jìn)行分配。初始化時(shí)將堆存儲(chǔ)空間分成若干個(gè)長度相等的塊，按鄰塊的順序把這些塊連接成一個(gè)鏈表。每次申請空間時(shí)就從鏈表最前面的未分配結(jié)點(diǎn)開始分配，歸還時(shí)把結(jié)點(diǎn)插入鏈表并保證第一個(gè)未使用的結(jié)點(diǎn)之后沒有已分配的塊。用戶對于申請到的塊的使用是自由的，可以存放各種類型的數(shù)據(jù)。

定長塊管理實(shí)現(xiàn)起來比較方便，但是內(nèi)存的使用效率偏低，堆式存儲(chǔ)分配通常按變長塊進(jìn)行。按這種方法，初始化存儲(chǔ)區(qū)時(shí)對空間不作分段，每次申請時(shí)都從空閑區(qū)分出滿足要求的最小塊；歸還時(shí)，如果新歸還的塊能和現(xiàn)有的空閑塊合并就把它們合并成一塊。如果有若干個(gè)空閑塊滿足需要時(shí)，一般采用以3種分配策略：

首次分配法：即順序查看空閑塊，選取其中第一個(gè)滿足所需容量要求的空閑塊進(jìn)行分配。如果空閑塊很大，則按申請的大小進(jìn)行分割；如果不大就整塊分配出去，以免產(chǎn)生碎片。

最優(yōu)匹配法：將不小于所申請塊且容量最接近于申請塊的空閑塊分配出去。

最差匹配法：將不小于所申請塊且容量最大的空閑塊分配出去。8.5臨時(shí)變量的存儲(chǔ)分配臨時(shí)變量等于簡單變量，可以登記到符號(hào)表中，一般不用登記到符號(hào)表中。雖然在產(chǎn)生中間代碼時(shí)產(chǎn)生了大量的臨時(shí)變量，但是，由于臨時(shí)變量具有“定義一次、使用一次的特點(diǎn)”，若采用合適的分配算法，實(shí)際只占用少量的存儲(chǔ)空間。

一般的分配原則：如果兩個(gè)臨時(shí)變量的作用域不相交，則它們可以分配到同一個(gè)存儲(chǔ)單元中。一個(gè)臨時(shí)變量從它第一次被賦值的地方起至它最后一次被引用的地方止，這個(gè)區(qū)間的程序所能到達(dá)的全體四元式構(gòu)成其作用域。臨時(shí)變量存儲(chǔ)分配的實(shí)現(xiàn)：令臨時(shí)變量名均分配在局部數(shù)據(jù)區(qū)中，若某一單元已分配給某些臨時(shí)變量，則把這些名字的作用域（互不相交）作為單元的分配信息記錄下來。每當(dāng)要