第5章運(yùn)行環(huán)境5.1過(guò)程的動(dòng)態(tài)特性

5.2運(yùn)行時(shí)數(shù)據(jù)空間的組織

5.3棧式動(dòng)態(tài)分配

5.4本章小結(jié)

5.1過(guò)程的動(dòng)態(tài)特性5.1.1過(guò)程與活動(dòng)過(guò)程的每一次運(yùn)行(或執(zhí)行)被稱(chēng)為一次活動(dòng)(activation)?；顒?dòng)是一個(gè)動(dòng)態(tài)的概念，除了設(shè)計(jì)為永不停機(jī)的過(guò)程(如操作系統(tǒng)等)，或者是因設(shè)計(jì)錯(cuò)誤而出現(xiàn)死循環(huán)的過(guò)程之外，任何過(guò)程的活動(dòng)均有有限的生存期(lifetime)。

定義5.1

活動(dòng)的生存期是指從進(jìn)入活動(dòng)的第一條指令執(zhí)行到離開(kāi)此活動(dòng)前的最后一條指令執(zhí)行的這段時(shí)間，其中包括調(diào)用其它過(guò)程時(shí)其它活動(dòng)的生存期。 活動(dòng)之間存在兩種調(diào)用關(guān)系：如果活動(dòng)A調(diào)用活動(dòng)B，從B中退出后又調(diào)用活動(dòng)C，B和C是被順序調(diào)用的活動(dòng)，顯然被順序調(diào)用的活動(dòng)的生存期是不交的；如果活動(dòng)A調(diào)用活動(dòng)B，而活動(dòng)B又調(diào)用活動(dòng)C，B和C是被嵌套調(diào)用的關(guān)系。特別需要指出的是，活動(dòng)的嵌套與過(guò)程的嵌套是兩個(gè)截然不同的概念。

過(guò)程的嵌套實(shí)際上是過(guò)程定義的嵌套，是指在一個(gè)過(guò)程的定義中包含另外一個(gè)過(guò)程的定義，這是一個(gè)靜態(tài)的概念，僅從讀源程序就可以確定過(guò)程之間的嵌套定義關(guān)系。而活動(dòng)的嵌套實(shí)際上是活動(dòng)調(diào)用的嵌套或者活動(dòng)生存期的嵌套，是指當(dāng)一個(gè)活動(dòng)正在執(zhí)行時(shí)，又調(diào)用了另外的活動(dòng)，這是一個(gè)動(dòng)態(tài)的概念，它們的嵌套關(guān)系是由確定活動(dòng)執(zhí)行軌跡的條件(例如參數(shù)等)動(dòng)態(tài)確定的。

順序執(zhí)行的程序的最大特征是程序的執(zhí)行在時(shí)間上是順序的和排他的。即一個(gè)程序的運(yùn)行軌跡由若干個(gè)順序或嵌套的活動(dòng)組成，并且在程序執(zhí)行的任一瞬間，有且僅有一個(gè)活動(dòng)正在活動(dòng)。假想時(shí)間是一支筆，則任何一個(gè)順序程序的執(zhí)行過(guò)程(控制流)是一個(gè)“一筆畫(huà)”，于是順序程序運(yùn)行時(shí)的控制流滿(mǎn)足以下兩點(diǎn)：

(1)控制流是連續(xù)的；

(2)過(guò)程間的控制流可以用樹(shù)來(lái)表示。

定義5.2

用來(lái)描繪控制進(jìn)入和離開(kāi)活動(dòng)方式的樹(shù)結(jié)構(gòu)被稱(chēng)為活動(dòng)樹(shù)，在活動(dòng)樹(shù)中：

(1)每個(gè)結(jié)點(diǎn)代表過(guò)程的一個(gè)活動(dòng)；

(2)根代表主程序的活動(dòng)；

(3)結(jié)點(diǎn)a是結(jié)點(diǎn)b的父親，當(dāng)且僅當(dāng)控制流從a的活動(dòng)進(jìn)入b的活動(dòng)；

(4)結(jié)點(diǎn)a處于結(jié)點(diǎn)b的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期。

活動(dòng)樹(shù)的實(shí)質(zhì)是它反映了順序執(zhí)行程序的調(diào)用和時(shí)序關(guān)系，它把每個(gè)活動(dòng)的生存期縮小到了一點(diǎn)。也就是說(shuō)，如果我們關(guān)心的僅是活動(dòng)之間的控制流和它們的生存期，而不關(guān)心活動(dòng)究竟執(zhí)行了多少時(shí)間的話(huà)，活動(dòng)樹(shù)是最好的表示形式?！纠?.1】

階乘函數(shù)的計(jì)算可以用下述程序test實(shí)現(xiàn)，首先調(diào)用get_line(n)得到一個(gè)整型數(shù)值，然后調(diào)用遞歸函數(shù)f(n)計(jì)算出n的階乘，最后將結(jié)果輸出。令n=4，則程序運(yùn)行時(shí)活動(dòng)的軌跡如圖5.1(a)所示。其中縱向是時(shí)間軸，橫向反映控制流，即調(diào)用與返回關(guān)系。如果忽略活動(dòng)執(zhí)行的時(shí)間，僅考慮控制流的流向，即將圖5.1(a)各活動(dòng)執(zhí)行時(shí)間均壓縮為一個(gè)點(diǎn)，且將其旋轉(zhuǎn)90o0，則演變成為如圖5.1(b)所示的活動(dòng)樹(shù)。樹(shù)的邊是雙向的，既表示調(diào)用又表示返回。圖5.1順序執(zhí)行的程序的控制流(a)活動(dòng)的調(diào)用關(guān)系與生存期；(b)僅反映控制流的活動(dòng)樹(shù)proceduretestisn:integer;proceduref(n:integer)returnintegerisbegin ifi<2thenreturn1;elsereturnn*f(n-1);endif;endf;beginget_line(n);n:=f(n);put_line(n);endtest;【例5.2】

