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

第10章目標(biāo)程序運(yùn)行時組織概述為了使目標(biāo)程序能夠運(yùn)行，編譯程序要從操作系統(tǒng)中得到一塊存儲區(qū)，以使目標(biāo)程序能夠在其上運(yùn)行。該存儲區(qū)需容納：（1）生成的目標(biāo)代碼（2）目標(biāo)代碼運(yùn)行時的數(shù)據(jù)空間數(shù)據(jù)空間應(yīng)包括：(1)用戶定義的各種類型的數(shù)據(jù)對象所需的存儲空間(2)保留中間結(jié)果和傳遞參數(shù)的臨時工作單元(3)調(diào)用過程時所需的連接單元(4)組織輸入/輸出所需的緩沖區(qū)目標(biāo)代碼所占用空間的大小在編譯時能確定。有些數(shù)據(jù)對象所占用的空間也能在編譯時確定。而有些數(shù)據(jù)對象具有可變體積和待分配性質(zhì)，無法在編譯時確定存儲空間的位置。因此運(yùn)行時的存儲區(qū)常常劃分成：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)目標(biāo)程序運(yùn)行時存儲區(qū)的典型劃分codestaticdatastack↓

↑heap代碼(code)區(qū)用以存放目標(biāo)代碼，這是固定長度的，即編譯時能確定的；靜態(tài)數(shù)據(jù)區(qū)(staticdata)用以存放編譯時能確定所占用空間的數(shù)據(jù)；棧區(qū)和堆區(qū)(stackandheap)用于可變數(shù)據(jù)以及管理過程活動的控制信息。所謂數(shù)據(jù)空間的分配，本質(zhì)上看，是將程序中的每個名字與一個存儲位置關(guān)聯(lián)起來，該存儲位置用以容納名字的值。關(guān)聯(lián)（Binding）將源程序的文本程序運(yùn)行動作的實(shí)現(xiàn)即源程序文本要做哪些功能，目標(biāo)程序要實(shí)現(xiàn)它的功能。源文件中的名字N

運(yùn)行時的存儲S(N到S的映射)10.1數(shù)據(jù)空間的三種不同使用方法和管理方法

數(shù)據(jù)空間的三種不同使用方法和管理方法:

靜態(tài)存儲分配、棧式動態(tài)存儲分配和堆式動態(tài)存儲分配。1、靜態(tài)存儲分配

這種存儲分配非常簡單，如果在編譯時能確定目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，稱這種分配策略為靜態(tài)存儲分配。像FORTRAN這樣的語言，其程序是段結(jié)構(gòu)的，即由主程序段和若干子程序段組成。各程序段中定義的名字一般是彼此獨(dú)立的，也即各段的數(shù)據(jù)對象名的作用域在各段中，同一個名字在不同的程序段表示不同的存儲單元，不會在不同段間互相引用、賦值。另外它的每個數(shù)據(jù)名所需的存儲空間大小都是常量（即不許含可變體積的數(shù)據(jù)，如可變數(shù)組），且所有數(shù)據(jù)名的性質(zhì)是完全確定的。這樣，整個程序所需數(shù)據(jù)空間的總量在編譯時完全確定，換句話說，一旦存儲空間的某個位置分配給了某個數(shù)據(jù)名（關(guān)聯(lián)起來）之后，在目標(biāo)程序的整個運(yùn)行過程中，此位置（地址）就屬于該數(shù)據(jù)名了。2動態(tài)存儲分配

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

例:

procedureA(m,n:integer);

beginrealz;

arrayB[m:n];

begin

··

·end;

end;

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

這種分配策略是將整個程序的數(shù)據(jù)空間設(shè)計為一個棧。例：在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個過程時，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程工作結(jié)束時就釋放這部分空間。過程所需的數(shù)據(jù)空間包括兩部分：一部分是生存期在本過程這次活動中的數(shù)據(jù)對象，如局部變量、參數(shù)單元、臨時變量等等；另一部分則是用以管理過程活動的記錄信息(連接數(shù)據(jù))。即當(dāng)一次過程調(diào)用出現(xiàn)時，調(diào)用該過程的那個過程的活動即被中斷，當(dāng)前機(jī)器的狀態(tài)信息，諸如返回地址、寄存器的值等等，也都必須保留在棧中。當(dāng)控制從調(diào)用返回時，便根據(jù)棧中記錄的信息恢復(fù)機(jī)器狀態(tài)，使該過程的活動繼續(xù)進(jìn)行。2、堆式動態(tài)存儲分配

如果一個程序語言提供用戶自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間的機(jī)制，通常使用一種稱為堆式的動態(tài)存儲分配方案。過程活動記錄:AR為說明方便，假定程序是由過程組成，過程運(yùn)行時稱作過程的激活。

一個過程的一次執(zhí)行所需要的信息使用一個連續(xù)的存儲區(qū)來管理，這個區(qū)（塊）叫做一個活動記錄

