運(yùn)行時(shí)存儲(chǔ)空間組織課件

1、運(yùn)行時(shí)存儲(chǔ)空間組織課件第一節(jié) 程序的存儲(chǔ)空間1. 代碼空間和數(shù)據(jù)空間1.1 程序投入運(yùn)行的必要條件程序要投入運(yùn)行，必須在內(nèi)存中分配一定的存儲(chǔ)空間，并將程序裝入其中，包括： 可運(yù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ù)、控制信息、描述符等。 靜態(tài)分配：在運(yùn)行前就可確定數(shù)據(jù)空間的大小, 在編譯時(shí)刻就能進(jìn)行的存儲(chǔ)分配。 動(dòng)態(tài)分配：運(yùn)行時(shí)才能進(jìn)行的存儲(chǔ)分配。2. 活動(dòng)記錄程序由程序單元函數(shù)、子程序組成，因此程序的數(shù)據(jù)空間由相應(yīng)程序單元的數(shù)據(jù)空間組成。 一個(gè)程序單元的數(shù)據(jù)空間叫做該程序

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

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

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

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

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

7、 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例子：過(guò)程A調(diào)用過(guò)程P返回地址動(dòng)態(tài)連接返回地址動(dòng)態(tài)連接A的活動(dòng)記錄P的活動(dòng)記錄currentfreefreecurrentcurrentcurrent1.5 RETURN語(yǔ)句的翻譯(1) 恢復(fù)freefree := current(2) 恢復(fù)主調(diào)過(guò)程的currentcurrent := Dcurrent + 1

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

9、3. 動(dòng)態(tài)變量的存儲(chǔ)分配n 在活動(dòng)記錄中為變量 i 分配兩個(gè)指針n 在堆上分配動(dòng)態(tài)變量的描述符和存儲(chǔ)空間n 用活動(dòng)記錄中的兩個(gè)指針指向上述兩個(gè)位置變量區(qū)返回地址currentfree變量 i 的描述符變量 i 的存儲(chǔ)區(qū)堆空間n 程序單元間通信方式是通過(guò)非局部環(huán)境和參數(shù)傳遞來(lái)實(shí)現(xiàn)的。n 對(duì)非局部環(huán)境的引用必須考慮變量的作用域，變量的作用域是指可訪問(wèn)該變量的程序范圍。第三節(jié) 非局部環(huán)境1. 動(dòng)態(tài)作用域規(guī)那么這是一種最近活動(dòng)規(guī)那么，對(duì)非局部變量，引用的應(yīng)是最近的“調(diào)用外層中說(shuō)明的變量。例：A-C-F的調(diào)用序列，F(xiàn)的直接調(diào)用外層為C、C的直接調(diào)用外層為A。2. 引用方法通過(guò)“動(dòng)態(tài)鏈找到最近的“調(diào)用外層

10、中說(shuō)明的變量。一、動(dòng)態(tài)作用域規(guī)那么1. 靜態(tài)作用域規(guī)那么這是一種最近嵌套規(guī)那么，對(duì)非局部變量，引用的應(yīng)是最近的“嵌套外層中說(shuō)明的變量。例：嵌套的層次假設(shè)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;x,y: int;.unit E;z:=x+y;end F;.end A;x: int;ABCDEFG2. 引

11、用方法通過(guò)“靜態(tài)鏈找到最近的“嵌套外層中說(shuō)明的變量。(1) 靜態(tài)連接和靜態(tài)鏈靜態(tài)連接：指向嵌套直接外層的最新活動(dòng)記錄的指針。靜態(tài)鏈：各嵌套程序單元的活動(dòng)記錄中，靜態(tài)連接的序列構(gòu)成一個(gè)靜態(tài)鏈。AEFGF例：例：A call E; E call F; F call G; G call F;.假設(shè)當(dāng)前處在棧頂?shù)氖菃卧狟的活動(dòng)記錄，單元B中引用了單元A中的變量x。單元A的層次為nA、單元B的層次為nB。要找到變量x的存放地址，即：DA + offset(x) 關(guān)鍵是要找到單元A的活動(dòng)記錄DA。(2) 非局部變量x的地址的求法nnB - nA = 0：A和B是同一層A就是BnDA = currentnn

12、B - nA = 1：A是B的直接外層第1個(gè)外層nDA Dcurrent + 2nnB - nA = 2：A是B的第2個(gè)外層nDA = DDcurrent + 2 + 2nnB - nA = 3：A是B的第3個(gè)外層nDA = DDDcurrent + 2 2 2DA的求法令nB - nA = d，定義函數(shù)f(d)，表示從B的活動(dòng)記錄出發(fā)，沿靜態(tài)鏈搜索d步，可以到達(dá)A的活動(dòng)記錄。f(d) if(d=0) then return current ; else return D f(d-1) + 2 ;(3) 靜態(tài)連接的建立單元X調(diào)用單元B時(shí)當(dāng)前棧頂為X的活動(dòng)記錄，需要建立B的活動(dòng)記錄。(3)nX-

13、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) Dfree + 1 := current 設(shè)置動(dòng)態(tài)鏈接 (3) Dfree + 2 := f(d+1) 設(shè)置靜態(tài)鏈接 (4) current :=

14、 free 建立新的current(5) free := free + L 調(diào)整free(6) ip := P轉(zhuǎn)移到P(4) CALL P的處理n 形參和實(shí)參形參(Formal Parameter)：被調(diào)用單元的參數(shù)實(shí)參(Actual Parameter) ：調(diào)用單元的參數(shù)n 參數(shù)傳遞的類型傳值、傳值得結(jié)果、傳地址第四節(jié) 參數(shù)傳遞參數(shù)傳遞實(shí)例procedure main begin a, b: integer ; a:=1; 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) 傳值單向傳遞實(shí)參的值形參的值運(yùn)行結(jié)果：1 , 21 , 22 , 11 , 2(2) 傳值得結(jié)果雙向傳遞實(shí)參的值形參的值形參的結(jié)果值實(shí)參的結(jié)果值運(yùn)行結(jié)果：1 , 21 , 22 , 12 , 1(3) 傳地址共用同一數(shù)據(jù)