考慮例4.14的快排序過(guò)程。如果忽略partition中對(duì)exchange的調(diào)用，則對(duì)于某個(gè)初始數(shù)據(jù)，sort的活動(dòng)樹(shù)可能如圖5.2(a)所示。其中的s、r、q、p分別是sort、readarray、quicksort和partition的縮寫(xiě)。圖5.2(a)反映了活動(dòng)的嵌套，而圖4.32(a)反映了過(guò)程的嵌套。圖5.2活動(dòng)樹(shù)與控制棧5.1.2控制棧與活動(dòng)記錄一個(gè)完整程序執(zhí)行的控制流，恰好是對(duì)它的活動(dòng)樹(shù)的一次深度優(yōu)先遍歷。根據(jù)順序執(zhí)行程序的控制流特性，活動(dòng)樹(shù)上各節(jié)點(diǎn)之間具有下述關(guān)系：

(1)同一層次的活動(dòng)生存期不交；

(2)任一時(shí)刻，處在生存期的活動(dòng)構(gòu)成一條從根到某節(jié)點(diǎn)的路徑；

(3)路徑上各節(jié)點(diǎn)生存期是嵌套的(后進(jìn)先出)。

換句話(huà)說(shuō)，任何時(shí)刻僅需要為所有處在生存期的活動(dòng)提供它們的活動(dòng)場(chǎng)所，稱(chēng)為運(yùn)行環(huán)境。根據(jù)上述的②和③，很顯然，運(yùn)行環(huán)境的最佳數(shù)據(jù)結(jié)構(gòu)應(yīng)該是一個(gè)棧，稱(chēng)為控制棧。而棧上的每個(gè)節(jié)點(diǎn)是每個(gè)活動(dòng)的運(yùn)行環(huán)境，稱(chēng)為活動(dòng)記錄(activationrecord)。每個(gè)活動(dòng)開(kāi)始時(shí)，就為它分配一個(gè)活動(dòng)記錄，即將此活動(dòng)記錄分配在棧頂上?；顒?dòng)的整個(gè)生命期中活動(dòng)記錄一直存在，而當(dāng)活動(dòng)結(jié)束時(shí)，將它從當(dāng)前棧頂取消?？刂茥５臈ｍ斠话阌蓆op指示，為了提高效率，top一般放在寄存器中。

活動(dòng)記錄中至少應(yīng)該存放兩類(lèi)信息：

(1)控制信息：用于控制活動(dòng)的正確調(diào)用與返回和用于控制活動(dòng)記錄的正確切換；

(2)訪(fǎng)問(wèn)信息：用于為當(dāng)前活動(dòng)提供對(duì)數(shù)據(jù)，如本地?cái)?shù)據(jù)和非本地?cái)?shù)據(jù)的訪(fǎng)問(wèn)?！纠?.3】圖5.2(b)給出了快排序程序運(yùn)行時(shí)的某個(gè)狀態(tài)，從s開(kāi)始，實(shí)線(xiàn)條所鏈接的活動(dòng)構(gòu)成了活動(dòng)樹(shù)上的一條路徑，也是控制棧的一個(gè)狀態(tài)，在當(dāng)前狀態(tài)下，棧中共有4個(gè)節(jié)點(diǎn)，分別是s、q(1,9)、q(1,3)、q(1,0)。這些活動(dòng)均處在它們的生存期，但是只有棧頂?shù)膓(1,0)是正在活動(dòng)的活動(dòng)。5.1.3名字的綁定

定義5.3

運(yùn)行時(shí)為名字X分配存儲(chǔ)空間S，這一過(guò)程稱(chēng)為綁定(binding)。綁定是名字X與存儲(chǔ)空間S的結(jié)合。此處，名字X是一個(gè)對(duì)象，它既可以是數(shù)據(jù)對(duì)象，如變量，與之結(jié)合的是一個(gè)存儲(chǔ)單元，也可以是操作對(duì)象，如過(guò)程，與之結(jié)合的是一段可執(zhí)行的代碼。本章的討論僅限于X是一個(gè)數(shù)據(jù)對(duì)象。

現(xiàn)在有兩個(gè)關(guān)于名字的問(wèn)題：名字的聲明與名字的綁定。它們都需要有對(duì)應(yīng)的存儲(chǔ)空間，而存儲(chǔ)空間的對(duì)應(yīng)方式，一個(gè)是靜態(tài)的，一個(gè)是動(dòng)態(tài)的。聲明時(shí)我們關(guān)心的是聲明的作用域，即當(dāng)一個(gè)名字被引用時(shí)，在不同的作用域中與該名字的不同聲明結(jié)合；綁定時(shí)我們關(guān)心的是綁定的生存期，即當(dāng)一個(gè)名字在運(yùn)行時(shí)被實(shí)際分配的存儲(chǔ)單元，名字與存儲(chǔ)單元結(jié)合的這段時(shí)間被稱(chēng)為綁定的生存期，顯然這個(gè)生存期應(yīng)該和名字的生存期是一致的。表5.1靜態(tài)與動(dòng)態(tài)

在名字綁定的概念下，對(duì)一個(gè)變量的賦值，實(shí)際上是通過(guò)兩步映射來(lái)實(shí)現(xiàn)的。源程序中的一個(gè)名字，需要經(jīng)過(guò)名字的綁定將名字映射到一個(gè)實(shí)際的存儲(chǔ)空間，然后經(jīng)過(guò)賦值將此存儲(chǔ)空間映射到一個(gè)實(shí)際的值。名字到存儲(chǔ)空間的映射被稱(chēng)為“環(huán)境”，存儲(chǔ)空間到值的映射被稱(chēng)為“狀態(tài)”。由于存儲(chǔ)空間對(duì)應(yīng)的是左值，而值對(duì)應(yīng)的是右值，因此我們也可以說(shuō)，環(huán)境將名字映射到左值，狀態(tài)將左值映射到右值，或者說(shuō)環(huán)境改變存儲(chǔ)空間，狀態(tài)改變值。同樣，在名字綁定的概念下，對(duì)一個(gè)常量的賦值實(shí)質(zhì)上就是直接將名字與一個(gè)具體的值綁定，或者說(shuō)環(huán)境將名字映射到右值，或者說(shuō)環(huán)境直接改變值。變量與常量的映射關(guān)系分別如圖5.3(a)、(b)所示。由于表示常量的名字沒(méi)有左值，因此，常量是不能通過(guò)賦值句被改變的。【例5.4】對(duì)于賦值句x:=3.14，首先為x分配一個(gè)存儲(chǔ)單元S，然后將3.14賦值給S。對(duì)于常量聲明constpi=3.14，直接將pi與3.14綁定，于是在程序運(yùn)行的任何時(shí)刻，pi的值不能被改變。它們的映射關(guān)系分別如圖5.3(c)、(d)所示。圖5.3變量與常量名字的映射(a)變量名字的映射；(b)常量名字的映射；(c)x:=3.14的映射；(d)pi=3.14的映射

