編譯原理_第9章

1、第九章第九章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 在程序的執(zhí)行過(guò)程中，程序中數(shù)據(jù)的存取是通過(guò)與之對(duì)應(yīng)的存儲(chǔ)單元來(lái)進(jìn)行的。 標(biāo)識(shí)符對(duì)應(yīng)的內(nèi)存地址都是由編譯程序在編譯時(shí)或由其生成的目標(biāo)程序運(yùn)行時(shí)進(jìn)行分配。程序中使用的存儲(chǔ)單元都由標(biāo)識(shí)符來(lái)表示。第九章運(yùn)行時(shí)存儲(chǔ)空間組織第九章運(yùn)行時(shí)存儲(chǔ)空間組織9.1 目標(biāo)程序運(yùn)行時(shí)的活動(dòng)（略）9.2 運(yùn)行時(shí)存儲(chǔ)器的劃分9.3 靜態(tài)存儲(chǔ)分配（略）9.4 簡(jiǎn)單的棧式存儲(chǔ)分配9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)9.6 堆式動(dòng)態(tài)存儲(chǔ)分配9.2 運(yùn)行時(shí)存儲(chǔ)器的劃分運(yùn)行時(shí)存儲(chǔ)器的劃分一、運(yùn)行時(shí)存儲(chǔ)器的劃分一、運(yùn)行時(shí)存儲(chǔ)器的劃分 1.編譯器需要在存儲(chǔ)區(qū)保護(hù)的對(duì)象編譯器需要在存儲(chǔ)區(qū)保護(hù)的

2、對(duì)象（1）目標(biāo)代碼目標(biāo)代碼編譯時(shí)可確定，故可放在一個(gè)靜態(tài)確定的區(qū)域編譯時(shí)可確定，故可放在一個(gè)靜態(tài)確定的區(qū)域（2）數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象部分?jǐn)?shù)據(jù)對(duì)象的大小在編譯時(shí)可確定，故也可部分?jǐn)?shù)據(jù)對(duì)象的大小在編譯時(shí)可確定，故也可 放在一個(gè)靜態(tài)確定的區(qū)域放在一個(gè)靜態(tài)確定的區(qū)域（3）跟蹤過(guò)程活動(dòng)的控制棧跟蹤過(guò)程活動(dòng)的控制棧目標(biāo)代碼目標(biāo)代碼靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)棧棧堆堆2.棧和堆棧和堆 A.棧棧：用擴(kuò)充的棧來(lái)管理過(guò)程的活動(dòng)，當(dāng)發(fā)生過(guò)程調(diào)用時(shí)，：用擴(kuò)充的棧來(lái)管理過(guò)程的活動(dòng)，當(dāng)發(fā)生過(guò)程調(diào)用時(shí)， 中斷當(dāng)前活動(dòng)的執(zhí)行，激活新被調(diào)用過(guò)程的活動(dòng)，中斷當(dāng)前活動(dòng)的執(zhí)行，激活新被調(diào)用過(guò)程的活動(dòng)， 并把包含在這個(gè)活動(dòng)生存期中的數(shù)據(jù)對(duì)象以及該活并

3、把包含在這個(gè)活動(dòng)生存期中的數(shù)據(jù)對(duì)象以及該活 動(dòng)有關(guān)的其它信息存入棧中。當(dāng)控制從調(diào)用返回時(shí)，動(dòng)有關(guān)的其它信息存入棧中。當(dāng)控制從調(diào)用返回時(shí)， 將所占存儲(chǔ)空間彈出棧頂。同時(shí)，被中斷的活動(dòng)恢將所占存儲(chǔ)空間彈出棧頂。同時(shí)，被中斷的活動(dòng)恢 復(fù)執(zhí)行。復(fù)執(zhí)行。 B.堆（堆（heap）存放動(dòng)態(tài)數(shù)據(jù)，大小可隨程序的運(yùn)存放動(dòng)態(tài)數(shù)據(jù)，大小可隨程序的運(yùn)行而改變。行而改變。9.2 運(yùn)行時(shí)存儲(chǔ)器的劃分運(yùn)行時(shí)存儲(chǔ)器的劃分二、活動(dòng)記錄二、活動(dòng)記錄 1.活動(dòng)記錄：活動(dòng)記錄：為了管理過(guò)程在一次執(zhí)行中所需要的信息，使為了管理過(guò)程在一次執(zhí)行中所需要的信息，使 用一個(gè)連續(xù)的存儲(chǔ)塊，該連續(xù)的存儲(chǔ)塊叫活動(dòng)記錄。用一個(gè)連續(xù)的存儲(chǔ)塊，該連續(xù)的存

