運行時存儲空間組織課件

第七章運行時存儲空間組織本章討論目標程序運行時的活動和運行時的存儲組織與管理本章要點：

過程的活動與參數(shù)傳遞 靜態(tài)存儲分配

簡單的棧式存儲分配嵌套過程語言的棧式實現(xiàn)堆式動態(tài)存儲分配

第七章運行時存儲空間組織本章討論目標程序運行時的活動和運行1

過程的活動與參數(shù)傳遞定義和調(diào)用過程（函數(shù)）是程序語言的主要特征之一。過程是模塊程序設計的主要手段，同時也是節(jié)省程序代碼和擴充語言能力的主要途徑。一個過程一旦定義后，就可以在別的地方調(diào)用它。調(diào)用與被調(diào)用(過程)兩者之間的信息往來通過全局量或參數(shù)傳遞。

過程的活動與參數(shù)傳遞定義和調(diào)用過程（2例如，下面的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);}例如，下面的C語言程序：3其中a、b、c稱為形式參數(shù)(簡稱形參)函數(shù)調(diào)用語句：showme(z,y,x)中的z、y、x則稱為實在參數(shù)(簡稱實參)。實參甚至也可以是一個較復雜的表達式而不僅僅只是一個變量。實參和對應的形參在性質(zhì)上應相容不悖。運行時存儲空間組織4過程的活動一個過程的活動是指該過程的一次執(zhí)行。過程的生存期是指從執(zhí)行該過程體第一步操作到最后一步操作之間的操作程序，包括執(zhí)行該過程時調(diào)用其他過程花費的時間。過程的活動一個過程的活動是指該過程的一次執(zhí)行。5形式參數(shù)提供了參數(shù)替換的手段，在過程調(diào)用時可以使用不同的數(shù)據(jù)作為實在參數(shù)來替換形式參數(shù)，從而實現(xiàn)了同一個過程可以對不同的實在參數(shù)進行相同操作的功能。那么，如何把實在參數(shù)傳遞給相應的形式參數(shù)呢？程序語言中參數(shù)傳遞的方式主要有傳值(callbyvalue)、傳地址(callbyreference)和傳名(callbyname)三種。參數(shù)的傳遞形式參數(shù)提供了參數(shù)替換的手段，在過程調(diào)61．傳值傳值是最簡單的參數(shù)傳遞方法。所謂傳值，就是計算出實在參數(shù)的值然后把它傳給被調(diào)用過程相對應的形式參數(shù)，具體過程如下：(1)把形式參數(shù)當作過程的局部變量處理，即在被調(diào)用過程中開辟形式參數(shù)的存儲空間(即形式單元)。(2)調(diào)用過程計算出實在參數(shù)的值，并將該值放入為形式單元開辟的空間中。1．傳值7(3)被調(diào)用過程執(zhí)行時就像使用局部變量一樣使用這些形式單元。傳值的一個重要特點是對形式參數(shù)的任何運算都不影響調(diào)用過程實在參數(shù)的值，即參數(shù)傳遞后實在參數(shù)與對應的形式參數(shù)不再發(fā)生聯(lián)系了。(3)被調(diào)用過程執(zhí)行時就像使用局部變量一樣82．傳地址所謂傳地址，是指把實在參數(shù)的地址傳遞給相應的形式參數(shù)所對應的形式單元。如果實在參數(shù)是一個變量，則直接將該變量的地址傳給相應的形式單元；如果實在參數(shù)是常數(shù)或表達式，則先計算其值并存放在某一臨時單元中，然后將這個臨時單元的地址傳給相應的形式單元。2．傳地址9被調(diào)用過程執(zhí)行時，對形式參數(shù)的任何引用或賦值都被處理成對形式單元的間接訪問，即按形式單元中存放的地址轉(zhuǎn)到調(diào)用過程中去訪問實在參數(shù)。對形式參數(shù)的任何運算實際上都是對實在參數(shù)的運算，而形式參數(shù)只不過起到輔助查找到實在參數(shù)的指針的作用。因此，當被調(diào)用過程工作完畢返回時，形式單元所指的實在參數(shù)單元就保留了運算的結(jié)果。被調(diào)用過程執(zhí)行時，對形式參數(shù)的任何引用或103．傳名傳名是高級語言ALGOL60所定義的一種特殊的參數(shù)傳遞方式，其傳遞參數(shù)的方法如下：(1)過程調(diào)用的作用相當于把被調(diào)用過程的過程體復制到調(diào)用處(替換調(diào)用語句)，并將過程體中所有出現(xiàn)的形式參數(shù)在文字上替換成相應的實在參數(shù)。這種文字上的替換稱為宏擴展(MarcroExpansion)。3．傳名11(2)被調(diào)用過程中的局部名如果與過程調(diào)用的實在參數(shù)名發(fā)生沖突，則在宏擴展前對被調(diào)用過程中的這些局部名重新命名以避免重名沖突。(3)為表現(xiàn)實在參數(shù)的整體性，必要時在替換前把實在參數(shù)用括號括起來。傳名這種參數(shù)傳遞方法因其操作過于復雜現(xiàn)在已很少采用。不同的參數(shù)傳遞方法得到的結(jié)果不同，因此，如何選擇參數(shù)傳遞的方法將影響語言的語義，這是編譯程序在處理參數(shù)傳遞時應引起重視的問題。(2)被調(diào)用過程中的局部名如果與過程調(diào)用的實12運行時存儲器的劃分目標代碼靜態(tài)數(shù)據(jù)棧堆管理過程的活動，過程調(diào)用時相關(guān)信息存入棧中存放動態(tài)數(shù)據(jù)圖7-1運行時存儲器的劃分目標代碼靜態(tài)數(shù)據(jù)棧堆管理過程的活動，過程調(diào)13靜態(tài)存儲分配如果在編譯時就能夠確定一個程序在運行時所需的存儲空間大小，則在編譯時就能夠安排好目標程序運行時的全部數(shù)據(jù)空間，并能確定每個數(shù)據(jù)項的單元地址，存儲空間的這種分配方法叫做靜態(tài)分配。靜態(tài)存儲分配如果在編譯時就能夠確定一14FORTRAN語言的特點：不允許過程有遞歸性；每個數(shù)據(jù)名所需的存儲空間大小都是常量(即不允許含可變體積的數(shù)據(jù)，如可變數(shù)組)；所有數(shù)據(jù)名的性質(zhì)是完全確定的(不允許出現(xiàn)在運行時再動態(tài)確定其性質(zhì)的名字)。這些特點確保整個程序所需數(shù)據(jù)空間的總量在編譯時是完全確定的，從而每個數(shù)據(jù)名的地址就可靜態(tài)地進行分配。FORTRAN語言的特點：15靜態(tài)存儲分配是一種最簡單的存儲管理。一般而言，適于靜態(tài)存儲分配的語言必須滿足以下條件：(1)數(shù)組的上下界必須是常數(shù)；(2)過程調(diào)用不允許遞歸；(3)不允許采用動態(tài)的數(shù)據(jù)結(jié)構(gòu)(即在程序運行過程中申請和釋放的數(shù)據(jù)結(jié)構(gòu))。靜態(tài)存儲分配是一種最簡單的存儲管理。一般而言，適于靜態(tài)存儲分16在編譯過程中，給程序中的變量或數(shù)組分配存儲單元的一般做法是：為每一個變量(或數(shù)組)確定一個有序的整數(shù)對；其中，第一個整數(shù)用來指示數(shù)據(jù)區(qū)(局部數(shù)據(jù)區(qū)或公用區(qū))的編號，第二個整數(shù)則用來指明該變量(或數(shù)組)所對應的存儲起始單元相對于其所在數(shù)據(jù)區(qū)起點的位移(即相對于數(shù)據(jù)區(qū)起點的地址)；并將這一對整數(shù)填入符號表相應登記項的信息欄中。至于各數(shù)據(jù)區(qū)的起始地址在編譯時可暫不確定，待各程序段全部編譯完成之后，再由連接裝配程序最終確定，并將各程序段的目標代碼組裝成一個完整的目標程序。在編譯過程中，給程序中的變量或數(shù)組分配17一個FORTRAN程序段的局部數(shù)據(jù)區(qū)可由圖7-2所示的項目組成。其中，隱參數(shù)是指過程調(diào)用時的連接信息(不在源程序中明顯出現(xiàn))，如調(diào)用時的返回地址、調(diào)用時寄存器的保護等；形式單元用來存放過程調(diào)用時形參與實參結(jié)合的實參地址或值。一個FORTRAN程序段的局部數(shù)據(jù)區(qū)可18一個FORTRAN程序段的局部數(shù)據(jù)區(qū)保存調(diào)用此程序段時的返回地址保存調(diào)用段留在寄存器中的相關(guān)信息存放實參的地址或值圖7-2一個FORTRAN程序段的局部數(shù)據(jù)區(qū)保存調(diào)用此程序段時的返回19簡單的棧式存儲分配我們首先考慮一種簡單程序語言的實現(xiàn)，這種語言沒有分程序結(jié)構(gòu)，過程定義不允許嵌套，但允許過程的遞歸調(diào)用，允許過程含有可變數(shù)組。例如，C語言除不允許含有可變數(shù)組外，就是這樣一種語言。C語言的程序結(jié)構(gòu)如下：簡單的棧式存儲分配我們首先考慮一種簡單程序20全局數(shù)據(jù)說明main(?){main中的數(shù)據(jù)說明}voidR(?){R中的數(shù)據(jù)說明}voidQ(){Q中的數(shù)據(jù)說明}全局數(shù)據(jù)說明21例如，下面計算n！的C語言程序就是一個遞歸調(diào)用的程序，它的執(zhí)行過程可以用棧來實現(xiàn)。#include“stdio.h”longfactorial(intn){if(n>1)return(n*factorial(n?1));elsereturn(1);}例如，下面計算n！的C語言程序就是一個遞歸調(diào)用的程序，它的執(zhí)22main(?){intnum;do{scanf(“%d”,&num);if(num>=0&&num<15)printf(“%d\n”,factorial(num));elseprintf(“error!\n”);}while(num>=0);}main(?)23使用棧式存儲分配法意味著程序運行時，每當進入一個過程(或函數(shù))就有一個相應的活動記錄累筑于棧頂，此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時工作單元等；在進入過程和執(zhí)行過程的可執(zhí)行語句之前，再把局部數(shù)組所需空間累筑于棧頂，從而形成過程工作時的完整數(shù)據(jù)區(qū)。棧式存儲分配與活動記錄使用棧式存儲分配法意味著程序運行時，每當進24注意，每個過程的活動記錄的體積在編譯時可以靜態(tài)地確定。但由于允許含有可變數(shù)組，所以數(shù)組的大小只有在運行時才能知道。因數(shù)組區(qū)的大小不能預先獲知，為了擴充方便，所以只能將數(shù)組區(qū)累筑于活動記錄之上的當前棧頂。當一個過程工作完畢返回時，它在棧頂?shù)臄?shù)據(jù)區(qū)(包括活動記錄和數(shù)組區(qū))也隨即不復存在。注意，每個過程的活動記錄的體積在編譯時可以25對C語言來說，由于其不含可變數(shù)組，因而它的活動記錄本身包含了局部數(shù)組的空間。圖7–3和圖7–4分別給出了C語言和含可變數(shù)組的某簡單語言程序運行時的數(shù)據(jù)空間結(jié)構(gòu)，即顯示了主程序在調(diào)用了過程Q，Q又調(diào)用了過程R，且在R投入運行后的存儲結(jié)構(gòu)。

