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

1、武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓第第10章章 目標(biāo)程序目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織運(yùn)行時(shí)的存儲(chǔ)組織 10.1 數(shù)據(jù)空間的三種不同使用方法和管理方法數(shù)據(jù)空間的三種不同使用方法和管理方法10.2 棧式存儲(chǔ)分配的實(shí)現(xiàn)棧式存儲(chǔ)分配的實(shí)現(xiàn)10.3 參數(shù)傳遞參數(shù)傳遞10.4 過程調(diào)用、過程進(jìn)入和過程返回過程調(diào)用、過程進(jìn)入和過程返回武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 從邏輯上看，在代碼生成前，編譯程序必須進(jìn)行從邏輯上看，在代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的配置和數(shù)據(jù)空間的分配。目標(biāo)程序運(yùn)行環(huán)境的配置和數(shù)據(jù)空間的分配。 數(shù)據(jù)空間應(yīng)包括：數(shù)據(jù)空間應(yīng)包括：u用

2、戶定義的各種類型的數(shù)據(jù)對象（變量和常數(shù)）所用戶定義的各種類型的數(shù)據(jù)對象（變量和常數(shù)）所需的存儲(chǔ)空間；需的存儲(chǔ)空間；u作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元；作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元；u調(diào)用過程時(shí)所需的連接單元；調(diào)用過程時(shí)所需的連接單元；u組織輸入組織輸入/輸出所需的緩沖區(qū)。輸出所需的緩沖區(qū)。 目標(biāo)代碼所占用空間的大小在編譯時(shí)能確定。有目標(biāo)代碼所占用空間的大小在編譯時(shí)能確定。有些數(shù)據(jù)對象所占用的空間也能在編譯時(shí)確定，其地址些數(shù)據(jù)對象所占用的空間也能在編譯時(shí)確定，其地址可以編譯進(jìn)目標(biāo)代碼中。而有些數(shù)據(jù)對象具有可變體可以編譯進(jìn)目標(biāo)代碼中。而有些數(shù)據(jù)對象具有可變體積和待分配性質(zhì)，無法

3、在編譯時(shí)確定存儲(chǔ)空間的位置。積和待分配性質(zhì)，無法在編譯時(shí)確定存儲(chǔ)空間的位置。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 因此運(yùn)行時(shí)的存儲(chǔ)區(qū)常常劃分成：目標(biāo)區(qū)、靜因此運(yùn)行時(shí)的存儲(chǔ)區(qū)常常劃分成：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如圖態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如圖10.1 。目標(biāo)代碼區(qū)目標(biāo)代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)靜態(tài)數(shù)據(jù)區(qū)棧棧Stack堆堆heap圖圖10.1 目標(biāo)程序運(yùn)行時(shí)存儲(chǔ)區(qū)的典型劃分目標(biāo)程序運(yùn)行時(shí)存儲(chǔ)區(qū)的典型劃分武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓所謂數(shù)據(jù)空間的分配，本質(zhì)上看，是將程序中的每個(gè)名所謂數(shù)據(jù)空間的分配，本質(zhì)上看，是將程序中的每個(gè)名字與一個(gè)存儲(chǔ)位置關(guān)聯(lián)起來，該

4、存儲(chǔ)位置用以容納名字的值。字與一個(gè)存儲(chǔ)位置關(guān)聯(lián)起來，該存儲(chǔ)位置用以容納名字的值。編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是程序語言設(shè)計(jì)時(shí)對程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的程序語言設(shè)計(jì)時(shí)對程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定。規(guī)定。在程序設(shè)計(jì)語言語義學(xué)中，使用術(shù)語在程序設(shè)計(jì)語言語義學(xué)中，使用術(shù)語environment表示將表示將一個(gè)名字映射到一個(gè)存儲(chǔ)位置的函數(shù)，術(shù)語一個(gè)名字映射到一個(gè)存儲(chǔ)位置的函數(shù)，術(shù)語state表示存儲(chǔ)位表示存儲(chǔ)位置到值的映射，如圖置到值的映射，如圖10.2所示。所示。圖圖10.2 名字到存儲(chǔ)位置、到值的映射名字到存

5、儲(chǔ)位置、到值的映射 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓l 編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基編譯程序分配目標(biāo)程序運(yùn)行時(shí)的數(shù)據(jù)空間的基本依據(jù)是程序語言設(shè)計(jì)時(shí)對程序運(yùn)行中存儲(chǔ)空本依據(jù)是程序語言設(shè)計(jì)時(shí)對程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定。間的使用和管理辦法的規(guī)定。l 決定存儲(chǔ)管理復(fù)雜程度的因素決定存儲(chǔ)管理復(fù)雜程度的因素-源語言本身，源語言本身，比如源語言允許的數(shù)據(jù)類型有多少？語言中允比如源語言允許的數(shù)據(jù)類型有多少？語言中允許的數(shù)據(jù)項(xiàng)是靜態(tài)確定還是動(dòng)態(tài)確定？程序結(jié)許的數(shù)據(jù)項(xiàng)是靜態(tài)確定還是動(dòng)態(tài)確定？程序結(jié)構(gòu)有什么特點(diǎn)，是段結(jié)構(gòu)還是分程序結(jié)構(gòu)？過構(gòu)有什么特點(diǎn)，是段結(jié)構(gòu)還是

6、分程序結(jié)構(gòu)？過程定義是否允許嵌套？等等。程定義是否允許嵌套？等等。l 源語言的結(jié)構(gòu)特點(diǎn)、源語言的數(shù)據(jù)類型、源語源語言的結(jié)構(gòu)特點(diǎn)、源語言的數(shù)據(jù)類型、源語言中決定名字作用域的規(guī)則等因素影響存儲(chǔ)空言中決定名字作用域的規(guī)則等因素影響存儲(chǔ)空間的管理和組織的復(fù)雜程度，決定數(shù)據(jù)空間分間的管理和組織的復(fù)雜程度，決定數(shù)據(jù)空間分配的基本策略。配的基本策略。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.1 數(shù)據(jù)空間的三種不同使用方法和管理方法數(shù)據(jù)空間的三種不同使用方法和管理方法數(shù)據(jù)空間的使用和管理方法數(shù)據(jù)空間的使用和管理方法: 簡單的棧式分配方案簡單的棧式分配方案 嵌套過程的棧式分配方案嵌套過程的

