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

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

教學(xué)要求：本章介紹目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織方式，包括靜態(tài)存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配。要求掌握各種存儲(chǔ)組織形式的基本方法。教學(xué)重點(diǎn)：靜態(tài)分配策略和動(dòng)態(tài)分配策略的基本思想，嵌套過(guò)程語(yǔ)言棧式分配，活動(dòng)記錄、運(yùn)行時(shí)棧的組織。

10.1概述從邏輯上看，代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的設(shè)計(jì)和數(shù)據(jù)空間的分配數(shù)據(jù)空間包括：用戶(hù)定義的各種類(lèi)型的數(shù)據(jù)對(duì)象（變量和常量）所需的存儲(chǔ)空間，作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元，調(diào)用過(guò)程時(shí)所需的連接單元，組織輸入/輸出所需的緩沖區(qū)。存儲(chǔ)管理復(fù)雜度取決于源語(yǔ)言本身，具體包括：允許的數(shù)據(jù)類(lèi)型的多少?語(yǔ)言中允許的數(shù)據(jù)項(xiàng)是:靜態(tài)確定?動(dòng)態(tài)確定?程序決定名字的作用域的規(guī)則和結(jié)構(gòu)段結(jié)構(gòu)?過(guò)程定義不嵌套?只允許過(guò)程遞歸調(diào)用?分程序結(jié)構(gòu):分程序嵌套?過(guò)程定義嵌套?

目標(biāo)代碼區(qū)

靜態(tài)數(shù)據(jù)區(qū)

Stackheap 1、存儲(chǔ)組織：編譯程序?qū)δ繕?biāo)程序運(yùn)行時(shí)的組織（運(yùn)行環(huán)境和分配存儲(chǔ)）。如通常存儲(chǔ)區(qū)布局可為：目標(biāo)代碼區(qū)用以存放目標(biāo)代碼，這是固定長(zhǎng)度的，即編譯時(shí)能確定的。靜態(tài)數(shù)據(jù)區(qū)用以存放編譯時(shí)能確定所占用空間的數(shù)據(jù)。堆/棧用于存放可變數(shù)據(jù)以及管理過(guò)程活動(dòng)的控制信息。三種數(shù)據(jù)區(qū)對(duì)應(yīng)著下述三種不同的分配策略2、存儲(chǔ)分配策略：（1）靜態(tài)存儲(chǔ)分配——在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置。注：1、程序結(jié)構(gòu)特點(diǎn)：不允許遞歸調(diào)用，而且不含有可變數(shù)組。（如FORTRAN語(yǔ)言）。

2、基本策略:在編譯時(shí)，根據(jù)各類(lèi)數(shù)據(jù)所需的存儲(chǔ)空間大小以及存儲(chǔ)方式規(guī)定，在符號(hào)表中建立“名字-地址”對(duì)應(yīng)關(guān)系，然后根據(jù)這些對(duì)應(yīng)關(guān)系進(jìn)行變量名的地址分配。（2）動(dòng)態(tài)存儲(chǔ)分配——在運(yùn)行階段動(dòng)態(tài)地為源程序中的量分配存儲(chǔ)空間。（棧式、堆式）注：1）若某程序設(shè)計(jì)語(yǔ)言允許過(guò)程遞歸調(diào)用，而且允許使用可變數(shù)組，那么在編譯時(shí)就不可能完全為其數(shù)據(jù)項(xiàng)目分配存儲(chǔ)單元，必須采取動(dòng)態(tài)存儲(chǔ)分配策略。