對C語言來說，由于其不含可變數(shù)組，因而26圖7–3C語言程序的存儲組織SP指示器總是指向執(zhí)行過程活動記錄的起點，而TOP指示器則始終指向(已占用)棧頂單元。當進入一個過程時，TOP指向為此過程創(chuàng)建的活動記錄的頂端；在分配數(shù)組區(qū)之后(如果有的話)，TOP又改為指向數(shù)組區(qū)(從而是該過程整個數(shù)據(jù)區(qū))的頂端。圖7–3C語言程序的存儲組織SP指示器總是指向執(zhí)行過27圖7–4含可變數(shù)組程序的存儲組織圖7–4含可變數(shù)組程序的存儲組織28C的活動記錄含有以下幾個區(qū)段(如圖7–5所示)：(1)連接數(shù)據(jù)(兩項)：老SP值(即前一活動記錄的起始地址)和返回地址；(2)參數(shù)個數(shù)；(3)形式單元(存放實在參數(shù)的值或地址)；(4)過程的局部變量(簡單變量)、數(shù)組的內(nèi)情向量和臨時工作單元。C的活動記錄含有以下幾個區(qū)段(如圖7–5所示)：29圖7–5C過程的活動記錄圖7–5C過程的活動記錄30

C語言不允許過程(函數(shù))嵌套，也即不允許一個過程的定義出現(xiàn)在另一個過程的定義之內(nèi)。因此，C語言的非局部變量僅能出現(xiàn)在源程序頭，非局部變量可采用靜態(tài)存儲分配并在編譯時確定它們的地址。由圖7–5可知，過程的每一局部變量或形參在活動記錄中的位置都是確定的；也就是說，這些變量或形參所分配的存儲單元其地址都是相對于活動記錄的基址SP的。因此，變量和形參運行時在棧上的絕對地址是：絕對地址=活動記錄基址(SP)+相對地址C語言不允許過程(函數(shù))嵌套，也即不允許一31對當前正在執(zhí)行(即活動)的過程，其任何局部變量或形參X的引用均可表示為變址訪問X[SP]。此處X代表X相對于活動記錄基址的偏移量，這個偏移量(即相對數(shù))在編譯時可完全確定下來。過程的局部數(shù)組的內(nèi)情向量的相對地址在編譯時也同樣可完全確定下來，一旦數(shù)據(jù)空間在過程里獲得分配后，對數(shù)組元素的引用也就容易用變址的方式進行訪問。對當前正在執(zhí)行(即活動)的過程，其任何32過程的執(zhí)行1．過程調(diào)用過程調(diào)用的中間代碼序列為：parT1parT2

parTncallP,n過程的執(zhí)行33由于此時TOP是指向被調(diào)用過程P之前的棧頂，而P的形式單元和活動記錄起點之間的距離是確定的(等于3，參見圖7–5)，因而由調(diào)用過程給將要調(diào)用的過程P的活動記錄(正在形成中)的形式單元傳遞實參值或?qū)崊⒌刂?，即每個parTi(i=1,2,…,n)可直接翻譯成如下指令：(i+3)[TOP]=Ti