7、棧式分配方案 分程序結(jié)構(gòu)的存儲(chǔ)分配方案分程序結(jié)構(gòu)的存儲(chǔ)分配方案靜態(tài)存儲(chǔ)分配、靜態(tài)存儲(chǔ)分配、動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配棧式棧式堆式堆式武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.1.1 靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配如果在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的如果在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部的數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序全部的數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對象的存運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對象的存儲(chǔ)位置，稱這種分配策略為靜態(tài)存儲(chǔ)分配。儲(chǔ)位置，稱這種分配策略為靜態(tài)存儲(chǔ)分配。如如C中的靜態(tài)變量，外部變量等。中的靜態(tài)變量，外部變量等

8、。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.1.2 動(dòng)態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、允許如果一個(gè)程序設(shè)計(jì)語言允許遞歸過程、允許動(dòng)態(tài)的申請建立和撤消存儲(chǔ)空間、可變數(shù)組或允動(dòng)態(tài)的申請建立和撤消存儲(chǔ)空間、可變數(shù)組或允許用戶自由申請和釋放空間，那么，就需要采用許用戶自由申請和釋放空間，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。動(dòng)態(tài)存儲(chǔ)管理技術(shù)。因?yàn)閷τ谶@種程序在編譯時(shí)無法知道它在運(yùn)因?yàn)閷τ谶@種程序在編譯時(shí)無法知道它在運(yùn)行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù)據(jù)空間行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù)據(jù)空間的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。

9、若一個(gè)數(shù)組所需的存儲(chǔ)空間的大小在編譯時(shí)若一個(gè)數(shù)組所需的存儲(chǔ)空間的大小在編譯時(shí)就已知道，則稱它為確定（靜態(tài)）數(shù)組，否則稱就已知道，則稱它為確定（靜態(tài)）數(shù)組，否則稱為可變（動(dòng)態(tài)）數(shù)組。為可變（動(dòng)態(tài)）數(shù)組。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.1.2.1 棧式動(dòng)態(tài)存儲(chǔ)分配棧式動(dòng)態(tài)存儲(chǔ)分配分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧。棧。在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個(gè)在具有遞歸結(jié)構(gòu)的語言程序中，每當(dāng)調(diào)用一個(gè)過程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過過程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程工作結(jié)束時(shí)就釋放這部分空間。程工作結(jié)

10、束時(shí)就釋放這部分空間。過程所需的數(shù)據(jù)空間包括兩部分：過程所需的數(shù)據(jù)空間包括兩部分： 生存期在本過程這次活動(dòng)中的數(shù)據(jù)對象；生存期在本過程這次活動(dòng)中的數(shù)據(jù)對象； 用以管理過程活動(dòng)的記錄信息用以管理過程活動(dòng)的記錄信息 。棧式動(dòng)態(tài)存儲(chǔ)分配策略適用于棧式動(dòng)態(tài)存儲(chǔ)分配策略適用于PASCAL，C，ALGOL之類具有遞歸結(jié)構(gòu)的語言的實(shí)現(xiàn)。之類具有遞歸結(jié)構(gòu)的語言的實(shí)現(xiàn)。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.1.2.2 堆式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序語言提供用戶自由地申請數(shù)據(jù)空如果一個(gè)程序語言提供用戶自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間的機(jī)制，或者不僅有過程而且有間和退還數(shù)據(jù)空

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

12、方法必須考慮的幾個(gè)問題。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓堆式的動(dòng)態(tài)存儲(chǔ)分配策略堆式的動(dòng)態(tài)存儲(chǔ)分配策略:當(dāng)運(yùn)行程序要求一塊體積為當(dāng)運(yùn)行程序要求一塊體積為N的空同時(shí)，我們應(yīng)該分配的空同時(shí)，我們應(yīng)該分配哪一塊給它呢？哪一塊給它呢？理論上說，應(yīng)從比理論上說，應(yīng)從比N稍大一點(diǎn)的一個(gè)空閑塊中取出稍大一點(diǎn)的一個(gè)空閑塊中取出N個(gè)個(gè)單元，以便使大的空閑塊派更大的用場。但這種做法較麻煩。單元，以便使大的空閑塊派更大的用場。但這種做法較麻煩。因此，常常仍采用因此，常常仍采用“先碰上哪塊比先碰上哪塊比N大就從其中分出大就從其中分出N個(gè)單元個(gè)單元”的原則。但不論采用什么原則，整個(gè)大存區(qū)在一定的

13、原則。但不論采用什么原則，整個(gè)大存區(qū)在一定時(shí)間之后必然會(huì)變成零碎不堪。時(shí)間之后必然會(huì)變成零碎不堪?？傆幸粋€(gè)時(shí)候會(huì)出現(xiàn)異樣的情形：運(yùn)行程序要求一塊體總有一個(gè)時(shí)候會(huì)出現(xiàn)異樣的情形：運(yùn)行程序要求一塊體積為積為N的空間，但發(fā)現(xiàn)沒有比的空間，但發(fā)現(xiàn)沒有比N大的空閑塊了，然而所有空閑大的空閑塊了，然而所有空閑塊的總和卻要比塊的總和卻要比N大得多！出現(xiàn)這種情形時(shí)怎么辦呢？這是大得多！出現(xiàn)這種情形時(shí)怎么辦呢？這是一個(gè)比前面的問題難得多的問題。一個(gè)比前面的問題難得多的問題。解決辦法似乎很簡單，這就是，把所有空閑塊連接在一解決辦法似乎很簡單，這就是，把所有空閑塊連接在一起，形成一片可分配的連續(xù)空間。起，形成一片可

