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

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

概述為了使目標程序能夠運行，編譯程序要從操作系統(tǒng)中得到一塊存儲區(qū)，以使目標程序能夠在其上運行。該存儲區(qū)需容納：（1）生成的目標代碼（2）目標代碼運行時的數(shù)據(jù)空間

數(shù)據(jù)空間應包括：用戶定義的各種類型的數(shù)據(jù)對象所需的存儲空間保留中間結(jié)果和傳遞參數(shù)的臨時工作單調(diào)用過程時所需的連接單元組織輸入/輸出所需的緩沖區(qū)目標代碼所占用空間的大小在編譯時能確定。有些數(shù)據(jù)對象所占用的空間也能在編譯時確定。而有些數(shù)據(jù)對象具有可變體積和待分配性質(zhì)，無法在編譯時確定存儲空間的位置。因此運行時的存儲區(qū)常常劃分成：目標區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)運行時存儲空間的劃分代碼空間數(shù)據(jù)空間目標代碼空間靜態(tài)數(shù)據(jù)空間棧自由空間

堆代碼區(qū)用以存放目標代碼，這是固定長度的，即編譯時能確定的；靜態(tài)數(shù)據(jù)區(qū)用以存放編譯時能確定所占用空間的數(shù)據(jù)；棧區(qū)和堆區(qū)用于可變數(shù)據(jù)以及管理過程活動的控制信息。靜態(tài)存儲分配、棧式動態(tài)存儲分配和堆式動態(tài)存儲分配。

靜態(tài)存儲分配

這種存儲分配非常簡單，如果在編譯時能確定目標程序運行中所需的全部數(shù)據(jù)空間的大小，稱這種分配策略為靜態(tài)存儲分配。10.1數(shù)據(jù)空間的三種不同使用方法和管理方法

動態(tài)存儲分配

如果一個程序設(shè)計語言允許遞歸過程、可變數(shù)組或允許用戶自由申請和釋放空間，那么，就需要采用動態(tài)存儲管理技術(shù)。因為對于這種程序在編譯時無法知道它在運行時需要多大的存儲空間，它所需要的數(shù)據(jù)空間的大小需待程序運行時動態(tài)地確定。若一個數(shù)組所需的存儲空間的大小在編譯時就已知道，則稱它為確定數(shù)組，否則稱為可變數(shù)組。

例:

procedureA(m,n:integer);

beginrealz;

arrayB[m:n];

begin

··

·end;

end;

B[m:n]為可變數(shù)組，B的上下界是過程A的實參，A被調(diào)用時才能確定。動態(tài)存儲管理技術(shù)有兩種方式：棧式（stack）和堆式（heap）。下面主要介紹棧式動態(tài)存儲分配

這種分配策略是將整個程序的數(shù)據(jù)空間設(shè)計為一個棧。在程序中，每當調(diào)用一個過程時，它所需的數(shù)據(jù)空間就分配在棧頂，每當過程工作結(jié)束時就釋放這部分空間。為了討論方便，我們引入一個術(shù)語：過程的活動記錄。棧式動態(tài)存儲分配過程的活動和活動記錄一個過程的活動：該過程的一次執(zhí)行。即每次執(zhí)行一個過程體，就產(chǎn)生該過程的一個活動?；顒佑涗洠菏且欢芜B續(xù)的存儲區(qū)，為了管理過程在一次執(zhí)行中所需要的信息。源語言不同，實現(xiàn)的方法不同，組成活動記錄的域也不同。棧式存儲分配策略。在運行時，每個過程開始時就把它的活動記錄壓入棧，直到該活動結(jié)束，它的活動記錄彈出棧。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時工作單元（如存放對表達式求值的結(jié)果）形式單元：存放相應的實在參數(shù)的地址或值。連接數(shù)據(jù)返回地址動態(tài)鏈：指向調(diào)用該過程前正在運行過程的數(shù)據(jù)段基地址。即指向調(diào)用本過程的那個過程的活動記錄的地址（老SP）靜態(tài)鏈：指向靜態(tài)直接外層最新活動記錄地址的指針，用來訪問非局部數(shù)據(jù)。sort

readarray

exchange

quicksort

partition

對于PL/0語言，每個過程的AR有3個聯(lián)系單元：SL：靜態(tài)鏈，指向定義該過程的直接外過程