/*傳遞參數(shù)值*/或(i+3)[TOP]=addr[Ti]/*傳遞參數(shù)地址*/由于此時TOP是指向被調(diào)用過程P之前的34而四元式callP,n則翻譯成：1[TOP]=SP/*保護現(xiàn)行SP*/3[TOP]=n /*傳遞參數(shù)個數(shù)*/JSRP /*轉(zhuǎn)子指令，轉(zhuǎn)向P過程的第一條指令*/過程P調(diào)用之前，先構(gòu)造出P的活動記錄部分內(nèi)容，見圖7–6所示。而四元式callP,n則翻譯成：35圖7–6過程P調(diào)用前先構(gòu)造P的活動記錄部分內(nèi)容圖7–6過程P調(diào)用前先構(gòu)造P的活動記錄部分內(nèi)容362．過程進入轉(zhuǎn)入過程P后，首先要做的工作是定義新活動記錄的SP，保護返回地址和定義新活動記錄的TOP值，即執(zhí)行下述指令：SP=TOP+1/*定義新SP*/1[SP]=返回地址/*保護返回地址*/TOP=TOP+L/*定義新TOP*/其中，L是過程P的活動記錄所需的單元數(shù)，這個數(shù)在編譯時可靜態(tài)地計算出來。2．過程進入37對含可變數(shù)組(非C語言)的情況來說，因為過程可含可變數(shù)組且所有數(shù)組都分配在活動記錄的頂上，所以緊接上述指令之后應是對數(shù)組進行存儲分配的指令(如果含有局部數(shù)組)，這些指令是在翻譯數(shù)組說明時產(chǎn)生的。對每個數(shù)組說明，相應的目標指令組將做以下幾件工作：(1)計算各維的上、下限；(2)調(diào)用數(shù)組空間分配子程序，其參數(shù)是各維的上、下限和內(nèi)情向量單元首地址。對含可變數(shù)組(非C語言)的情況來說，因為38數(shù)組空間分配子程序計算并填好內(nèi)情向量的所有信息，然后在TOP所指的位置之上留出數(shù)組所需的空間，并將TOP調(diào)整為指向數(shù)組區(qū)的頂端。?進入過程P后所做的工作如圖7–7所示。此后，在過程段執(zhí)行語句的工作過程中，凡引用形式參數(shù)、局部變量或數(shù)組元素都將以SP為基址進行相對訪問。數(shù)組空間分配子程序計算并填好內(nèi)情向量的所有39圖7–7進入過程P后所做的工作示意圖7–7進入過程P后所做的工作示意403．過程返回C語言以及其它一些相似的語言含有return(E)形式的返回語句，其中E為表達式。假定E值已計算出來并存放在某臨時單元T中，則此時即可將T值傳送到某個特定的寄存器中(調(diào)用過程將從這個特定的寄存器中獲得被調(diào)用過程P的結(jié)果)。剩下的工作就是恢復SP和TOP為進入過程P之前的原值(即指向調(diào)用過程的活動記錄及工作空間)，并按返回地址實行無條件轉(zhuǎn)移，即執(zhí)行下述指令序列：3．過程返回41TOP=SP–1 /*恢復調(diào)用過程的TOP值*/SP=0[SP] /*恢復調(diào)用過程的SP值*/X=2[TOP] /*將返回地址送X*/UJ0[X] /*無條件轉(zhuǎn)移，即按X的地址返回到調(diào)用過程*/過程P的返回示意如圖7–8所示。TOP=SP–142圖7–8過程P的返回示意圖7–8過程P的返回示意43嵌套過程語言的棧式實現(xiàn)在簡單程序語言實現(xiàn)中是允許過程的遞歸調(diào)用的，并且過程中可含有可變數(shù)組?，F(xiàn)在，我們再加上一種功能，即允許過程的嵌套性。嵌套過程語言的棧式實現(xiàn)在簡單程序語言實44在討論中，常常要用到過程定義的“嵌套層次”(簡稱層數(shù))這個概念。我們始終假定主程序的層數(shù)為0，因此主程序稱為第0層過程。如果過程Q是在層數(shù)為i的過程P內(nèi)定義的，并且P是包圍Q的最小過程，則Q的層數(shù)就為i+1。當編譯程序處理過程說明時，過程的層數(shù)將作為過程名的一個重要屬性登記在符號表中。嵌套層次顯示表(DISPLAY)和活動記錄在討論中，常常要用到過程定義的“嵌套層次”(45由于過程定義是嵌套的，因而一個過程可以引用包圍它的任一外層過程所定義的變量或數(shù)組。也就是說，運行時，一個過程Q可能引用它的任一外層過程P的最新活動記錄中的某些數(shù)據(jù)。因此，過程Q運行時必須知道它的所有外層的最新活動記錄的地址。由于允許遞歸和可變數(shù)組的存在，過程的活動記錄位置(即使是相對位置)也往往是變遷的，因而必須設法跟蹤每個外層過程的最新活動記錄的位置。由于過程定義是嵌套的，因而一個過程可以引用包46采用嵌套層次顯示表DISPLAY，其優(yōu)點是訪問非局部量的速度較快。

每進入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表DISPLAY。假定現(xiàn)在進入的過程層數(shù)為i，則它的DISPLAY表含有i+1個單元。此表本身是一個小棧，自頂而下每個單元依次存放著現(xiàn)行層、直接外層……直至最外層(第0層，即主程序?qū)?的每一層的最新活動記錄的起始地址。例如，令過程R的外層為Q，Q的外層為主程序P，則過程R運行時的DISPLAY表內(nèi)容如表7-1所示。采用嵌套層次顯示表DISPLAY，其優(yōu)點是訪問非局部量的速度47表7-1DISPLAY表2R的現(xiàn)行活動記錄的始址(SP的現(xiàn)行值)1Q的最新活動記錄的始址0P的活動記錄的始址表7-1DISPLAY表2R的現(xiàn)行活動記錄的始址1Q的最48由于過程的層數(shù)可靜態(tài)確定，因此每個過程的DISPLAY表的體積在編譯時即可知道。為了便于組織存儲區(qū)和簡化處理手續(xù)，我們把DISPLAY作為活動記錄的一部分置于形式單元的上端，如圖7–9所示。由于過程的層數(shù)可靜態(tài)確定，因此每個過程49由于每個過程的形式單元數(shù)目在編譯時是知道的，因此DISPLAY的相對地址d(相對于活動記錄的起點)在編譯時也是完全確定的。被調(diào)用過程為了建立自己的DISPLAY，就必須知道它的直接外層過程的DISPLAY，這意味著必須把直接外層的DISPLAY地址作為連接數(shù)據(jù)之一(稱為“全局DISPLAY地址”)傳送給被調(diào)用過程。于是，此時的連接數(shù)據(jù)包含老SP值、返回地址和全局DISPLAY地址這三項內(nèi)容。整個活動記錄的結(jié)構(gòu)如圖7–9所示。由于每個過程的形式單元數(shù)目在編譯時是知道50圖7–9活動記錄結(jié)構(gòu)圖7–9活動記錄結(jié)構(gòu)51存取鏈(也稱靜態(tài)鏈)方法。存取鏈方法引入一個稱為存取鏈的指針，該指針作為活動記錄的一項指向直接外層的最新活動記錄的地址，這就意味著在運行時棧中的每個數(shù)據(jù)區(qū)(活動記錄)之間又拉出一條鏈，這個鏈稱為存取鏈。注意，運行時棧中數(shù)據(jù)區(qū)之間原先就存在一條鏈，即每個活動記錄中所保存的老SP值這一項，它是指向調(diào)用該過程(子過程)的那個過程(父過程)的最新活動記錄的起點，由此向前形成了一條SP鏈。存取鏈(也稱靜態(tài)鏈)方法。52為了區(qū)別于存取鏈，稱SP鏈為控制鏈(也稱動態(tài)鏈)，它記錄了在運行中過程之間相互調(diào)用的關(guān)系。注意，控制鏈是動態(tài)的，而存取鏈是靜態(tài)的?？刂奇溣涗浟水斍皶r刻程序中各過程相互調(diào)用的情況；而存取鏈則始終記錄著程序靜態(tài)定義時該過程所有的直接外層(嵌套過程規(guī)定，內(nèi)層過程只允許調(diào)用其靜態(tài)定義時的外層過程說明的變量和數(shù)組)；因此，存取鏈指出了一個過程的當前活動記錄指向其直接定義的外層過程直至最外層的最新活動記錄的起點。具有存取鏈的活動記錄結(jié)構(gòu)如圖7–10所示。為了區(qū)別于存取鏈，稱SP鏈為控制鏈(也稱動態(tài)鏈)，它記錄了在53圖7–10具有存取鏈的活動記錄結(jié)構(gòu)圖7–10具有存取鏈的活動記錄結(jié)構(gòu)54假定過程的嵌套關(guān)系：假定過程的嵌套關(guān)系：55程序中每個過程的靜態(tài)結(jié)構(gòu)(嵌套層次)是確定的，如嵌套深度為2的過程R引用了非局部量a和b，其嵌套深度分別為0和1。從R的活動記錄開始，分別沿著2???0?=?2和2?1=1個存取鏈向前查找，則可找到包含這兩個非局部量的活動記錄。上述過程P調(diào)用S以及S調(diào)用Q運行時棧的變化過程如圖7–11(a)、(b)所示。程序中每個過程的靜態(tài)結(jié)構(gòu)(嵌套層次)是確定56由圖7–11可以看出，指針SP總是指向當前正在執(zhí)行過程的活動記錄起點，控制鏈(老SP)則指向調(diào)用運行過程的父過程的活動記錄起點。因此，當運行過程調(diào)用結(jié)束返回時，利用控制鏈老SP值可以得到調(diào)用前原父過程活動記錄的起點。從程序的靜態(tài)結(jié)構(gòu)來看，P是S和Q的靜態(tài)直接外層，所以，S和Q活動記錄中的存取鏈均指向其直接外層P的活動記錄起點。由圖7–11可以看出，指針SP總是指向當前57圖7–11過程調(diào)用時運行棧的變化圖7–11過程調(diào)用時運行棧的變化58例1:某程序的結(jié)構(gòu)如圖7–12所示，其中A、B、C為過程名，請分別畫出過程C調(diào)用A前后的棧頂活動記錄。圖7–12例中的程序結(jié)構(gòu)示意例1:某程序的結(jié)構(gòu)如圖7–12所示，其中A、B、C為過程名59解：過程C調(diào)用A前后的棧頂活動記錄示意如圖7–13所示。由圖7–13可知，當過程C執(zhí)行時，它可使用主程序、A、B和C過程所說明的變量，且其外層嵌套的過程活動記錄始址由DISPLAY表指出。當C調(diào)用A而使過程A執(zhí)行時，我們看到此時的DISPLAY表已變?yōu)閮身棧粗鞒绦蚝虯過程自身；也即此時A只可使用主程序和A過程所說明的變量。解：過程C調(diào)用A前后的棧頂活動記錄示意如圖7–13所示。由圖60圖7–13例1的運行棧與活動記錄示意圖7–13例1的運行棧與活動記錄示意61例2：在下面的PASCAL程序中，已經(jīng)第二次(遞歸地)進入了f，請給出第三次進入f后的運行棧及DISPLAY的示意圖PROGRAMtest(input,output);VARK:integer;FUNCTIONf(n:integer):integer;BEGINIFn<=0THENf:=1例2：在下面的PASCAL程序中，已經(jīng)第二次(遞歸地)進入62解：第三次進入f后的運行棧及DISPLAY的示意圖如圖7–14所示。由于靜態(tài)嵌套層次只有兩層，故每一次遞歸調(diào)用產(chǎn)生的DISPLAY表只有兩項，一項是test的SP(即0)，另一項是當前活動記錄的SPi(i=1,2,3)。解：第三次進入f后的運行棧及DISPLAY的示意圖如圖7–163圖7–14例2的運行棧及DISPLAY示意圖圖7–14例2的運行棧及DISPLAY示意圖64堆式動態(tài)存儲分配如果一種程序語言允許數(shù)據(jù)對象能夠自由地分配和釋放，或者不僅有過程而且有進程(process)這樣的程序結(jié)構(gòu)，那么由于空間的使用不一定遵循“先申請后釋放”的原則，則棧式存儲分配就不適用了。在這種情況下，通常使用一種稱之為堆的動態(tài)存儲分配方案。假定程序運行時有一個大的存儲空間，需要時就從這個空間中借用一塊，不用時再退還給它。堆式動態(tài)存儲分配如果一種程序語言允許數(shù)65由于借、還的時間先后不一，因而經(jīng)過一段時間的運行后，這個大空間就必然被分割成如圖7–15所示的許多小塊，這些塊有些正在使用，有些則是空閑的(未被使用)。由于借、還的時間先后不一，因而經(jīng)過一段時間的運行后，這個大空66圖7–15堆式存儲分配示意圖7–15堆式存儲分配示意67對于堆式存儲分配來說，需要解決兩個問題：一是堆空間的分配，即當運行程序需要一塊空間時應分配哪一塊給它；另一個問題是分配空間的回收，由于返回堆的不用空間是按任意次序進行的，所以需要研究專門的回收分配策略。在許多語言中都有顯式的堆空間分配和回收語句或函數(shù)，如PASCAL語言中的new和dispose、C語言中的malloc和free以及C++語言中的new和delete。對于堆式存儲分配來說，需要解決兩個問題：一68堆式存儲管理的方法的簡單討論當運行程序要求一塊體積為N的存儲空間時應如何分配？從理論上講，這時應從比N稍大一些的空閑塊中取出N個單元予以分配，這種做法的目的是保持較大的空閑塊以備將來之需。但這種方法實現(xiàn)起來難度較大，實際中采用的辦法是：掃描空閑塊鏈并在首次遇到的比N大的空閑塊中取出N個單元進行分配。堆式存儲管理的方法的簡單討論69如果找不到一塊比N大的空閑塊，但所有空閑塊的總和卻比N大，這時就需要用某種方法使這些空閑塊拼接在一起，形成一個可分配的連續(xù)空間。如果所有空閑塊的總和都不及N大，則需要采用更復雜的辦法，如廢品回收技術(shù)(即尋找那些運行程序已不使用但仍未釋放的存儲塊或運行程序目前很少使用的存儲塊)，把這些存儲塊回收后再重新分配。