4、儲(chǔ)塊叫活動(dòng)記錄。 當(dāng)過(guò)程調(diào)用時(shí)當(dāng)過(guò)程調(diào)用時(shí)，產(chǎn)生一個(gè)過(guò)程的新的活動(dòng)，用一個(gè)活動(dòng)記錄表，產(chǎn)生一個(gè)過(guò)程的新的活動(dòng)，用一個(gè)活動(dòng)記錄表 示該活動(dòng)的相關(guān)信息，并將其壓入棧。示該活動(dòng)的相關(guān)信息，并將其壓入棧。 當(dāng)過(guò)程返回時(shí)當(dāng)過(guò)程返回時(shí)，將該活動(dòng)記錄從棧中彈出。，將該活動(dòng)記錄從棧中彈出。9.2 運(yùn)行時(shí)存儲(chǔ)器的劃分運(yùn)行時(shí)存儲(chǔ)器的劃分2.活動(dòng)記錄的內(nèi)容活動(dòng)記錄的內(nèi)容（1）連接數(shù)據(jù)）連接數(shù)據(jù) SP指向現(xiàn)行過(guò)程的活動(dòng)記錄在棧里的起始位置。指向現(xiàn)行過(guò)程的活動(dòng)記錄在棧里的起始位置。 返回地址返回地址 動(dòng)態(tài)鏈動(dòng)態(tài)鏈指向調(diào)用該過(guò)程前的最新活動(dòng)記錄地址的指針。指向調(diào)用該過(guò)程前的最新活動(dòng)記錄地址的指針。 靜態(tài)鏈靜態(tài)鏈指向靜態(tài)直

5、接外層最新活動(dòng)記錄地址的指針，指向靜態(tài)直接外層最新活動(dòng)記錄地址的指針， 用來(lái)訪問(wèn)非局部數(shù)據(jù)用來(lái)訪問(wèn)非局部數(shù)據(jù).（2）形式單元）形式單元存放相應(yīng)的實(shí)在參數(shù)的地址或值存放相應(yīng)的實(shí)在參數(shù)的地址或值（3）局部數(shù)據(jù)區(qū)）局部數(shù)據(jù)區(qū) 局部變量局部變量簡(jiǎn)單變量簡(jiǎn)單變量 內(nèi)情向量?jī)?nèi)情向量局部數(shù)據(jù)的內(nèi)情向量，即數(shù)組元素局部數(shù)據(jù)的內(nèi)情向量，即數(shù)組元素 臨時(shí)工作單元臨時(shí)工作單元存放對(duì)表達(dá)式求值的結(jié)果存放對(duì)表達(dá)式求值的結(jié)果9.2 運(yùn)行時(shí)存儲(chǔ)器的劃分運(yùn)行時(shí)存儲(chǔ)器的劃分9.2 運(yùn)行時(shí)存儲(chǔ)器的劃分運(yùn)行時(shí)存儲(chǔ)器的劃分三、存儲(chǔ)分配策略 1.靜態(tài)存儲(chǔ)分配策略靜態(tài)存儲(chǔ)分配策略 在編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元，且在編譯時(shí)對(duì)所