2)動(dòng)態(tài)分配數(shù)據(jù)單元時(shí)一般使用棧，即棧式存儲(chǔ)管理。棧式:簡(jiǎn)單的棧式分配方案嵌套過(guò)程的棧式分配方案分程序結(jié)構(gòu)的存儲(chǔ)分配方案3、過(guò)程活動(dòng)：一個(gè)過(guò)程的活動(dòng)指的是該過(guò)程的一次執(zhí)行。4、活動(dòng)記錄（AR）：一個(gè)過(guò)程的一次執(zhí)行所需要的信息使用一個(gè)連續(xù)的存儲(chǔ)區(qū)來(lái)管理，這個(gè)區(qū)（塊）叫做一個(gè)活動(dòng)記錄。此記錄含有連接數(shù)據(jù)、形式單元、局部變量、局部數(shù)組的內(nèi)情向量和臨時(shí)工作單元等。對(duì)任何局部變量X的引用可表示為變址訪(fǎng)問(wèn):dx[SP]dx:變量X相對(duì)于活動(dòng)記錄起點(diǎn)的地址，在編譯時(shí)可確定。SP012TOP每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容(非嵌套語(yǔ)言)臨時(shí)單元內(nèi)情向量局部變量形式單元參數(shù)個(gè)數(shù)動(dòng)態(tài)鏈返回地址連接數(shù)據(jù)返回地址動(dòng)態(tài)鏈：指向調(diào)用該過(guò)程的最新活動(dòng)記錄地址的指針。靜態(tài)鏈：指向直接外層最新活動(dòng)記錄地址的指針，用來(lái)訪(fǎng)問(wèn)非局部數(shù)據(jù)。SP012TOP每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容(嵌套語(yǔ)言)臨時(shí)單元內(nèi)情向量局部變量形式單元靜態(tài)鏈動(dòng)態(tài)鏈返回地址形式單元：存放相應(yīng)的實(shí)參的地址或值。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時(shí)工作單元（如存放對(duì)表達(dá)式求值的結(jié)果）。SP012TOP每個(gè)過(guò)程的活動(dòng)記錄內(nèi)容臨時(shí)單元內(nèi)情向量局部變量形式單元靜態(tài)鏈動(dòng)態(tài)鏈返回地址臨時(shí)單元內(nèi)情向量局部變量形式單元靜態(tài)鏈動(dòng)態(tài)鏈返回地址

SPTOP連接數(shù)據(jù)(控制信息)SP為當(dāng)前活動(dòng)記錄的起始位置。TOP為棧頂單元。分別放在兩個(gè)寄存器中。訪(fǎng)問(wèn)信息1、

callP被翻譯成:1[TOP]:=SP(保護(hù)現(xiàn)行SP)JSRP(轉(zhuǎn)子指令)參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元活動(dòng)記錄的填寫(xiě)TOP

SP調(diào)用過(guò)程的活動(dòng)記錄老SP2、轉(zhuǎn)進(jìn)過(guò)程P后，首先應(yīng)執(zhí)行下述指令:

SP:=TOP+1

(定義新的SP)1[SP]:=返回地址(保護(hù)返回地址)TOP:=TOP+L

(新TOP)

L：過(guò)程P的活動(dòng)記錄所需單元數(shù)，

在編譯時(shí)可確定。

參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元TOP調(diào)用過(guò)程的活動(dòng)記錄返回地址TOPSP3、

過(guò)程返回時(shí)，應(yīng)執(zhí)行下列指令: TOP:=SP-1(恢復(fù)調(diào)用前TOP) X:=2[TOP](把返回地址取到X中)

SP:=0[SP](恢復(fù)調(diào)用前SP) UJX(按X返回)參數(shù)個(gè)數(shù)返回地址形式單元內(nèi)情向量局部變量老SP臨時(shí)單元調(diào)用過(guò)程的活動(dòng)記錄TOPSPSPTOP

10.2棧式存儲(chǔ)分配的實(shí)現(xiàn)一、簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn)程序結(jié)構(gòu)特點(diǎn)：沒(méi)有分程序結(jié)構(gòu)，過(guò)程定義不嵌套，過(guò)程可遞歸調(diào)用。簡(jiǎn)單棧式分配方案：把存儲(chǔ)區(qū)組織成一個(gè)棧，運(yùn)行時(shí)每進(jìn)入一個(gè)過(guò)程，就把它的活動(dòng)記錄壓入棧，形成過(guò)程工作時(shí)的臨時(shí)數(shù)據(jù)區(qū)，該過(guò)程結(jié)束時(shí)取消該數(shù)據(jù)區(qū)。

例:Main(){ Main中的數(shù)據(jù)說(shuō)明}procR(){ R中的數(shù)據(jù)說(shuō)明}…procQ(){Q中的數(shù)據(jù)說(shuō)明}主程序→過(guò)程Q

→過(guò)程RQ的活動(dòng)記錄TOPR的活動(dòng)記錄SP主程序活動(dòng)記錄全局?jǐn)?shù)據(jù)區(qū)

R的數(shù)組區(qū)

R的活動(dòng)記錄