（或主程序）運行時最新數(shù)據(jù)段的基地址。DL：動態(tài)鏈，指向調(diào)用該過程前正在運行過 程的數(shù)據(jù)段基地址。即指向調(diào)用本過程的那個過程的活動記錄的地址（老SP）RA：返回地址，記錄調(diào)用該過程時目標程序的斷點，保存該過程返回后的地址。這種情況可以直接采用棧式存儲分配策略。在運行時，每個過程開始時就把它的活動記錄壓入棧，直到該活動結(jié)束，它的活動記錄彈出棧。10.2簡單的棧式存儲分配程序的特點:過程定義不嵌套,過程可遞歸調(diào)用,允許有可變數(shù)組.例如:C語言

全局數(shù)據(jù)說明

Main(){Main中的數(shù)據(jù)說明}VoidR(){R中的數(shù)據(jù)說明}VoidQ{Q中的數(shù)據(jù)說明}MainQR

嵌套過程語言的棧式分配方案前面我們講的過程不允許語言嵌套定義，現(xiàn)在我們?nèi)∠@個限制，即允許過程嵌套定義，一個過程可以引用包圍它的任一外層過程所定義的標識（如變量，數(shù)組或過程等）。如：我們所熟悉的PASCAL語言程序結(jié)構(gòu)就是這樣一種語言。由于過程定義是嵌套的，一個過程可以引用包圍它的任一外層過程所定義的標識（如變量，數(shù)組或過程等）。也就是說，運行時，一個過程Q可以引用它的的任意外層的最新活動記錄的名字所對應的存儲空間，過程Q運行時，必須知道它的所有外層的最新活動記錄的地址。

辦法：

1.用靜態(tài)鏈（如PL/0的SL）。引入一個稱為靜態(tài)鏈的指針，該指針為活動記錄的一個域，指向直接外層的最新活動記錄的地址。

2.用DISPLAY表。例：(1)programsort(input,output);

(2)

vara:array[0..10]ofinteger;

(3)

x:integer;

(4)

procedurereadarray;

(5)

vari:integer;

(6)

begin…a…end{readarray};//readarray的過程體

(7)

procedureexchange(i,j:integer);

(8)

begin

(9)

x∶=a[i];a[i]∶=a[j];a[j]∶=x;//exchange的過程體

(10)

end{exchange};

(11)

procedurequicksort(m,n:integer);

(12)

vark,v:integer;

(13)

functionpartition(y,z:integer):integer;

(14)

vari.j:integer;

(15)

begin…a…//partition的函數(shù)體

(16)

…v…

(17)

…exchange(i,j);…

(18)

end{partition};

(19)

begin…end{quicksort};//quicksort的過程體

(20)begin…end{sort}.見P236它的嵌套情況如下：sort

readarray

exchange

quicksort

partition

如果該程序的某次執(zhí)行順序為：

sort→quicksort→quicksort→partition→exchange…

即主程序(最外層過程)sort開始執(zhí)行,繼而進入過程quicksort，而又一次進入過程quicksort，接著進入過程partition，進入過程exchange…。

sort→quicksort→quicksort→partition→exchange…sort

readarray

exchange

quicksort

partition

解決對非局部量的引用（存?。?/p>

用Display表另外一種存取非局部變量的辦法，也是常用的有效辦法。即每進入一個過程后，在建立它的活動記錄的同時建立一張嵌套層次顯示表display。Display表---嵌套層次顯示表當前激活過程的層次為K，它的Display表含有K+1個單元，依次存放著現(xiàn)行層，直接外層…直至最外層的每一過程的最新活動記錄的基地址令過程R的外層為Q，Q的外層為主程序為P，則過程R運行時的DISPLAY表內(nèi)容為：問題：當過程P1調(diào)用過程P2而進入P2后，P2應如何建立起自己的display表？P0P1P2P0P2P1P0P1P2問題：當過程P1調(diào)用過程P2而進入P2后，P2應如何建立起自己的display表？P0P1P2

P1的最新活動記錄的起始地址P0的最新活動記錄的起始地址P1的display表P0的最新活動記錄的起始地址

P2的最新活動記錄的起始地址…………P2的display表問題：當過程P1調(diào)用過程P2而進入P2后，P2應如何建立起自己的display表？