如果找不到一塊比N大的空閑塊，但所有70可以采用多種策略進行堆式動態(tài)存儲管理。使用可利用空間表進行動態(tài)分配的方法可利用空間表是指將所有空閑塊用一張表記錄下來，表的結(jié)構(gòu)可以是目錄表，也可以是鏈表，其結(jié)構(gòu)分別如圖7–16(b)、(c)所示?？梢圆捎枚喾N策略進行堆式動態(tài)存儲管理。71圖7–16內(nèi)存狀態(tài)和可利用空間表圖7–16內(nèi)存狀態(tài)和可利用空間表72使用可利用空間表進行動態(tài)存儲分配的方法又可分為如下兩種：(1)定長塊的管理。最簡單的堆式存儲管理方法是采用定長塊的管理方法，即將堆存儲空間在初始化時就劃分成大小相同的若干塊，將各個塊通過鏈表鏈接起來形成一個單向線性鏈表。由于各塊大小相同，故分配時無需查找，只需將頭指針所指的第一塊分配給用戶即可，然后頭指針指向下一塊。同樣，當回收時，系統(tǒng)將待回收的存儲塊插入到表頭即完成了該塊的回收。使用可利用空間表進行動態(tài)存儲分配的方法又可73

(2)變長塊的管理。變長塊管理方法是一種常用的堆式存儲管理方法，它可以根據(jù)實際需要來分配長度不同的空閑塊；對空閑塊的管理則可以采用圖7–16(c)中的鏈表形式。系統(tǒng)開始時，存儲空間是一完整空間，可利用空間表中只有一個大小為整個存儲空間的空閑塊。當系統(tǒng)運行一段時間后，隨著分配和回收的進行，可利用空間表中空閑塊的大小和個數(shù)也隨之改變。由于可利用空間表中的空閑塊大小不同，因而存在著如何進行空閑塊分配的問題。若可利用空間表存在多個大于所要求空間的空閑塊，可采取以下三種方法之一進行存儲分配：(2)變長塊的管理。變長塊管理方法是一種常74(1)首次滿足法。從表頭開始查找可利用空間表，將找到的第一個滿足需要的空閑塊或空閑塊的一部分分配出去(當空閑塊略大于所要求的空間時，則整塊分配出去)，而其余部分仍作為一個空閑塊留在表中。(2)最優(yōu)滿足法。系統(tǒng)掃描整個可利用空間表，從中找出一塊不小于要求的最小空閑塊予以分配。為了避免每次分配都要掃描整個表，通常將空閑塊按由小到大的順序進行排列。這樣，所找到的第一個大于或等于所需空間的空閑塊即為所求，無須再掃描整個表。(1)首次滿足法。從表頭開始查找可利用空間75(3)最差滿足法。系統(tǒng)將可利用空間表中最大的空閑塊予以分配(當然也要求其不小于所需空間的大小)，這種方法應使空閑塊按由大到小的順序排列，此時表頭的空閑塊即為所求。最優(yōu)滿足法和最差滿足法在回收時都需將待回收的空閑塊插入到鏈表中適當?shù)奈恢蒙先ァ?3)最差滿足法。系統(tǒng)將可利用空間76以上三種方法各有所長。一般來說，最優(yōu)滿足法適用于請求分配的內(nèi)存大小范圍較廣的系統(tǒng)；最差滿足法適用于請求分配的內(nèi)存大小范圍較窄的系統(tǒng)；而首次滿足法則適用于事先無法獲知請求分配和回收情況的系統(tǒng)。從時間上來看，最優(yōu)滿足法無論分配與回收都需要查表，故最費時間；最差滿足法分配時無需查表，但回收時卻需查表并根據(jù)回收空閑塊的大小確定其在表中應插入的位置；而首次滿足法在分配時需要查表，回收時直接插入到表頭即可。以上三種方法各有所長。一般來說，最優(yōu)滿足法77對于已分配的存儲塊，可以采用不同的回收策略。有的程序語言干脆不做回收工作，直到內(nèi)存空間用完為止；如果當空間用完后還有分配存儲塊的請求，就停止程序的運行。這樣做的缺點是浪費空間，但如果系統(tǒng)具有海量虛存或堆中的多數(shù)數(shù)據(jù)是一分配就一直使用的情形，則這種方法也是可行的。如果程序語言有顯式的分配命令，那么就可用顯式的回收命令(如C語言中的free)來回收不用的空間。對于已分配的存儲塊，可以采用不同的回收策78第七章運行時存儲空間組織本章討論目標程序運行時的活動和運行時的存儲組織與管理本章要點：