6、有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元，且 在運(yùn)行時(shí)始終保持不變。在運(yùn)行時(shí)始終保持不變。2.棧式動(dòng)態(tài)分配策略棧式動(dòng)態(tài)分配策略 在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，運(yùn)行時(shí)，每當(dāng)調(diào)在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，運(yùn)行時(shí)，每當(dāng)調(diào)用一個(gè)過(guò)程，它所需要的存儲(chǔ)空間就動(dòng)態(tài)地分配于棧頂，一旦用一個(gè)過(guò)程，它所需要的存儲(chǔ)空間就動(dòng)態(tài)地分配于棧頂，一旦退出，它所占空間就予以釋放。退出，它所占空間就予以釋放。3.堆式動(dòng)態(tài)分配策略堆式動(dòng)態(tài)分配策略 在運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存儲(chǔ)空在運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存儲(chǔ)空間的申請(qǐng)與歸還（回收），凡申請(qǐng)者從堆中分給一塊，凡釋放間的申請(qǐng)與歸還（回收），凡申請(qǐng)者

7、從堆中分給一塊，凡釋放者退回給堆者退回給堆.9.4 簡(jiǎn)單的棧式存儲(chǔ)分配1.前提：前提：假設(shè)程序語(yǔ)言無(wú)分程序結(jié)構(gòu)，過(guò)程定義不允假設(shè)程序語(yǔ)言無(wú)分程序結(jié)構(gòu)，過(guò)程定義不允 許嵌套，但允許過(guò)程的遞歸調(diào)用。許嵌套，但允許過(guò)程的遞歸調(diào)用。例如：例如：C 語(yǔ)言語(yǔ)言2.過(guò)程：過(guò)程：運(yùn)行時(shí)運(yùn)行時(shí)每當(dāng)進(jìn)入一個(gè)過(guò)程每當(dāng)進(jìn)入一個(gè)過(guò)程 即一個(gè)新的活動(dòng)開(kāi)始，就把其它活動(dòng)記錄壓入棧（置即一個(gè)新的活動(dòng)開(kāi)始，就把其它活動(dòng)記錄壓入棧（置于棧頂），從而形成過(guò)程工作時(shí)的數(shù)據(jù)區(qū)于棧頂），從而形成過(guò)程工作時(shí)的數(shù)據(jù)區(qū).當(dāng)活動(dòng)結(jié)束當(dāng)活動(dòng)結(jié)束 即過(guò)程退出時(shí)，再把其活動(dòng)記錄彈出棧，這樣，它在即過(guò)程退出時(shí)，再把其活動(dòng)記錄彈出棧，這樣，它在棧頂上的數(shù)

8、據(jù)區(qū)也隨即不復(fù)存在棧頂上的數(shù)據(jù)區(qū)也隨即不復(fù)存在.3.舉例舉例 （1）主程序調(diào)用過(guò)程）主程序調(diào)用過(guò)程Q，而，而Q又調(diào)用又調(diào)用R， 在在R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu).9.4 簡(jiǎn)單的棧式存儲(chǔ)分配R的活動(dòng)記錄Q的活動(dòng)記錄Main的活動(dòng)記錄全局?jǐn)?shù)據(jù)SPTOP靜態(tài)分配3.舉例舉例（2）主程序調(diào)用過(guò)程）主程序調(diào)用過(guò)程Q，Q遞歸調(diào)用自己，在遞歸調(diào)用自己，在Q過(guò)程過(guò)程 第二次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)第二次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu).9.4 簡(jiǎn)單的棧式存儲(chǔ)分配Q2的活動(dòng)記錄Q1的活動(dòng)記錄Main的活動(dòng)記錄全局?jǐn)?shù)據(jù)9.4 簡(jiǎn)單的棧式存儲(chǔ)分配3.舉例舉例（3）主程序先調(diào)用過(guò)程）主程序先調(diào)用過(guò)程Q，然后主程序調(diào)用，