lllllll一般這個段要記錄：臨時值，如計算表達(dá)式時的中間工作單元。局部變量（數(shù)據(jù)）保存運(yùn)行過程前的狀態(tài)（寄存器值……）存取鏈（可選）對于非局部量的引用?？刂奇湥蛇x）指向調(diào)用者的活動記錄。實(shí)參（形式單元）返回地址術(shù)語：每個過程的AR有3個聯(lián)系單元：SL：靜態(tài)鏈，指向定義該過程的直接外過程 （或主程序）運(yùn)行時最新數(shù)據(jù)段的基地址。DL：動態(tài)鏈，指向調(diào)用該過程前正在運(yùn)行過 程的數(shù)據(jù)段基地址。即指向調(diào)用本過程的那個過程的活動記錄的地址（老SP）RA：返回地址，記錄調(diào)用該過程時目標(biāo)程序的斷點(diǎn)，保存該過程返回后的地址。這種情況可以直接采用棧式存儲分配策略。在運(yùn)行時，每個過程開始時就把它的活動記錄壓入棧，直到該活動結(jié)束，它的活動記錄彈出棧。10.2簡單的棧式存儲分配程序的特點(diǎn):過程定義不嵌套,過程可遞歸調(diào)用,允許有可變數(shù)組.例如:C語言

全局?jǐn)?shù)據(jù)說明

Main(){Main中的數(shù)據(jù)說明

}VoidR(){R中的數(shù)據(jù)說明

}VoidQ{Q中的數(shù)據(jù)說明

}MainQR

嵌套過程語言的棧式分配方案

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

辦法：

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}.它的嵌套情況如下：sort

readarray

exchange

quicksort

partition

如果該程序的某次執(zhí)行順序?yàn)椋?/p>

sort→quicksort→quicksort→partition→exchange…

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

sort→quicksort→quicksort→partition→exchange…解決對非局部量的引用（存取）

用Display表另外一種存取非局部變量的辦法，也是常用的有效辦法。即每進(jìn)入一個過程后，在建立它的活動記錄的同時建立一張嵌套層次顯示表display。

Display表---嵌套層次顯示表當(dāng)前激活過程的層次為K，它的Display表含有K+1個單元，依次存放著現(xiàn)行層，直接外層…直至最外層的每一過程的最新活動記錄的基地址例如：上例的程序，假定有如下四種調(diào)用情況：(a)sort→quicksort…;(b)sort→quicksort→quicksort…;(c)sort→quicksort→quicksort→partition…;(d)sort→quicksort→quicksort→partition→exchange…。則P225圖10.16的（a），（b），（c），（d）分別說明了上述四種情形的運(yùn)行棧和display。確實(shí)看出，display顯示了存取鏈的信息。

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

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

d[1]d[0]displaysptop主程序的活動記錄

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

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

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

displayd[2]d[1]d[0]

d[1]d[0]

displaysptoptopsp（3）（4）display本身的體積在編譯時可確定。至于display本身作為單獨(dú)的表分配存儲，還是作為活動記錄的一部分，比如置于實(shí)參（形式單元）的上端（如圖所示），則取決于編譯程序的設(shè)計者。display作為活動記錄的一部分Display表：當(dāng)過程的層次為n，它的display為n+1個值。即第0層到第n層的SP的值。全局Display表：直接外層的Display地址。連接數(shù)據(jù)：有3個，即老SP，返回地址，全局Display。例：P227圖10.19的程序中，分程序有B0,B1,B2,B3。分程序的作用域遵循的是最近嵌套原則:P226過程的TOP單元始終是指向活動記錄的棧頂。而過程運(yùn)行中的任何時刻的現(xiàn)行分程序的TOP則存放最新的棧頂?shù)刂?。過程體中的并列分程序可享用同一存儲空間,因?yàn)樗鼈儾粫瑫r執(zhí)行。分程序除數(shù)組外的所有數(shù)據(jù)的地址在編譯時可以靜態(tài)地確定。

參數(shù)傳遞

參數(shù)傳遞的三種途徑：傳地址、傳值、傳名傳地址：把實(shí)參的地址傳遞給形參。即調(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀鬟f給被調(diào)用過程相應(yīng)的形參。1、實(shí)在參數(shù)是一個變量，則直接傳遞它的地址。2、實(shí)在參數(shù)是表達(dá)式----計算值，放入一存儲單元，傳此存儲單元地址3、過程對形參的引用或賦值都被處理成對形式單元的間接訪問（指針操作）

(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)s);(13)writeln(‘a(chǎn)=‘,a);writeln(‘b=‘,b)(14)end.PASCAL程序有關(guān)鍵字var時，PASCAL語言的參數(shù)傳遞使用的方式是傳地址；去掉var，則使用的方式是傳值。傳值：①在被調(diào)過程的活動記錄中開辟形參的存儲空間，這些存儲位置即是我們所說的形參或形式單元。

②調(diào)用過程計算實(shí)參的值，并將它們的右值放在為形式單元開辟的空間中。

③被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。

procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；

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

x:=a；

y:=b；

temp:=x；

x:=y；

y:=temp

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

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

在一個值調(diào)用過程中使用指針的C程序在C程序中傳地址，用指針實(shí)現(xiàn)。例:主程序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