Q的活動(dòng)記錄主程序全局?jǐn)?shù)據(jù)區(qū)分配了數(shù)組區(qū)之后的運(yùn)行棧TOPSP二、嵌套過(guò)程語(yǔ)言的棧式分配的實(shí)現(xiàn)1、程序結(jié)構(gòu)特點(diǎn)：語(yǔ)言的定義允許嵌套，一個(gè)過(guò)程可以引用包圍它的任一外層過(guò)程所定義的標(biāo)識(shí)符（如變量，數(shù)組或過(guò)程等）（如PASCAL語(yǔ)言）。如何才能引用外層數(shù)據(jù)？2、關(guān)鍵：設(shè)法跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄AR的位置。跟蹤辦法：（1）用靜態(tài)鏈。（2）用DISPLAY表。PASCALPASCAL程序本身可以看成是一個(gè)操作系統(tǒng)所調(diào)用的過(guò)程，過(guò)程可以嵌套和遞歸。一個(gè)PASCAL過(guò)程：過(guò)程頭；說(shuō)明段（由一系列的說(shuō)明語(yǔ)句組成）；begin執(zhí)行體（由一系列的執(zhí)行語(yǔ)句組成）；end作用域：一個(gè)名字能被使用的區(qū)域范圍稱(chēng)作這個(gè)名字的作用域。允許同一個(gè)標(biāo)識(shí)符在不同的過(guò)程中代表不同的名字。名字作用域規(guī)則--"最近嵌套原則"一個(gè)在子程序B1中說(shuō)明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個(gè)內(nèi)層子程序且B2中對(duì)標(biāo)識(shí)符X沒(méi)有新的說(shuō)明，則原來(lái)的名字X在B2中仍然有效。如果B2對(duì)X重新作了說(shuō)明，那么，B2對(duì)X的任何引用都是指重新說(shuō)明過(guò)的這個(gè)X。programmain

varA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integr)

非局部名字的訪(fǎng)問(wèn)的實(shí)現(xiàn)

主程序的層次為0；在i層中定義的過(guò)程，其層次為i+1;過(guò)程運(yùn)行時(shí)，必須知道其所有外層過(guò)程的當(dāng)前活動(dòng)記錄的起始地址。（1）用靜態(tài)鏈在過(guò)程活動(dòng)記錄中增設(shè)靜態(tài)鏈，指向包含該過(guò)程的直接外層過(guò)程的最新活動(dòng)記錄的起始位置。見(jiàn)P223-224mainp1

p2

p3

p4main過(guò)程定義的嵌套執(zhí)行順序→p2→p4→p3→p3main活動(dòng)記錄P3活動(dòng)記錄存取鏈(靜態(tài)鏈)控制鏈(動(dòng)態(tài)鏈)P3活動(dòng)記錄存取鏈(靜態(tài)鏈)控制鏈(動(dòng)態(tài)鏈)P4活動(dòng)記錄存取鏈(靜態(tài)鏈)控制鏈(動(dòng)態(tài)鏈)P2活動(dòng)記錄存取鏈(靜態(tài)鏈)控制鏈(動(dòng)態(tài)鏈)2、用Display表Display表---嵌套層次顯示表當(dāng)前激活過(guò)程的層次為K，它的Display表含有K+1個(gè)單元，依次存放著現(xiàn)行層，直接外層…直至最外層的每一過(guò)程的最新活動(dòng)記錄的基地址。說(shuō)明：1、由于過(guò)程的層數(shù)可以靜態(tài)確定，因此每個(gè)過(guò)程的Display表的體積在編譯時(shí)即可以確定。

2、某過(guò)程p是在層次為i的過(guò)程q內(nèi)定義的，并且q是包圍p的直接外層，那么p的過(guò)程層數(shù)為i+1。programP;

varx,y:integer;...procedureP1;

vari,j:integer;...procedureP11(a,b:integer);...begin...end;begin...callP11(i,j);...end;

procedureP2;

vars,t:integer;...procedureP21;begin...end;begin...callP1...end;begin...callP2;...end.012x3y4RA567s8t9152主程序P

過(guò)程

P2

過(guò)程

P1

過(guò)程

P11DisplayP的活動(dòng)記錄P2的活動(dòng)記錄RA101112i13j142P1的活動(dòng)記錄RA151617a18b19P11的活動(dòng)記錄3例：programmain(i,0);

程序結(jié)構(gòu)圖

……

procR(c,d);

……

R

end/*R*/

procP(a);主

……

procQ(b);

……

P

Q

callR

R(x,y);

end/*Q*/callQ

……

Q(z);callP

end/*P*/

……

callR

P（W）；