9、然后主程序調(diào)用R，且過(guò)，且過(guò) 程程Q不調(diào)用不調(diào)用Q和和R.R的活動(dòng)記錄Main的活動(dòng)記錄全局?jǐn)?shù)據(jù)4.指示器指示器SP總是指向現(xiàn)行過(guò)程活動(dòng)記錄的總是指向現(xiàn)行過(guò)程活動(dòng)記錄的起點(diǎn)，用于訪問(wèn)局部數(shù)據(jù)起點(diǎn)，用于訪問(wèn)局部數(shù)據(jù). 指示器指示器TOP始終指向（已占用）棧頂單元始終指向（已占用）棧頂單元.9.4 簡(jiǎn)單的棧式存儲(chǔ)分配一、C的活動(dòng)記錄 1.C的活動(dòng)記錄的項(xiàng)目的活動(dòng)記錄的項(xiàng)目 （1）連接數(shù)據(jù)連接數(shù)據(jù)A.老老SP值值: 即前一活動(dòng)記錄的地址即前一活動(dòng)記錄的地址 B.返回地址返回地址 （2）參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù) （3）形式單元形式單元存放實(shí)在參數(shù)的值或地址存放實(shí)在參數(shù)的值或地址 （4）過(guò)程的局部變量過(guò)程的局部

10、變量數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量 臨時(shí)工作單元臨時(shí)工作單元 臨時(shí)工作單元臨時(shí)工作單元內(nèi)情向量?jī)?nèi)情向量簡(jiǎn)單變量簡(jiǎn)單變量形式單元形式單元參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址老老SPSPTOPSP9.4 簡(jiǎn)單的棧式存儲(chǔ)分配2.（1）不允許過(guò)程嵌套）不允許過(guò)程嵌套非局部量?jī)H能出現(xiàn)在源程非局部量?jī)H能出現(xiàn)在源程 序頭，可采用靜態(tài)存儲(chǔ)分配，編譯時(shí)可確定其地址序頭，可采用靜態(tài)存儲(chǔ)分配，編譯時(shí)可確定其地址 （2）局部變量或形參在活動(dòng)記錄中的位置確定）局部變量或形參在活動(dòng)記錄中的位置確定 即對(duì)它們都分配了存儲(chǔ)單元，其地址是相對(duì)于活動(dòng)記錄即對(duì)它們都分配了存儲(chǔ)單元，其地址是相對(duì)于活動(dòng)記錄 的基地址的基地址SP的的 絕對(duì)地址絕

11、對(duì)地址=活動(dòng)記錄基地址活動(dòng)記錄基地址+相對(duì)地址相對(duì)地址 變址訪問(wèn)變址訪問(wèn)XSP X代表相對(duì)數(shù)，即相對(duì)于活動(dòng)記錄起點(diǎn)的地址，編譯代表相對(duì)數(shù)，即相對(duì)于活動(dòng)記錄起點(diǎn)的地址，編譯 時(shí)可完全確定下來(lái)時(shí)可完全確定下來(lái).9.4 簡(jiǎn)單的棧式存儲(chǔ)分配二、C的過(guò)程調(diào)用,過(guò)程進(jìn)入、數(shù)組空間分配 和過(guò)程返回已知過(guò)程調(diào)用的四元式序列為：par T1 par Tn call P,n9.4 簡(jiǎn)單的棧式存儲(chǔ)分配C語(yǔ)言過(guò)程調(diào)用與返回Par Ti(i+3)TOP := Ti （傳值） 或(i+3)TOP := addr(Ti)（傳地址）Call P,n1TOP := SP3 TOP := nJSR P (轉(zhuǎn)P)SP := TOP

12、+11SP := 返回地址TOP := TOP + 活動(dòng)單元數(shù)Return(E)TOP := SP1SP := 0SPX := 2TOPUJ 0 x /* UJ:無(wú)條件轉(zhuǎn)移*/9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)前提：前提：假定允許過(guò)程定義嵌套，如假定允許過(guò)程定義嵌套，如PascalPascal語(yǔ)言，語(yǔ)言， 但去掉但去掉PascalPascal中的中的“文件。文件。程序舉例：程序舉例：課本P258 圖9.15一、非局部名字的訪問(wèn)的實(shí)現(xiàn)一、非局部名字的訪問(wèn)的實(shí)現(xiàn)9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)1.1.靜態(tài)鏈和活動(dòng)記錄靜態(tài)鏈和活動(dòng)記錄 A.A.靜

