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

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

10.1數(shù)據(jù)空間的三種不同使用方法和管理方法10.2棧式存儲分配的實現(xiàn)10.3參數(shù)傳遞10.4過程調(diào)用、過程進入和過程返回

從邏輯上看，在代碼生成前，編譯程序必須進行目標程序運行環(huán)境的配置和數(shù)據(jù)空間的分配。數(shù)據(jù)空間應包括：用戶定義的各種類型的數(shù)據(jù)對象（變量和常數(shù)）所需的存儲空間；作為保留中間結果和傳遞參數(shù)的臨時工作單元；調(diào)用過程時所需的連接單元；組織輸入/輸出所需的緩沖區(qū)。目標代碼所占用空間的大小在編譯時能確定。有些數(shù)據(jù)對象所占用的空間也能在編譯時確定，其地址可以編譯進目標代碼中。而有些數(shù)據(jù)對象具有可變體積和待分配性質(zhì)，無法在編譯時確定存儲空間的位置。

因此運行時的存儲區(qū)常常劃分成：目標區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如圖10.1

。目標代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)棧Stack堆heap圖10.1目標程序運行時存儲區(qū)的典型劃分所謂數(shù)據(jù)空間的分配，本質(zhì)上看，是將程序中的每個名字與一個存儲位置關聯(lián)起來，該存儲位置用以容納名字的值。編譯程序分配目標程序運行時的數(shù)據(jù)空間的基本依據(jù)是程序語言設計時對程序運行中存儲空間的使用和管理辦法的規(guī)定。在程序設計語言語義學中，使用術語environment表示將一個名字映射到一個存儲位置的函數(shù)，術語state表示存儲位置到值的映射，如圖10.2所示。圖10.2名字到存儲位置、到值的映射編譯程序分配目標程序運行時的數(shù)據(jù)空間的基本依據(jù)是程序語言設計時對程序運行中存儲空間的使用和管理辦法的規(guī)定。決定存儲管理復雜程度的因素--源語言本身，比如源語言允許的數(shù)據(jù)類型有多少？語言中允許的數(shù)據(jù)項是靜態(tài)確定還是動態(tài)確定？程序結構有什么特點，是段結構還是分程序結構？過程定義是否允許嵌套？等等。源語言的結構特點、源語言的數(shù)據(jù)類型、源語言中決定名字作用域的規(guī)則等因素影響存儲空間的管理和組織的復雜程度，決定數(shù)據(jù)空間分配的基本策略。10.1數(shù)據(jù)空間的三種不同使用方法和管理方法數(shù)據(jù)空間的使用和管理方法:

簡單的棧式分配方案嵌套過程的棧式分配方案分程序結構的存儲分配方案靜態(tài)存儲分配、動態(tài)存儲分配——棧式堆式10.1.1靜態(tài)存儲分配如果在編譯時能確定目標程序運行中所需的全部的數(shù)據(jù)空間的大小，編譯時安排好目標程序運行時的全部數(shù)據(jù)空間，確定每個數(shù)據(jù)對象的存儲位置，稱這種分配策略為靜態(tài)存儲分配。如C中的靜態(tài)變量，外部變量等。10.1.2動態(tài)存儲分配如果一個程序設計語言允許遞歸過程、允許動態(tài)的申請建立和撤消存儲空間、可變數(shù)組或允許用戶自由申請和釋放空間，那么，就需要采用動態(tài)存儲管理技術。因為對于這種程序在編譯時無法知道它在運行時需要多大的存儲空間，它所需要的數(shù)據(jù)空間的大小需待程序運行時動態(tài)地確定。若一個數(shù)組所需的存儲空間的大小在編譯時就已知道，則稱它為確定（靜態(tài)）數(shù)組，否則稱為可變（動態(tài)）數(shù)組。10.1.2.1棧式動態(tài)存儲分配分配策略是將整個程序的數(shù)據(jù)空間設計為一個棧。在具有遞歸結構的語言程序中，每當調(diào)用一個過程時，它所需的數(shù)據(jù)空間就分配在棧頂，每當過程工作結束時就釋放這部分空間。過程所需的數(shù)據(jù)空間包括兩部分：生存期在本過程這次活動中的數(shù)據(jù)對象；用以管理過程活動的記錄信息。棧式動態(tài)存儲分配策略適用于PASCAL，C，ALGOL之類具有遞歸結構的語言的實現(xiàn)。

