第10章目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織

1、第第1010章章 目標(biāo)程序運(yùn)行時(shí)的組織目標(biāo)程序運(yùn)行時(shí)的組織 教學(xué)要求：本章介紹目標(biāo)程序運(yùn)行時(shí)的教學(xué)要求：本章介紹目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織方式，包括靜態(tài)存儲(chǔ)分配和動(dòng)存儲(chǔ)組織方式，包括靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配。態(tài)存儲(chǔ)分配。 要求掌握各種存儲(chǔ)組織形要求掌握各種存儲(chǔ)組織形式的基本方法。式的基本方法。 教學(xué)重點(diǎn)：靜態(tài)分配策略和動(dòng)態(tài)分配策教學(xué)重點(diǎn)：靜態(tài)分配策略和動(dòng)態(tài)分配策略的基本思想，嵌套過(guò)程語(yǔ)言棧式分配，略的基本思想，嵌套過(guò)程語(yǔ)言棧式分配，活動(dòng)記錄、運(yùn)行時(shí)棧的組織?；顒?dòng)記錄、運(yùn)行時(shí)棧的組織。 10.1 10.1 概述概述 從邏輯上看，代碼生成前，編譯程序必須從邏輯上看，代碼生成前，編譯程序必須進(jìn)行目標(biāo)

2、程序運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間的分配的分配 數(shù)據(jù)空間包括：用戶定義的各種類型的數(shù)數(shù)據(jù)空間包括：用戶定義的各種類型的數(shù)據(jù)對(duì)象（變量和常量）所需的存儲(chǔ)空間，據(jù)對(duì)象（變量和常量）所需的存儲(chǔ)空間，作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元，調(diào)用過(guò)程時(shí)所需的連接單元，組織單元，調(diào)用過(guò)程時(shí)所需的連接單元，組織輸入輸入/ /輸出所需的緩沖區(qū)。輸出所需的緩沖區(qū)。存儲(chǔ)管理復(fù)雜度取決于源語(yǔ)言本身，具體包括：存儲(chǔ)管理復(fù)雜度取決于源語(yǔ)言本身，具體包括：允許的數(shù)據(jù)類型的多少允許的數(shù)據(jù)類型的多少? ?語(yǔ)言中允許的數(shù)據(jù)項(xiàng)是語(yǔ)言中允許的數(shù)據(jù)項(xiàng)是: : 靜態(tài)確

3、定靜態(tài)確定? ?動(dòng)態(tài)確定動(dòng)態(tài)確定? ?程序決定名字的作用域的規(guī)則和結(jié)構(gòu)程序決定名字的作用域的規(guī)則和結(jié)構(gòu)段結(jié)構(gòu)段結(jié)構(gòu)? ?過(guò)程定義不嵌套過(guò)程定義不嵌套? ?只允許過(guò)程遞歸調(diào)用只允許過(guò)程遞歸調(diào)用? ?分程序結(jié)構(gòu)分程序結(jié)構(gòu): : 分程序嵌套分程序嵌套? ?過(guò)程定義嵌套過(guò)程定義嵌套? ? 目標(biāo)代碼區(qū)目標(biāo)代碼區(qū) 靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū) Stack heap目標(biāo)代碼區(qū)用以存放目標(biāo)代碼，這是目標(biāo)代碼區(qū)用以存放目標(biāo)代碼，這是固定長(zhǎng)度的，即編譯時(shí)能確定的。固定長(zhǎng)度的，即編譯時(shí)能確定的。靜態(tài)數(shù)據(jù)區(qū)用以存放編譯時(shí)能確定所靜態(tài)數(shù)據(jù)區(qū)用以存放編譯時(shí)能確定所占用空間的數(shù)據(jù)。占用空間的數(shù)據(jù)。堆堆/棧用于存放可變數(shù)據(jù)以及管理過(guò)

4、棧用于存放可變數(shù)據(jù)以及管理過(guò)程活動(dòng)的控制信息。程活動(dòng)的控制信息。三種數(shù)據(jù)區(qū)對(duì)應(yīng)著下述三種不同的分配策略三種數(shù)據(jù)區(qū)對(duì)應(yīng)著下述三種不同的分配策略在編譯時(shí)能確定在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置對(duì)任何局部變量對(duì)任何局部變量X X的引的引用可表示為變址訪問(wèn)用可表示為變址訪問(wèn): : dxSP dxSP dx: dx: 變量變量X X相對(duì)于活相對(duì)于活動(dòng)記錄起點(diǎn)的地址，動(dòng)記錄起點(diǎn)的地址，在編譯時(shí)可確定。在編譯時(shí)可確