……

R（U，V）；

……end/*main*/用Display表的方案(1)主程序--->(2)P--->(3)Q--->(4)R主程序的活動(dòng)記錄

d[0]spdisplaytop（1）

P的活動(dòng)記錄主程序的活動(dòng)記錄

d[1]d[0]displaysptop（2）用Display表的方案(1)主程序--->(2)P--->(3)Q--->(4)RQ的活動(dòng)記錄

P的活動(dòng)記錄主程序的活動(dòng)記錄

displayd[2]d[1]d[0]sptop（3）R的活動(dòng)記錄Q的活動(dòng)記錄

P的活動(dòng)記錄主程序的活動(dòng)記錄

d[1]d[0]

displaytopsp（4）DISPLAY表的維護(hù)和建立

為便于組織存儲(chǔ)區(qū)，將display作為活動(dòng)記錄的一部分，其相對(duì)地址在編譯時(shí)是完全可以確定的。假設(shè)過(guò)程P1可調(diào)用P2，為了能在P2中建立P2的display，在P1調(diào)用P2時(shí)設(shè)法把P1的display地址作為連接數(shù)據(jù)之一（全局display地址）傳送給P2，因此連接數(shù)據(jù)包括：老SP值（動(dòng)態(tài)鏈）返回地址全局display地址

……dDISPLAY4形式單元

3參數(shù)個(gè)數(shù)

2全局DISPLAY地址

1返回地址

0老SP當(dāng)過(guò)程的層次為n，它的display為n+1個(gè)值。一個(gè)過(guò)程被調(diào)用時(shí)，從調(diào)用過(guò)程的DISPLAY表中自下向上抄錄n個(gè)SP值，再加上本層的SP值。

10.3堆式存儲(chǔ)分配

堆：通常是一片連續(xù)的足夠大的存儲(chǔ)區(qū)，當(dāng)需要時(shí)，就從堆中分配一小塊存儲(chǔ)區(qū)；用完就及時(shí)退還給堆。注：在高級(jí)語(yǔ)言中有些數(shù)據(jù)存儲(chǔ)空間的請(qǐng)求與釋放不再遵循后進(jìn)先出的原則，而且是全局性的。為此，需要讓運(yùn)行程序持有一塊專(zhuān)用的全局存儲(chǔ)空間來(lái)滿(mǎn)足這些數(shù)據(jù)的存儲(chǔ)要求。這種存儲(chǔ)空間就是堆。

10.4參數(shù)傳遞(1)procedureexchangel(i,j:integer);(2)varx:integer;(3)begin;(4)x:=a[i];a[i]:=a[j];a[j]:=x(5)end;

帶有非局部變量和形參的PASCAL過(guò)程非局變量a[i]和a[j]的值進(jìn)行交換，i,j為形參傳值的實(shí)現(xiàn)1.形式參數(shù)當(dāng)作過(guò)程的局部變量處理，即在被調(diào)過(guò)程的活動(dòng)記錄中開(kāi)辟了形參的存儲(chǔ)空間，這些存儲(chǔ)位置即是我們所說(shuō)的形式單元（用以存放實(shí)參）。2.調(diào)用過(guò)程計(jì)算實(shí)參的值，并將其放在對(duì)應(yīng)形式單元開(kāi)辟的空間中。3.被調(diào)用過(guò)程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。

(1)programreference(input,output);(2)vara,b:integer;(3)procedureswap({var}x,y:integer);(4)vartemp:integer;(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(chǎn)=‘,a);writeln(‘b=‘,b)(14)end.

帶有過(guò)程swap的PASCAL程序傳地址的實(shí)現(xiàn)

把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即調(diào)用過(guò)程把一個(gè)指向?qū)崊⒌拇鎯?chǔ)地址的指針傳遞給被調(diào)用過(guò)程相應(yīng)的形參：1.實(shí)在參數(shù)是一個(gè)名字，或具有左值的表達(dá)式----傳遞左值2.實(shí)在參數(shù)是無(wú)左值的表達(dá)式----計(jì)算值，放入一存儲(chǔ)單元，傳此存儲(chǔ)單元地址3.目標(biāo)代碼中，被調(diào)用過(guò)程對(duì)形參的引用變成對(duì)傳遞給被調(diào)用過(guò)程的指針的間接引用

(1)swap(x,y)(2)int*x,*y;(3){inttemp;(4)temp=*x;*x=*y;*y=temp;(5)