在允許過(guò)程遞歸的情況下，當(dāng)一個(gè)活動(dòng)還沒(méi)有執(zhí)行完成時(shí)，可能又會(huì)進(jìn)入同一過(guò)程的另一個(gè)活動(dòng)。為了同時(shí)保存兩個(gè)同一過(guò)程活動(dòng)的運(yùn)行環(huán)境，同一作用域中的一個(gè)名字在運(yùn)行時(shí)可能會(huì)被分配多個(gè)存儲(chǔ)空間，也就是說(shuō)，同一作用域中的一個(gè)名字可以同時(shí)綁定到多個(gè)存儲(chǔ)單元。例如圖5.2(b)中同一個(gè)快排序過(guò)程的三個(gè)活動(dòng)的活動(dòng)記錄q(1,9)、q(1,3)和q(1,0)均被放在控制棧中，相同參數(shù)在三個(gè)活動(dòng)記錄中有不同的存儲(chǔ)空間用于存放不同的值，從而使得在快排序的遞歸調(diào)用中，能夠通過(guò)實(shí)在參數(shù)的值進(jìn)行正確的排序操作。因此，環(huán)境是一個(gè)一對(duì)多的映射。同樣，由于一個(gè)存儲(chǔ)單元可以存放不同的值，狀態(tài)也是一個(gè)一對(duì)多的映射。

編譯器怎樣對(duì)存儲(chǔ)空間進(jìn)行組織和采用什么樣的存儲(chǔ)分配策略，很大程度上取決于程序設(shè)計(jì)語(yǔ)言中所采用的機(jī)制，如過(guò)程能否遞歸、過(guò)程能否嵌套、過(guò)程調(diào)用時(shí)參數(shù)如何傳遞、哪些實(shí)體可以作為參數(shù)和返回值、是否允許動(dòng)態(tài)的為對(duì)象分配和撤銷(xiāo)存儲(chǔ)空間、存儲(chǔ)空間是否必須顯式地釋放，等等。5.2運(yùn)行時(shí)數(shù)據(jù)空間的組織5.2.1運(yùn)行時(shí)內(nèi)存的劃分與數(shù)據(jù)空間的存儲(chǔ)分配策略程序運(yùn)行時(shí)，內(nèi)存用來(lái)保存可執(zhí)行代碼和代碼所操作的數(shù)據(jù)。可執(zhí)行代碼的大小在編譯時(shí)可以靜態(tài)確定，因此可以把它放在靜態(tài)數(shù)據(jù)區(qū)。而對(duì)于數(shù)據(jù)，可以有三種存儲(chǔ)方式，對(duì)應(yīng)三種組織形式的數(shù)據(jù)區(qū)，它們分別是靜態(tài)數(shù)據(jù)區(qū)、棧和堆。靜態(tài)數(shù)據(jù)區(qū)用于存放一對(duì)一的綁定且編譯時(shí)就可確定存儲(chǔ)空間大小的數(shù)據(jù)；棧用于存放一對(duì)多的綁定且與活動(dòng)同生存期的數(shù)據(jù)；堆用于存放與活動(dòng)生存期不一致且可以動(dòng)態(tài)生成和撤消的數(shù)據(jù)，典型的如PASCAL中new(p)和dispose(p)等。棧與堆的典型安排如圖5.4所示，它們的增長(zhǎng)空間是共享的。圖5.4內(nèi)存空間劃分

三種數(shù)據(jù)區(qū)對(duì)應(yīng)著下述三種不同的分配策略，編譯器具體實(shí)現(xiàn)時(shí)，根據(jù)語(yǔ)言機(jī)制的特性，可以采用三種方式的其中若干種。

(1)靜態(tài)分配策略：編譯時(shí)安排所有數(shù)據(jù)對(duì)象的存儲(chǔ)；

(2)棧分配策略：按棧的方式管理運(yùn)行時(shí)的存儲(chǔ)；

(3)堆分配策略：在運(yùn)行時(shí)根據(jù)要求從堆數(shù)據(jù)區(qū)動(dòng)態(tài)地分配和釋放存儲(chǔ)空間。5.2.2靜態(tài)與動(dòng)態(tài)分配簡(jiǎn)介

1．靜態(tài)分配策略在靜態(tài)分配中，名字在程序編譯時(shí)與存儲(chǔ)空間結(jié)合，運(yùn)行時(shí)不再改變，每次過(guò)程活動(dòng)時(shí)，過(guò)程中的名字映射到同一存儲(chǔ)單元。這種性質(zhì)允許局部名字的值在活動(dòng)停止后仍能保持，即當(dāng)控制再次進(jìn)入活動(dòng)時(shí)，變量的值和控制上一次離開(kāi)時(shí)相同。

采用靜態(tài)分配策略的存儲(chǔ)空間可以組織如下，編譯器為每個(gè)模塊分配一塊連續(xù)的存儲(chǔ)空間，根據(jù)模塊中名字的類(lèi)型確定它所需空間的大小。為了稱(chēng)呼上的統(tǒng)一，我們稱(chēng)每個(gè)模塊的數(shù)據(jù)區(qū)為活動(dòng)記錄。由于每個(gè)活動(dòng)記錄的大小均是確定的，所以若干活動(dòng)記錄組成的連續(xù)存儲(chǔ)空間的大小也是確定的。這一確定的空間在程序運(yùn)行時(shí)一并裝入內(nèi)存，而不管各活動(dòng)記錄是否在某次特定的運(yùn)行中被使用，程序運(yùn)行時(shí)不再有對(duì)存儲(chǔ)空間的分配。