5、定。SP 012TOP 每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容( (非嵌套語(yǔ)言非嵌套語(yǔ)言) )臨時(shí)單臨時(shí)單元元內(nèi)情向內(nèi)情向量量局部變局部變量量形式單形式單元元參數(shù)個(gè)參數(shù)個(gè)數(shù)數(shù)動(dòng)態(tài)鏈動(dòng)態(tài)鏈返回地返回地址址q連接數(shù)據(jù)連接數(shù)據(jù)返回地址返回地址動(dòng)態(tài)鏈：指向調(diào)用該動(dòng)態(tài)鏈：指向調(diào)用該過(guò)程的最新活動(dòng)記錄過(guò)程的最新活動(dòng)記錄地址的指針。地址的指針。靜態(tài)鏈：指向直接外靜態(tài)鏈：指向直接外層最新活動(dòng)記錄地址層最新活動(dòng)記錄地址的指針，用來(lái)訪問(wèn)非的指針，用來(lái)訪問(wèn)非局部數(shù)據(jù)。局部數(shù)據(jù)。SP 012TOP 每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容( (嵌套語(yǔ)言嵌套語(yǔ)言) )臨時(shí)單臨時(shí)單元元內(nèi)情向內(nèi)情向量量局部變局部

6、變量量形式單形式單元元靜態(tài)鏈靜態(tài)鏈動(dòng)態(tài)鏈動(dòng)態(tài)鏈返回地返回地址址q形式單元：存放相形式單元：存放相應(yīng)的實(shí)參的地址或應(yīng)的實(shí)參的地址或值。值。q局部數(shù)據(jù)區(qū)：局部局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、變量、內(nèi)情向量、臨時(shí)工作單元（如臨時(shí)工作單元（如存放對(duì)表達(dá)式求值存放對(duì)表達(dá)式求值的結(jié)果）。的結(jié)果）。SP 012TOP 每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容臨時(shí)單元臨時(shí)單元內(nèi)情向量?jī)?nèi)情向量局部變量局部變量形式單元形式單元靜態(tài)鏈靜態(tài)鏈動(dòng)態(tài)鏈動(dòng)態(tài)鏈返回地址返回地址 1 1、 call P call P 被翻譯成被翻譯成: :11TOP:=SP (TOP:=SP (保護(hù)現(xiàn)行保護(hù)現(xiàn)行SP)SP)JSR P (J

7、SR P (轉(zhuǎn)子指令轉(zhuǎn)子指令) )參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量?jī)?nèi)情向量局部變量局部變量老老SP臨時(shí)單元臨時(shí)單元活動(dòng)記錄的填寫活動(dòng)記錄的填寫TOP SP 調(diào)用過(guò)程的調(diào)用過(guò)程的活動(dòng)記錄活動(dòng)記錄老老SP2 2、轉(zhuǎn)進(jìn)過(guò)程、轉(zhuǎn)進(jìn)過(guò)程P P后，首先應(yīng)執(zhí)行下述指令后，首先應(yīng)執(zhí)行下述指令: :SP:=TOP+1 (SP:=TOP+1 (定義新的定義新的SP)SP)1SP:=1SP:=返回地址返回地址 ( (保護(hù)返回地址保護(hù)返回地址) )TOP:=TOP+L (TOP:=TOP+L (新新TOP)TOP) L L：過(guò)程過(guò)程P P的活動(dòng)記錄所需單元數(shù)，的活動(dòng)記錄所需單元數(shù)， 在編譯時(shí)可

8、確定。在編譯時(shí)可確定。 參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量?jī)?nèi)情向量局部變量局部變量老老SP臨時(shí)單元臨時(shí)單元TOP 調(diào)用過(guò)程的活動(dòng)記錄調(diào)用過(guò)程的活動(dòng)記錄返回地址返回地址TOPSP3 3、 過(guò)程返回時(shí)，應(yīng)執(zhí)行下列指令過(guò)程返回時(shí)，應(yīng)執(zhí)行下列指令: :TOP:=SP-1 (TOP:=SP-1 (恢復(fù)調(diào)用前恢復(fù)調(diào)用前TOP)TOP)X:=2TOP (X:=2TOP (把返回地址取到把返回地址取到X X中中) ) SP:=0SP (SP:=0SP (恢復(fù)調(diào)用前恢復(fù)調(diào)用前SP)SP)UJ X (UJ X (按按X X返回返回) )參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)返回地址返回地址形式單元形式單元內(nèi)情向量