14、分配的連續(xù)空間。這里主要問題是，我們必須調(diào)整運(yùn)行程序?qū)Ω髡加脡K的這里主要問題是，我們必須調(diào)整運(yùn)行程序?qū)Ω髡加脡K的全部引用點(diǎn)。全部引用點(diǎn)。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓堆式的動(dòng)態(tài)存儲(chǔ)分配策略堆式的動(dòng)態(tài)存儲(chǔ)分配策略:另外，如果運(yùn)行程序要求一塊體積為另外，如果運(yùn)行程序要求一塊體積為N的空間，但的空間，但所有空閑塊的總和也不夠所有空閑塊的總和也不夠N，那又應(yīng)怎么辦呢？，那又應(yīng)怎么辦呢？有的管理系統(tǒng)采用一種叫做廢品回收的辦法來對付有的管理系統(tǒng)采用一種叫做廢品回收的辦法來對付這種局面。即尋找那些運(yùn)行程序業(yè)己無用但尚未釋放的這種局面。即尋找那些運(yùn)行程序業(yè)己無用但尚未釋放的占用塊，

15、或者那些程序目前很少使用的占用塊，把這些占用塊，或者那些程序目前很少使用的占用塊，把這些占用塊收回來，重新分配。占用塊收回來，重新分配。但是，我們?nèi)绾沃滥男K運(yùn)行時(shí)在使用或者目前但是，我們?nèi)绾沃滥男K運(yùn)行時(shí)在使用或者目前很少使用呢？即便知道了，一經(jīng)收回后運(yùn)行程序在某個(gè)很少使用呢？即便知道了，一經(jīng)收回后運(yùn)行程序在某個(gè)時(shí)候又要用它時(shí)又應(yīng)該怎么辦呢？時(shí)候又要用它時(shí)又應(yīng)該怎么辦呢？要使用廢品回收技術(shù)，除了在語言上要有明確的具要使用廢品回收技術(shù)，除了在語言上要有明確的具體限制外，還需要有特別的硬件措施，否則回收幾乎不體限制外，還需要有特別的硬件措施，否則回收幾乎不能實(shí)現(xiàn)。能實(shí)現(xiàn)。武漢理工大學(xué)計(jì)算機(jī)科

16、學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓堆式動(dòng)態(tài)儲(chǔ)分配的實(shí)現(xiàn)通常有如下兩種途徑：堆式動(dòng)態(tài)儲(chǔ)分配的實(shí)現(xiàn)通常有如下兩種途徑：1）定長塊管理）定長塊管理 堆式動(dòng)態(tài)儲(chǔ)分配最簡單的實(shí)現(xiàn)是按定長塊進(jìn)行。堆式動(dòng)態(tài)儲(chǔ)分配最簡單的實(shí)現(xiàn)是按定長塊進(jìn)行。初始化時(shí)，將堆存儲(chǔ)空間分成長度相等的若干塊，初始化時(shí)，將堆存儲(chǔ)空間分成長度相等的若干塊，每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈成一個(gè)鏈表，用指針成一個(gè)鏈表，用指針available指向鏈表中的第一塊。指向鏈表中的第一塊。 分配時(shí)每次都分配指針分配時(shí)每次都分配指針available所指的塊，然所指的塊，然后后availab

17、le指向相鄰的下一塊。歸還時(shí)，把所歸還指向相鄰的下一塊。歸還時(shí)，把所歸還的塊插入鏈表?？紤]插入方便，可以把所歸還的塊的塊插入鏈表。考慮插入方便，可以把所歸還的塊插在插在available所指的塊之前，然后所指的塊之前，然后available指向新指向新歸還的塊。歸還的塊。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓占用占用占用占用占用占用空閑空閑空閑空閑空閑空閑available(a)占用占用占用占用空閑空閑空閑空閑空閑空閑(b)空閑空閑available圖圖10.3 定長塊管理定長塊管理武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓2）變長塊管理）變長塊管理 除了按定長

18、塊進(jìn)行分配之外，還可以根據(jù)需要除了按定長塊進(jìn)行分配之外，還可以根據(jù)需要分配長度不同的存儲(chǔ)塊，可以隨要求而變。按這種分配長度不同的存儲(chǔ)塊，可以隨要求而變。按這種方法，初始化時(shí)存儲(chǔ)空間是一個(gè)整塊。按照用戶的方法，初始化時(shí)存儲(chǔ)空間是一個(gè)整塊。按照用戶的需要，分配時(shí)先是從一個(gè)整塊里分割出滿足需要的需要，分配時(shí)先是從一個(gè)整塊里分割出滿足需要的一小塊，以后，歸還時(shí)，如果新歸還的塊能和現(xiàn)有一小塊，以后，歸還時(shí)，如果新歸還的塊能和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。再進(jìn)行閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。再進(jìn)行分

19、配時(shí)，從空閑塊鏈表中找出滿足需要的一塊，或分配時(shí)，從空閑塊鏈表中找出滿足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出者整塊分配出去，或者從該塊上分割一小塊分配出去。若空閑塊表中有若干個(gè)滿足需要的空閑塊時(shí)，去。若空閑塊表中有若干個(gè)滿足需要的空閑塊時(shí)，該分配哪一塊呢該分配哪一塊呢 ?通常有三種不同的分配策略：通常有三種不同的分配策略： 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓變長塊管理通常有三種不同的分配策略：變長塊管理通常有三種不同的分配策略： 首次滿足法（時(shí)間優(yōu)先）首次滿足法（時(shí)間優(yōu)先）; ;最優(yōu)滿足法（空間優(yōu)先）最優(yōu)滿足法（空間優(yōu)先）; ;最差滿足法（時(shí)間優(yōu)先）

