1、第第10章章 目的程序運轉時的組織目的程序運轉時的組織概概 述述為了使目的程序可以運轉，編譯程序要從操作系統中得為了使目的程序可以運轉，編譯程序要從操作系統中得到一塊存儲區，以使目的程序可以在其上運轉。到一塊存儲區，以使目的程序可以在其上運轉。該存儲區需包容該存儲區需包容 ： 1 1生成的目的代碼生成的目的代碼2 2目的代碼運轉時的數據空間目的代碼運轉時的數據空間數據空間應包括：數據空間應包括：(1)(1)用戶定義的各種類型的數據對象所需的存儲空間用戶定義的各種類型的數據對象所需的存儲空間(2)(2)保管中間結果和傳送參數的暫時任務單元保管中間結果和傳送參數的暫時任務單元(3)(3)調用過程時

2、所需的銜接單元調用過程時所需的銜接單元(4)(4)組織輸入組織輸入/ /輸出所需的緩沖區輸出所需的緩沖區目的代碼所占用空間的大小在編譯時能確定。目的代碼所占用空間的大小在編譯時能確定。有些數據對象所占用的空間也能在編譯時確定。有些數據對象所占用的空間也能在編譯時確定。而有些數據對象具有可變體積和待分配性質，無法在編譯而有些數據對象具有可變體積和待分配性質，無法在編譯時確定存儲空間的位置。時確定存儲空間的位置。因此運轉時的存儲區經常劃分成：目的區、靜態數據區、因此運轉時的存儲區經常劃分成：目的區、靜態數據區、棧區和堆區棧區和堆區目的程序運轉時存儲區的典型劃分目的程序運轉時存儲區的典型劃分code

3、static datastack heap代碼代碼(code)(code)區用以存區用以存放目的代碼，這是固放目的代碼，這是固定長度的，即編譯時定長度的，即編譯時能確定的；靜態數據能確定的；靜態數據區區(static data)(static data)用以用以存放編譯時能確定所存放編譯時能確定所占用空間的數據；棧占用空間的數據；棧區和堆區區和堆區(stack and (stack and heap)heap)用于可變數據以用于可變數據以及管理過程活動的控及管理過程活動的控制信息。制信息。所謂數據空間的分配，本質上看，是將程所謂數據空間的分配，本質上看，是將程序中的每個名字與一個存儲位置關聯起

4、來，序中的每個名字與一個存儲位置關聯起來，該存儲位置用以包容名字的值。該存儲位置用以包容名字的值。 關聯關聯Binding將源程序的文本將源程序的文本 程序運轉動作的程序運轉動作的實現實現 即源程序文本要做哪些功能，目的程序要即源程序文本要做哪些功能，目的程序要實現它的功能。實現它的功能。 源文件中的名字源文件中的名字N 運轉時的存儲運轉時的存儲S (N到到S的映射的映射)10.1 10.1 數據空間的三種不同運用方法和管理方法數據空間的三種不同運用方法和管理方法 數據空間的三種不同運用方法和管理方法數據空間的三種不同運用方法和管理方法: : 靜態存儲分配、棧式動態存儲分配和堆式靜態存儲分配、

5、棧式動態存儲分配和堆式動態存儲分配。動態存儲分配。 1 1、 靜態存儲分配靜態存儲分配這種存儲分配非常簡單，假設在編譯時能確定目這種存儲分配非常簡單，假設在編譯時能確定目的程序運轉中所需的全部數據空間的大小，稱這種分的程序運轉中所需的全部數據空間的大小，稱這種分配戰略為靜態存儲分配。配戰略為靜態存儲分配。像像FORTRANFORTRAN這樣的言語，其程序是段構造的，即由主程序這樣的言語，其程序是段構造的，即由主程序段和假設干子程序段組成。段和假設干子程序段組成。各程序段中定義的名字普通是彼此獨立的，也即各段的各程序段中定義的名字普通是彼此獨立的，也即各段的數據對象名的作用域在各段中，同一個名字