9、內(nèi)情向量局部變量局部變量老老SP臨時(shí)單元臨時(shí)單元調(diào)用過(guò)程的活動(dòng)記錄調(diào)用過(guò)程的活動(dòng)記錄TOPSPSPTOP 例例:Main( ) Main中的數(shù)據(jù)說(shuō)明中的數(shù)據(jù)說(shuō)明 proc R( ) R中的數(shù)據(jù)說(shuō)明中的數(shù)據(jù)說(shuō)明 proc Q( ) Q中的數(shù)據(jù)說(shuō)明中的數(shù)據(jù)說(shuō)明 主程序主程序過(guò)程過(guò)程Q 過(guò)程過(guò)程RQ的活動(dòng)記錄的活動(dòng)記錄TOPR的活動(dòng)記錄的活動(dòng)記錄SP主程序活動(dòng)記錄主程序活動(dòng)記錄全局?jǐn)?shù)據(jù)區(qū)全局?jǐn)?shù)據(jù)區(qū) R R的數(shù)組區(qū)的數(shù)組區(qū) R R的活動(dòng)記錄的活動(dòng)記錄 Q Q的活動(dòng)記錄的活動(dòng)記錄 主程序全局主程序全局 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)分配了數(shù)組區(qū)之后的運(yùn)行棧分配了數(shù)組區(qū)之后的運(yùn)行棧TOPSP PASCALPASCALPAS

10、CALPASCAL程序本身可以看成是一個(gè)操作程序本身可以看成是一個(gè)操作系統(tǒng)所調(diào)用的過(guò)程，過(guò)程可以嵌套和系統(tǒng)所調(diào)用的過(guò)程，過(guò)程可以嵌套和遞歸。遞歸。一個(gè)一個(gè)PASCALPASCAL過(guò)程：過(guò)程：過(guò)程頭；過(guò)程頭；說(shuō)明段（由一系列的說(shuō)明語(yǔ)句組成）；說(shuō)明段（由一系列的說(shuō)明語(yǔ)句組成）；beginbegin執(zhí)行體（由一系列的執(zhí)行語(yǔ)句組成）；執(zhí)行體（由一系列的執(zhí)行語(yǔ)句組成）；endend作用域作用域：一個(gè)名字能被使用的區(qū)域范圍：一個(gè)名字能被使用的區(qū)域范圍稱作這個(gè)名字的作用域。稱作這個(gè)名字的作用域。允許同一個(gè)標(biāo)識(shí)符在不同的過(guò)程中代表允許同一個(gè)標(biāo)識(shí)符在不同的過(guò)程中代表不同的名字。不同的名字。名字作用域規(guī)則名字作用

11、域規(guī)則- 最近嵌套原則最近嵌套原則 一個(gè)在子程序一個(gè)在子程序B1B1中說(shuō)明的名字中說(shuō)明的名字X X只在只在B1B1中有效（局部于中有效（局部于B1B1）；）； 如果如果B2B2是是B1B1的一個(gè)內(nèi)層子程序且的一個(gè)內(nèi)層子程序且B2B2中中對(duì)標(biāo)識(shí)符對(duì)標(biāo)識(shí)符X X沒有新的說(shuō)明，則原來(lái)的沒有新的說(shuō)明，則原來(lái)的名字名字X X在在B2B2中仍然有效。如果中仍然有效。如果B2B2對(duì)對(duì)X X重重新作了說(shuō)明，那么，新作了說(shuō)明，那么，B2B2對(duì)對(duì)X X的任何引的任何引用都是指重新說(shuō)明過(guò)的這個(gè)用都是指重新說(shuō)明過(guò)的這個(gè)X X。program main var A, B : real; procedure P1 var

12、 B:boolean; begin end procedure P2 var A:integer; begin endbegin endA(real)B(real)B(bool)A(integr) 非局部名字的訪問(wèn)的實(shí)現(xiàn)非局部名字的訪問(wèn)的實(shí)現(xiàn) 主程序的層次為主程序的層次為0 0；在；在i i層中定義的過(guò)程，層中定義的過(guò)程，其層次為其層次為i+1;i+1; 過(guò)程運(yùn)行時(shí)，必須知道其所有外層過(guò)程的過(guò)程運(yùn)行時(shí)，必須知道其所有外層過(guò)程的當(dāng)前活動(dòng)記錄的起始地址。當(dāng)前活動(dòng)記錄的起始地址。main p1 p2 p3 p4 main過(guò)過(guò)程程定定義義的的嵌嵌套套執(zhí)執(zhí)行行順順序序p2p4p3p3mainmain活動(dòng)