20、。最差滿足法（時(shí)間優(yōu)先）。上述三種分配策略各有所長。上述三種分配策略各有所長。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.2 棧式存儲(chǔ)分配的實(shí)現(xiàn)棧式存儲(chǔ)分配的實(shí)現(xiàn) 前面提到，使用棧式存儲(chǔ)分配策略意味著，運(yùn)前面提到，使用棧式存儲(chǔ)分配策略意味著，運(yùn)行時(shí)每當(dāng)進(jìn)入一個(gè)過程，就在棧頂為該過程的臨時(shí)行時(shí)每當(dāng)進(jìn)入一個(gè)過程，就在棧頂為該過程的臨時(shí)工作單元，局部變量，機(jī)器狀態(tài)及返回地址等信息工作單元，局部變量，機(jī)器狀態(tài)及返回地址等信息分配所需的數(shù)據(jù)空間，當(dāng)一個(gè)過程工作完畢返回時(shí)，分配所需的數(shù)據(jù)空間，當(dāng)一個(gè)過程工作完畢返回時(shí)，它在棧頂?shù)臄?shù)據(jù)空間也即釋放。它在棧頂?shù)臄?shù)據(jù)空間也即釋放。 為討論方便

21、，首先引入為討論方便，首先引入一個(gè)術(shù)語一個(gè)術(shù)語-過程的活動(dòng)記錄過程的活動(dòng)記錄AR(Activation Record)。過。過程的活動(dòng)記錄是一段連續(xù)的程的活動(dòng)記錄是一段連續(xù)的存儲(chǔ)區(qū)，用以存放過程的一存儲(chǔ)區(qū)，用以存放過程的一次執(zhí)行所需要的動(dòng)態(tài)信息，次執(zhí)行所需要的動(dòng)態(tài)信息，這些信息可以如圖這些信息可以如圖10.6所示。所示。 圖圖 10.6 過程的活動(dòng)記錄過程的活動(dòng)記錄返回地址返回地址實(shí)參實(shí)參控制鏈控制鏈存取鏈存取鏈機(jī)器狀態(tài)信息機(jī)器狀態(tài)信息局部變量局部變量臨時(shí)工作單元臨時(shí)工作單元武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 臨時(shí)工作單元臨時(shí)工作單元：比如計(jì)算表達(dá)式過程中：比如計(jì)算表達(dá)式

22、過程中需存放中間結(jié)果用的臨時(shí)值單元。需存放中間結(jié)果用的臨時(shí)值單元。 局部變量局部變量：一個(gè)過程的局部變量。：一個(gè)過程的局部變量。 機(jī)器狀態(tài)信息：機(jī)器狀態(tài)信息：保存該過程執(zhí)行前關(guān)于保存該過程執(zhí)行前關(guān)于機(jī)器狀態(tài)的信息，諸如程序計(jì)數(shù)器、寄機(jī)器狀態(tài)的信息，諸如程序計(jì)數(shù)器、寄存器的值，這些值都需要在控制從該過存器的值，這些值都需要在控制從該過程返回時(shí)給予恢復(fù)。程返回時(shí)給予恢復(fù)。 存取鏈存取鏈：用以存取非局部變量，這些變：用以存取非局部變量，這些變量存放于其它過程的活動(dòng)記錄中。并不量存放于其它過程的活動(dòng)記錄中。并不是所有語言需要該信息。是所有語言需要該信息。 控制鏈控制鏈：指向調(diào)用該過程的那個(gè)過程的：指向

23、調(diào)用該過程的那個(gè)過程的活動(dòng)記錄，這也不是所有語言都需要的?；顒?dòng)記錄，這也不是所有語言都需要的。 實(shí)參實(shí)參：也稱形式單元，由調(diào)用過程向該：也稱形式單元，由調(diào)用過程向該被調(diào)過程提供實(shí)參的值（或地址）。當(dāng)被調(diào)過程提供實(shí)參的值（或地址）。當(dāng)然在實(shí)際編譯程序中，也常常使用機(jī)器然在實(shí)際編譯程序中，也常常使用機(jī)器寄存器傳遞實(shí)參。寄存器傳遞實(shí)參。 返回地址返回地址：保存該被調(diào)過程返回后的地：保存該被調(diào)過程返回后的地址。址。 圖圖 10.6 過程的活動(dòng)記錄過程的活動(dòng)記錄返回地址返回地址實(shí)參實(shí)參控制鏈控制鏈存取鏈存取鏈機(jī)器狀態(tài)信息機(jī)器狀態(tài)信息局部變量局部變量臨時(shí)工作單元臨時(shí)工作單元靜態(tài)鏈，指向靜態(tài)直接外層最新活動(dòng)

24、靜態(tài)鏈，指向靜態(tài)直接外層最新活動(dòng)記錄的起始地址，記錄的起始地址，即指向即指向定義定義本過程本過程的的直接外層過程直接外層過程 （或主程序）運(yùn)行時(shí)（或主程序）運(yùn)行時(shí)最新最新活動(dòng)記錄的基地址活動(dòng)記錄的基地址。動(dòng)態(tài)鏈動(dòng)態(tài)鏈，指向，指向調(diào)用調(diào)用該過程前正該過程前正在運(yùn)行過程的數(shù)據(jù)段基地址。在運(yùn)行過程的數(shù)據(jù)段基地址。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.2.1 簡單的棧式分配的實(shí)現(xiàn)簡單的棧式分配的實(shí)現(xiàn) 程序結(jié)構(gòu)特點(diǎn)程序結(jié)構(gòu)特點(diǎn):過程定義不嵌套，過程可遞歸過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組；例：調(diào)用，含可變數(shù)組；例： main 全局變量的說明全局變量的說明proc Rend

25、 R;proc Q end Q;主程序執(zhí)行語句主程序執(zhí)行語句 end main武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓TOP 臨時(shí)工作單元臨時(shí)工作單元局部簡單變量局部簡單變量局部數(shù)組的內(nèi)情向量局部數(shù)組的內(nèi)情向量 保存運(yùn)保存運(yùn)行過程前的狀態(tài)行過程前的狀態(tài)（返回地址，寄存器值（返回地址，寄存器值）實(shí)參實(shí)參（形式單元）和參數(shù)個(gè)數(shù)（形式單元）和參數(shù)個(gè)數(shù) SP 存取鏈（存取鏈（靜態(tài)鏈靜態(tài)鏈）控制鏈控制鏈（動(dòng)態(tài)鏈，動(dòng)態(tài)鏈，老老SP）圖圖10.3 過程的活動(dòng)記錄過程的活動(dòng)記錄指向調(diào)用該過程的那個(gè)過程指向調(diào)用該過程的那個(gè)過程的最新活動(dòng)記錄的起始地址的最新活動(dòng)記錄的起始地址用以存取非局部變量，用