6、在不同的程數據對象名的作用域在各段中，同一個名字在不同的程序段表示不同的存儲單元，不會在不同段間相互援用、序段表示不同的存儲單元，不會在不同段間相互援用、賦值。賦值。另外它的每個數據名所需的存儲空間大小都是常量另外它的每個數據名所需的存儲空間大小都是常量即即不許含可變體積的數據，如可變數組不許含可變體積的數據，如可變數組，且一切數據名，且一切數據名的性質是完全確定的。的性質是完全確定的。這樣，整個程序所需數據空間的總量在編譯時完全確定，這樣，整個程序所需數據空間的總量在編譯時完全確定，換句話說，一旦存儲空間的某個位置分配給了某個數據換句話說，一旦存儲空間的某個位置分配給了某個數據名名關聯起來關

7、聯起來之后，在目的程序的整個運轉過程中，之后，在目的程序的整個運轉過程中，此位置此位置地址地址就屬于該數據名了。就屬于該數據名了。 2 2 動態存儲分配動態存儲分配假設一個程序設計言語允許遞歸過程、可變數組或允假設一個程序設計言語允許遞歸過程、可變數組或允許用戶自在懇求和釋放空間，那么，就需求采用動態存儲許用戶自在懇求和釋放空間，那么，就需求采用動態存儲管理技術。管理技術。由于對于這種程序在編譯時無法知道它在運轉時需求多大由于對于這種程序在編譯時無法知道它在運轉時需求多大的存儲空間，它所需求的數據空間的大小需待程序運轉時的存儲空間，它所需求的數據空間的大小需待程序運轉時動態地確定。動態地確定。

8、假設一個數組所需的存儲空間的大小在編譯時就知道，那假設一個數組所需的存儲空間的大小在編譯時就知道，那么稱它為確定數組，否那么稱為可變數組。么稱它為確定數組，否那么稱為可變數組。例例 : procedure A(m,n:integer);begin real z;array Bm:n;begin end;end;Bm:n 為可變數組，為可變數組，B的上下界是過程的上下界是過程A的實參，的實參，A被被調用時才干確定。調用時才干確定。動態存儲管理技術有兩種方式：棧式動態存儲管理技術有兩種方式：棧式stack和堆式和堆式heap。下面簡述這兩種方式的原那么。下面簡述這兩種方式的原那么。1 1、棧式動態

9、存儲分配、棧式動態存儲分配這種分配戰略是將整個程序的數據空間設計為一個棧。這種分配戰略是將整個程序的數據空間設計為一個棧。例：在具有遞歸構造的言語程序中，每當調用一個過程時，例：在具有遞歸構造的言語程序中，每當調用一個過程時，它所需的數據空間就分配在棧頂，每當過程任務終了時就釋它所需的數據空間就分配在棧頂，每當過程任務終了時就釋放這部分空間。放這部分空間。過程所需的數據空間包括兩部分：過程所需的數據空間包括兩部分：一部分是生存期在本過程這次活動中的數據對象，如部分變一部分是生存期在本過程這次活動中的數據對象，如部分變量、參數單元、暫時變量等等；量、參數單元、暫時變量等等；另一部分那么是用以管理

10、過程活動的記錄信息另一部分那么是用以管理過程活動的記錄信息( (銜接數據銜接數據) )。即當一次過程調用出現時，調用該過程的那個過程的活動即即當一次過程調用出現時，調用該過程的那個過程的活動即被中斷，當前機器的形狀信息，諸如前往地址、存放器的值被中斷，當前機器的形狀信息，諸如前往地址、存放器的值等等，也都必需保管在棧中。當控制從調用前往時，便根據等等，也都必需保管在棧中。當控制從調用前往時，便根據棧中記錄的信息恢復機器形狀，使該過程的活動繼續進展。棧中記錄的信息恢復機器形狀，使該過程的活動繼續進展。2 2、堆式動態存儲分配、堆式動態存儲分配假設一個程序文語提供用戶自在地懇求數據空間和假設一個程

11、序文語提供用戶自在地懇求數據空間和退還數據空間的機制，通常運用一種稱為堆式的動態存退還數據空間的機制，通常運用一種稱為堆式的動態存儲分配方案。儲分配方案。過程活動記錄過程活動記錄: :AR為闡明方便，假定程序是由過程組成，過程運轉時稱作過為闡明方便，假定程序是由過程組成，過程運轉時稱作過程的激活。程的激活。 一個過程的一次執行所需求的信息運用一個延續的存儲區來一個過程的一次執行所需求的信息運用一個延續的存儲區來管理，這個區管理，這個區塊塊叫做一個活動記錄叫做一個活動記錄 lllllll普通這個段要記錄：普通這個段要記錄：暫時值，如計算表達式時的中間任務單元。暫時值，如計算表達式時的中間任務單元