13、態(tài)鏈靜態(tài)鏈活動(dòng)記錄的一個(gè)域，從一個(gè)過(guò)程的當(dāng)前活活動(dòng)記錄的一個(gè)域，從一個(gè)過(guò)程的當(dāng)前活 動(dòng)記錄指向其靜態(tài)直接外層的最新活動(dòng)記錄。動(dòng)記錄指向其靜態(tài)直接外層的最新活動(dòng)記錄。動(dòng)態(tài)鏈動(dòng)態(tài)鏈活動(dòng)記錄一個(gè)域，從一個(gè)過(guò)程的當(dāng)前活動(dòng)記錄活動(dòng)記錄一個(gè)域，從一個(gè)過(guò)程的當(dāng)前活動(dòng)記錄 指向調(diào)用該過(guò)程前正在運(yùn)行的過(guò)程的最新的活指向調(diào)用該過(guò)程前正在運(yùn)行的過(guò)程的最新的活 動(dòng)記錄的基地址。動(dòng)記錄的基地址。B.B.活動(dòng)記錄結(jié)構(gòu)活動(dòng)記錄結(jié)構(gòu)P259 P259 圖圖9.169.16C.C.程序運(yùn)行時(shí)棧的變化過(guò)程程序運(yùn)行時(shí)棧的變化過(guò)程 舉例：舉例：ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0 xa0返回地址0ic0(形參個(gè)數(shù)

14、)0返回地址0 xa0返回地址0過(guò)程過(guò)程S中調(diào)中調(diào)用用Q時(shí)時(shí)161514131211109876543210SPTOPTOPSP109876543210過(guò)程過(guò)程P中中調(diào)用調(diào)用S時(shí)時(shí)dcv(形參)u(形參)2(形參個(gè)數(shù))11返回地址11ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0 xa0返回地址0TOPSP1211109876543210242322212019181716151413過(guò)程過(guò)程Q中調(diào)用中調(diào)用R時(shí)時(shí)dcvu211返回地址17dcv(形參)u(形參)2(形參個(gè)數(shù))11返回地址11ib(形參)1(形參個(gè)數(shù))0返回地址5ic00返回地址0 xa0返回地址03231302928

15、2726252423222120191817161514131211109876543210SPTOP過(guò)程過(guò)程R中遞歸調(diào)用中遞歸調(diào)用R靜態(tài)鏈靜態(tài)鏈: :通過(guò)其值可以找到當(dāng)前過(guò)程通過(guò)其值可以找到當(dāng)前過(guò)程/ /活動(dòng)可以引用的活動(dòng)可以引用的“非非 局部變量局部變量”的過(guò)程的活動(dòng)記錄的基址，從而找到的過(guò)程的活動(dòng)記錄的基址，從而找到要要 引用的引用的“非局部變量非局部變量”。9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)動(dòng)態(tài)鏈動(dòng)態(tài)鏈: :通過(guò)其值可以找到當(dāng)前過(guò)程通過(guò)其值可以找到當(dāng)前過(guò)程/ /活動(dòng)結(jié)束后，需要返回的活動(dòng)結(jié)束后，需要返回的 上一層活動(dòng)記錄的基址上一層活動(dòng)記錄的基址SPSP。D.

16、D.含義：含義：2.2.嵌套層次顯示表（嵌套層次顯示表（displaydisplay）和活動(dòng)記錄）和活動(dòng)記錄2 2R R的現(xiàn)行活動(dòng)記錄地址（的現(xiàn)行活動(dòng)記錄地址（SPSP的現(xiàn)行值）的現(xiàn)行值）1 1Q Q的最新活動(dòng)記錄的地址的最新活動(dòng)記錄的地址0 0P P的活動(dòng)記里的地址的活動(dòng)記里的地址9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)A.A.嵌套層次顯示表：嵌套層次顯示表：每進(jìn)入一個(gè)過(guò)程后，在建立它的每進(jìn)入一個(gè)過(guò)程后，在建立它的 活動(dòng)區(qū)的同時(shí)建立該表。活動(dòng)區(qū)的同時(shí)建立該表。B.B.表的內(nèi)容：表的內(nèi)容：舉例：舉例：令過(guò)程令過(guò)程R R的外層為的外層為Q Q，Q Q的外層為的外層為P P，則