10.1.2.2堆式動態(tài)存儲分配如果一個程序語言提供用戶自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間的機制，或者不僅有過程而且有進程的程序結構，一般用堆式的動態(tài)存儲分配方案。如Ｃ++中的new，delete，PASCAL的new等機制。此時,空間的使用未必服從“先申請后釋放，后申請先釋放”的原則，那么棧式的動態(tài)分配方案就不適用了。通常使用一種稱為堆式的動態(tài)存儲分配方案。這種分配方式的存儲管理技術甚為復雜，我們這里舉出這種分配方法必須考慮的幾個問題。

堆式的動態(tài)存儲分配策略:當運行程序要求一塊體積為N的空同時，我們應該分配哪一塊給它呢？理論上說，應從比N稍大一點的一個空閑塊中取出N個單元，以便使大的空閑塊派更大的用場。但這種做法較麻煩。因此，常常仍采用“先碰上哪塊比N大就從其中分出N個單元”的原則。但不論采用什么原則，整個大存區(qū)在一定時間之后必然會變成零碎不堪?？傆幸粋€時候會出現(xiàn)異樣的情形：運行程序要求一塊體積為N的空間，但發(fā)現(xiàn)沒有比N大的空閑塊了，然而所有空閑塊的總和卻要比N大得多！出現(xiàn)這種情形時怎么辦呢？這是一個比前面的問題難得多的問題。解決辦法似乎很簡單，這就是，把所有空閑塊連接在一起，形成一片可分配的連續(xù)空間。這里主要問題是，我們必須調(diào)整運行程序?qū)Ω髡加脡K的全部引用點。

堆式的動態(tài)存儲分配策略:另外，如果運行程序要求一塊體積為N的空間，但所有空閑塊的總和也不夠N，那又應怎么辦呢？有的管理系統(tǒng)采用一種叫做廢品回收的辦法來對付這種局面。即尋找那些運行程序業(yè)己無用但尚未釋放的占用塊，或者那些程序目前很少使用的占用塊，把這些占用塊收回來，重新分配。但是，我們?nèi)绾沃滥男K運行時在使用或者目前很少使用呢？即便知道了，一經(jīng)收回后運行程序在某個時候又要用它時又應該怎么辦呢？要使用廢品回收技術，除了在語言上要有明確的具體限制外，還需要有特別的硬件措施，否則回收幾乎不能實現(xiàn)。堆式動態(tài)儲分配的實現(xiàn)通常有如下兩種途徑：1）定長塊管理堆式動態(tài)儲分配最簡單的實現(xiàn)是按定長塊進行。初始化時，將堆存儲空間分成長度相等的若干塊，每塊中指定一個鏈域，按照鄰塊的順序把所有塊鏈成一個鏈表，用指針available指向鏈表中的第一塊。分配時每次都分配指針available所指的塊，然后available指向相鄰的下一塊。歸還時，把所歸還的塊插入鏈表。考慮插入方便，可以把所歸還的塊插在available所指的塊之前，然后available指向新歸還的塊。占用占用占用空閑空閑空閑available(a)占用占用空閑空閑空閑(b)空閑available圖10.3定長塊管理2）變長塊管理除了按定長塊進行分配之外，還可以根據(jù)需要分配長度不同的存儲塊，可以隨要求而變。按這種方法，初始化時存儲空間是一個整塊。按照用戶的需要，分配時先是從一個整塊里分割出滿足需要的一小塊，以后，歸還時，如果新歸還的塊能和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個鏈表。再進行分配時，從空閑塊鏈表中找出滿足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出去。若空閑塊表中有若干個滿足需要的空閑塊時，該分配哪一塊呢?通常有三種不同的分配策略：

變長塊管理通常有三種不同的分配策略：

首次滿足法（時間優(yōu)先）;最優(yōu)滿足法（空間優(yōu)先）;最差滿足法（時間優(yōu)先）。上述三種分配策略各有所長。

10.2棧式存儲分配的實現(xiàn)前面提到，使用棧式存儲分配策略意味著，運行時每當進入一個過程，就在棧頂為該過程的臨時工作單元，局部變量，機器狀態(tài)及返回地址等信息分配所需的數(shù)據(jù)空間，當一個過程工作完畢返回時，它在棧頂?shù)臄?shù)據(jù)空間也即釋放。