過程的活動與參數(shù)傳遞 靜態(tài)存儲分配

簡單的棧式存儲分配嵌套過程語言的棧式實現(xiàn)堆式動態(tài)存儲分配

第七章運行時存儲空間組織本章討論目標程序運行時的活動和運行79

過程的活動與參數(shù)傳遞定義和調(diào)用過程（函數(shù)）是程序語言的主要特征之一。過程是模塊程序設計的主要手段，同時也是節(jié)省程序代碼和擴充語言能力的主要途徑。一個過程一旦定義后，就可以在別的地方調(diào)用它。調(diào)用與被調(diào)用(過程)兩者之間的信息往來通過全局量或參數(shù)傳遞。

過程的活動與參數(shù)傳遞定義和調(diào)用過程（80例如，下面的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);}例如，下面的C語言程序：81其中a、b、c稱為形式參數(shù)(簡稱形參)函數(shù)調(diào)用語句：showme(z,y,x)中的z、y、x則稱為實在參數(shù)(簡稱實參)。實參甚至也可以是一個較復雜的表達式而不僅僅只是一個變量。實參和對應的形參在性質(zhì)上應相容不悖。運行時存儲空間組織82過程的活動一個過程的活動是指該過程的一次執(zhí)行。過程的生存期是指從執(zhí)行該過程體第一步操作到最后一步操作之間的操作程序，包括執(zhí)行該過程時調(diào)用其他過程花費的時間。過程的活動一個過程的活動是指該過程的一次執(zhí)行。83形式參數(shù)提供了參數(shù)替換的手段，在過程調(diào)用時可以使用不同的數(shù)據(jù)作為實在參數(shù)來替換形式參數(shù)，從而實現(xiàn)了同一個過程可以對不同的實在參數(shù)進行相同操作的功能。那么，如何把實在參數(shù)傳遞給相應的形式參數(shù)呢？程序語言中參數(shù)傳遞的方式主要有傳值(callbyvalue)、傳地址(callbyreference)和傳名(callbyname)三種。參數(shù)的傳遞形式參數(shù)提供了參數(shù)替換的手段，在過程調(diào)841．傳值傳值是最簡單的參數(shù)傳遞方法。所謂傳值，就是計算出實在參數(shù)的值然后把它傳給被調(diào)用過程相對應的形式參數(shù)，具體過程如下：(1)把形式參數(shù)當作過程的局部變量處理，即在被調(diào)用過程中開辟形式參數(shù)的存儲空間(即形式單元)。(2)調(diào)用過程計算出實在參數(shù)的值，并將該值放入為形式單元開辟的空間中。1．傳值85(3)被調(diào)用過程執(zhí)行時就像使用局部變量一樣使用這些形式單元。傳值的一個重要特點是對形式參數(shù)的任何運算都不影響調(diào)用過程實在參數(shù)的值，即參數(shù)傳遞后實在參數(shù)與對應的形式參數(shù)不再發(fā)生聯(lián)系了。(3)被調(diào)用過程執(zhí)行時就像使用局部變量一樣862．傳地址所謂傳地址，是指把實在參數(shù)的地址傳遞給相應的形式參數(shù)所對應的形式單元。如果實在參數(shù)是一個變量，則直接將該變量的地址傳給相應的形式單元；如果實在參數(shù)是常數(shù)或表達式，則先計算其值并存放在某一臨時單元中，然后將這個臨時單元的地址傳給相應的形式單元。2．傳地址87被調(diào)用過程執(zhí)行時，對形式參數(shù)的任何引用或賦值都被處理成對形式單元的間接訪問，即按形式單元中存放的地址轉(zhuǎn)到調(diào)用過程中去訪問實在參數(shù)。對形式參數(shù)的任何運算實際上都是對實在參數(shù)的運算，而形式參數(shù)只不過起到輔助查找到實在參數(shù)的指針的作用。因此，當被調(diào)用過程工作完畢返回時，形式單元所指的實在參數(shù)單元就保留了運算的結(jié)果。被調(diào)用過程執(zhí)行時，對形式參數(shù)的任何引用或883．傳名傳名是高級語言ALGOL60所定義的一種特殊的參數(shù)傳遞方式，其傳遞參數(shù)的方法如下：(1)過程調(diào)用的作用相當于把被調(diào)用過程的過程體復制到調(diào)用處(替換調(diào)用語句)，并將過程體中所有出現(xiàn)的形式參數(shù)在文字上替換成相應的實在參數(shù)。這種文字上的替換稱為宏擴展(MarcroExpansion)。3．傳名89(2)被調(diào)用過程中的局部名如果與過程調(diào)用的實在參數(shù)名發(fā)生沖突，則在宏擴展前對被調(diào)用過程中的這些局部名重新命名以避免重名沖突。(3)為表現(xiàn)實在參數(shù)的整體性，必要時在替換前把實在參數(shù)用括號括起來。傳名這種參數(shù)傳遞方法因其操作過于復雜現(xiàn)在已很少采用。不同的參數(shù)傳遞方法得到的結(jié)果不同，因此，如何選擇參數(shù)傳遞的方法將影響語言的語義，這是編譯程序在處理參數(shù)傳遞時應引起重視的問題。(2)被調(diào)用過程中的局部名如果與過程調(diào)用的實90運行時存儲器的劃分目標代碼靜態(tài)數(shù)據(jù)棧堆管理過程的活動，過程調(diào)用時相關(guān)信息存入棧中存放動態(tài)數(shù)據(jù)圖7-1運行時存儲器的劃分目標代碼靜態(tài)數(shù)據(jù)棧堆管理過程的活動，過程調(diào)91靜態(tài)存儲分配如果在編譯時就能夠確定一個程序在運行時所需的存儲空間大小，則在編譯時就能夠安排好目標程序運行時的全部數(shù)據(jù)空間，并能確定每個數(shù)據(jù)項的單元地址，存儲空間的這種分配方法叫做靜態(tài)分配。靜態(tài)存儲分配如果在編譯時就能夠確定一92FORTRAN語言的特點：不允許過程有遞歸性；每個數(shù)據(jù)名所需的存儲空間大小都是常量(即不允許含可變體積的數(shù)據(jù)，如可變數(shù)組)；所有數(shù)據(jù)名的性質(zhì)是完全確定的(不允許出現(xiàn)在運行時再動態(tài)確定其性質(zhì)的名字)。這些特點確保整個程序所需數(shù)據(jù)空間的總量在編譯時是完全確定的，從而每個數(shù)據(jù)名的地址就可靜態(tài)地進行分配。FORTRAN語言的特點：93靜態(tài)存儲分配是一種最簡單的存儲管理。一般而言，適于靜態(tài)存儲分配的語言必須滿足以下條件：(1)數(shù)組的上下界必須是常數(shù)；(2)過程調(diào)用不允許遞歸；(3)不允許采用動態(tài)的數(shù)據(jù)結(jié)構(gòu)(即在程序運行過程中申請和釋放的數(shù)據(jù)結(jié)構(gòu))。靜態(tài)存儲分配是一種最簡單的存儲管理。一般而言，適于靜態(tài)存儲分94在編譯過程中，給程序中的變量或數(shù)組分配存儲單元的一般做法是：為每一個變量(或數(shù)組)確定一個有序的整數(shù)對；其中，第一個整數(shù)用來指示數(shù)據(jù)區(qū)(局部數(shù)據(jù)區(qū)或公用區(qū))的編號，第二個整數(shù)則用來指明該變量(或數(shù)組)所對應的存儲起始單元相對于其所在數(shù)據(jù)區(qū)起點的位移(即相對于數(shù)據(jù)區(qū)起點的地址)；并將這一對整數(shù)填入符號表相應登記項的信息欄中。至于各數(shù)據(jù)區(qū)的起始地址在編譯時可暫不確定，待各程序段全部編譯完成之后，再由連接裝配程序最終確定，并將各程序段的目標代碼組裝成一個完整的目標程序。在編譯過程中，給程序中的變量或數(shù)組分配95一個FORTRAN程序段的局部數(shù)據(jù)區(qū)可由圖7-2所示的項目組成。其中，隱參數(shù)是指過程調(diào)用時的連接信息(不在源程序中明顯出現(xiàn))，如調(diào)用時的返回地址、調(diào)用時寄存器的保護等；形式單元用來存放過程調(diào)用時形參與實參結(jié)合的實參地址或值。一個FORTRAN程序段的局部數(shù)據(jù)區(qū)可96一個FORTRAN程序段的局部數(shù)據(jù)區(qū)保存調(diào)用此程序段時的返回地址保存調(diào)用段留在寄存器中的相關(guān)信息存放實參的地址或值圖7-2一個FORTRAN程序段的局部數(shù)據(jù)區(qū)保存調(diào)用此程序段時的返回97簡單的棧式存儲分配我們首先考慮一種簡單程序語言的實現(xiàn)，這種語言沒有分程序結(jié)構(gòu)，過程定義不允許嵌套，但允許過程的遞歸調(diào)用，允許過程含有可變數(shù)組。例如，C語言除不允許含有可變數(shù)組外，就是這樣一種語言。C語言的程序結(jié)構(gòu)如下：簡單的棧式存儲分配我們首先考慮一種簡單程序98全局數(shù)據(jù)說明main(?){main中的數(shù)據(jù)說明}voidR(?){R中的數(shù)據(jù)說明}voidQ(){Q中的數(shù)據(jù)說明}全局數(shù)據(jù)說明99例如，下面計算n！的C語言程序就是一個遞歸調(diào)用的程序，它的執(zhí)行過程可以用棧來實現(xiàn)。#include“stdio.h”longfactorial(intn){if(n>1)return(n*factorial(n?1));elsereturn(1);}例如，下面計算n！的C語言程序就是一個遞歸調(diào)用的程序，它的執(zhí)100main(?){intnum;do{scanf(“%d”,&num);if(num>=0&&num<15)printf(“%d\n”,factorial(num));elseprintf(“error!\n”);}while(num>=0);}main(?)101使用棧式存儲分配法意味著程序運行時，每當進入一個過程(或函數(shù))就有一個相應的活動記錄累筑于棧頂，此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時工作單元等；在進入過程和執(zhí)行過程的可執(zhí)行語句之前，再把局部數(shù)組所需空間累筑于棧頂，從而形成過程工作時的完整數(shù)據(jù)區(qū)。棧式存儲分配與活動記錄使用棧式存儲分配法意味著程序運行時，每當進102注意，每個過程的活動記錄的體積在編譯時可以靜態(tài)地確定。但由于允許含有可變數(shù)組，所以數(shù)組的大小只有在運行時才能知道。因數(shù)組區(qū)的大小不能預先獲知，為了擴充方便，所以只能將數(shù)組區(qū)累筑于活動記錄之上的當前棧頂。當一個過程工作完畢返回時，它在棧頂?shù)臄?shù)據(jù)區(qū)(包括活動記錄和數(shù)組區(qū))也隨即不復存在。注意，每個過程的活動記錄的體積在編譯時可以103對C語言來說，由于其不含可變數(shù)組，因而它的活動記錄本身包含了局部數(shù)組的空間。圖7–3和圖7–4分別給出了C語言和含可變數(shù)組的某簡單語言程序運行時的數(shù)據(jù)空間結(jié)構(gòu)，即顯示了主程序在調(diào)用了過程Q，Q又調(diào)用了過程R，且在R投入運行后的存儲結(jié)構(gòu)。

