運(yùn)行時存儲空間組織

第七章運(yùn)轉(zhuǎn)時存儲空間組織本章討論目的程序運(yùn)轉(zhuǎn)時的活動和運(yùn)轉(zhuǎn)時的存儲組織與管理本章要點(diǎn)：過程的活動與參數(shù)傳送 靜態(tài)存儲分配 簡單的棧式存儲分配嵌套過程言語的棧式實(shí)現(xiàn)堆式動態(tài)存儲分配

過程的活動與參數(shù)傳送定義和調(diào)用過程〔函數(shù)〕是程序文語的主要特征之一。過程是模塊程序設(shè)計(jì)的主要手段，同時也是節(jié)省程序代碼和擴(kuò)展言語才干的主要途徑。一個過程一旦定義后，就可以在別的地方調(diào)用它。調(diào)用與被調(diào)用(過程)兩者之間的信息往來經(jīng)過全局量或參數(shù)傳送。例如，下面的C言語程序：#include“stdio.h〞voidshowme(inta,intb,intc){printf(“a=%d,b=%d,c=%d\n〞,a,b,c);}main(?){intx=10,y=20,z=30;showme(z,y,x);}其中a、b、c稱為方式參數(shù)(簡稱形參)函數(shù)調(diào)用語句：showme(z,y,x)中的z、y、x那么稱為真實(shí)參數(shù)(簡稱實(shí)參)。實(shí)參甚至也可以是一個較復(fù)雜的表達(dá)式而不僅僅只是一個變量。實(shí)參和對應(yīng)的形參在性質(zhì)上應(yīng)相容不悖。過程的活動一個過程的活動是指該過程的一次執(zhí)行。過程的生存期是指從執(zhí)行該過程體第一步操作到最后一步操作之間的操作程序，包括執(zhí)行該過程時調(diào)用其他過程破費(fèi)的時間。方式參數(shù)提供了參數(shù)交換的手段，在過程調(diào)用時可以運(yùn)用不同的數(shù)據(jù)作為真實(shí)參數(shù)來交換方式參數(shù)，從而實(shí)現(xiàn)了同一個過程可以對不同的真實(shí)參數(shù)進(jìn)展一樣操作的功能。那么，如何把真實(shí)參數(shù)傳送給相應(yīng)的方式參數(shù)呢？程序文語中參數(shù)傳送的方式主要有傳值(callbyvalue)、傳地址(callbyreference)和傳名(callbyname)三種。參數(shù)的傳送1．傳值傳值是最簡單的參數(shù)傳送方法。所謂傳值，就是計(jì)算出真實(shí)參數(shù)的值然后把它傳給被調(diào)用過程相對應(yīng)的方式參數(shù)，詳細(xì)過程如下：(1)把方式參數(shù)當(dāng)作過程的部分變量處置，即在被調(diào)用過程中開辟方式參數(shù)的存儲空間(即方式單元)。(2)調(diào)用過程計(jì)算出真實(shí)參數(shù)的值，并將該值放入為方式單元開辟的空間中。(3)被調(diào)用過程執(zhí)行時就像運(yùn)用部分變量一樣運(yùn)用這些方式單元。傳值的一個重要特點(diǎn)是對方式參數(shù)的任何運(yùn)算都不影響調(diào)用過程真實(shí)參數(shù)的值，即參數(shù)傳送后真實(shí)參數(shù)與對應(yīng)的方式參數(shù)不再發(fā)生聯(lián)絡(luò)了。2．傳地址所謂傳地址，是指把真實(shí)參數(shù)的地址傳送給相應(yīng)的方式參數(shù)所對應(yīng)的方式單元。假照真實(shí)參數(shù)是一個變量，那么直接將該變量的地址傳給相應(yīng)的方式單元；假照真實(shí)參數(shù)是常數(shù)或表達(dá)式，那么先計(jì)算其值并存放在某一暫時單元中，然后將這個暫時單元的地址傳給相應(yīng)的方式單元。被調(diào)用過程執(zhí)行時，對方式參數(shù)的任何援用或賦值都被處置成對方式單元的間接訪問，即按方式單元中存放的地址轉(zhuǎn)到調(diào)用過程中去訪問真實(shí)參數(shù)。對方式參數(shù)的任何運(yùn)算實(shí)踐上都是對真實(shí)參數(shù)的運(yùn)算，而方式參數(shù)只不過起到輔助查找到真實(shí)參數(shù)的指針的作用。因此，當(dāng)被調(diào)用過程任務(wù)終了前往時，方式單元所指的真實(shí)參數(shù)單元就保管了運(yùn)算的結(jié)果。3．傳名傳名是高級言語ALGOL60所定義的一種特殊的參數(shù)傳送方式，其傳送參數(shù)的方法如下：(1)過程調(diào)用的作用相當(dāng)于把被調(diào)用過程的過程體復(fù)制到調(diào)用途(交換調(diào)用語句)，并將過程體中一切出現(xiàn)的方式參數(shù)在文字上交換成相應(yīng)的真實(shí)參數(shù)。這種文字上的交換稱為宏擴(kuò)展(MarcroExpansion)。(2)被調(diào)用過程中的部分名假設(shè)與過程調(diào)用的真實(shí)參數(shù)名發(fā)生沖突，那么在宏擴(kuò)展前對被調(diào)用過程中的這些部分名重新命名以防止重名沖突。(3)為表現(xiàn)真實(shí)參數(shù)的整體性，必要時在交換前把真實(shí)參數(shù)用括號括起來。傳名這種參數(shù)傳送方法因其操作過于復(fù)雜如今已很少采用。不同的參數(shù)傳送方法得到的結(jié)果不同，因此，如何選擇參數(shù)傳送的方法將影響言語的語義，這是編譯程序在處置參數(shù)傳送時應(yīng)引起注重的問題。運(yùn)轉(zhuǎn)時存儲器的劃分目的代碼靜態(tài)數(shù)據(jù)棧堆管理過程的活動，過程調(diào)用時相關(guān)信息存入棧中存放動態(tài)數(shù)據(jù)圖7-1靜態(tài)存儲分配假設(shè)在編譯時就可以確定一個程序在運(yùn)轉(zhuǎn)時所需的存儲空間大小，那么在編譯時就可以安排好目的程序運(yùn)轉(zhuǎn)時的全部數(shù)據(jù)空間，并能確定每個數(shù)據(jù)項(xiàng)的單元地址，存儲空間的這種分配方法叫做靜態(tài)分配。FORTRAN言語的特點(diǎn)：不允許過程有遞歸性；每個數(shù)據(jù)名所需的存儲空間大小都是常量(即不允許含可變體積的數(shù)據(jù)，如可變數(shù)組)；一切數(shù)據(jù)名的性質(zhì)是完全確定的(不允許出如今運(yùn)轉(zhuǎn)時再動態(tài)確定其性質(zhì)的名字)。這些特點(diǎn)確保整個程序所需數(shù)據(jù)空間的總量在編譯時是完全確定的，從而每個數(shù)據(jù)名的地址就可靜態(tài)地進(jìn)展分配。靜態(tài)存儲分配是一種最簡單的存儲管理。普通而言，適于靜態(tài)存儲分配的言語必需滿足以下條件：(1)數(shù)組的上下界必需是常數(shù)；(2)過程調(diào)用不允許遞歸；(3)不允許采用動態(tài)的數(shù)據(jù)構(gòu)造(即在程序運(yùn)轉(zhuǎn)過程中懇求和釋放的數(shù)據(jù)構(gòu)造)。在編譯過程中，給程序中的變量或數(shù)組分配存儲單元的普通做法是：為每一個變量(或數(shù)組)確定一個有序的整數(shù)對；其中，第一個整數(shù)用來指示數(shù)據(jù)區(qū)(部分?jǐn)?shù)據(jù)區(qū)或公用區(qū))的編號，第二個整數(shù)那么用來指明該變量(或數(shù)組)所對應(yīng)的存儲起始單元相對于其所在數(shù)據(jù)區(qū)起點(diǎn)的位移(即相對于數(shù)據(jù)區(qū)起點(diǎn)的地址)；并將這一對整數(shù)填入符號表相應(yīng)登記項(xiàng)的信息欄中。至于各數(shù)據(jù)區(qū)的起始地址在編譯時可暫不確定，待各程序段全部編譯完成之后，再由銜接裝配程序最終確定，并將各程序段的目的代碼組裝成一個完好的目的程序。一個FORTRAN程序段的部分?jǐn)?shù)據(jù)區(qū)可由圖7-2所示的工程組成。其中，隱參數(shù)是指過程調(diào)用時的銜接信息(不在源程序中明顯出現(xiàn))，如調(diào)用時的前往地址、調(diào)用時存放器的維護(hù)等；方式單元用來存放過程調(diào)用時形參與實(shí)參結(jié)合的實(shí)參地址或值。一個FORTRAN程序段的部分?jǐn)?shù)據(jù)區(qū)保管調(diào)用此程序段時的前往地址保管調(diào)用段留在存放器中的相關(guān)信息存放實(shí)參的地址或值圖7-2簡單的棧式存儲分配我們首先思索一種簡單程序文語的實(shí)現(xiàn)，這種言語沒有分程序構(gòu)造，過程定義不允許嵌套，但允許過程的遞歸調(diào)用，允許過程含有可變數(shù)組。例如，C言語除不允許含有可變數(shù)組外，就是這樣一種言語。C言語的程序構(gòu)造如下：全局?jǐn)?shù)聽闡明main(?){main中的數(shù)聽闡明}voidR(?){R中的數(shù)聽闡明}voidQ(){Q中的數(shù)聽闡明}例如，下面計(jì)算n！的C言語程序就是一個遞歸調(diào)用的程序，它的執(zhí)行過程可以用棧來實(shí)現(xiàn)。#include“stdio.h〞longfactorial(intn){if(n>1)return(n*factorial(n?1));elsereturn(1);}main(?){intnum;do{scanf(“%d〞,&num);if(num>=0&&num<15)printf(“%d\n〞,factorial(num));elseprintf(“error!\n〞);}while(num>=0);}運(yùn)用棧式存儲分配法意味著程序運(yùn)轉(zhuǎn)時，每當(dāng)進(jìn)入一個過程(或函數(shù))就有一個相應(yīng)的活動記錄累筑于棧頂，此記錄含有銜接數(shù)據(jù)、方式單元、部分變量、部分?jǐn)?shù)組的內(nèi)情向量和暫時任務(wù)單元等；在進(jìn)入過程和執(zhí)行過程的可執(zhí)行語句之前，再把部分?jǐn)?shù)組所需空間累筑于棧頂，從而構(gòu)成過程任務(wù)時的完好數(shù)據(jù)區(qū)。棧式存儲分配與活動記錄留意，每個過程的活動記錄的體積在編譯時可以靜態(tài)地確定。但由于允許含有可變數(shù)組，所以數(shù)組的大小只需在運(yùn)轉(zhuǎn)時才干知道。因數(shù)組區(qū)的大小不能預(yù)先獲知，為了擴(kuò)展方便，所以只能將數(shù)組區(qū)累筑于活動記錄之上的當(dāng)前棧頂。當(dāng)一個過程任務(wù)終了前往時，它在棧頂?shù)臄?shù)據(jù)區(qū)(包括活動記錄和數(shù)組區(qū))也隨即不復(fù)存在。對C言語來說，由于其不含可變數(shù)組，因此它的活動記錄本身包含了部分?jǐn)?shù)組的空間。圖7–3和圖7–4分別給出了C言語和含可變數(shù)組的某簡單言語程序運(yùn)轉(zhuǎn)時的數(shù)據(jù)空間構(gòu)造，即顯示了主程序在調(diào)用了過程Q，Q又調(diào)用了過程R，且在R投入運(yùn)轉(zhuǎn)后的存儲構(gòu)造。