靜態(tài)數(shù)據(jù)區(qū)中變量的地址可以有兩種表示方法。以圖5.5中變量X的地址Δx為例，它可以相對(duì)base尋址，也可以相對(duì)base2尋址。事實(shí)上，由于數(shù)據(jù)的靜態(tài)特性，所有的basei相對(duì)于base的偏移量均是編譯時(shí)可以確定的常量，因此兩種表示方法沒(méi)有實(shí)質(zhì)性區(qū)別。但是，相對(duì)于basei尋址的方法，可以將靜態(tài)存儲(chǔ)分配與棧式存儲(chǔ)分配的方法統(tǒng)一起來(lái)，同時(shí)也有利于將各活動(dòng)記錄中的共享數(shù)據(jù)提取出來(lái)進(jìn)行統(tǒng)一處理。圖5.5靜態(tài)存儲(chǔ)分配

靜態(tài)分配的特點(diǎn)，使得它所適用的程序設(shè)計(jì)語(yǔ)言在某些方面受到限制：

(1)數(shù)據(jù)對(duì)象的大小和它在內(nèi)存中位置的限制必須在編譯時(shí)確定，如數(shù)組的大小不能是動(dòng)態(tài)的；

(2)不允許程序遞歸，因?yàn)橐粋€(gè)過(guò)程的所有活動(dòng)使用同樣的名字綁定，即綁定是一對(duì)一的；

(3)不允許動(dòng)態(tài)生成數(shù)據(jù)，因?yàn)闆](méi)有運(yùn)行時(shí)的存儲(chǔ)分配機(jī)制。FORTRAN語(yǔ)言可以完全采用靜態(tài)存儲(chǔ)分配策略，因?yàn)镕ORTRAN滿(mǎn)足上述限制。但是，F(xiàn)ORTRAN中的等價(jià)片與公用區(qū)機(jī)制，使得分配比較復(fù)雜。允許分別編譯的程序設(shè)計(jì)語(yǔ)言，分別編譯模塊中的數(shù)據(jù)定義模塊(特別是全程引用的數(shù)據(jù))，也可以采用靜態(tài)分配策略，因?yàn)樗鼈円话阍谡麄€(gè)程序運(yùn)行的期間是被共享的。

2．棧分配策略棧分配策略是一種動(dòng)態(tài)分配的策略，它的基礎(chǔ)是活動(dòng)的控制棧，所有與活動(dòng)同生存期的數(shù)據(jù)均可以采用棧分配策略。當(dāng)活動(dòng)處在生存期時(shí)，相應(yīng)的數(shù)據(jù)被分配，生存期結(jié)束后，數(shù)據(jù)被撤銷(xiāo)。對(duì)于這樣的數(shù)據(jù)，他們的分配與撤銷(xiāo)實(shí)際上就是控制棧上活動(dòng)記錄的分配與撤銷(xiāo)?；顒?dòng)記錄被分配在棧數(shù)據(jù)區(qū)中，棧頂由統(tǒng)一的棧頂指針top指示?；顒?dòng)記錄的大小如果是L，則活動(dòng)開(kāi)始時(shí)(確切講應(yīng)是開(kāi)始前)，top增加L，活動(dòng)結(jié)束后，top減少L。

對(duì)于靜態(tài)分配策略分配的數(shù)據(jù)，棧分配策略均可進(jìn)行分配。因?yàn)殪o態(tài)分配數(shù)據(jù)的特征是編譯時(shí)可以確定大小，所以棧分配策略可以把這些靜態(tài)可確定的數(shù)據(jù)在編譯時(shí)就安排在棧的底部。而對(duì)于靜態(tài)存儲(chǔ)分配無(wú)法處理的遞歸程序調(diào)用問(wèn)題和動(dòng)態(tài)數(shù)組問(wèn)題，均可以采用棧分配的策略來(lái)解決，因?yàn)檫f歸調(diào)用的活動(dòng)的活動(dòng)記錄的分配和撤銷(xiāo)，可以在程序運(yùn)行時(shí)(活動(dòng)活動(dòng)時(shí))動(dòng)態(tài)地添加到棧頂，或是從棧頂撤銷(xiāo)；動(dòng)態(tài)數(shù)組的存儲(chǔ)空間大小，也可以根據(jù)保存在活動(dòng)記錄中的內(nèi)情向量信息計(jì)算出來(lái)，然后動(dòng)態(tài)地添加在當(dāng)前的棧頂。

雖然棧分配策略是可以進(jìn)行動(dòng)態(tài)分配的，但是由于可以進(jìn)行棧分配的數(shù)據(jù)必須與活動(dòng)同生存期，所以它對(duì)程序設(shè)計(jì)語(yǔ)言的下述要求也無(wú)法滿(mǎn)足：

(1)當(dāng)活動(dòng)停止時(shí)，局部活動(dòng)中名字的值必須保持(否則會(huì)出現(xiàn)懸空引用)；

(2)在程序運(yùn)行的任意時(shí)刻，可以隨時(shí)生成或撤銷(xiāo)的動(dòng)態(tài)數(shù)據(jù)；

(3)被調(diào)用者的活動(dòng)比調(diào)用者的活得更長(zhǎng)，此時(shí)，活動(dòng)樹(shù)不能正確描繪過(guò)程間的控制流。

3．堆分配策略堆分配策略是三種分配策略中最靈活的一種，它對(duì)程序設(shè)計(jì)語(yǔ)言幾乎不做什么限制，可以采用靜態(tài)分配策略或棧分配策略進(jìn)行分配的數(shù)據(jù)，均可采用堆分配策略。同時(shí)，對(duì)于棧分配策略不能分配的數(shù)據(jù)，堆分配策略也可以進(jìn)行分配。堆分配策略采用一個(gè)雙向鏈表的結(jié)構(gòu)，將所有可以被分配的自由空間鏈接在鏈表中，鏈表中的每個(gè)節(jié)點(diǎn)指示一個(gè)連續(xù)可用空間的信息，典型的如可用空間的起始和結(jié)束地址。節(jié)點(diǎn)的順序應(yīng)與可用空間的地址先后一致。