12、。部分變量部分變量數據數據保管運轉過程前的形狀保管運轉過程前的形狀 存放器值存放器值存取鏈存取鏈可選可選 對于非部分量的援用。對于非部分量的援用。控制鏈控制鏈可選可選 指向調用者的活動記錄。指向調用者的活動記錄。實參實參方式單元方式單元前往地址前往地址術語：術語：每個過程的每個過程的ARAR有有3 3個聯絡單元：個聯絡單元：SLSL： 靜態鏈，指向定義該過程的直接外過程靜態鏈，指向定義該過程的直接外過程 或主程序或主程序運轉時最新數據段的基地運轉時最新數據段的基地址。址。DLDL： 動態鏈，指向調用該過程前正在運轉過動態鏈，指向調用該過程前正在運轉過 程的數據段基地址。即指向調用本過程的數據段

13、基地址。即指向調用本過程的那個過程的活動記錄的地址程的那個過程的活動記錄的地址老老SPSPRARA： 前往地址，記錄調用該過程時目的程序前往地址，記錄調用該過程時目的程序的斷點，保管該過程前往后的地址。的斷點，保管該過程前往后的地址。這種情況可以直接采用棧式這種情況可以直接采用棧式存儲分配戰略。存儲分配戰略。在運轉時，每個過程開場時在運轉時，每個過程開場時就把它的活動記錄壓入棧，就把它的活動記錄壓入棧，直到該活動終了，它的活動直到該活動終了，它的活動記錄彈出棧。記錄彈出棧。10.2 簡單的棧式存儲分配簡單的棧式存儲分配程序的特點程序的特點: 過程定義不嵌套過程定義不嵌套,過程可遞歸調用過程可遞

14、歸調用,允許有可變數組允許有可變數組. 例如例如:C言語言語 全局數聽闡明 Main ( ) Main 中的數聽闡明 Void R( ) R 中的數聽闡明 Void Q Q中的數聽闡明 Main Q R 嵌套過程言語的棧式分配方案嵌套過程言語的棧式分配方案n前面我們講的過程不允許言語嵌套定義，如今前面我們講的過程不允許言語嵌套定義，如今我們取消這個限制，即允許過程嵌套定義，一我們取消這個限制，即允許過程嵌套定義，一個過程可以援用包圍它的任一外層過程所定義個過程可以援用包圍它的任一外層過程所定義的標識的標識如變量，數組或過程等如變量，數組或過程等。如：我們。如：我們所熟習的所熟習的PASCALP

15、ASCAL言語程序構培育是這樣一種言言語程序構培育是這樣一種言語。語。n由于過程定義是嵌套的，一個過程可以援用包由于過程定義是嵌套的，一個過程可以援用包圍它的任一外層過程所定義的標識圍它的任一外層過程所定義的標識如變量，如變量，數組或過程等數組或過程等。也就是說，運轉時，一個過。也就是說，運轉時，一個過程程Q Q可以援用它的的任不測層的最新活動記錄可以援用它的的任不測層的最新活動記錄的名字所對應的存儲空間，過程的名字所對應的存儲空間，過程Q Q運轉時，必運轉時，必需知道它的一切外層的最新活動記錄的地址。需知道它的一切外層的最新活動記錄的地址。 方法：方法： 1. 1. 用靜態鏈用靜態鏈如如PL

16、/0PL/0的的SLSL。 引入一個稱為靜態鏈的指針，該指針引入一個稱為靜態鏈的指針，該指針 為活動為活動 記錄的一個域，指向直接外層記錄的一個域，指向直接外層 的最新活動記錄的地址。的最新活動記錄的地址。 2. 2. 用用DISPLAYDISPLAY表。表。例：(1) program sort(input, output); (2)var a: array 0.10 of integer; (3)x: integer; (4)procedure readarray; (5)var i: integer; (6)beginaendreadarray; /readarray的過程體 (7)pro

17、cedure exchange(i,j: integer); (8)begin (9) x =ai; ai =aj; aj =x; /exchange的過程體 (10) endexchange; (11) procedure quicksort(m,n: integer); (12) var k,v: integer; (13) function partition(y,z:integer):integer; (14)var i.j:integer; (15)begin a /partition的函數體 (16)v (17) exchange(i,j); (18) endpartition;

