第13章運(yùn)行時存儲空間的組織

1、第13章 運(yùn)行時存儲空間的組織第一節(jié) 程序的存儲空間1. 代碼空間和數(shù)據(jù)空間1.1 程序投入運(yùn)行的必要條件程序要投入運(yùn)行，必須在內(nèi)存中分配一定的存儲空間，并將程序裝入其中，包括：n 可運(yùn)行的代碼（代碼空間）n 代碼運(yùn)行的環(huán)境（數(shù)據(jù)空間）1.2 代碼空間（C）內(nèi)容：線性存放著目標(biāo)指令序列。當(dāng)前執(zhí)行的指令位置由指令指針ip指示。1.3 數(shù)據(jù)空間（D）內(nèi)容：變量、常數(shù)、控制信息、描述符等。n 靜態(tài)分配：在運(yùn)行前就可確定數(shù)據(jù)空間的大小, 在編譯時刻就能進(jìn)行的存儲分配。n 動態(tài)分配：運(yùn)行時才能進(jìn)行的存儲分配。2. 活動記錄程序由程序單元（函數(shù)、子程序）組成，因此程序的數(shù)據(jù)空間由相應(yīng)程序單元的數(shù)據(jù)空間組成

2、。n 一個程序單元的數(shù)據(jù)空間叫做該程序單元的活動記錄。n 一個程序單元在執(zhí)行過程中所需要的數(shù)據(jù)信息、管理信息都是通過它的活動記錄來存放的。n 一個程序單元的每一次激活，都應(yīng)在內(nèi)存中建立相應(yīng)的活動記錄。2.1 活動記錄的內(nèi)容(1) 返回地址(2) 動態(tài)連接(3) 靜態(tài)連接(4) 現(xiàn)場保護(hù)(5) 參數(shù)區(qū)(6) 變量區(qū)變量區(qū)變量區(qū)變量區(qū)參數(shù)區(qū)現(xiàn)場保護(hù)靜態(tài)連接動態(tài)連接返回地址2.2 活動記錄的特點除了變量存儲區(qū)外，其余部分存儲長度編譯時可以確定，所以變量 i 的地址可用下式表示：D + offset(i)其中， D是活動記錄的首地址；offset(i)是變量 i 在活動記錄中的位移。2.3 變量的類型

3、1) 靜態(tài)變量編譯時可以確定活動記錄的首地址D和變量的相對位置offset(i) 。不管在程序單元的哪一次激活中，變量的存儲位置均為：D+offset(i)。2) 半靜態(tài)變量編譯時可確定變量i的相對位置offset(i)，單元激活時可確定活動記錄的首地址D。則每一次激活，變量對應(yīng)一個不同的存儲位置：D+offset(i)。3) 半動態(tài)變量編譯時不能確定變量 i 的相對位置offset(i)，但能確定 i 的存儲格式?？稍诨顒佑涗浿袨?i 建立一個描述符，用于記錄 i 在內(nèi)存中的存儲格式，并在描述符中建立一個指針域，用于記錄 i 在運(yùn)行時的具體存儲地址。例：動態(tài)數(shù)組 int a1.m; int

4、b1.m1.n;4) 動態(tài)變量編譯時不能確定變量 i 的相對位置offset(i)，也不能確定 i 的存儲格式。即描述符需要到運(yùn)行時才能確定，因此可在活動記錄中為 i 設(shè)置兩個指針，一個記錄運(yùn)行時描述符的地址，另一個記錄運(yùn)行時 i 的地址。例： 某些語言中類型可變的變量；某些語言中維數(shù)可變的數(shù)組。 4. 存儲分配模式4.1 靜態(tài)分配n 可用于靜態(tài)變量的分配，變量與存儲區(qū)域的綁定關(guān)系在編譯時便可建立，并完成存儲分配；n 不允許遞歸調(diào)用，不允許動態(tài)數(shù)組，不允許動態(tài)類型的數(shù)據(jù)對象。4.2 棧式分配n 用棧分配活動記錄；n 各程序單元之間的調(diào)用遵循“后進(jìn)先出”模式；n 活動記錄的建立和撤消也滿足“后進(jìn)