堆分配的思想并不復(fù)雜，當(dāng)需要空間時(shí)，就在鏈表的節(jié)點(diǎn)中找到一塊大小合適的區(qū)域，將區(qū)域中的部分或全部分給需要空間的對(duì)象，并將已分配的空間從鏈表的節(jié)點(diǎn)信息中刪除，根據(jù)是全部還是部分分配，將節(jié)點(diǎn)從鏈中摘除或者修改節(jié)點(diǎn)可用空間信息。當(dāng)空間需要釋放時(shí)，首先在鏈表中進(jìn)行查找，看是否釋放的空間與某個(gè)(或某兩個(gè)連續(xù)的)節(jié)點(diǎn)中的可用空間相鄰：若與一個(gè)相鄰，則修改當(dāng)前鏈表中的節(jié)點(diǎn)可用信息；若與兩個(gè)相連，則合并兩個(gè)節(jié)點(diǎn)為一個(gè)節(jié)點(diǎn)，且修改節(jié)點(diǎn)中的可用空間信息；若不與任何可用空間相鄰，則在鏈表的適當(dāng)位置加入一個(gè)新的節(jié)點(diǎn)。

一開(kāi)始，鏈表中僅有一個(gè)節(jié)點(diǎn)，它提供的是一個(gè)連續(xù)的可用空間的全部。隨著程序的運(yùn)行，各活動(dòng)和動(dòng)態(tài)分配的數(shù)據(jù)不斷地從可用空間中獲取存儲(chǔ)空間，或者將釋放的空間放回可用空間。經(jīng)過(guò)一段時(shí)間之后，堆中可能包含交錯(cuò)出現(xiàn)的正在使用和已經(jīng)釋放的區(qū)域，使得到一定的時(shí)候，堆分配的可用存儲(chǔ)空間變成若干個(gè)不連續(xù)的可用空間(如圖5.6(a)、(b)所示)。如果存儲(chǔ)空間的分配與撤銷(xiāo)算法設(shè)計(jì)不合理，就會(huì)造成程序運(yùn)行到一定的時(shí)刻，所有可用的存儲(chǔ)空間被分割成許許多多不連續(xù)的碎片，使得無(wú)法再進(jìn)行分配。因此堆分配的空間分配與撤銷(xiāo)算法的核心思想之一，就是使可用存儲(chǔ)空間盡可能地保持連續(xù)。當(dāng)然，算法的效率也是需要考慮的問(wèn)題之一。圖5.6堆分配(a)堆分配的存儲(chǔ)空間；(b)堆分配的可用存儲(chǔ)空間鏈5.3棧式動(dòng)態(tài)分配5.3.1控制棧中的活動(dòng)記錄前邊已經(jīng)提到，控制棧中的活動(dòng)記錄的作用是為當(dāng)前的活動(dòng)提供運(yùn)行環(huán)境，因此它既需要提供活動(dòng)所操作的數(shù)據(jù)對(duì)象的存儲(chǔ)空間，也需要提供適當(dāng)?shù)男畔?，以保證活動(dòng)調(diào)用與返回時(shí)實(shí)現(xiàn)代碼的正確轉(zhuǎn)移和活動(dòng)記錄的正確切換，即活動(dòng)記錄中需要保存兩類(lèi)信息：控制信息與訪(fǎng)問(wèn)信息。活動(dòng)記錄的具體內(nèi)容可如下：圖5.7活動(dòng)記錄的內(nèi)容(1)參數(shù)與返回地址：用于存放實(shí)參和返回地址，如果是函數(shù)，還應(yīng)有返回值；

(2)控制鏈：指向調(diào)用者活動(dòng)記錄的指針，用于當(dāng)調(diào)用返回時(shí)，將當(dāng)前棧頂正確切換到調(diào)用者的活動(dòng)記錄；如果是靜態(tài)分配，該項(xiàng)可以沒(méi)有；

(3)訪(fǎng)問(wèn)鏈：用于指示訪(fǎng)問(wèn)非本地?cái)?shù)據(jù)；當(dāng)過(guò)程不允許嵌套時(shí)，該項(xiàng)也可以沒(méi)有；(4)調(diào)用時(shí)需要保存的機(jī)器狀態(tài)。如程序計(jì)數(shù)器，寄存器等，對(duì)于某特定的計(jì)算機(jī)，這些被保存信息是固定的；

(5)過(guò)程內(nèi)部聲明的數(shù)據(jù)，如VARX，Y:INTEGER等；

(6)臨時(shí)變量：源程序中不出現(xiàn)的、由編譯器產(chǎn)生的變量，如表達(dá)式x+y+z計(jì)值時(shí)產(chǎn)生的T1，T2，…；指示當(dāng)前活動(dòng)記錄的一般有兩個(gè)指針，一個(gè)是當(dāng)前的棧頂指針top，另一個(gè)是用于數(shù)據(jù)訪(fǎng)問(wèn)的sp。活動(dòng)記錄中的所有數(shù)據(jù)，均可以是相對(duì)于sp的偏移量。通常，top和sp分別放在兩個(gè)寄存器中，并且讓sp作為活動(dòng)記錄的代表?！纠?.5】

回顧圖5.2(b)控制棧的一個(gè)狀態(tài)，當(dāng)前棧中有4個(gè)活動(dòng)記錄s、q(1,9)、q(1,3)、q(1,0)。從活動(dòng)s開(kāi)始，控制棧中的活動(dòng)記錄需要根據(jù)控制流的轉(zhuǎn)變，經(jīng)過(guò)一系列的變化，才能到達(dá)當(dāng)前的狀態(tài)。活動(dòng)s剛開(kāi)始時(shí)，棧中僅有s的活動(dòng)記錄。當(dāng)s調(diào)用r之后，棧頂加入了r的活動(dòng)記錄。當(dāng)控制從r退出，又進(jìn)入q(1,9)時(shí)，首先需要在退出r時(shí)將r的活動(dòng)記錄從棧頂彈出，然后再將q(1,9)的活動(dòng)記錄壓進(jìn)棧。圖5.8給出了控制流與控制棧的部分變化過(guò)程。圖5.8控制流與活動(dòng)記錄5.3.2調(diào)用序列與返回序列實(shí)現(xiàn)控制流正確轉(zhuǎn)移和活動(dòng)記錄正確切換的方法，是在過(guò)程發(fā)生調(diào)用和返回處加入適當(dāng)?shù)目蓤?zhí)行代碼：調(diào)用處加入的代碼被稱(chēng)為調(diào)用序列(callsequence)，返回處加入的代碼稱(chēng)為返回序列(returnsequence)。以圖5.9所示的源程序中過(guò)程A調(diào)用過(guò)程B為例，調(diào)用前的棧頂是A的活動(dòng)記錄，top(A)指向當(dāng)前棧頂，A代碼段中的變量i相對(duì)于sp(A)尋址(如：Δi[sp]:=Δi[sp]+1)。調(diào)用發(fā)生時(shí)，調(diào)用序列將B的活動(dòng)記錄加入到棧頂，使得棧頂指針改變?yōu)閠op(B)，而B(niǎo)中的變量j相對(duì)于sp(B)尋址(如：Δj[sp]:=Δj[sp]+1)。B運(yùn)行結(jié)束返回時(shí)，將當(dāng)前棧頂?shù)幕顒?dòng)記錄彈出，又恢復(fù)到調(diào)用前的top(A)和sp(A)。圖5.9過(guò)程的調(diào)用與返回