17、，則R R運(yùn)行時(shí)運(yùn)行時(shí)display display 表為：表為：C.“C.“非局部量非局部量”地址的確定：地址的確定：絕對(duì)地址絕對(duì)地址= display= display靜態(tài)層數(shù)靜態(tài)層數(shù)+相對(duì)地址相對(duì)地址D.D.活動(dòng)記錄結(jié)構(gòu)活動(dòng)記錄結(jié)構(gòu): : P261 P261 圖圖9.189.18E.E.程序運(yùn)行時(shí)棧的變化過(guò)程程序運(yùn)行時(shí)棧的變化過(guò)程 P262-263 P262-263 圖圖9.199.19 TOPa321SP 0臨時(shí)單元臨時(shí)單元內(nèi)情向量?jī)?nèi)情向量簡(jiǎn)單變量簡(jiǎn)單變量display形參單元形參單元參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)全局全局DisplayDisplay返回地址返回地址老老SP(SP(動(dòng)態(tài)鏈動(dòng)態(tài)鏈) )

18、9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)F.F.靜態(tài)鏈方法與顯示表方法的比較：靜態(tài)鏈方法與顯示表方法的比較： 通過(guò)顯示表訪問(wèn)非局部量要比沿著靜態(tài)鏈訪問(wèn)非局部通過(guò)顯示表訪問(wèn)非局部量要比沿著靜態(tài)鏈訪問(wèn)非局部量的速度快。量的速度快。原因：原因：因?yàn)橥ㄟ^(guò)顯示表的一個(gè)域，可以確定任意外層活因?yàn)橥ㄟ^(guò)顯示表的一個(gè)域，可以確定任意外層活 動(dòng)記錄的指針，再沿著這個(gè)指針便可以找到處于動(dòng)記錄的指針，再沿著這個(gè)指針便可以找到處于 外層活動(dòng)記錄的非局部量。外層活動(dòng)記錄的非局部量。9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)1

19、.par T1.par T T T為數(shù)組為數(shù)組（1 1）或者傳遞數(shù)組）或者傳遞數(shù)組T T的首地址的首地址（2 2）或者傳遞數(shù)組）或者傳遞數(shù)組T T的內(nèi)情向量地址的內(nèi)情向量地址 2.Par T2.Par TT T為過(guò)程為過(guò)程 假設(shè)：過(guò)程假設(shè)：過(guò)程P P把過(guò)程把過(guò)程T T作為在世在參數(shù)傳遞過(guò)程作為在世在參數(shù)傳遞過(guò)程Q Q，隨，隨 后，后，Q Q又通過(guò)引用相應(yīng)的形式參數(shù)調(diào)用又通過(guò)引用相應(yīng)的形式參數(shù)調(diào)用T T。 3.Par T3.Par T T T為標(biāo)號(hào)為標(biāo)號(hào)二二. .參數(shù)傳遞的實(shí)現(xiàn)參數(shù)傳遞的實(shí)現(xiàn) 在進(jìn)入在進(jìn)入T T之后，為了建立之后，為了建立T T自己的自己的display display ，T T

20、必須知道它直接必須知道它直接 外層的外層的displaydisplay。 又又P P的的display display 或者或者正好就是這個(gè)外層的正好就是這個(gè)外層的displaydisplay， 或者或者包含了這個(gè)外層包含了這個(gè)外層displaydisplay 而由于而由于T T的層數(shù)是已知的的層數(shù)是已知的 只要知道只要知道P P的的displaydisplay，T T就可以用它來(lái)建立自己的就可以用它來(lái)建立自己的displaydisplay。 即假定即假定T T的層數(shù)為的層數(shù)為1 1，則，則T T的的displaydisplay乃是由乃是由P P的的displaydisplay的前的前1 1個(gè)