5、先出”模式；n 分配方法：當(dāng)一個程序單元被激活時, 在棧頂分配其活動記錄；當(dāng)程序單元退出時，在棧頂將其活動記錄撤銷。例子：某程序中各程序單元的調(diào)用順序為：P運(yùn)行P調(diào)用QQ調(diào)用RR退出Q退出P退出P的活動記錄Q的活動記錄R的活動記錄.4.3 堆分配由于動態(tài)變量的首地址、長度、類型等在編譯時無法確定，在執(zhí)行過程中也可能改變，所以不可能在棧上為這樣的對象分配存儲區(qū)。對于這些變量，必須分配在堆上。例如：C中通過malloc分配的變量；某些語言中的動態(tài)變量等。4.4 存儲空間的組織代碼代碼靜態(tài)數(shù)據(jù)靜態(tài)數(shù)據(jù)棧棧堆堆第二節(jié) 棧式分配1. 半靜態(tài)變量的棧式分配1.1 特點n 變量及活動記錄的長度都可靜態(tài)確定；

6、n 一個程序單元可能被多次激活，活動記錄是在程序單元激活時動態(tài)建立，并與代碼段建立聯(lián)系的。1.2 處理方法(1) 設(shè)置當(dāng)前棧指針current，表示當(dāng)前活動記錄的開始位置（活動記錄首地址D）；(2) 指針free表示數(shù)據(jù)存儲器下一個可用單元；(3) 變量綁定于它在活動記錄中的常數(shù)位移 i，變量通過current變址訪問；(4) A調(diào)用B時，在A活動記錄的棧頂之上建立B的當(dāng)前實例的活動記錄；(5) 從B返回時，釋放其活動記錄。1.3 動態(tài)連接和動態(tài)鏈n 動態(tài)連接：A調(diào)用B時，B的活動記錄中保存的A的活動記錄地址。n 動態(tài)鏈：由動態(tài)連接組成的一個調(diào)用鏈。AEFGF例：例：A call E; E c

7、all F; F call G; G call F;.1.4 CALL P的翻譯(1) D free := ip + 5（保存返回地址）(2) Dfree + 1 := current （保存current ）(3) current := free （建立新的current）(4) free := free + L （調(diào)整free）(5) ip := P（轉(zhuǎn)移到P）例子：過程A調(diào)用過程P返回地址動態(tài)連接返回地址動態(tài)連接A的活動記錄P的活動記錄currentfreefreecurrentcurrentcurrent1.5 RETURN語句的翻譯(1) 恢復(fù)freefree := current(

8、2) 恢復(fù)主調(diào)過程的currentcurrent := Dcurrent + 1(3) 返回ip := Dfree返回地址動態(tài)連接返回地址動態(tài)連接A的活動記錄P的活動記錄freecurrent過程P退出，返回過程Acurrentfree2. 半動態(tài)變量的棧式分配n 在活動記錄中為變量 i建立描述符；n 在活動記錄的最后分配變量 i ；n 用描述中的指針域指向變量 i 的存儲位置。變量區(qū)變量 i 的存儲區(qū)參數(shù)區(qū)現(xiàn)場保護(hù)靜態(tài)連接動態(tài)連接返回地址currentfree(1) 編譯時創(chuàng)建描述符，并產(chǎn)生在運(yùn)行時動態(tài)修改描述符和創(chuàng)建變量存儲空間的指令。(2) 一個單元激活后（進(jìn)入該單元），遇到變量 i 的

9、說明時，調(diào)用上述指令（填描述符，分配存儲空間），并調(diào)整free := free + L。3. 動態(tài)變量的存儲分配n 在活動記錄中為變量 i 分配兩個指針n 在堆上分配動態(tài)變量的描述符和存儲空間n 用活動記錄中的兩個指針指向上述兩個位置變量區(qū)返回地址currentfree變量 i 的描述符變量 i 的存儲區(qū)堆空間n 程序單元間通信方式是通過非局部環(huán)境和參數(shù)傳遞來實現(xiàn)的。n 對非局部環(huán)境的引用必須考慮變量的作用域，變量的作用域是指可訪問該變量的程序范圍。第三節(jié) 非局部環(huán)境1. 動態(tài)作用域規(guī)則這是一種最近活動規(guī)則，對非局部變量，引用的應(yīng)是最近的“調(diào)用外層調(diào)用外層”中說明的變量。例：A-C-F的調(diào)用序

10、列，F(xiàn)的直接調(diào)用外層為C、C的直接調(diào)用外層為A。2. 引用方法通過“動態(tài)鏈動態(tài)鏈”找到最近的“調(diào)用外層調(diào)用外層”中說明的變量。一、動態(tài)作用域規(guī)則1. 靜態(tài)作用域規(guī)則這是一種最近嵌套規(guī)則，對非局部變量，引用的應(yīng)是最近的“嵌套外層嵌套外層”中說明的變量。例：嵌套的層次若A是B的直接外層，則B的層次=A的層次+1。A(0)、B(1)、C(2)、D(3)、E(1)、F(2)、G(2)二、靜態(tài)作用域規(guī)則unit A;y: int;unit B;end B;y: int;unit C;end D;end C;.unit D;.ABCDEFGend E;z: int;unit F;end G;unit G;