13、記活動(dòng)記錄錄P3P3活動(dòng)記錄活動(dòng)記錄存取鏈存取鏈( (靜靜態(tài)鏈態(tài)鏈) )控制鏈控制鏈( (動(dòng)動(dòng)態(tài)鏈態(tài)鏈) )P3P3活動(dòng)記錄活動(dòng)記錄存取鏈存取鏈( (靜靜態(tài)鏈態(tài)鏈) )控制鏈控制鏈( (動(dòng)動(dòng)態(tài)鏈態(tài)鏈) )P4P4活動(dòng)記錄活動(dòng)記錄存取鏈存取鏈( (靜靜態(tài)鏈態(tài)鏈) )控制鏈控制鏈( (動(dòng)動(dòng)態(tài)鏈態(tài)鏈) )P2P2活動(dòng)記錄活動(dòng)記錄存取鏈存取鏈( (靜靜態(tài)鏈態(tài)鏈) )控制鏈控制鏈( (動(dòng)動(dòng)態(tài)鏈態(tài)鏈) )program P; var x,y: integer; . procedure P1; var i,j:integer; . procedure P11(a,b:integer); . begin .

14、end; begin . call P11(i,j); . end; procedure P2; var s,t:integer; . procedure P21; begin . end; begin . call P1 . end; begin . call P2; . end.012x3y4RA567s8t9152主程序主程序P過(guò)程過(guò)程 P2過(guò)程過(guò)程 P1過(guò)程過(guò)程 P11DisplayP的的活動(dòng)活動(dòng)記錄記錄P2的的活動(dòng)活動(dòng)記錄記錄RA101112i13j142P1的的活動(dòng)活動(dòng)記錄記錄RA151617a18b19P11的活的活動(dòng)記動(dòng)記錄錄3例：例：program main(i,0); 程序

15、結(jié)構(gòu)圖程序結(jié)構(gòu)圖 proc R(c,d); R end /*R*/ proc P (a); 主主 proc Q (b); P Q call R R(x,y); end /*Q*/ call Q Q(z); call P end /*P*/ call R P（W）；）； R（U，V）；）； end /*main*/用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R主程序的主程序的活動(dòng)記錄活動(dòng)記錄 d0spdisplaytop（1） P P的的活動(dòng)記錄活動(dòng)記錄主程序的主程序的活動(dòng)記錄活動(dòng)記錄 d1d0displaysptop（2）用用Display表的方案表的方案(

16、1)主程序主程序-(2)P-(3)Q-(4)RQ Q的的活動(dòng)記錄活動(dòng)記錄 P P的的活動(dòng)記錄活動(dòng)記錄主程序的主程序的活動(dòng)記錄活動(dòng)記錄 displayd2d1d0sptop（3）R R的的活動(dòng)記錄活動(dòng)記錄 Q Q的的活動(dòng)記錄活動(dòng)記錄 P P的的活動(dòng)記錄活動(dòng)記錄主程序的主程序的活動(dòng)記錄活動(dòng)記錄 d1d0 displaytopsp（4） d DISPLAY d DISPLAY 4 4 形式單元形式單元 3 3 參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù) 2 2 全局全局DISPLAYDISPLAY地址地址 1 1 返回地址返回地址 0 0 老老SPSP堆：堆：通常是一片連續(xù)的足夠大的存儲(chǔ)區(qū)，當(dāng)需要通常是一片連續(xù)的足夠大的存儲(chǔ)

17、區(qū)，當(dāng)需要時(shí)，就從堆中分配一小塊存儲(chǔ)區(qū)；用完就及時(shí)退時(shí)，就從堆中分配一小塊存儲(chǔ)區(qū)；用完就及時(shí)退還給堆。還給堆。注：注：在高級(jí)語(yǔ)言中有些數(shù)據(jù)存儲(chǔ)空間的請(qǐng)求與釋在高級(jí)語(yǔ)言中有些數(shù)據(jù)存儲(chǔ)空間的請(qǐng)求與釋放不再遵循后進(jìn)先出的原則，而且是全局性的。放不再遵循后進(jìn)先出的原則，而且是全局性的。為此，需要讓運(yùn)行程序持有一塊專用的全局存儲(chǔ)為此，需要讓運(yùn)行程序持有一塊專用的全局存儲(chǔ)空間來(lái)滿足這些數(shù)據(jù)的存儲(chǔ)要求。這種存儲(chǔ)空間空間來(lái)滿足這些數(shù)據(jù)的存儲(chǔ)要求。這種存儲(chǔ)空間就是堆。就是堆。 10.4 10.4 參數(shù)傳遞參數(shù)傳遞(1)procedure exchangel(i,j:integer);(1)procedure e