圖7–3C言語程序的存儲組織SP指示器總是指向執(zhí)行過程活動記錄的起點(diǎn)，而TOP指示器那么一直指向(已占用)棧頂單元。當(dāng)進(jìn)入一個過程時，TOP指向?yàn)榇诉^程創(chuàng)建的活動記錄的頂端；在分配數(shù)組區(qū)之后(假設(shè)有的話)，TOP又改為指向數(shù)組區(qū)(從而是該過程整個數(shù)據(jù)區(qū))的頂端。圖7–4含可變數(shù)組程序的存儲組織C的活動記錄含有以下幾個區(qū)段(如圖7–5所示)：(1)銜接數(shù)據(jù)(兩項(xiàng))：老SP值(即前一活動記錄的起始地址)和前往地址；(2)參數(shù)個數(shù)；(3)方式單元(存放真實(shí)參數(shù)的值或地址)；(4)過程的部分變量(簡單變量)、數(shù)組的內(nèi)情向量和暫時任務(wù)單元。圖7–5C過程的活動記錄C言語不允許過程(函數(shù))嵌套，也即不允許一個過程的定義出如今另一個過程的定義之內(nèi)。因此，C言語的非部分變量僅能出如今源程序頭，非部分變量可采用靜態(tài)存儲分配并在編譯時確定它們的地址。由圖7–5可知，過程的每一部分變量或形參在活動記錄中的位置都是確定的；也就是說，這些變量或形參所分配的存儲單元其地址都是相對于活動記錄的基址SP的。因此，變量和形參運(yùn)轉(zhuǎn)時在棧上的絕對地址是：絕對地址=活動記錄基址(SP)+相對地址對當(dāng)前正在執(zhí)行(即活動)的過程，其任何部分變量或形參X的援用均可表示為變址訪問X[SP]。此處X代表X相對于活動記錄基址的偏移量，這個偏移量(即相對數(shù))在編譯時可完全確定下來。過程的部分?jǐn)?shù)組的內(nèi)情向量的相對地址在編譯時也同樣可完全確定下來，一旦數(shù)據(jù)空間在過程里獲得分配后，對數(shù)組元素的援用也就容易用變址的方式進(jìn)展訪問。過程的執(zhí)行1．過程調(diào)用過程調(diào)用的中間代碼序列為：parT1parT2