26、以存取非局部變量，這些變量存放于其他過這些變量存放于其他過程的活動(dòng)記錄中。程的活動(dòng)記錄中。Main Q R TOP R的活動(dòng)記錄的活動(dòng)記錄 SP 主程序全局主程序全局?jǐn)?shù)據(jù)區(qū)數(shù)據(jù)區(qū)Q的活動(dòng)記錄的活動(dòng)記錄MainQQQ的活動(dòng)記錄的活動(dòng)記錄主程序全局主程序全局?jǐn)?shù)據(jù)區(qū)數(shù)據(jù)區(qū)Q的活動(dòng)記錄的活動(dòng)記錄圖圖10.4 棧式存儲(chǔ)分配棧式存儲(chǔ)分配靜態(tài)鏈，指向靜態(tài)直接外層最新活靜態(tài)鏈，指向靜態(tài)直接外層最新活動(dòng)記錄的起始地址，動(dòng)記錄的起始地址，即指向即指向定義定義本本過程的過程的直接外層過程直接外層過程 （或主程序）（或主程序）運(yùn)行時(shí)運(yùn)行時(shí)最新最新活動(dòng)記錄的基地址活動(dòng)記錄的基地址。動(dòng)態(tài)鏈動(dòng)態(tài)鏈，指向，指向調(diào)用調(diào)用該過程

27、前正該過程前正在運(yùn)行過程的數(shù)據(jù)段基地址。在運(yùn)行過程的數(shù)據(jù)段基地址。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓TOPR R的數(shù)組區(qū)的數(shù)組區(qū) SPR R的活動(dòng)記錄的活動(dòng)記錄Q Q的活動(dòng)記錄的活動(dòng)記錄主程序全局主程序全局?jǐn)?shù)據(jù)區(qū)數(shù)據(jù)區(qū)圖圖10.6 10.6 分配了數(shù)組區(qū)之后的運(yùn)行棧分配了數(shù)組區(qū)之后的運(yùn)行棧TOP 臨時(shí)工作單元臨時(shí)工作單元局部簡單變量局部簡單變量局部數(shù)組的內(nèi)情向量局部數(shù)組的內(nèi)情向量 返回地址返回地址實(shí)參實(shí)參（形式單元）（形式單元） SP 參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù)控制鏈控制鏈（老（老SP）圖圖10.5 10.5 無嵌套定義無嵌套定義的過程活動(dòng)記錄內(nèi)容的過程活動(dòng)記錄內(nèi)容武漢理工大學(xué)計(jì)算

28、機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 10.2.2 嵌套過程語言的棧式實(shí)現(xiàn)嵌套過程語言的棧式實(shí)現(xiàn)主要特點(diǎn)：主要特點(diǎn)： （語言）一個(gè)過程可以引用包圍它的任一外層（語言）一個(gè)過程可以引用包圍它的任一外層過程所定義的標(biāo)識符（如變量，數(shù)組或過程過程所定義的標(biāo)識符（如變量，數(shù)組或過程等）。等）。 （實(shí)現(xiàn)）一個(gè)過程可以引用它的任一外層過程（實(shí)現(xiàn)）一個(gè)過程可以引用它的任一外層過程的最新活動(dòng)記錄中的某些數(shù)據(jù)。的最新活動(dòng)記錄中的某些數(shù)據(jù)。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓(1) program (1) program sortsort(input, output); /sort(inp

29、ut, output); /sort的過程頭的過程頭(2)(2)var a: array 0.10 of integer;var a: array 0.10 of integer;(3)(3)x: integer;x: integer;(4)(4)procedure procedure readarrayreadarray; /sort; /sort內(nèi)嵌套定義的內(nèi)嵌套定義的readarrayreadarray的過程頭的過程頭(5)(5)var i: integer;var i: integer;(6)(6)beginaendreadarray; /readarraybeginaendreada

30、rray; /readarray的過程體的過程體(7)(7)procedure procedure exchangeexchange(i,j: integer);(i,j: integer);/sort/sort內(nèi)嵌套定義的內(nèi)嵌套定義的exchangeexchange的過程頭的過程頭(8)(8)beginbegin(9) (9) x=ai; ai=aj; aj=x; /exchangex=ai; ai=aj; aj=x; /exchange的過程體的過程體(10)(10) endexchange;endexchange;(11)(11) procedure procedure quicksor

31、tquicksort(m,n: integer);(m,n: integer);/sort/sort內(nèi)嵌套定義的內(nèi)嵌套定義的quicksortquicksort的過程頭的過程頭(12) (12) var k,v: integer; var k,v: integer; (13)(13) function function partitionpartition(y,z:integer):integer;(y,z:integer):integer;/quicksort/quicksort內(nèi)嵌套定義的內(nèi)嵌套定義的partitionpartition的函數(shù)頭的函數(shù)頭(14)(14)var i.j:int

32、eger;var i.j:integer;(15)(15)begin a /partitionbegin a /partition的函數(shù)體的函數(shù)體(16)(16) vv(17) (17) exchangeexchange(i,j);(i,j);(18) (18) endpartition;endpartition;(19) (19) beginendquicksort; /quicksortbeginendquicksort; /quicksort的過程體的過程體(20) beginendsort. /sort(20) beginendsort. /sort的例程體的例程體 圖圖10.11 具

33、有嵌套過程的具有嵌套過程的PASCAL程序程序武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓圖圖10.11的的PASCAL程序中過程定義的嵌套情況如下：程序中過程定義的嵌套情況如下：sortreadarrayexchangequicksortpartition 局部變量局部變量a,x局部變量局部變量k,v過程過程quicksort的活動(dòng)記的活動(dòng)記錄錄過程過程sort的活動(dòng)記錄的活動(dòng)記錄圖圖10.12 存儲(chǔ)棧布存儲(chǔ)棧布局局記錄下列信息：記錄下列信息： 可以引用過程可以引用過程 sort的局部變量的局部變量武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 關(guān)鍵技術(shù)：解決對非局部量

