第10章 目標程序運行時的存儲組織

第10章目標程序運行時的組織

教學要求：本章介紹目標程序運行時的存儲組織方式，包括靜態(tài)存儲分配和動態(tài)存儲分配。要求掌握各種存儲組織形式的基本方法。教學重點：靜態(tài)分配策略和動態(tài)分配策略的基本思想，嵌套過程語言棧式分配，活動記錄、運行時棧的組織。

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

目標代碼區(qū)

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

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

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

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

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

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

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

SP:=TOP+1

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

(新TOP)

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

在編譯時可確定。

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

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

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

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

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

→過程RQ的活動記錄TOPR的活動記錄SP主程序活動記錄全局數(shù)據(jù)區(qū)

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

R的活動記錄

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

varA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

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

非局部名字的訪問的實現(xiàn)

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

p2

p3

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

2、某過程p是在層次為i的過程q內(nèi)定義的，并且q是包圍p的直接外層，那么p的過程層數(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

過程

P2

過程

P1

過程

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

程序結構圖

……

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[0]spdisplaytop（1）

P的活動記錄主程序的活動記錄

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

P的活動記錄主程序的活動記錄

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

P的活動記錄主程序的活動記錄

d[1]d[0]

displaytopsp（4）DISPLAY表的維護和建立

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

……dDISPLAY4形式單元

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

2全局DISPLAY地址

1返回地址

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

10.3堆式存儲分配

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

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過程非局變量a[i]和a[j]的值進行交換，i,j為形參傳值的實現(xiàn)1.形式參數(shù)當作過程的局部變量處理，即在被調(diào)過程的活動記錄中開辟了形參的存儲空間，這些存儲位置即是我們所說的形式單元（用以存放實參）。2.調(diào)用過程計算實參的值，并將其放在對應形式單元開辟的空間中。3.被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。

(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.

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

把實在參數(shù)的地址傳遞給相應的形參，即調(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀鬟f給被調(diào)用過程相應的形參：1.實在參數(shù)是一個名字，或具有左值的表達式----傳遞左值2.實在參數(shù)是無左值的表達式----計算值，放入一存儲單元，傳此存儲單元地址3.目標代碼中，被調(diào)用過程對形參的引用變成對傳遞給被調(diào)用過程的指針的間接引用

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