21、單元的個(gè)單元的 內(nèi)容和內(nèi)容和SPSP的現(xiàn)行值所組成。的現(xiàn)行值所組成。為了使得過(guò)程為了使得過(guò)程T T工作時(shí)能夠知道過(guò)程工作時(shí)能夠知道過(guò)程P P的的displaydisplay，必須在，必須在P P把把T T作為實(shí)作為實(shí) 參傳遞給參傳遞給Q Q的時(shí)候把的時(shí)候把P P自身的自身的displaydisplay地址也傳過(guò)去。地址也傳過(guò)去。即：過(guò)程即：過(guò)程P P中的中的par Tpar T的作用可刻畫為建立如下所示的兩個(gè)相繼臨時(shí)單元：的作用可刻畫為建立如下所示的兩個(gè)相繼臨時(shí)單元：第一個(gè)臨時(shí)單元第一個(gè)臨時(shí)單元B1B1：過(guò)程過(guò)程T T的入口地址；的入口地址；第二個(gè)臨時(shí)單元第二個(gè)臨時(shí)單元B2B2：現(xiàn)行的現(xiàn)行的d

22、isplaydisplay地址。；地址。； 然后執(zhí)行（然后執(zhí)行（i+1i+1）TOP:=addr(B1)TOP:=addr(B1)把第一臨時(shí)單元把第一臨時(shí)單元B1B1的地址傳給的地址傳給Q Q9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)2.Par T2.Par TT T為過(guò)程為過(guò)程假定過(guò)程假定過(guò)程Q Q現(xiàn)在執(zhí)行到調(diào)用語(yǔ)句現(xiàn)在執(zhí)行到調(diào)用語(yǔ)句call Z, mcall Z, m Z Z形式參數(shù)，形式單元形式參數(shù)，形式單元Z Z中已含有上述中已含有上述B B1 1的地址的地址 故故B B1 1的內(nèi)容將用來(lái)作為轉(zhuǎn)子指令的目的地址的內(nèi)容將用來(lái)作為轉(zhuǎn)子指令的目的地址（即轉(zhuǎn)進(jìn)過(guò)程（即轉(zhuǎn)進(jìn)過(guò)程

23、T T） B B2 2的內(nèi)容將作為的內(nèi)容將作為“全局全局displaydisplay地址地址”（第三項(xiàng)連接數(shù)據(jù)）傳送給（第三項(xiàng)連接數(shù)據(jù)）傳送給T T9.5 9.5 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)2.Par T2.Par TT T為過(guò)程為過(guò)程9.6 9.6 堆式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)分配1.1.堆式動(dòng)態(tài)存儲(chǔ)分配使用的情況堆式動(dòng)態(tài)存儲(chǔ)分配使用的情況（1 1）允許用戶自由地申請(qǐng)數(shù)據(jù)空間和退還空間）允許用戶自由地申請(qǐng)數(shù)據(jù)空間和退還空間（2 2）不僅有過(guò)程而且有進(jìn)程的程序結(jié)構(gòu)）不僅有過(guò)程而且有進(jìn)程的程序結(jié)構(gòu)即空間的使用未必服從即空間的使用未必服從“先請(qǐng)后還，后請(qǐng)先還先請(qǐng)后還，后請(qǐng)先還”的原則的原則例如：例如：PascalPascal語(yǔ)言中的標(biāo)準(zhǔn)過(guò)程語(yǔ)言中的標(biāo)準(zhǔn)過(guò)程new-disposenew-dispose2.2.該種分配方法必須考慮的幾個(gè)主要問(wèn)題該種分配方法必須考慮的幾個(gè)主要問(wèn)題（1 1）當(dāng)運(yùn)行程序要求一塊體積為）當(dāng)運(yùn)行程序要求一塊體積為N N的空間時(shí)，應(yīng)該分配哪一塊的空間時(shí)，應(yīng)該分配哪一塊 給它？給它？（2 2）如果運(yùn)行程序要求一塊體積為）如果運(yùn)行程序要求一塊體積為N N的空間，但所有空閑塊的的空間，但所有空閑塊的 總和也不夠總和也不夠N N，那該怎么辦？，那該怎么辦？一、堆式動(dòng)態(tài)存儲(chǔ)分配的實(shí)現(xiàn)一、堆式動(dòng)態(tài)存儲(chǔ)分配的實(shí)現(xiàn)1.1.定長(zhǎng)塊管理定長(zhǎng)塊