34、的引用（存?。ｊP(guān)鍵技術(shù)：解決對非局部量的引用（存?。ＴO(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)記錄設(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)記錄AR的的位置。位置。跟蹤辦法：跟蹤辦法： 1. 用靜態(tài)鏈（如用靜態(tài)鏈（如PL/0的的SL）。）。 2. 用用DISPLAY表。表。跟蹤的辦法很多，我們介紹兩種，一種是在過跟蹤的辦法很多，我們介紹兩種，一種是在過程活動(dòng)記錄中增設(shè)存取鏈，指向包含該過程的直接程活動(dòng)記錄中增設(shè)存取鏈，指向包含該過程的直接外層過程的最新活動(dòng)記錄的起始位置。過程活動(dòng)記外層過程的最新活動(dòng)記錄的起始位置。過程活動(dòng)記錄的內(nèi)容如圖錄的內(nèi)容如圖10.13（a）所示。圖）所示。圖10.12所提到的情所提到的情況

35、可用圖況可用圖10.13（b）說明。）說明。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓圖圖 10.13 嵌套定義過程的活動(dòng)記錄和存儲(chǔ)棧嵌套定義過程的活動(dòng)記錄和存儲(chǔ)棧(a)局部變量局部變量存取鏈存取鏈控制鏈控制鏈TOPSP存取鏈存取鏈控制鏈控制鏈(老老SP)TOPSP(b)quicksort的的ARsort的的AR武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓再回到圖再回到圖10.11的例子。如果該程序的某次執(zhí)行順的例子。如果該程序的某次執(zhí)行順序?yàn)椋盒驗(yàn)椋簊ortquicksortquicksortpartitionexchange即主程序即主程序(最外層過程最外層過程

36、)sort開始執(zhí)行開始執(zhí)行,繼而進(jìn)入過繼而進(jìn)入過程程quicksort，而又一次進(jìn)入過程，而又一次進(jìn)入過程quicksort，接著進(jìn)入，接著進(jìn)入過程過程partition，進(jìn)入過程，進(jìn)入過程exchange。圖圖10.15給出了進(jìn)入過程給出了進(jìn)入過程exchange之后運(yùn)行棧的示之后運(yùn)行棧的示意，我們僅把存取鏈和控制鏈的值標(biāo)明。意，我們僅把存取鏈和控制鏈的值標(biāo)明。 可以看出，過程可以看出，過程exchange由過程（函數(shù)）由過程（函數(shù)）partition調(diào)用，但調(diào)用，但exchange的直接外層過程是的直接外層過程是sort，所以過程所以過程exchange的活動(dòng)記錄的存取鏈指向的活動(dòng)記錄的存

37、取鏈指向sort的活的活動(dòng)記錄的始址。動(dòng)記錄的始址。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓圖圖10.15 運(yùn)行棧運(yùn)行棧靜態(tài)鏈，指向靜態(tài)直接外層最新靜態(tài)鏈，指向靜態(tài)直接外層最新活動(dòng)記錄的起始地址，活動(dòng)記錄的起始地址，動(dòng)態(tài)鏈動(dòng)態(tài)鏈，指向，指向調(diào)用調(diào)用該過程前正該過程前正在運(yùn)行過程的數(shù)據(jù)段基地址。在運(yùn)行過程的數(shù)據(jù)段基地址。exchange的活動(dòng)記錄的活動(dòng)記錄partition的活動(dòng)記錄的活動(dòng)記錄quicksort的活動(dòng)記錄的活動(dòng)記錄quicksort的活動(dòng)記錄的活動(dòng)記錄sort的活動(dòng)記錄的活動(dòng)記錄武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 解決對非局部量的引用（存取

38、）的有效辦解決對非局部量的引用（存?。┑挠行мk法是用法是用Display表。表。Display表表-嵌套層次顯示表嵌套層次顯示表，即每進(jìn)入一個(gè)過，即每進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄的同時(shí)建立一張程后，在建立它的活動(dòng)記錄的同時(shí)建立一張Display表。表。當(dāng)前激活過程的層次為當(dāng)前激活過程的層次為K，它的，它的Display表含有表含有K+1個(gè)單元，依次存放著現(xiàn)行層，直接外層個(gè)單元，依次存放著現(xiàn)行層，直接外層直至直至最外層的每一過程的最新活動(dòng)記錄的基地址。最外層的每一過程的最新活動(dòng)記錄的基地址。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓例：例：program main(i,0);

39、程序結(jié)構(gòu)圖程序結(jié)構(gòu)圖proc R(c,d);Rend /*R*/proc P (a); 主主 proc Q (b);P Q call R R(x,y);end /*Q*/ call QQ(z); call Pend /*P*/call RP（W）；）；R（U，V）；）；end /*main*/武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R主程序的主程序的活動(dòng)記錄活動(dòng)記錄 d0spdisplaytop（1）d1d0 P 的的活動(dòng)記錄活動(dòng)記錄主程序的主程序的活動(dòng)記錄活動(dòng)記錄 displaysptop（2）武

40、漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓用用Display表的方案表的方案 主程序主程序-P-Q-Rd2d1d0Q 的的活動(dòng)記錄活動(dòng)記錄 P 的的活動(dòng)記錄活動(dòng)記錄主程序的主程序的活動(dòng)記錄活動(dòng)記錄 displaysptop（3）R 的的活動(dòng)記錄活動(dòng)記錄 Q 的的活動(dòng)記錄活動(dòng)記錄 P 的的活動(dòng)記錄活動(dòng)記錄主程序的主程序的活動(dòng)記錄活動(dòng)記錄 d1d0 displaytopsp（4）武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓DISPLAY表的維護(hù)和建立表的維護(hù)和建立 DISPLAY表表d 運(yùn)行棧運(yùn)行棧 0 主程活動(dòng)記錄地址主程活動(dòng)記錄地址 1 R活動(dòng)記錄地址活動(dòng)記錄地址 .