這一系列的控制流轉(zhuǎn)移和棧頂活動(dòng)記錄的切換，由調(diào)用序列和返回序列來(lái)完成。一般來(lái)講，調(diào)用序列和返回序列的內(nèi)容既可以放在調(diào)用者中，也可以放在被調(diào)用者中。經(jīng)驗(yàn)認(rèn)為，能讓被調(diào)用者做的事情盡量不要讓調(diào)用者做，因?yàn)樵诒徽{(diào)用者中只需要一個(gè)序列，而在調(diào)用者中每調(diào)用一次就需要一個(gè)序列。表5.2是一個(gè)可能的調(diào)用序列與返回序列的安排，其中圖5.9的①和②形成調(diào)用序列，③和④形成返回序列。表5.2調(diào)用序列與返回序列5.3.3棧式分配中對(duì)非本地名字的訪(fǎng)問(wèn)如果過(guò)程不允許嵌套定義，則過(guò)程中只可能訪(fǎng)問(wèn)局部于過(guò)程的本地?cái)?shù)據(jù)和全局的靜態(tài)數(shù)據(jù)。全局?jǐn)?shù)據(jù)可以放在靜態(tài)數(shù)據(jù)區(qū)中(或者棧底)，而本地?cái)?shù)據(jù)均可以放在過(guò)程的活動(dòng)記錄中，且相對(duì)于活動(dòng)記錄的sp尋址。如果過(guò)程允許嵌套定義，則過(guò)程中會(huì)訪(fǎng)問(wèn)到一些定義在其它過(guò)程中的數(shù)據(jù)，這些數(shù)據(jù)既不是本地?cái)?shù)據(jù)，又不是全局?jǐn)?shù)據(jù)。

對(duì)允許嵌套定義過(guò)程的語(yǔ)言進(jìn)行棧式分配，需要考慮兩個(gè)關(guān)鍵問(wèn)題：

(1)名字在不同的作用域內(nèi)表示不同的數(shù)據(jù)對(duì)象；

(2)如何通過(guò)當(dāng)前的活動(dòng)記錄，訪(fǎng)問(wèn)非本地?cái)?shù)據(jù)。第一個(gè)問(wèn)題由名字的作用域規(guī)則解決(靜態(tài)作用域＋最近嵌套)，第二個(gè)問(wèn)題通過(guò)引入訪(fǎng)問(wèn)鏈的方法解決。

1．訪(fǎng)問(wèn)鏈

(1)它本身所在的位置可以作為本活動(dòng)記錄中數(shù)據(jù)尋址的基礎(chǔ)，即活動(dòng)記錄的sp。

(2)訪(fǎng)問(wèn)鏈的內(nèi)容指向它直接外層過(guò)程的最新活動(dòng)記錄的訪(fǎng)問(wèn)鏈，即最新直接外層活動(dòng)記錄的sp。如果當(dāng)前棧頂活動(dòng)記錄的過(guò)程p的嵌套深度為np,則沿當(dāng)前sp間接訪(fǎng)問(wèn)一次(習(xí)慣上稱(chēng)沿訪(fǎng)問(wèn)鏈追蹤一次)，sp所到達(dá)活動(dòng)記錄的嵌套深度減1。沿訪(fǎng)問(wèn)鏈進(jìn)行若干次追蹤，則可到達(dá)任何嵌套深度小于np過(guò)程的活動(dòng)記錄。這實(shí)際上等價(jià)于可以沿訪(fǎng)問(wèn)鏈找到所有p的外層最新活動(dòng)記錄的sp，通過(guò)這些sp就可以訪(fǎng)問(wèn)任何p的非本地?cái)?shù)據(jù)。

2．利用訪(fǎng)問(wèn)鏈訪(fǎng)問(wèn)非本地?cái)?shù)據(jù)假定過(guò)程p的嵌套深度是np，在過(guò)程p中引用一個(gè)嵌套深度為na，且na≤np的變量a。設(shè)p和a的層次之差為x，即na+x=np，于是x=np-na。則a的存儲(chǔ)可以按如下方法找到：

(1)當(dāng)控制在p中，p的一個(gè)活動(dòng)記錄肯定在棧頂。從棧頂?shù)幕顒?dòng)記錄中追蹤訪(fǎng)問(wèn)鏈np-na次。np-na

的值是靜態(tài)作用域規(guī)則決定的，可以在編譯時(shí)通過(guò)計(jì)算得到；(2)追蹤訪(fǎng)問(wèn)鏈np-na次后，找到a的聲明所在過(guò)程的活動(dòng)記錄的訪(fǎng)問(wèn)鏈sp(a)。因此，過(guò)程p中變量a的地址計(jì)算需要兩個(gè)信息：層次差np-na和偏移量Δa，它們均可以在編譯時(shí)計(jì)算得到，因此可以將有序?qū)Γ?np-na，Δa) (5.1)存放在符號(hào)表a的條目中，這些信息用于生成存取變量a的代碼。

3．如何在調(diào)用序列中生成訪(fǎng)問(wèn)鏈建立訪(fǎng)問(wèn)鏈的代碼是過(guò)程調(diào)用序列的一部分。假定嵌套深度是np的過(guò)程p調(diào)用嵌套深度為nx的過(guò)程x，則建立訪(fǎng)問(wèn)鏈分下邊兩種情況：