parTncallP,n由于此時TOP是指向被調(diào)用過程P之前的棧頂，而P的方式單元和活動記錄起點(diǎn)之間的間隔是確定的(等于3，參見圖7–5)，因此由調(diào)用過程給將要調(diào)用的過程P的活動記錄(正在構(gòu)成中)的方式單元傳送實(shí)參值或?qū)崊⒌刂罚疵總€parTi(i=1,2,…,n)可直接翻譯成如下指令：(i+3)[TOP]=Ti /*傳送參數(shù)值*/或(i+3)[TOP]=addr[Ti]/*傳送參數(shù)地址*/而四元式callP,n那么翻譯成：1[TOP]=SP/*維護(hù)現(xiàn)行SP*/3[TOP]=n /*傳送參數(shù)個數(shù)*/JSRP /*轉(zhuǎn)子指令，轉(zhuǎn)向P過程的第一條指令*/過程P調(diào)用之前，先構(gòu)造出P的活動記錄部分內(nèi)容，見圖7–6所示。圖7–6過程P調(diào)用前先構(gòu)造P的活動記錄部分內(nèi)容2．過程進(jìn)入轉(zhuǎn)入過程P后，首先要做的任務(wù)是定義新活動記錄的SP，維護(hù)前往地址和定義新活動記錄的TOP值，即執(zhí)行下述指令：SP=TOP+1/*定義新SP*/1[SP]=前往地址/*維護(hù)前往地址*/TOP=TOP+L/*定義新TOP*/其中，L是過程P的活動記錄所需的單元數(shù)，這個數(shù)在編譯時可靜態(tài)地計(jì)算出來。對含可變數(shù)組(非C言語)的情況來說，由于過程可含可變數(shù)組且一切數(shù)組都分配在活動記錄的頂上，所以緊接上述指令之后應(yīng)是對數(shù)組進(jìn)展存儲分配的指令(假設(shè)含有部分?jǐn)?shù)組)，這些指令是在翻譯數(shù)組闡明時產(chǎn)生的。對每個數(shù)組闡明，相應(yīng)的目的指令組將做以下幾件任務(wù)：(1)計(jì)算各維的上、下限；(2)調(diào)用數(shù)組空間分配子程序，其參數(shù)是各維的上、下限和內(nèi)情向量單元首地址。數(shù)組空間分配子程序計(jì)算并填好內(nèi)情向量的一切信息，然后在TOP所指的位置之上留出數(shù)組所需的空間，并將TOP調(diào)整為指向數(shù)組區(qū)的頂端。?進(jìn)入過程P后所做的任務(wù)如圖7–7所示。以后，在過程段執(zhí)行語句的任務(wù)過程中，凡援用方式參數(shù)、部分變量或數(shù)組元素都將以SP為基址進(jìn)展相對訪問。圖7–7進(jìn)入過程P后所做的任務(wù)表示3．過程前往C言語以及其它一些類似的言語含有return(E)方式的前往語句，其中E為表達(dá)式。假定E值已計(jì)算出來并存放在某暫時單元T中，那么此時即可將T值傳送到某個特定的存放器中(調(diào)用過程將從這個特定的存放器中獲得被調(diào)用過程P的結(jié)果)。剩下的任務(wù)就是恢復(fù)SP和TOP為進(jìn)入過程P之前的原值(即指向調(diào)用過程的活動記錄及任務(wù)空間)，并按前往地址實(shí)行無條件轉(zhuǎn)移，即執(zhí)行下述指令序列：TOP=SP–1 /*恢復(fù)調(diào)用過程的TOP值*/SP=0[SP] /*恢復(fù)調(diào)用過程的SP值*/X=2[TOP] /*將前往地址送X*/UJ0[X] /*無條件轉(zhuǎn)移，即按X的地址前往到調(diào)用過程*/過程P的前往表示如圖7–8所示。圖7–8過程P的前往表示嵌套過程言語的棧式實(shí)現(xiàn)在簡單程序文語實(shí)現(xiàn)中是允許過程的遞歸調(diào)用的，并且過程中可含有可變數(shù)組。如今，我們再加上一種功能，即允許過程的嵌套性。在討論中，經(jīng)常要用到過程定義的“嵌套層次〞(簡稱層數(shù))這個概念。我們一直假定主程序的層數(shù)為0，因此主程序稱為第0層過程。假設(shè)過程Q是在層數(shù)為i的過程P內(nèi)定義的，并且P是包圍Q的最小過程，那么Q的層數(shù)就為i+1。當(dāng)編譯程序處置過程闡明時，過程的層數(shù)將作為過程名的一個重要屬性登記在符號表中。嵌套層次顯示表(DISPLAY)和活動記錄由于過程定義是嵌套的，因此一個過程可以援用包圍它的任一外層過程所定義的變量或數(shù)組。也就是說，運(yùn)轉(zhuǎn)時，一個過程Q能夠援用它的任一外層過程P的最新活動記錄中的某些數(shù)據(jù)。因此，過程Q運(yùn)轉(zhuǎn)時必需知道它的一切外層的最新活動記錄的地址。由于允許遞歸和可變數(shù)組的存在，過程的活動記錄位置(即使是相對位置)也往往是變化的，因此必需設(shè)法跟蹤每個外層過程的最新活動記錄的位置。采用嵌套層次顯示表DISPLAY，其優(yōu)點(diǎn)是訪問非部分量的速度較快。每進(jìn)入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表DISPLAY。假定如今進(jìn)入的過程層數(shù)為i，那么它的DISPLAY表含有i+1個單元。此表本身是一個小棧，自頂而下每個單元依次存放著現(xiàn)行層、直接外層……直至最外層(第0層，即主程序?qū)?的每一層的最新活動記錄的起始地址。例如，令過程R的外層為Q，Q的外層為主程序P，那么過程R運(yùn)轉(zhuǎn)時的DISPLAY表內(nèi)容如表7-1所示。表7-1DISPLAY表2R的現(xiàn)行活動記錄的始址(SP的現(xiàn)行值)1Q的最新活動記錄的始址0P的活動記錄的始址由于過程的層數(shù)可靜態(tài)確定，因此每個過程的DISPLAY表的體積在編譯時即可知道。為了便于組織存儲區(qū)和簡化處置手續(xù)，我們把DISPLAY作為活動記錄的一部分置于方式單元的上端，如圖7–9所示。由于每個過程的方式單元數(shù)目在編譯時是知道的，因此DISPLAY的相對地址d(相對于活動記錄的起點(diǎn))在編譯時也是完全確定的。被調(diào)用過程為了建立本人的DISPLAY，就必需知道它的直接外層過程的DISPLAY，這意味著必需把直接外層的DISPLAY地址作為銜接數(shù)據(jù)之一(稱為“全局DISPLAY地址〞)傳送給被調(diào)用過程。于是，此時的銜接數(shù)據(jù)包含老SP值、前往地址和全局DISPLAY地址這三項(xiàng)內(nèi)容。整個活動記錄的構(gòu)造如圖7–9所示。圖7–9活動記錄構(gòu)造存取鏈(也稱靜態(tài)鏈)方法。存取鏈方法引入一個稱為存取鏈的指針，該指針作為活動記錄的一項(xiàng)指向直接外層的最新活動記錄的地址，這就意味著在運(yùn)轉(zhuǎn)時棧中的每個數(shù)據(jù)區(qū)(活動記錄)之間又拉出一條鏈，這個鏈稱為存取鏈。留意，運(yùn)轉(zhuǎn)時棧中數(shù)據(jù)區(qū)之間原先就存在一條鏈，即每個活動記錄中所保管的老SP值這一項(xiàng)，它是指向調(diào)用該過程(子過程)的那個過程(父過程)的最新活動記錄的起點(diǎn)，由此向前構(gòu)成了一條SP鏈。為了區(qū)別于存取鏈，稱SP鏈為控制鏈(也稱動態(tài)鏈)，它記錄了在運(yùn)轉(zhuǎn)中過程之間相互調(diào)用的關(guān)系。留意，控制鏈?zhǔn)莿討B(tài)的，而存取鏈?zhǔn)庆o態(tài)的?？刂奇溣涗浟水?dāng)前時辰程序中各過程相互調(diào)用的情況；而存取鏈那么一直記錄著程序靜態(tài)定義時該過程一切的直接外層(嵌套過程規(guī)定，內(nèi)層過程只允許調(diào)用其靜態(tài)定義時的外層過程闡明的變量和數(shù)組)；因此，存取鏈指出了一個過程的當(dāng)前活動記錄指向其直接定義的外層過程直至最外層的最新活動記錄的起點(diǎn)。具有存取鏈的活動記錄構(gòu)造如圖7–10所示。圖7–10具有存取鏈的活動記錄構(gòu)造假定過程的嵌套關(guān)系：程序中每個過程的靜態(tài)構(gòu)造(嵌套層次)是確定的，如嵌套深度為2的過程R援用了非部分量a和b，其嵌套深度分別為0和1。從R的活動記錄開場，分別沿著2???0?=?2和2?1=1個存取鏈向前查找，那么可找到包含這兩個非部分量的活動記錄。上述過程P調(diào)用S以及S調(diào)用Q運(yùn)轉(zhuǎn)時棧的變化過程如圖7–11(a)、(b)所示。由圖7–11可以看出，指針SP總是指向當(dāng)前正在執(zhí)行過程的活動記錄起點(diǎn)，控制鏈(老SP)那么指向調(diào)用運(yùn)轉(zhuǎn)過程的父過程的活動記錄起點(diǎn)。因此，當(dāng)運(yùn)轉(zhuǎn)過程調(diào)用終了前往時，利用控制鏈老SP值可以得到調(diào)用前原父過程活動記錄的起點(diǎn)。從程序的靜態(tài)構(gòu)造來看，P是S和Q的靜態(tài)直接外層，所以，S和Q活動記錄中的存取鏈均指向其直接外層P的活動記錄起點(diǎn)。圖7–11過程調(diào)用時運(yùn)轉(zhuǎn)棧的變化例1:某程序的構(gòu)造如圖7–12所示，其中A、B、C為過程名，請分別畫出過程C調(diào)用A前后的棧頂活動記錄。圖7–12例中的程序構(gòu)造表示解：過程C調(diào)用A前后的棧頂活動記錄表示如圖7–13所示。由圖7–13可知，當(dāng)過程C執(zhí)行時，它可運(yùn)用主程序、A、B和C過程所闡明的變量，且其外層嵌套的過程活動記錄始址由DISPLAY表指出。當(dāng)C調(diào)用A而使過程A執(zhí)行時，我們看到此時的DISPLAY表已變?yōu)閮身?xiàng)，即主程序和A過程本身；也即此時A只可運(yùn)用主程序和A過程所闡明的變量。圖7–13例1的運(yùn)轉(zhuǎn)棧與活動記錄表示例2：在下面的PASCAL程序中，曾經(jīng)第二次(遞歸地)進(jìn)入了f，請給出第三次進(jìn)入f后的運(yùn)轉(zhuǎn)棧及DISPLAY的表示圖PROGRAMtest(input,output);VARK:integer;FUNCTIONf(n:integer):integer;BEGINIFn<=0THENf:=1解：第三次進(jìn)入f后的運(yùn)轉(zhuǎn)棧及DISPLAY的表示圖如圖7–14所示。由于靜態(tài)嵌套層次只需兩層，故每一次遞歸調(diào)用產(chǎn)生的DISPLAY表只需兩項(xiàng)，一項(xiàng)為哪一項(xiàng)test的SP(即0)，另一項(xiàng)為哪一項(xiàng)當(dāng)前活動記錄的SPi(i=1,2,3)。圖7–14例2的運(yùn)轉(zhuǎn)棧及DISPLAY表示圖堆式動態(tài)存儲分配假設(shè)一種程序文語允許數(shù)據(jù)對象可以自在地分配和釋放，或者不僅有過程而且有進(jìn)程(process)這樣的程序構(gòu)造，那么由于空間的運(yùn)用不一定遵照“先懇求后釋放〞的原那么，那么棧式存儲分配就不適用了。在這種情況下，通常運(yùn)用一種稱之為堆的動態(tài)存儲分配方案。假定程序運(yùn)轉(zhuǎn)時有一個大的存儲空間，需求時就從這個空間中借用一塊，不用時再退還給它。由于借、還的時間先后不一，因此經(jīng)過一段時間的運(yùn)轉(zhuǎn)后，這個大空間就必然被分割成如圖7–15所示的許多小塊，這些塊有些正在運(yùn)用，有些那么是空閑的(未被運(yùn)用)。圖7–15堆式存儲分配表示對于堆式存儲分配來說，需求處理兩個問題：一是堆空間的分配，即當(dāng)運(yùn)轉(zhuǎn)程序需求一塊空間時應(yīng)分配哪一塊給它；另一個問題是分配空間的回收，由于前往堆的不用空間是按恣意次序進(jìn)展的，所以需求研討專門的回收分配戰(zhàn)略。在許多言語中都有顯式的堆空間分配和回收語句或函數(shù)，如PASCAL言語中的new和dispose、C言語中的malloc和free以及C++言語中的new和delete。堆式存儲管理的方法的簡單討論當(dāng)運(yùn)轉(zhuǎn)程序要求一塊體積為N的存儲空間時應(yīng)如何分配？從實(shí)際上講，這時應(yīng)從比N稍大一些的空閑塊中取出N個單元予以分配，這種做法的目的是堅(jiān)持較大的空閑塊以備未來之需。但這種方法實(shí)現(xiàn)起來難度較大，實(shí)踐中采用的方法是：掃描空閑塊鏈并在初次遇到的比N大的空閑塊中取出N個單元進(jìn)展分配。假設(shè)找不到一塊比N大的空閑塊，但一切空閑塊的總和卻比N大，這時就需求用某種方法使這些空閑塊拼接在一同，構(gòu)成一個可分配的延續(xù)空間。假設(shè)一切空閑塊的總和都不及N大，那么需求采用更復(fù)雜的方法，如廢品回收技術(shù)(即尋覓那些運(yùn)轉(zhuǎn)程序已不運(yùn)用但仍未釋放的存儲塊或運(yùn)轉(zhuǎn)程序目前很少運(yùn)用的存儲塊)，把這些存儲塊回收后再重新分配。

可以采用多種戰(zhàn)略進(jìn)展堆式動態(tài)存儲管理。運(yùn)用可利用空間表進(jìn)展動態(tài)分配的方法可利用空間表是指將一切空閑塊用一張表記錄下來，表的構(gòu)造可以是目錄表，也可以是鏈表，其構(gòu)造分別如圖7–16(b)、(c)所示。圖7–16內(nèi)存形狀和可利用空間表運(yùn)用可利用空間表進(jìn)展動態(tài)存儲分配的方法又可分為如下兩種：(1)定長塊的管理。最簡單的堆式存儲管理方法是采用定長塊的管理方法，即將堆存儲空間在初始化時就劃分成大小一樣的假設(shè)干塊，將各個塊經(jīng)過鏈表鏈接起來構(gòu)成一個單向線性鏈表。由于各塊大小一樣，故分配時無需查找，只需將頭指針?biāo)傅牡?/p>