18、xchangel(i,j:integer);(2) var x:integer;(2) var x:integer;(3) begin;(3) begin;(4) x:=ai; ai:=aj; aj:=x(4) x:=ai; ai:=aj; aj:=x(5) end;(5) end; 帶有非局部變量和形參的帶有非局部變量和形參的PASCALPASCAL過(guò)程過(guò)程非局變量非局變量aiai和和ajaj的值進(jìn)行交換，的值進(jìn)行交換，i,ji,j為為形參形參傳值的實(shí)現(xiàn)傳值的實(shí)現(xiàn) 1.1.形式參數(shù)當(dāng)作過(guò)程的局部變量處理，形式參數(shù)當(dāng)作過(guò)程的局部變量處理，即在被調(diào)過(guò)程的活動(dòng)記錄中開辟了形參即在被調(diào)過(guò)程的活動(dòng)記錄

19、中開辟了形參的存儲(chǔ)空間，這些存儲(chǔ)位置即是我們所的存儲(chǔ)空間，這些存儲(chǔ)位置即是我們所說(shuō)的形式單元（用以存放實(shí)參）。說(shuō)的形式單元（用以存放實(shí)參）。 2.2.調(diào)用過(guò)程計(jì)算實(shí)參的值，并將其放在調(diào)用過(guò)程計(jì)算實(shí)參的值，并將其放在對(duì)應(yīng)形式單元開辟的空間中。對(duì)應(yīng)形式單元開辟的空間中。 3.3.被調(diào)用過(guò)程執(zhí)行時(shí)，就像使用局部變被調(diào)用過(guò)程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。量一樣使用這些形式單元。 (1)program reference(input,output);(2)var a,b:integer;(3)procedure swap(var x,y:integer);(4) var temp:int

20、eger;(5) begin (6) temp:=x;(7) x:=y;(8) y:=temp(9) end;(10)begin(11) a:=1; b:=2;(12) swap(a,b);(13) writeln(a=,a);writeln(b=,b)(14)end. 帶有過(guò)程帶有過(guò)程swap的的PASCAL程序程序傳地址的實(shí)現(xiàn)傳地址的實(shí)現(xiàn) 把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即調(diào)用過(guò)程把一個(gè)指向?qū)崊⒌拇鎯?chǔ)地址的指針調(diào)用過(guò)程把一個(gè)指向?qū)崊⒌拇鎯?chǔ)地址的指針傳遞給被調(diào)用過(guò)程相應(yīng)的形參：傳遞給被調(diào)用過(guò)程相應(yīng)的形參：1.1.實(shí)在參數(shù)是一個(gè)名字，或具有左值的表達(dá)式實(shí)在

21、參數(shù)是一個(gè)名字，或具有左值的表達(dá)式-傳遞左值傳遞左值2.2.實(shí)在參數(shù)是無(wú)左值的表達(dá)式實(shí)在參數(shù)是無(wú)左值的表達(dá)式-計(jì)算值，放計(jì)算值，放入一存儲(chǔ)單元，傳此存儲(chǔ)單元地址入一存儲(chǔ)單元，傳此存儲(chǔ)單元地址3.3.目標(biāo)代碼中，被調(diào)用過(guò)程對(duì)形參的引用變成目標(biāo)代碼中，被調(diào)用過(guò)程對(duì)形參的引用變成對(duì)傳遞給被調(diào)用過(guò)程的指針的間接引用對(duì)傳遞給被調(diào)用過(guò)程的指針的間接引用 (1)swap(x,y)(1)swap(x,y)(2)int (2)int * *x,x,* *y;y;(3) int temp;(3) int temp;(4)temp=(4)temp=* *x; x; * *x=x=* *y; y; * *y=temp

22、;y=temp;(5) (5) (6)main( )(6)main( )(7) int a=1,b=2;(7) int a=1,b=2;(8) swap(&a,&b);(8) swap(&a,&b);(9) printf(“a is now %d,b is now (9) printf(“a is now %d,b is now %dn”,a,b);%dn”,a,b); 在一個(gè)值調(diào)用過(guò)程中使用指針的在一個(gè)值調(diào)用過(guò)程中使用指針的C C程序程序, ,在在C C程序中無(wú)傳地址所以用指針實(shí)現(xiàn)。程序中無(wú)傳地址所以用指針實(shí)現(xiàn)。 (1)program param(input,output); (2)procedure b(function h(n:in