(1)np＜nx的情況：因?yàn)楸徽{(diào)用過(guò)程x比p嵌套得更深，根據(jù)作用域規(guī)則，x肯定直接聲明在p中。例如sort調(diào)用quicksort，quicksort調(diào)用partition等。此時(shí)，被調(diào)用過(guò)程x的訪(fǎng)問(wèn)鏈必須指向棧中剛好在它下面的調(diào)用過(guò)程p活動(dòng)記錄的訪(fǎng)問(wèn)鏈。(2)np≥nx的情況：根據(jù)作用域規(guī)則，p和x具有公共外層，即靜態(tài)包圍p和x且嵌套深度為1，2，…，nx-1的過(guò)程。例如quicksort調(diào)用本身，partition調(diào)用exchange等。從調(diào)用過(guò)程追蹤訪(fǎng)問(wèn)鏈np-(nx+1)=np-nx+1次，到達(dá)靜態(tài)包圍x和p的最接近過(guò)程的最新活動(dòng)記錄。所到達(dá)的訪(fǎng)問(wèn)鏈就是被調(diào)用過(guò)程x必須指向的訪(fǎng)問(wèn)鏈。同樣，np-nx+1 (5.2)可以在編譯時(shí)計(jì)算。

【例5.6】再考察例4.14的快排序過(guò)程。假設(shè)當(dāng)前控制棧的狀態(tài)是：s、q(1,9)、q(1,3)、p(1,3)、e(1,3)，其中，ns=1，nq=2，np=3，ne=2，則從s開(kāi)始，每個(gè)活動(dòng)記錄和訪(fǎng)問(wèn)鏈的建立過(guò)程如圖5.10所示。圖中簡(jiǎn)化的活動(dòng)記錄中cl和al分別表示控制鏈和訪(fǎng)問(wèn)鏈。左邊的控制鏈反映了動(dòng)態(tài)的調(diào)用關(guān)系(活動(dòng)的嵌套)，右邊的訪(fǎng)問(wèn)鏈反映了靜態(tài)的嵌套關(guān)系(過(guò)程嵌套)。下述是部分訪(fǎng)問(wèn)鏈建立和利用訪(fǎng)問(wèn)鏈訪(fǎng)問(wèn)非本地?cái)?shù)據(jù)的過(guò)程。

(1)s調(diào)用q(1，9)時(shí)訪(fǎng)問(wèn)鏈的建立：當(dāng)前控制棧如圖5.10(a)所示，根據(jù)公式(5.2)，ns–nq+1=1–2+1=0，直接令q(1，9)的訪(fǎng)問(wèn)鏈指向s的訪(fǎng)問(wèn)鏈地址，形成圖5.10(b)所示的訪(fǎng)問(wèn)鏈；(2)p(1,3)調(diào)用e(1,3)時(shí)訪(fǎng)問(wèn)鏈的建立：當(dāng)前控制棧如圖5.10(d)所示，np–ne+1=3–2+1=2，從p(1,3)追蹤訪(fǎng)問(wèn)鏈兩次，到達(dá)s的訪(fǎng)問(wèn)鏈，于是形成圖5.10(e)所示的訪(fǎng)問(wèn)鏈；

(3)e(1,3)中訪(fǎng)問(wèn)變量x：根據(jù)有序?qū)?5.1)的計(jì)算公式，追蹤訪(fǎng)問(wèn)鏈ne–nx=2–1=1次，到達(dá)s的訪(fǎng)問(wèn)鏈，利用此訪(fǎng)問(wèn)鏈對(duì)x進(jìn)行尋址；

(4)p(1,3)中訪(fǎng)問(wèn)數(shù)組a：追蹤訪(fǎng)問(wèn)鏈np–na=3–1=2次，也同樣到達(dá)s的訪(fǎng)問(wèn)鏈，利用此訪(fǎng)問(wèn)鏈對(duì)a進(jìn)行尋址。圖5.10活動(dòng)記錄中的控制鏈與訪(fǎng)問(wèn)鏈4．利用顯示表(display)快速訪(fǎng)問(wèn)非本地?cái)?shù)據(jù)考察訪(fǎng)問(wèn)鏈的特點(diǎn)不難看出，對(duì)于任何一個(gè)深度為i的活動(dòng)來(lái)說(shuō)，它可能訪(fǎng)問(wèn)的本地與非本地?cái)?shù)據(jù)只能是嵌套深度不大于i的、最新被調(diào)用的活動(dòng)。例如在圖5.10(d)中，當(dāng)前的活動(dòng)p(1,3)的嵌套深度是3，它除了可以訪(fǎng)問(wèn)本地的i和j之外，還可以沿訪(fǎng)問(wèn)鏈訪(fǎng)問(wèn)嵌套深度為2的最新活動(dòng)q(1,3)中的k和v，以及嵌套深度為1的最新活動(dòng)s中的a和x。雖然棧中嵌套深度為2的活動(dòng)有兩個(gè)，但是在p(1,3)中可以訪(fǎng)問(wèn)的是最新的活動(dòng)q(1,3)，而不是q(1,9)。換句話(huà)說(shuō)，在嵌套層次小于等于當(dāng)前活動(dòng)嵌套層次的活動(dòng)中，每層僅有一個(gè)活動(dòng)中的數(shù)據(jù)可以被當(dāng)前的活動(dòng)訪(fǎng)問(wèn)到。