P1的最新活動記錄的起始地址P0的最新活動記錄的起始地址P1的display表P0的最新活動記錄的起始地址P1的最新活動記錄的起始地址…………P2的display表P2的最新活動記錄的起始地址P0P2P1問題：當過程P1調(diào)用過程P2而進入P2后，P2應如何建立起自己的display表？P0P1P2P1的最新活動記錄的起始地址P0的最新活動記錄的起始地址P1的display表P0的最新活動記錄的起始地址…………P2的display表P2的最新活動記錄的起始地址P2的最新活動記錄的起始地址例如：上例的程序，假定有如下四種調(diào)用情況：(a)sort→quicksort…;(b)sort→quicksort→quicksort…;(c)sort→quicksort→quicksort→partition…;(d)sort→quicksort→quicksort→partition→exchange…。則P239圖10.16的（a），（b），（c），（d）分別說明了上述四種情形的運行棧和display。確實看出，display顯示了存取鏈的信息。

sort

readarray

exchange

quicksort

partition

用Display表的方案(1)主程序--->(2)P--->(3)Q--->(4)R主程序的活動記錄

d[0]spdisplaytop（1）

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

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

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

displaysptop（3）topR的活動記錄Q的活動記錄

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

d[1]d[0]

displaysp（4）display本身的體積在編譯時可確定。至于display本身作為單獨的表分配存儲，還是作為活動記錄的一部分，比如置于實參（形式單元）的上端（如圖所示），則取決于編譯程序的設(shè)計者。display作為活動記錄的一部分Display表：當過程的層次為n，它的display為n+1個值。即第0層到第n層的SP的值。連接數(shù)據(jù)：有3個，即老SP，返回地址，全局Display。全局Display是調(diào)用該過程的那個過程的display表的地址。programP;vara,x:integer;procedureQ(b:integer); vari:integer; procedureR(u:integer;varv:integer); varc,d:integer; begin ifu=1thenR(u+1,v) ...... v:=(a+c)*(b-d); ...... end{R}begin ...... R(1,x); ......end{Q}procedureS; varc,i:integer; begin a:=1; Q(c); ...... end{S}begin a:=0; S; ......end.{P}0112PRQS00返回地址10(display)2a3x405返回地址62(全局display)70(形參個數(shù))809510主程序過程

Sc11i12TOPSP動態(tài)鏈displayRQSP00返回地址10(display)2a3x405返回地址62(全局display)70(形參個數(shù))809510主程序P過程

S

過程

Qc11i12動態(tài)鏈513返回地址149(全局display)151(形參個數(shù))16b(形參)170181319i20TOPSPPRQSdisplaydisplay00返回地址10(display)2a3x405返回地址62(全局display)70(形參個數(shù))809510主程序P過程

S

過程

Q

過程

Rc11i12動態(tài)鏈513返回地址149(全局display)151(形參個數(shù))16b(形參)170181319i201321返回地址2218(全局display)232(形參個數(shù))24u(形參)25v(形參)2602713282129c30d31TOPSPPRQS00返回地址10(display)2a3x405返回地址62(全局display)70(形參個數(shù))809510主程序P

過程

S

過程

Q

過程

R

過程

Rc11i12動態(tài)鏈513返回地址149(全局display)151(形參個數(shù))16b(形參)170181319i201321返回地址2218(全局display)232(形參個數(shù))24u(形參)25v(形參)2602713282129c30d31TOPSP2132返回地址3327(全局display)342(形參個數(shù))35u(形參)36v(形參)3703813393240c41d42分程序結(jié)構(gòu)的存儲管理例：main(){inta=0;intb=0;{intb=1;{inta=2;

B2Printf(“%d%d\n”,a,b);B0}

B1{intb=3;

B3Printf(“%d%d\n”,a,b);}Printf(“%d%d\n”,a,b);}Printf(“%d%d\n”,a,b);}圖中，分程序有B0,B1,B2,B3。分程序的作用域遵循的是最近嵌套原則見P240:

聲明