41、武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 當(dāng)過程的層次為當(dāng)過程的層次為n，它的它的 display為為n+1個(gè)個(gè)值。值。 一個(gè)過程被調(diào)用時(shí)，一個(gè)過程被調(diào)用時(shí)，從調(diào)用過程的從調(diào)用過程的DISPLAY表中自下向表中自下向上抄錄上抄錄n個(gè)個(gè)SP值，再加值，再加上本層的上本層的SP值。值。全局全局DISPLAY地址地址 0 老老 SP 1 返回地址返回地址 2 全局全局 DISPLAY地址地址 3 參數(shù)個(gè)數(shù)參數(shù)個(gè)數(shù) 4形式單元形式單元 . . . d DISPLAY . . . 簡單變量簡單變量 數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量 臨時(shí)變量臨時(shí)變量 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)

42、科學(xué)系林泓 分程序結(jié)構(gòu)分程序結(jié)構(gòu)Procedure A(m,n); integer m,n; B1:begin real z; array Bm:n; B2:begin real d, e; L3: 2 end; B4:begin array C1:m; 1 B5:begin real e; L6: 5 4 end; end; L8:end; 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 分程序結(jié)構(gòu)的存儲(chǔ)分配方案分程序結(jié)構(gòu)的存儲(chǔ)分配方案 處理分程序結(jié)構(gòu)存儲(chǔ)分配方案的一種簡單辦處理分程序結(jié)構(gòu)存儲(chǔ)分配方案的一種簡單辦法是，把分程序看成法是，把分程序看成 “無名無參過無名無參過 程程”，

43、它在，它在哪里定義就在哪里被調(diào)用。因此，可以把處理過哪里定義就在哪里被調(diào)用。因此，可以把處理過程的存儲(chǔ)辦法應(yīng)用到處理分程序中。但這種做法程的存儲(chǔ)辦法應(yīng)用到處理分程序中。但這種做法是極為低效的。是極為低效的。 一則，每逢進(jìn)入一則，每逢進(jìn)入 一個(gè)分程序，就照樣建立一個(gè)分程序，就照樣建立連接數(shù)據(jù)和連接數(shù)據(jù)和DISPLAY表表,這是不必要的。這是不必要的。 二則二則 ，當(dāng)從內(nèi)層分程序向外層轉(zhuǎn)移時(shí)，可，當(dāng)從內(nèi)層分程序向外層轉(zhuǎn)移時(shí)，可能同時(shí)要結(jié)束若干個(gè)分程序。能同時(shí)要結(jié)束若干個(gè)分程序。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓按照過程處理辦法，意味著必須一層一層地按照過程處理辦法，意味著必須

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

45、退出。但這種辦法是很浪費(fèi)時(shí)間的。浪費(fèi)時(shí)間的。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 為了解決上述問題，可采取兩種措施。第一，為了解決上述問題，可采取兩種措施。第一，對每個(gè)過程或分程序都建立有自己的棧頂指示器對每個(gè)過程或分程序都建立有自己的棧頂指示器TOP，代替原來僅有過程的棧頂指示器，代替原來僅有過程的棧頂指示器, 每個(gè)每個(gè)TOP的值保存在各自活動(dòng)記錄中。這樣，上述的的值保存在各自活動(dòng)記錄中。這樣，上述的第二個(gè)問題便可解決。第二，不把分程序看作第二個(gè)問題便可解決。第二，不把分程序看作“無參過程無參過程”，每個(gè)分程序享用包圍它的那個(gè)最，每個(gè)分程序享用包圍它的那個(gè)最近過程的近過程

46、的DISPLAY。每個(gè)分程序都隸屬于某個(gè)。每個(gè)分程序都隸屬于某個(gè)確定的過程，分程序的層次是相對于它所屬的那確定的過程，分程序的層次是相對于它所屬的那個(gè)過程進(jìn)行編號的。個(gè)過程進(jìn)行編號的。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓： 每個(gè)過程被當(dāng)作是每個(gè)過程被當(dāng)作是0層分程序。而過程體分程層分程序。而過程體分程序（假定是一個(gè)分程序）當(dāng)作是它所管轄的第序（假定是一個(gè)分程序）當(dāng)作是它所管轄的第1層層分程序。分程序。 這樣，每個(gè)過程的活動(dòng)記錄所含的內(nèi)容有：這樣，每個(gè)過程的活動(dòng)記錄所含的內(nèi)容有：1.過程的過程的TOP值，它指向過程活動(dòng)記錄的棧頂位置。值，它指向過程活動(dòng)記錄的棧頂位置。2.連接

47、數(shù)據(jù)，共四項(xiàng)：連接數(shù)據(jù)，共四項(xiàng)： (1)老老SP值；值；(2)返回地址；返回地址；(3)全局全局DISPAY地址；地址；(4)調(diào)用時(shí)的棧頂單元地址，老調(diào)用時(shí)的棧頂單元地址，老TOP。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 3. 參數(shù)個(gè)數(shù)和形式單元參數(shù)個(gè)數(shù)和形式單元 4. DISPAY表。表。5. 過程所轄的各分程序的局部數(shù)據(jù)單元。過程所轄的各分程序的局部數(shù)據(jù)單元。 對于對于每個(gè)分程序來說，它們包括：每個(gè)分程序來說，它們包括：（1)分程序的分程序的TOP值。當(dāng)進(jìn)入分程序時(shí)它含現(xiàn)行值。當(dāng)進(jìn)入分程序時(shí)它含現(xiàn)行棧頂?shù)刂?，以后，用來定義棧的新高度（分程棧頂?shù)刂?，以后，用來定義棧的新高度