為討論方便，首先引入一個術語--過程的活動記錄AR(ActivationRecord)。過程的活動記錄是一段連續(xù)的存儲區(qū)，用以存放過程的一次執(zhí)行所需要的動態(tài)信息，這些信息可以如圖10.6所示。圖10.6過程的活動記錄返回地址實參控制鏈存取鏈機器狀態(tài)信息局部變量臨時工作單元①臨時工作單元：比如計算表達式過程中需存放中間結果用的臨時值單元。②局部變量：一個過程的局部變量。③機器狀態(tài)信息：保存該過程執(zhí)行前關于機器狀態(tài)的信息，諸如程序計數(shù)器、寄存器的值，這些值都需要在控制從該過程返回時給予恢復。④存取鏈：用以存取非局部變量，這些變量存放于其它過程的活動記錄中。并不是所有語言需要該信息。⑤控制鏈：指向調(diào)用該過程的那個過程的活動記錄，這也不是所有語言都需要的。⑥實參：也稱形式單元，由調(diào)用過程向該被調(diào)過程提供實參的值（或地址）。當然在實際編譯程序中，也常常使用機器寄存器傳遞實參。⑦返回地址：保存該被調(diào)過程返回后的地址。圖10.6過程的活動記錄返回地址實參控制鏈存取鏈機器狀態(tài)信息局部變量臨時工作單元靜態(tài)鏈，指向靜態(tài)直接外層最新活動記錄的起始地址，即指向定義本過程的直接外層過程

（或主程序）運行時最新活動記錄的基地址。動態(tài)鏈，指向調(diào)用該過程前正在運行過程的數(shù)據(jù)段基地址。10.2.1簡單的棧式分配的實現(xiàn)

程序結構特點:過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組；例：main

全局變量的說明procR……endR;procQ……endQ;主程序執(zhí)行語句endmainTOP

臨時工作單元局部簡單變量局部數(shù)組的內(nèi)情向量

保存運行過程前的狀態(tài)（返回地址，寄存器值…）實參（形式單元）和參數(shù)個數(shù)SP

存取鏈（靜態(tài)鏈）控制鏈（動態(tài)鏈，老SP）圖10.3過程的活動記錄指向調(diào)用該過程的那個過程的最新活動記錄的起始地址用以存取非局部變量，這些變量存放于其他過程的活動記錄中。Main

Q

R

TOP

R的活動記錄SP

主程序全局數(shù)據(jù)區(qū)Q的活動記錄MainQQQ的活動記錄主程序全局數(shù)據(jù)區(qū)Q的活動記錄圖10.4棧式存儲分配靜態(tài)鏈，指向靜態(tài)直接外層最新活動記錄的起始地址，即指向定義本過程的直接外層過程

（或主程序）運行時最新活動記錄的基地址。動態(tài)鏈，指向調(diào)用該過程前正在運行過程的數(shù)據(jù)段基地址。TOPR的數(shù)組區(qū)SPR的活動記錄Q的活動記錄主程序全局數(shù)據(jù)區(qū)圖10.6分配了數(shù)組區(qū)之后的運行棧TOP

臨時工作單元局部簡單變量局部數(shù)組的內(nèi)情向量

返回地址實參（形式單元）SP

參數(shù)個數(shù)控制鏈（老SP）圖10.5無嵌套定義的過程活動記錄內(nèi)容10.2.2嵌套過程語言的棧式實現(xiàn)主要特點：（語言）一個過程可以引用包圍它的任一外層過程所定義的標識符（如變量，數(shù)組或過程等）。（實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。(1)programsort(input,output);//sort的過程頭

(2)

vara:array[0..10]ofinteger;

(3)

x:integer;

(4)

procedurereadarray;//sort內(nèi)嵌套定義的readarray的過程頭

(5)

vari:integer;

(6)

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

(7)

procedureexchange(i,j:integer);

//sort內(nèi)嵌套定義的exchange的過程頭

(8)

begin

(9)

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

(10)

end{exchange};

(11)

procedurequicksort(m,n:integer);

//sort內(nèi)嵌套定義的quicksort的過程頭

(12)

vark,v:integer;

(13)

functionpartition(y,z:integer):integer;

//quicksort內(nèi)嵌套定義的partition的函數(shù)頭