11、x,y: int;.unit E;z:=x+y;end F;.end A;x: int;ABCDEFG2. 引用方法通過“靜態(tài)鏈靜態(tài)鏈”找到最近的“嵌套外層嵌套外層”中說明的變量。(1) 靜態(tài)連接和靜態(tài)鏈靜態(tài)連接：指向嵌套直接外層嵌套直接外層的最新最新活動記錄的指針。靜態(tài)鏈：各嵌套程序單元的活動記錄中，靜態(tài)連接的序列構(gòu)成一個靜態(tài)鏈。AEFGF例：例：A call E; E call F; F call G; G call F;.假設(shè)當(dāng)前處在棧頂?shù)氖菃卧狟的活動記錄，單元B中引用了單元A中的變量x。單元A的層次為nA、單元B的層次為nB。要找到變量x的存放地址，即：DA + offset(x)

12、關(guān)鍵是要找到單元A的活動記錄DA。(2) 非局部變量x的地址的求法nnB - nA = 0：A和B是同一層（A就是B）DA = currentnnB - nA = 1：A是B的直接外層（第1個外層）DA Dcurrent + 2nnB - nA = 2：A是B的第2個外層DA = DDcurrent + 2 + 2nnB - nA = 3：A是B的第3個外層DA = DDDcurrent + 2 2 2DA的求法令nB - nA = d，定義函數(shù)f(d)，表示從B的活動記錄出發(fā)，沿靜態(tài)鏈搜索d步，可以到達(dá)A的活動記錄。f(d) if(d=0) then return current ; els

13、e return D f(d-1) + 2 ;(3) 靜態(tài)連接的建立（單元X調(diào)用單元B時）當(dāng)前棧頂為X的活動記錄，需要建立B的活動記錄。(3)nX-nB=1(4)nX-nB1(1)nX-nB=-1XBcall BBXcall BBcall BX(2)nX-nB=0BXcall B(1) nX-nB = -1, B的靜態(tài)連接f(0)(2) nX-nB = 0, B的靜態(tài)連接f(1)(3) nX-nB = 1, B的靜態(tài)連接f(2)(4) nX-nB = d, B的靜態(tài)連接f(d+1)因此，靜態(tài)連接算法為：Dfree+2 = f(d+1)(1) D free := ip + 6（保存返回地址）(2

14、) Dfree + 1 := current （設(shè)置動態(tài)鏈接 ）(3) Dfree + 2 := f(d+1) （設(shè)置靜態(tài)鏈接 ）(4) current := free （建立新的current）(5) free := free + L （調(diào)整free）(6) ip := P（轉(zhuǎn)移到P）(4) CALL P的處理n 形參和實參形參(Formal Parameter)：被調(diào)用單元的參數(shù)實參(Actual Parameter) ：調(diào)用單元的參數(shù)n 參數(shù)傳遞的類型傳值、傳值得結(jié)果、傳地址第四節(jié) 參數(shù)傳遞參數(shù)傳遞實例procedure main begin a, b: integer ; a:=1;

15、b:=2 ;print ( a , b ) ; swap( a , b ) ;print ( a , b ) ; endprocedure swap(x , y)var x,y: intger;beginprint ( x , y ) ;x := x+y ;y := x-y ;x := x-y; print ( x , y ) end(1) 傳值（單向傳遞）實參的值形參的值運(yùn)行結(jié)果：1 , 21 , 22 , 11 , 2(2) 傳值得結(jié)果（雙向傳遞）實參的值形參的值形參的結(jié)果值實參的結(jié)果值運(yùn)行結(jié)果：1 , 21 , 22 , 12 , 1(3) 傳地址（共用同一數(shù)據(jù)單元）實參的地址形參的地址運(yùn)行結(jié)果：1 , 21 , 22 , 12 , 1注意(3)和(2)的區(qū)別，如調(diào)用swap( a , a )時的運(yùn)行結(jié)果。習(xí)題1. 對下列程序，試描述每次調(diào)用時活動記錄棧的狀況，直到C中調(diào)用B時。重點注意動態(tài)連接和靜態(tài)連接的情況。program A;procedure B;procedure C; call B; end C; call C; end Bprocedure