對C語言來說，由于其不含可變數(shù)組，因而104圖7–3C語言程序的存儲組織SP指示器總是指向執(zhí)行過程活動記錄的起點，而TOP指示器則始終指向(已占用)棧頂單元。當進入一個過程時，TOP指向為此過程創(chuàng)建的活動記錄的頂端；在分配數(shù)組區(qū)之后(如果有的話)，TOP又改為指向數(shù)組區(qū)(從而是該過程整個數(shù)據(jù)區(qū))的頂端。圖7–3C語言程序的存儲組織SP指示器總是指向執(zhí)行過105圖7–4含可變數(shù)組程序的存儲組織圖7–4含可變數(shù)組程序的存儲組織106C的活動記錄含有以下幾個區(qū)段(如圖7–5所示)：(1)連接數(shù)據(jù)(兩項)：老SP值(即前一活動記錄的起始地址)和返回地址；(2)參數(shù)個數(shù)；(3)形式單元(存放實在參數(shù)的值或地址)；(4)過程的局部變量(簡單變量)、數(shù)組的內(nèi)情向量和臨時工作單元。C的活動記錄含有以下幾個區(qū)段(如圖7–5所示)：107圖7–5C過程的活動記錄圖7–5C過程的活動記錄108

C語言不允許過程(函數(shù))嵌套，也即不允許一個過程的定義出現(xiàn)在另一個過程的定義之內(nèi)。因此，C語言的非局部變量僅能出現(xiàn)在源程序頭，非局部變量可采用靜態(tài)存儲分配并在編譯時確定它們的地址。由圖7–5可知，過程的每一局部變量或形參在活動記錄中的位置都是確定的；也就是說，這些變量或形參所分配的存儲單元其地址都是相對于活動記錄的基址SP的。因此，變量和形參運行時在棧上的絕對地址是：絕對地址=活動記錄基址(SP)+相對地址C語言不允許過程(函數(shù))嵌套，也即不允許一109對當前正在執(zhí)行(即活動)的過程，其任何局部變量或形參X的引用均可表示為變址訪問X[SP]。此處X代表X相對于活動記錄基址的偏移量，這個偏移量(即相對數(shù))在編譯時可完全確定下來。過程的局部數(shù)組的內(nèi)情向量的相對地址在編譯時也同樣可完全確定下來，一旦數(shù)據(jù)空間在過程里獲得分配后，對數(shù)組元素的引用也就容易用變址的方式進行訪問。對當前正在執(zhí)行(即活動)的過程，其任何110過程的執(zhí)行1．過程調(diào)用過程調(diào)用的中間代碼序列為：parT1parT2