(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的例程體圖10.11具有嵌套過程的PASCAL程序圖10.11的PASCAL程序中過程定義的嵌套情況如下：

sort

readarray

exchange

quicksort

partition局部變量a,x局部變量k,v過程quicksort的活動記錄過程sort的活動記錄圖10.12存儲棧布局記錄下列信息：可以引用過程

sort的局部變量

關鍵技術：解決對非局部量的引用（存?。ＴO法跟蹤每個外層過程的最新活動記錄AR的位置。跟蹤辦法：

1.用靜態(tài)鏈（如PL/0的SL）。

2.用DISPLAY表。跟蹤的辦法很多，我們介紹兩種，一種是在過程活動記錄中增設存取鏈，指向包含該過程的直接外層過程的最新活動記錄的起始位置。過程活動記錄的內(nèi)容如圖10.13（a）所示。圖10.12所提到的情況可用圖10.13（b）說明。

圖10.13嵌套定義過程的活動記錄和存儲棧(a)局部變量┆存取鏈控制鏈TOPSP┆┆存取鏈控制鏈(老SP)┆┆TOPSP(b)quicksort的ARsort的AR再回到圖10.11的例子。如果該程序的某次執(zhí)行順序為：

sort→quicksort→quicksort→partition→exchange…

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

圖10.15給出了進入過程exchange之后運行棧的示意，我們僅把存取鏈和控制鏈的值標明。

可以看出，過程exchange由過程（函數(shù)）partition調(diào)用，但exchange的直接外層過程是sort，所以過程exchange的活動記錄的存取鏈指向sort的活動記錄的始址。圖10.15運行棧靜態(tài)鏈，指向靜態(tài)直接外層最新活動記錄的起始地址，動態(tài)鏈，指向調(diào)用該過程前正在運行過程的數(shù)據(jù)段基地址。exchange的活動記錄partition的活動記錄quicksort的活動記錄quicksort的活動記錄sort的活動記錄

解決對非局部量的引用（存?。┑挠行мk法是用Display表。Display表---嵌套層次顯示表，即每進入一個過程后，在建立它的活動記錄的同時建立一張Display表。當前激活過程的層次為K，它的Display表含有K+1個單元，依次存放著現(xiàn)行層，直接外層…直至最外層的每一過程的最新活動記錄的基地址。例：programmain(i,0);程序結構圖……procR(c,d);……Rend/*R*/procP(a);主……

procQ(b);……P

QcallR

R(x,y);end/*Q*/callQ……Q(z);callPend/*P*/……callRP（W）；……R（U，V）；……end/*main*/用Display表的方案(1)主程序--->(2)P--->(3)Q--->(4)R主程序的活動記錄

d[0]spdisplaytop（1）d[1]d[0]

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

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

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

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

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

d[1]d[0]

displaytopsp（4）DISPLAY表的維護和建立DISPLAY表d運行棧

0主程活動記錄地址

1R活動記錄地址

...

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

老SP1

返回地址2

全局DISPLAY地址3

參數(shù)個數(shù)4形式單元...

dDISPLAY...

簡單變量

數(shù)組內(nèi)情向量

臨時變量

分程序結構ProcedureA(m,n);integerm,n;

B1:beginrealz;arrayB[m:n];B2:beginreald,e;L3:2end;B4:beginarrayC[1:m];1B5:beginreale;L6:54end;end;L8:end;

分程序結構的存儲分配方案

處理分程序結構存儲分配方案的一種簡單辦法是，把分程序看成“無名無參過程”，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲辦法應用到處理分程序中。但這種做法是極為低效的。一則，每逢進入一個分程序，就照樣建立連接數(shù)據(jù)和DISPLAY表,這是不必要的。二則，當從內(nèi)層分程序向外層轉(zhuǎn)移時，可能同時要結束若干個分程序。

按照過程處理辦法，意味著必須一層一層地通過“返回”來恢復所要到達的那個分程序的數(shù)據(jù)區(qū)，但不能直接到達。例如：如果有一個從第5層分程序轉(zhuǎn)出到達第1層分程序的標號L，雖然在第5層分程序工作時知道L所屬的層數(shù)，我們極易從DISPLAY中獲得第1層分程序的活動記錄基址（SP），但是怎么知道第1層分程序進入時的TOP呢？唯一的辦法是從5,4,3和2各層順序退出。但這種辦法是很浪費時間的。

為了解決上述問題，可采取兩種措施。第一，對每個過程或分程序都建立有自己的棧頂指示器TOP，代替原來僅有過程的棧頂指示器,每個TOP的值保存在各自活動記錄中。這樣，上述的第二個問題便可解決。第二，不把分程序看作“無參過程”，每個分程序享用包圍它的那個最近過程的DISPLAY。每個分程序都隸屬于某個確定的過程，分程序的層次是相對于它所屬的那個過程進行編號的。：

每個過程被當作是0層分程序。而過程體分程序（假定是一個分程序）當作是它所管轄的第1層分程序。這樣，每個過程的活動記錄所含的內(nèi)容有：1.過程的TOP值，它指向過程活動記錄的棧頂位置。2.連接數(shù)據(jù)，共四項：(1)老SP值；(2)返回地址；(3)全局DISPAY地址；(4)調(diào)用時的棧頂單元地址，老TOP。

3.參數(shù)個數(shù)和形式單元4.DISPAY表。5.過程所轄的各分程序的局部數(shù)據(jù)單元。對于每個分程序來說，它們包括：（1)分程序的TOP值。當進入分程序時它含現(xiàn)行棧頂?shù)刂?，以后，用來定義棧的新高度（分程序的TOP值）；（2)分程序的局部變量，數(shù)組內(nèi)情向量和臨時工作單元。過程Ａ的活動記錄B４的ＴＯＰ