18、(19) beginendquicksort; /quicksort的過程體 (20) beginendsort. 它的嵌套情況如下：sortreadarrayexchangequicksort partition假設該程序的某次執行順序為：sortquicksortquicksortpartitionexchange即主程序(最外層過程)sort開場執行,繼而進入過程quicksort，而又一次進入過程quicksort，接著進入過程partition，進入過程exchange。 sortquicksortquicksortpartitionexchange處理對非部分量的援用處理對非部分量

19、的援用存取存取用用DisplayDisplay表表另外一種存取非部分變量的方法，也是常用的有效另外一種存取非部分變量的方法，也是常用的有效方法。即每進入一個過程后，在建立它的活動記方法。即每進入一個過程后，在建立它的活動記錄的同時建立一張嵌套層次顯示表錄的同時建立一張嵌套層次顯示表displaydisplay。DisplayDisplay表表-嵌套層次顯示表嵌套層次顯示表當前激活過程的層次為當前激活過程的層次為K K，它的，它的DisplayDisplay表含有表含有K+1K+1個單元，依次存放著現行層，直接外層個單元，依次存放著現行層，直接外層直至最直至最外層的每一過程的最新活動記錄的基地址

20、外層的每一過程的最新活動記錄的基地址例如：上例的程序，假定有如下四種調用情況：例如：上例的程序，假定有如下四種調用情況：(a)sortquicksort;(b)sortquicksortquicksort;(c)sortquicksortquicksortpartition;(d)sortquicksortquicksortpartitionexchange。那么那么P225 圖圖10.16的的a，b，c，d分別闡分別闡明了上述四種情形的運轉棧和明了上述四種情形的運轉棧和display。確實看出，。確實看出，display顯示了存取鏈的信息。顯示了存取鏈的信息。例：例：program main

21、(i,0); 程序結構圖程序結構圖 proc R(c,d); R end /*R*/ proc P (a); 主主 proc Q (b); P Q call R R(x,y); end /*Q*/ call Q Q(z); call P end /*P*/ call R P（W）；）； R（U，V）；）； end /*main*/用用Display表的方案表的方案(1)主程序主程序-(2)P-(3)Q-(4)R P 的活動記錄主程序的活動記錄 d1d0displaysptop主程序的主程序的活動記錄活動記錄 d0spdisplaytop12用用Display表的方案表的方案n主程序主程序-P-

22、Q-RR 的的活動記錄活動記錄 Q 的的活動記錄活動記錄 P 的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄Q 的的活動記錄活動記錄 P 的的活動記錄活動記錄主程序的主程序的活動記錄活動記錄 displayd2d1d0 d1d0 displaysptoptopsp34displaydisplay本身的體積在編譯時可確定。至于本身的體積在編譯時可確定。至于displaydisplay本身本身作為單獨的表分配存儲，還是作為活動記錄的一部分，作為單獨的表分配存儲，還是作為活動記錄的一部分，比如置于實參比如置于實參方式單元方式單元的上端的上端如下圖如下圖，那么取，那么取決于編譯程序的設計者。決于

23、編譯程序的設計者。display作為活動記錄的一部分Display表：當過程的層表：當過程的層次為次為n，它的，它的 display為為n+1個值。即第個值。即第0層到第層到第n層的層的SP的值。的值。全局全局Display表：直接外表：直接外層的層的Display 地址。地址。銜接數據：有銜接數據：有3個，個，即老即老SP，前往地址，前往地址，全局全局Display。例：例：P227 圖圖10.19的程序中，分程序有的程序中，分程序有B0,B1,B2,B3。 分程序的作用域遵照的是最近嵌套原那么分程序的作用域遵照的是最近嵌套原那么: P226過程的過程的TOPTOP單元一直是指向活動記錄的棧

24、頂。單元一直是指向活動記錄的棧頂。而過程運轉中的任何時辰的現行分程序的而過程運轉中的任何時辰的現行分程序的TOPTOP那么存放最新的那么存放最新的棧頂地址。棧頂地址。過程體中的并列分程序可享用同一存儲空間過程體中的并列分程序可享用同一存儲空間, ,由于它們不會同由于它們不會同時執行。時執行。分程序除數組外的一切數據的地址在編譯時可以靜態地確定。分程序除數組外的一切數據的地址在編譯時可以靜態地確定。 參數傳送參數傳送參數參數 傳送的三種途徑：傳送的三種途徑：傳地址、傳值、傳名傳地址、傳值、傳名傳地址：把實參的地址傳送給形參。即調用過程把傳地址：把實參的地址傳送給形參。即調用過程把一個指向實參的存