parTncallP,n過程的執(zhí)行111由于此時TOP是指向被調(diào)用過程P之前的棧頂，而P的形式單元和活動記錄起點之間的距離是確定的(等于3，參見圖7–5)，因而由調(diào)用過程給將要調(diào)用的過程P的活動記錄(正在形成中)的形式單元傳遞實參值或?qū)崊⒌刂?，即每個parTi(i=1,2,…,n)可直接翻譯成如下指令：(i+3)[TOP]=Ti

/*傳遞參數(shù)值*/或(i+3)[TOP]=addr[Ti]/*傳遞參數(shù)地址*/由于此時TOP是指向被調(diào)用過程P之前的112而四元式callP,n則翻譯成：1[TOP]=SP/*保護現(xiàn)行SP*/3[TOP]=n /*傳遞參數(shù)個數(shù)*/JSRP /*轉(zhuǎn)子指令，轉(zhuǎn)向P過程的第一條指令*/過程P調(diào)用之前，先構(gòu)造出P的活動記錄部分內(nèi)容，見圖7–6所示。而四元式callP,n則翻譯成：113圖7–6過程P調(diào)用前先構(gòu)造P的活動記錄部分內(nèi)容圖7–6過程P調(diào)用前先構(gòu)造P的活動記錄部分內(nèi)容1142．過程進入轉(zhuǎn)入過程P后，首先要做的工作是定義新活動記錄的SP，保護返回地址和定義新活動記錄的TOP值，即執(zhí)行下述指令：SP=TOP+1/*定義新SP*/1[SP]=返回地址/*保護返回地址*/TOP=TOP+L/*定義新TOP*/其中，L是過程P的活動記錄所需的單元數(shù)，這個數(shù)在編譯時可靜態(tài)地計算出來。2．過程進入115對含可變數(shù)組(非C語言)的情況來說，因為過程可含可變數(shù)組且所有數(shù)組都分配在活動記錄的頂上，所以緊接上述指令之后應是對數(shù)組進行存儲分配的指令(如果含有局部數(shù)組)，這些指令是在翻譯數(shù)組說明時產(chǎn)生的。對每個數(shù)組說明，相應的目標指令組將做以下幾件工作：(1)計算各維的上、下限；(2)調(diào)用數(shù)組空間分配子程序，其參數(shù)是各維的上、下限和內(nèi)情向量單元首地址。對含可變數(shù)組(非C語言)的情況來說，因為116數(shù)組空間分配子程序計算并填好內(nèi)情向量的所有信息，然后在TOP所指的位置之上留出數(shù)組所需的空間，并將TOP調(diào)整為指向數(shù)組區(qū)的頂端。?進入過程P后所做的工作如圖7–7所示。此后，在過程段執(zhí)行語句的工作過程中，凡引用形式參數(shù)、局部變量或數(shù)組元素都將以SP為基址進行相對訪問。數(shù)組空間分配子程序計算并填好內(nèi)情向量的所有117圖7–7進入過程P后所做的工作示意圖7–7進入過程P后所做的工作示意1183．過程返回C語言以及其它一些相似的語言含有return(E)形式的返回語句，其中E為表達式。假定E值已計算出來并存放在某臨時單元T中，則此時即可將T值傳送到某個特定的寄存器中(調(diào)用過程將從這個特定的寄存器中獲得被調(diào)用過程P的結(jié)果)。剩下的工作就是恢復SP和TOP為進入過程P之前的原值(即指向調(diào)用過程的活動記錄及工作空間)，并按返回地址實行無條件轉(zhuǎn)移，即執(zhí)行下述指令序列：3．過程返回119TOP=SP–1 /*恢復調(diào)用過程的TOP值*/SP=0[SP] /*恢復調(diào)用過程的SP值*/X=2[TOP] /*將返回地址送X*/UJ0[X] /*無條件轉(zhuǎn)移，即按X的地址返回到調(diào)用過程*/過程P的返回示意如圖7–8所示。TOP=SP–1120圖7–8過程P的返回示意圖7–8過程P的返回示意121嵌套過程語言的棧式實現(xiàn)在簡單程序語言實現(xiàn)中是允許過程的遞歸調(diào)用的，并且過程中可含有可變數(shù)組?，F(xiàn)在，我們再加上一種功能，即允許過程的嵌套性。嵌套過程語言的棧式實現(xiàn)在簡單程序語言實122在討論中，常常要用到過程定義的“嵌套層次”(簡稱層數(shù))這個概念。我們始終假定主程序的層數(shù)為0，因此主程序稱為第0層過程。如果過程Q是在層數(shù)為i的過程P內(nèi)定義的，并且P是包圍Q的最小過程，則Q的層數(shù)就為i+1。當編譯程序處理過程說明時，過程的層數(shù)將作為過程名的一個重要屬性登記在符號表中。嵌套層次顯示表(DISPLAY)和活動記錄在討論中，常常要用到過程定義的“嵌套層次”(123由于過程定義是嵌套的，因而一個過程可以引用包圍它的任一外層過程所定義的變量或數(shù)組。也就是說，運行時，一個過程Q可能引用它的任一外層過程P的最新活動記錄中的某些數(shù)據(jù)。因此，過程Q運行時必須知道它的所有外層的最新活動記錄的地址。由于允許遞歸和可變數(shù)組的存在，過程的活動記錄位置(即使是相對位置)也往往是變遷的，因而必須設法跟蹤每個外層過程的最新活動記錄的位置。由于過程定義是嵌套的，因而一個過程可以引用包124采用嵌套層次顯示表DISPLAY，其優(yōu)點是訪問非局部量的速度較快。

每進入一個過程后，在建立它的活動記錄區(qū)的同時建立一張嵌套層次顯示表DISPLAY。假定現(xiàn)在進入的過程層數(shù)為i，則它的DISPLAY表含有i+1個單元。此表本身是一個小棧，自頂而下每個單元依次存放著現(xiàn)行層、直接外層……直至最外層(第0層，即主程序?qū)?的每一層的最新活動記錄的起始地址。例如，令過程R的外層為Q，Q的外層為主程序P，則過程R運行時的DISPLAY表內(nèi)容如表7-1所示。采用嵌套層次顯示表DISPLAY，其優(yōu)點是訪問非局部量的速度125表7-1DISPLAY表2R的現(xiàn)行活動記錄的始址(SP的現(xiàn)行值)1Q的最新活動記錄的始址0P的活動記錄的始址表7-1DISPLAY表2R的現(xiàn)行活動記錄的始址1Q的最126由于過程的層數(shù)可靜態(tài)確定，因此每個過程的DISPLAY表的體積在編譯時即可知道。為了便于組織存儲區(qū)和簡化處理手續(xù)，我們把DISPLAY作為活動記錄的一部分置于形式單元的上端，如圖7–9所示。由于過程的層數(shù)可靜態(tài)確定，因此每個過程127由于每個過程的形式單元數(shù)目在編譯時是知道的，因此DISPLAY的相對地址d(相對于活動記錄的起點)在編譯時也是完全確定的。被調(diào)用過程為了建立自己的DISPLAY，就必須知道它的直接外層過程的DISPLAY，這意味著必須把直接外層的DISPLAY地址作為連接數(shù)據(jù)之一(稱為“全局DISPLAY地址”)傳送給被調(diào)用過程。于是，此時的連接數(shù)據(jù)包含老SP值、返回地址和全局DISPLAY地址這三項內(nèi)容。整個活動記錄的結(jié)構(gòu)如圖7–9所示。由于每個過程的形式單元數(shù)目在編譯時是知道128圖7–9活動記錄結(jié)構(gòu)圖7–9活動記錄結(jié)構(gòu)129存取鏈(也稱靜態(tài)鏈)方法。存取鏈方法引入一個稱為存取鏈的指針，該指針作為活動記錄的一項指向直接外層的最新活動記錄的地址，這就意味著在運行時棧中的每個數(shù)據(jù)區(qū)(活動記錄)之間又拉出一條鏈，這個鏈稱為存取鏈。注意，運行時棧中數(shù)據(jù)區(qū)之間原先就存在一條鏈，即每個活動記錄中所保存的老SP值這一項，它是指向調(diào)用該過程(子過程)的那個過程(父過程)的最新活動記錄的起點，由此向前形成了一條SP鏈。存取鏈(也稱靜態(tài)鏈)方法。130為了區(qū)別于存取鏈，稱SP鏈為控制鏈(也稱動態(tài)鏈)，它記錄了在運行中過程之間相互調(diào)用的關(guān)系。注意，控制鏈是動態(tài)的，而存取鏈是靜態(tài)的?？刂奇溣涗浟水斍皶r刻程序中各過程相互調(diào)用的情況；而存取鏈則始終記錄著程序靜態(tài)定義時該過程所有的直接外層(嵌套過程規(guī)定，內(nèi)層過程只允許調(diào)用其靜態(tài)定義時的外層過程說明的變量和數(shù)組)；因此，存取鏈指出了一個過程的當前活動記錄指向其直接定義的外層過程直至最外層的最新活動記錄的起點。具有存取鏈的活動記錄結(jié)構(gòu)如圖7–10所示。為了區(qū)別于存取鏈，稱SP鏈為控制鏈(也稱動態(tài)鏈)，它記錄了在131圖7–10具有存取鏈的活動記錄結(jié)構(gòu)圖7–10具有存取鏈的活動記錄結(jié)構(gòu)132假定過程的嵌套關(guān)系：假定過程的嵌套關(guān)系：133程序中每個過程的靜態(tài)結(jié)構(gòu)(嵌套層次)是確定的，如嵌套深度為2的過程R引用了非局部量a和b，其嵌套深度分別為0和1。從R的活動記錄開始，分別沿著2???0?=?2和2?1=1個存取鏈向前查找，則可找到包含這兩個非局部量的活動記錄。上述過程P調(diào)用S以及S調(diào)用Q運行時棧的變化過程如圖7–11(a)、(b)所示。程序中每個過程的靜態(tài)結(jié)構(gòu)(嵌套層次)是確定134由圖7–11可以看出，指針SP總是指向當前正在執(zhí)行過程的活動記錄起點，控制鏈(老SP)則指向調(diào)用運行過程的父過程的活動記錄起點。因此，當運行過程調(diào)用結(jié)束返回時，利用控制鏈老SP值可以得到調(diào)用前原父過程活動記錄的起點。從程序的靜態(tài)結(jié)構(gòu)來看，P是S和Q的靜態(tài)直接外層，所以，S和Q活動記錄中的存取鏈均指向其直接外層P的活動記錄起點。由圖7–11可以看出，指針SP總是指向當前135圖7–11過程調(diào)用時運行棧的變化圖7–11過程調(diào)用時運行棧的變化136例1:某程序的結(jié)構(gòu)如圖7–12所示，其中A、B、C為過程名，請分別畫出過程C調(diào)用A前后的棧頂活動記錄。圖7–12例中的程序結(jié)構(gòu)示意例1:某程序的結(jié)構(gòu)如圖7–12所示，其中A、B、C為過程名137解：過程C調(diào)用A前后的棧頂活動記錄示意如圖7–13所示。由圖7–13可知，當過程C執(zhí)行時，它可使用主程序、A、B和C過程所說明的變量，且其外層嵌套的過程活動記錄始址由DISPLAY表指出。當C調(diào)用A而使過程A執(zhí)行時，我們看到此時的DISPLAY表已變?yōu)閮身棧粗鞒绦蚝虯過程自身；也即此時A只可使用主程序和A過程所說明的變量。解：過程C調(diào)用A前后的棧頂活動記錄示意如圖7–13所示。由圖138圖7–13例1的運行棧與活動記錄示意圖7–13例1的運行棧與活動記錄示意139例2：在下面的PASCAL程序中，已經(jīng)第二次(遞歸地)進入了f，請給出第三次進入f后的運行棧及DISPLAY的示意圖PROGRAMtest(input,output);VARK:integer;FUNCTIONf(n:integer):integer;BEGINIFn<=0THENf:=1例2：在下面的PASCAL程序中，已經(jīng)第二次(遞歸地)進入140解：第三次進入f后的運行棧及DISPLAY的示意圖如圖7–14所示。由于靜態(tài)嵌套層次只有兩層，故每一次遞歸調(diào)用產(chǎn)生的DISPLAY表只有兩項，一項是test的SP(即0)，另一項是當前活動記錄的SPi(i=1,2,3)。解：第三次進入f后的運行棧及DISPLAY的示意圖如圖7–1141圖7–14例2的運行棧及DISPLAY示意圖圖7–14例2的運行棧及DISPLAY示意圖142堆式動態(tài)存儲分配