數(shù)組B的內(nèi)情向量變量z

kdDISPLAY6形式單元m,n5參數(shù)個數(shù)：２4調(diào)用時的棧頂?shù)刂罚ɡ希裕希校?全局DISPLAY

地址2返回地址1老SP0過程的ＴＯＰ，指向活動記錄之頂SP數(shù)組Ｃ的內(nèi)情向量B２的ＴＯＰB５的ＴＯＰB１的ＴＯＰ變量e變量d和eB

B1T

OB的

信

息

向

量

ZB1的

PDISPLAY

形式單元

m,n2連

接數(shù)

據(jù)A的TOP

∶

∶(b)進

入

分

程

序B1DISPLAY

形式單元

m,n2連

接數(shù)

據(jù)

∶

∶(a)到

達

標

號B1處A的TOP

（d）進入分程序B2

數(shù)

組Be

dB22的TOPB的

信

息

向

量

zB1的TOPDISPLAY

形式單元

m,n2連接

數(shù)

據(jù)A的TOP

∶

∶

數(shù)

組BB的

信

息

向

量

zB1的TOPDISPLAY

形式單元

m,n2連

接

數(shù)

據(jù)A的TOP

∶

∶（c）數(shù)組Ｂ分配之后(e)進入分程序B4分配數(shù)組C之后

數(shù)

組C

數(shù)

組BC的

向

量

內(nèi)

情B4的TOPB的

內(nèi)

情

向

量

ZB1的TOPDISPLAY

形式單元

m,n2連

接

數(shù)

據(jù)A的TOP

∶

∶(f)進入分程序B5

數(shù)

組

C

數(shù)

組B

eB5的TOPC

的

內(nèi)

情

向

量B4的TOPB的

內(nèi)

情

向

量

zB1的TOPDISPLAY

形式單元

m,n2連接數(shù)據(jù)A的TOP

∶

∶10.3參數(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為形參（在這里是傳值）

(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程序

10.3.1傳值（值調(diào)用call-by-value）特點是對形式參數(shù)的任何運算不影響實參的值。例如：過程swap(x,y:integer);swap(a,b）；

其結果：a,b調(diào)用前的值不改變。傳值的實現(xiàn)（1）形式參數(shù)當作過程的局部變量處理，即在被調(diào)過程的活動記錄中開辟了形參的存儲空間，這些存儲位置即是我們所說的形式單元（用以存放實參）。（2）調(diào)用過程計算實參的值，并將其放在對應形式單元開辟的空間中。（3）被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這些形式單元。procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用swap(a,b)過程將不會影響a和b的值。其結果等價于執(zhí)行下列運算：

x:=a；

y:=b；

temp:=x；

x:=y；

y:=temp10.3.2傳地址（變量參數(shù)call-by-address、call-by-location、call-by-reference）

例如：過程swap(varx,y:integer);swap(a,b）；（a,b為調(diào)用時的實參）調(diào)用結果a,b的值被改變。傳地址的實現(xiàn)把實在參數(shù)的地址傳遞給相應的形參，即調(diào)用過程把一個指向?qū)崊⒌拇鎯Φ刂返闹羔槀鬟f給被調(diào)用過程相應的形參：（1）實在參數(shù)是一個名字，或具有左值的表達式----傳遞左值（2）實在參數(shù)是無左值的表達式----計算值，放入一存儲單元，傳此存儲單元地址（3）目標代碼中，被調(diào)用過程對形參的引用變成對傳遞給被調(diào)用過程的指針的間接引用procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用swap(i,a[i])其結果等價于執(zhí)行下列運算：1把i和a[i]的地址分別放到x和y相應的單元a1,a22(temp:=x；)temp的內(nèi)容置為a1所指單元中存的內(nèi)容

3(x:=