25、儲地址的指針傳送給被調用過程一個指向實參的存儲地址的指針傳送給被調用過程相應的形參。相應的形參。1 1、真實參數是一個變量，那么直接傳送它的地址。、真實參數是一個變量，那么直接傳送它的地址。2 2、真實參數是表達式、真實參數是表達式-計算值，放入一存儲單計算值，放入一存儲單元，傳此存儲單元地址元，傳此存儲單元地址3 3、過程對形參的援用或賦值都被處置成對方式單、過程對形參的援用或賦值都被處置成對方式單元的間接訪問元的間接訪問指針操作指針操作 (1)program reference(input,output);(2)var a,b:integer;(3)procedure swap(var x

26、,y:integer);(4) var temp: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=,a);writeln(b=,b)(14)end.PASCAL程序有關鍵字var時，PASCAL言語的參數傳送運用的方式是傳地址；去掉var，那么運用的方式是傳值。傳值：傳值： 在被調過程的活動記錄中開辟形參的存儲空間，這些在被調過程的活動記錄中開辟形參的存儲空間，這些存儲位置即是我們所說的形參或方式單元。存儲位置即是我們

27、所說的形參或方式單元。 調用過程計算實參的值，并將它們的右值放在為方式調用過程計算實參的值，并將它們的右值放在為方式單元開辟的空間中。單元開辟的空間中。 被調用過程執行時，就像運用部分變量一樣運用這被調用過程執行時，就像運用部分變量一樣運用這些方式單元。些方式單元。procedure swap( x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end； 調用調用swap(a,b) 過程將不會影響過程將不會影響a和和b的值。的值。 其其結果等價于執行以下運算：結果等價于執行以下運算： x :=a； y :=b； temp

28、:=x； x :=y； y :=temp n傳地址傳地址變量參數變量參數n 例如：過程例如：過程 swap(var x,y:integer);swap(var x,y:integer);n swap(a,b swap(a,b； a,b a,b為調用時的實參為調用時的實參 n 調用結果調用結果a,ba,b的值被改動。的值被改動。n傳值傳值值調用值調用n特點是對方式參數的任何運算不影響實參的值。特點是對方式參數的任何運算不影響實參的值。n 例如：過程例如：過程 swap(x,y:integer);swap(x,y:integer);n swap(a,b swap(a,b；其結果：；其結果： a,b

29、a,b調用前的值不調用前的值不改動。改動。 (1)swap(x,y)(2)int *x,*y;(3) int temp;(4) temp=*x; *x=*y; *y=temp;(5)(6)main( )(7) int a=1,b=2;(8) swap(&a,&b);(9) printf(“a is now %d,b is now %dn,a,b);(10) 在一個值調用過程中運用指針的在一個值調用過程中運用指針的C程序程序在在C程序中傳地址，用指針實現。程序中傳地址，用指針實現。例例:主程序主程序A：2；B:=3;P(A+B, A, A)Print(A);子程序：子程序：P(X

30、, Y ,Z ) Y:=Y+1; Z:=Z+X; 問傳地址和傳值問傳地址和傳值PrintA的結果是多少？的結果是多少？傳地址：傳地址：T：AB5，X := &T ;Y := &A ;Z := &A ;即即X 所指的變量為所指的變量為T，Y ,Z所指的變量是所指的變量是AY:=Y +1=2+1=3 即即A的值變為的值變為3Z :=Z +X =AT358主程序主程序A：2；B:=3;P(A+B, A, A)Print(A);子程序：子程序：P(X, Y ,Z ) Y:=Y+1; Z:=Z+X; 所以：傳地址的結果為所以：傳地址的結果為 ： 8傳值的結果為：傳值的結果為：2傳名：將被調用的過程體復制到調用途，并將每個傳名：將被調用的過程體復制到調用途，并將每個形參形參“文字地文字地交換成實參。交換成實參。主程序主程序A：2；B:=3;P(A+B, A, A)Print(A);子程序：子程序：P(X, Y ,Z ) Y:=Y+1; Z:=Z+X; 例：傳名時傳名時Print(A)的結果是多少？的結果是多少？主程序主程序A：2；B:=3;P(A+B, A, A)Print(A);子程序：子程序：P(X, Y