作用域inta=0;B0-B2intb=0;B0-B1intb=1;B1-B3inta=2;B2intb=3;B3分程序結(jié)構(gòu)的特點：分程序內(nèi)可以定義變量分程序允許嵌套定義變量，內(nèi)層分程序可以引用包圍它的任意一外層分程序定義的標識符分程序在哪里定義就在哪里被調(diào)用處理分程序結(jié)構(gòu)存儲分配方案的一種簡單辦法是:把分程序看成“無參過程”，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲辦法應用到處理分程序中。但這種做法是極為低效的。一則：分程序不存在調(diào)用問題，在進入一個分程序時，沒有必要將連接數(shù)據(jù)（如動態(tài)鏈，返回地址）和DISPLAY表都放在活動記錄中；二則：當從內(nèi)層分程序向外層轉(zhuǎn)移時，可能同時要結(jié)束若干個分程序。1.過程的TOP值，它指向過程活動記錄的棧頂位置。2.連接數(shù)據(jù)，共四項：（1)老SP值；（2)返回地址；

(3)全局DISPAY地址；（4)調(diào)用時的棧頂單元地址，老TOP。為了操作方便，對于分程序結(jié)構(gòu)，每個過程的活動記錄所含的內(nèi)容有：3.參數(shù)個數(shù)和形式單元4.DISPAY表。5.過程所轄的各分程序的局部數(shù)據(jù)單元。對于每個分程序來說，它們包括：（1)分程序的TOP值。（2)分程序的局部變量，數(shù)組內(nèi)情向量和臨時工作單元。過程的TOP單元始終是指向活動記錄的棧頂。而過程運行中的任何時刻的現(xiàn)行分程序的TOP則存放最新的棧頂?shù)刂?。過程體中的并列分程序可享用同一存儲空間,因為它們不會同時執(zhí)行。分程序除數(shù)組外的所有數(shù)據(jù)的地址在編譯時可以靜態(tài)地確定。

參數(shù)傳遞參數(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.PASCAL程序有關(guān)鍵字var時，PASCAL語言的參數(shù)傳遞使用的方式是傳地址；去掉var，則使用的方式是傳值。procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

調(diào)用swap(a,b)過程將不會影響a和b的值。其結(jié)果等價于執(zhí)行下列運算：

x:=a；

y:=b；

temp:=x；

x:=y；

y:=temp

傳地址（變量參數(shù)）例如：過程swap(varx,y:integer);swap(a,b）；（a,b為調(diào)用時的實參）調(diào)用結(jié)果a,b的值被改變。傳值（值調(diào)用）特點是對形式參數(shù)的任何運算不影響實參的值。例如：過程swap(x,y:integer);swap(a,b）；其結(jié)果：a,b調(diào)用前的值不改變。

(1)swap(x,y)(2)int*x,*y;(3){inttemp;(4)temp=*x;*x=*y;*y=temp;(5)}(6)main()(7){inta=1,b=2;(8)swap(&a,&b);(9)printf(“aisnow%d,bisnow%d\n”,a,b);(10)}

在一個值調(diào)用過程中使用指針的C程序，在C程序中傳地址，用指針實現(xiàn)。傳地址：把實參的地址傳遞給形參。即調(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀鬟f給被調(diào)用過程相應的形參。1、實在參數(shù)是一個變量，則直接傳遞它的地址。2、實在參數(shù)是表達式----計算值，放入一存儲單元，傳此存儲單元地址3、過程對形參的引用或賦值都被處理成對形式單元的間接訪問（指針操作）例:主程序A：＝2；B:=3;P(A+B,A,A)Print(A);子程序：P(X,Y,Z){Y:=Y+1;Z:=Z+X;}問傳地址和傳值Print（A）的結(jié)果是多少？傳地址：T：＝A＋B＝5，X:=&T;Y:=&A;Z:=&A;（即X所指的變量為T，Y,Z所指的變量是A）Y↑:=Y↑+1=2+1=3（即A的值變?yōu)?）Z↑:=Z↑+X↑=A＋T＝3＋5＝8主程序A：＝2；B:=3;P(A+B,A,A)Print(A);子程序：P(X,Y,Z){Y:=Y+1;Z:=Z+X;}所以：傳地址的結(jié)果為：8傳值的結(jié)果為：2傳名：將被調(diào)用的過程體復制到調(diào)用處，并將每個形參“文字地”替換成實參。主程序A：＝2；B:=3;P(A+B,A,A)Print(A)