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

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

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

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

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

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

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

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

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

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

變長(zhǎng)塊管理通常有三種不同的分配策略：

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

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

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

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

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

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

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

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

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

Q

R

TOP

R的活動(dòng)記錄SP

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

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

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

返回地址實(shí)參（形式單元）SP

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

(2)

vara:array[0..10]ofinteger;

(3)

x:integer;

(4)

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

(5)

vari:integer;

(6)

begin…a…end{readarray};//readarray的過(guò)程體

(7)

procedureexchange(i,j:integer);

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

(8)

begin

(9)

x∶=a[i];a[i]∶=a[j];a[j]∶=x;//exchange的過(guò)程體

(10)

end{exchange};

(11)

procedurequicksort(m,n:integer);

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

(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的過(guò)程體

(20)begin…end{sort}.//sort的例程體圖10.11具有嵌套過(guò)程的PASCAL程序圖10.11的PASCAL程序中過(guò)程定義的嵌套情況如下：

sort

readarray

exchange

quicksort

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

sort的局部變量

關(guān)鍵技術(shù)：解決對(duì)非局部量的引用（存取）。設(shè)法跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄AR的位置。跟蹤辦法：

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

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

圖10.13嵌套定義過(guò)程的活動(dòng)記錄和存儲(chǔ)棧(a)局部變量┆存取鏈控制鏈TOPSP┆┆存取鏈控制鏈(老SP)┆┆TOPSP(b)quicksort的ARsort的AR再回到圖10.11的例子。如果該程序的某次執(zhí)行順序?yàn)椋?/p>

sort→quicksort→quicksort→partition→exchange…

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

圖10.15給出了進(jìn)入過(guò)程exchange之后運(yùn)行棧的示意，我們僅把存取鏈和控制鏈的值標(biāo)明。

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

解決對(duì)非局部量的引用（存取）的有效辦法是用Display表。Display表---嵌套層次顯示表，即每進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄的同時(shí)建立一張Display表。當(dāng)前激活過(guò)程的層次為K，它的Display表含有K+1個(gè)單元，依次存放著現(xiàn)行層，直接外層…直至最外層的每一過(guò)程的最新活動(dòng)記錄的基地址。例：programmain(i,0);程序結(jié)構(gòu)圖……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òng)記錄

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

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

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

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

displaysptop（3）R的活動(dòng)記錄Q的活動(dòng)記錄

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

d[1]d[0]

displaytopsp（4）DISPLAY表的維護(hù)和建立DISPLAY表d運(yùn)行棧

0主程活動(dòng)記錄地址

1R活動(dòng)記錄地址

...

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

老SP1

返回地址2

全局DISPLAY地址3

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

dDISPLAY...

簡(jiǎn)單變量

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

臨時(shí)變量

分程序結(jié)構(gòu)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;

分程序結(jié)構(gòu)的存儲(chǔ)分配方案

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

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

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

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

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

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

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

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

B1T

OB的

信

息

向

量

ZB1的

PDISPLAY

形式單元

m,n2連

接數(shù)

據(jù)A的TOP

∶

∶(b)進(jìn)

入

分

程

序B1DISPLAY

形式單元

m,n2連

接數(shù)

據(jù)

∶

∶(a)到

達(dá)

標(biāo)

號(hào)B1處A的TOP

（d）進(jìn)入分程序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)進(jìn)入分程序B4分配數(shù)組C之后

數(shù)

組C

數(shù)

組BC的

向

量

內(nèi)

情B4的TOPB的

內(nèi)

情

向

量

ZB1的TOPDISPLAY

形式單元

m,n2連

接

數(shù)

據(jù)A的TOP

∶

∶(f)進(jìn)入分程序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過(guò)程非局變量a[i]和a[j]的值進(jìn)行交換，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.

帶有過(guò)程swap的PASCAL程序

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

其結(jié)果：a,b調(diào)用前的值不改變。傳值的實(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í)，就像使用局部變量一樣使用這些形式單元。procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用swap(a,b)過(guò)程將不會(huì)影響a和b的值。其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算：

x:=a；

y:=b；

temp:=x；

x:=y；

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

例如：過(guò)程swap(varx,y:integer);swap(a,b）；（a,b為調(diào)用時(shí)的實(shí)參）調(diào)用結(jié)果a,b的值被改變。傳地址的實(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ò)程的指針的間接引用procedureswap(x,y:integer);vartemp:integer;begintemp:=x;x:=y；y:=tempend；調(diào)用swap(i,a[i])其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算：1把i和a[i]的地址分別放到x和y相應(yīng)的單元a1,a22(temp:=x；)temp的內(nèi)容置為a1所指單元中存的內(nèi)容

3(x:=