48、（分程序的序的TOP值）；值）；（2)分程序的局部變量，分程序的局部變量， 數(shù)組內(nèi)情向量和臨時(shí)工數(shù)組內(nèi)情向量和臨時(shí)工作單元。作單元。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓過程的活動(dòng)記錄過程的活動(dòng)記錄B的的 數(shù)數(shù)組組B的內(nèi)情向量的內(nèi)情向量變量變量 z z kdD I S P L A Y6 形式單元形式單元m,nm,n5 參數(shù)個(gè)數(shù)：參數(shù)個(gè)數(shù)：4調(diào)用時(shí)的棧頂?shù)刂罚ɡ希┱{(diào)用時(shí)的棧頂?shù)刂罚ɡ希? 全局全局D I S P L A Y 地址地址2返回地址返回地址1老老 S P0 過程的，指向活動(dòng)記錄之頂過程的，指向活動(dòng)記錄之頂SP數(shù)數(shù)組的內(nèi)情向量組的內(nèi)情向量B的的B的的B的的變量變量 e

49、e變量變量 d d和和e e武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓B B1T OB的的 信信 息息 向向 量量 ZB1的的 PD I S P L A Y 形式單元形式單元 m , n 2連連 接接數(shù)數(shù) 據(jù)據(jù)A的的T O P (b)進(jìn)進(jìn) 入入 分分 程程 序序 B1D I S P L A Y 形式單元形式單元 m , n 2連連 接接數(shù)數(shù) 據(jù)據(jù) (a) 到到 達(dá)達(dá) 標(biāo)標(biāo) 號號 B1處處A的的T O P武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 （d d）進(jìn)入分程序）進(jìn)入分程序B2 數(shù)數(shù) 組組 B e dB22的的 T O PB 的的 信信 息息 向向 量量 zB1

50、的的 T O PD I S P L A Y 形式單元形式單元 m,n2連接連接 數(shù)數(shù) 據(jù)據(jù)A 的的 T O P 數(shù)數(shù) 組組 BB 的的 信信 息息 向向 量量 zB1 的的 T O PD I S P L A Y 形式單元形式單元 m,n2連連 接接 數(shù)數(shù) 據(jù)據(jù)A 的的 T O P （c c）數(shù)組分配之后）數(shù)組分配之后武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓(e) 進(jìn)入分程序進(jìn)入分程序B4分配數(shù)組分配數(shù)組C之后之后 數(shù)數(shù) 組組C 數(shù)數(shù) 組組BC的的 向向 量量 內(nèi)內(nèi) 情情B4的的T O PB的的 內(nèi)內(nèi) 情情 向向 量量 ZB1 的的T O PD I S P L A Y 形式單元形

51、式單元 m,n 2連連 接接 數(shù)數(shù) 據(jù)據(jù)A的的T O P (f) 進(jìn)入分程序進(jìn)入分程序B5 數(shù)數(shù) 組組 C 數(shù)數(shù) 組組 B eB5的的T O PC 的的 內(nèi)內(nèi) 情情 向向 量量B4的的T O PB 的的 內(nèi)內(nèi) 情情 向向 量量 zB1的的T O PD I S P L A Y 形式單元形式單元 m,n 2連接數(shù)據(jù)連接數(shù)據(jù)A的的T O P 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.3 參數(shù)傳遞參數(shù)傳遞(1)procedure exchangel(i,j:integer);(2) var x:integer;(3) begin;(4) x:=ai; ai:=aj; aj:=x(5

52、) end; 帶有非局部變量和形參的帶有非局部變量和形參的PASCAL過程過程非局變量非局變量ai和和aj的的值進(jìn)行交換，值進(jìn)行交換，i,j為形參（在為形參（在這里是傳值）這里是傳值）武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 (1)program reference(input,output);(2)var a,b:integer;(3)procedure swap(var x,y:integer);(4) var temp:integer;(5) begin (6) temp:=x;(7) x:=y;(8) y:=temp(9) end;(10)begin(11) a:=1;

53、 b:=2;(12) swap(a,b);(13) writeln(a=,a);writeln(b=,b)(14)end. 帶有過程帶有過程swap的的PASCAL程序程序武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 10.3.1 傳值（值調(diào)用傳值（值調(diào)用call-by-value）特點(diǎn)是對形式參數(shù)的任何運(yùn)算不影響實(shí)參特點(diǎn)是對形式參數(shù)的任何運(yùn)算不影響實(shí)參的值。的值。 例如：過程例如：過程 swap(x,y:integer); swap(a,b）；）； 其結(jié)果：其結(jié)果： a,b調(diào)用前的值不改變。調(diào)用前的值不改變。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓傳值的實(shí)現(xiàn)傳值的

54、實(shí)現(xiàn)（1）形式參數(shù)當(dāng)作過程的局部變量處理，即在）形式參數(shù)當(dāng)作過程的局部變量處理，即在被調(diào)過程的活動(dòng)記錄中開辟了形參的存儲(chǔ)空間，被調(diào)過程的活動(dòng)記錄中開辟了形參的存儲(chǔ)空間，這些存儲(chǔ)位置即是我們所說的形式單元（用以這些存儲(chǔ)位置即是我們所說的形式單元（用以存放實(shí)參）。存放實(shí)參）。（2）調(diào)用過程計(jì)算實(shí)參的值，并將其放在對應(yīng)）調(diào)用過程計(jì)算實(shí)參的值，并將其放在對應(yīng)形式單元開辟的空間中。形式單元開辟的空間中。（3）被調(diào)用過程執(zhí)行時(shí)，就像使用局部變量一）被調(diào)用過程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。樣使用這些形式單元。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓procedure swap

55、( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 調(diào)用調(diào)用swap(a,b) 過程將不會(huì)影響過程將不會(huì)影響a和和b的值。的值。 其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算：其結(jié)果等價(jià)于執(zhí)行下列運(yùn)算： x :=a； y :=b； temp :=x； x :=y； y :=temp武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓10.3.2 傳地址（變量參數(shù)傳地址（變量參數(shù)call-by-address 、 call-by-location 、 call- by- reference ） 例如：過程例如：過程 swap(var x,y:integer); swap(a,b）；）； （ a,b為為調(diào)用時(shí)的實(shí)參調(diào)用時(shí)的實(shí)參 ） 調(diào)用結(jié)果調(diào)用結(jié)果a,b的值被改變。的值被改變。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓傳地址的實(shí)現(xiàn)傳地址的實(shí)現(xiàn)把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，即把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形參，