為了加快對(duì)非本地?cái)?shù)據(jù)的訪(fǎng)問(wèn)，我們可以考慮把訪(fǎng)問(wèn)鏈組織成一個(gè)棧，稱(chēng)為顯示表(display)。顯示表中的d[i]，存放的是嵌套深度為i的最新活動(dòng)記錄的訪(fǎng)問(wèn)鏈地址。因此，一個(gè)活動(dòng)記錄處在棧頂且深度為i的活動(dòng)，可以通過(guò)顯示表的內(nèi)容直接訪(fǎng)問(wèn)任何一個(gè)它外層的非本地?cái)?shù)據(jù)，而無(wú)需再沿訪(fǎng)問(wèn)鏈進(jìn)行若干次追蹤。假定過(guò)程p的嵌套深度是np，它引用一個(gè)嵌套深度為na(na≤np)的變量a，則a的活動(dòng)記錄的訪(fǎng)問(wèn)鏈地址可以在d[na]中找到，于是過(guò)程p中變量a的地址信息的有序?qū)?5.1)可以簡(jiǎn)化為下述的(5.3)，它同樣可以在編譯時(shí)確定，并存放在符號(hào)表中。(na，Δa)(5.3)5．生成與維護(hù)顯示表在沿訪(fǎng)問(wèn)鏈追蹤的訪(fǎng)問(wèn)模式中，訪(fǎng)問(wèn)鏈只需建立，無(wú)需撤銷(xiāo)，因?yàn)榛顒?dòng)記錄的撤銷(xiāo)自然也撤銷(xiāo)了訪(fǎng)問(wèn)鏈。如果采用顯示表方式，則當(dāng)進(jìn)入和退出活動(dòng)時(shí)，均需對(duì)顯示表進(jìn)行維護(hù)。維護(hù)的方法是利用活動(dòng)記錄中的訪(fǎng)問(wèn)鏈。與前述訪(fǎng)問(wèn)鏈的方法不同，在顯示表方案中，活動(dòng)記錄中的訪(fǎng)問(wèn)鏈已不是指向直接外層的最新活動(dòng)記錄，而是指向同層次的次新活動(dòng)記錄。

維護(hù)的過(guò)程被分別加入在對(duì)應(yīng)的調(diào)用和返回序列中。一開(kāi)始，顯示表的初值被置為0，表示不指向任何活動(dòng)記錄的訪(fǎng)問(wèn)鏈。當(dāng)一個(gè)嵌套深度為i的活動(dòng)被調(diào)用時(shí)，調(diào)用序列在為它建立新的活動(dòng)記錄時(shí)，也對(duì)顯示表進(jìn)行如下修改：

(1)將d[i]的值保存在新活動(dòng)記錄的訪(fǎng)問(wèn)鏈中，并且

(2)置d[i]指向新的活動(dòng)記錄(置d[i]內(nèi)容為新活動(dòng)記錄訪(fǎng)問(wèn)鏈地址)。當(dāng)活動(dòng)結(jié)束時(shí)，返回序列中恢復(fù)d[i]原來(lái)的值，即執(zhí)行上述(1)的逆操作。6．顯示表的存儲(chǔ)分配由于順序執(zhí)行程序的排他性特點(diǎn)，程序運(yùn)行到任何一個(gè)時(shí)刻，只需一個(gè)顯示表副本。為了提高訪(fǎng)問(wèn)速度，可以用一組寄存器來(lái)作為顯示表的存儲(chǔ)空間，寄存器的個(gè)數(shù)(即顯示表的容量)就是程序設(shè)計(jì)語(yǔ)言允許過(guò)程嵌套的層次數(shù)。原理上，程序嵌套的深度是不應(yīng)受到限制的，而寄存器資源是十分寶貴的，因此，也可以設(shè)立一塊靜態(tài)存儲(chǔ)區(qū)作為顯示表，在棧分配中，它可以被放在棧底。顯示表的另外一種存儲(chǔ)分配是，給顯示表多個(gè)副本。棧頂每生成一個(gè)新的活動(dòng)記錄時(shí)，從舊棧頂?shù)幕顒?dòng)記錄中復(fù)制兩個(gè)活動(dòng)的公共外層的顯示表部分，而把當(dāng)前活動(dòng)記錄的訪(fǎng)問(wèn)鏈地址作為顯示表中的最新元素?！纠?.7】

將圖5.10中訪(fǎng)問(wèn)鏈改為顯示表方案，則顯示表建立的過(guò)程如圖5.11(a)~(f)所示。讀者可以根據(jù)上述方法，在活動(dòng)返回的序列中將顯示表和控制棧的內(nèi)容從圖5.11(f)恢復(fù)到圖5.11(a)。圖5.11顯示表的維護(hù)5.3.4參數(shù)傳遞的實(shí)現(xiàn)根據(jù)上一章的分析，我們知道參數(shù)傳遞的主要區(qū)別在于傳遞的是左值還是右值，而且無(wú)論是哪種情況，均可按下述原則處理：

(1)過(guò)程定義時(shí)形參被當(dāng)作局部名看待，即在活動(dòng)記錄中為參數(shù)分配存儲(chǔ)單元；

(2)將調(diào)用時(shí)實(shí)參的左值或者右值放入形參單元；

(3)根據(jù)傳遞的是左值還是右值確定過(guò)程中對(duì)形參單元的數(shù)據(jù)是間接訪(fǎng)問(wèn)還是直接訪(fǎng)問(wèn)。

此處我們僅考慮最簡(jiǎn)單的情況，即參數(shù)是簡(jiǎn)單變量，且傳遞的是右值(值調(diào)用)。對(duì)于4.9節(jié)中的過(guò)程調(diào)用callsum(X+Y，Z)，當(dāng)時(shí)生成了如下的中間代碼：

(k–3)paramT(k–2)paramZ(k–1)call2,sum

設(shè)sum的聲明為：procsum(a,b:int)，則可具體處理如下。1．設(shè)計(jì)含有參數(shù)存儲(chǔ)單元的活動(dòng)記錄設(shè)計(jì)一個(gè)簡(jiǎn)化的活動(dòng)記錄，如圖5.12(a)所示，其中訪(fǎng)問(wèn)鏈和控制鏈存放在連續(xù)的兩個(gè)單元中，sp指向訪(fǎng)問(wèn)鏈的存儲(chǔ)單元。當(dāng)所處理的語(yǔ)言不需要訪(fǎng)問(wèn)鏈時(shí)，sp直接指向控制鏈。如果有n個(gè)參數(shù)，則相對(duì)sp尋址的前n+1個(gè)單元分配給參數(shù)，從第n+2個(gè)單元開(kāi)始分配給過(guò)程中聲明的變量，最后是代碼生成時(shí)引進(jìn)的臨時(shí)變量。對(duì)于一段完整的過(guò)程來(lái)講，所有這些內(nèi)容在編譯時(shí)均是可以確定的，因此，過(guò)程活動(dòng)記錄的長(zhǎng)度L是可確定的。這實(shí)際上給棧