第9章 運行時存儲空間組織.ppt

1、第九章運行時存儲空間組織,在程序的執(zhí)行過程中，程序中數(shù)據(jù) 的存取是通過與之對應(yīng)的存儲單元來進 行的。 程序中使用的存儲單元都由標(biāo)識符 來表示。 標(biāo)識符對應(yīng)的內(nèi)存地址都是由編譯 程序在編譯時或由其生成的目標(biāo)程序運行時進行分配。,第九章運行時存儲空間組織,9.1 目標(biāo)程序運行時的活動 9.2 運行時存儲器的劃分 9.3 靜態(tài)存儲分配 9.4 簡單的棧式存儲分配 9.5 嵌套過程語言的棧式實現(xiàn) 9.6 堆式動態(tài)存儲分配,1、過程的活動 P240,9.1 目標(biāo)程序運行時的活動,2、參數(shù)傳遞 （1） 傳值 （2）傳地址 （3）傳名 （4）得結(jié)果,9.1 目標(biāo)程序運行時的活動,例： procedure s

2、wap(n,m:real); var j:real; begin j:=n; n:=m; m:=j; end;,若存在調(diào)用：swap(i,k(i) （1）傳值 （2）傳地址 （3）傳名： j:=i; i:=K(i) ; k(i):=j;,例： procedure swap(n,m:real); var j:real; begin j:=n; n:=m; m:=j; end;,若存在調(diào)用：swap(i,k(i) (4) 得結(jié)果 swap(m,n) addr(i), i addr(k(i),K(i),9.2運行時存儲器的劃分,一、運行時存儲器的劃分 1、編譯器需要在存儲區(qū)保護的對象 （1）目標(biāo)代碼

3、編譯是可確定，故可放在一個靜態(tài)確 定的區(qū)域 （2）數(shù)據(jù)對象部分數(shù)據(jù)對象的大小在編譯時可確 定，故也可放在一個靜態(tài)確定的區(qū)域 （3）跟蹤過程活動的控制棧,9.2運行時存儲器的劃分,2、棧和堆 A、棧：用擴充的棧來管理過程的活動，當(dāng)發(fā)生過程 調(diào)用時，中斷當(dāng)前活動的執(zhí)行，激活新被調(diào) 用過程的活動，并把包含在這個活動生存期 中的數(shù)據(jù)對象以及該活動有關(guān)的其它信息存 入棧中。當(dāng)控制從調(diào)用返回時，將所占存儲 空間彈出棧頂。同時，被中斷的活動恢復(fù)執(zhí)行。 B、堆（heap）存放動態(tài)數(shù)據(jù)，大小可隨程序的運 行而改變。,9.2運行時存儲器的劃分,二、活動記錄 1、活動記錄：為了管理過程在一次執(zhí)行中所需要 的信息，使

4、用一個連續(xù)的存儲塊，該連 續(xù)的存儲塊叫活動記錄。 當(dāng)過程調(diào)用時，產(chǎn)生一個過程的新的活動，用一 個活動記錄表示該活動的相關(guān)信息，并將 其壓入棧。 當(dāng)過程返回時，將該活動記錄從棧中彈出。,9.2運行時存儲器的劃分,2、活動記錄的內(nèi)容 （1）連接數(shù)據(jù) SP指向現(xiàn)行過程的活動記錄在棧里的起始位置。 返回地址 動態(tài)鏈 指向調(diào)用該過程前的最新活動記錄地址 的指針。運行時，使運行棧上各數(shù)據(jù)全動態(tài)建 立的次序結(jié)成鏈。鏈頭為棧頂起始位置。 靜態(tài)鏈指向靜態(tài)直接外層最新活動記錄地址的 指針，用來訪問非局部數(shù)據(jù) （2）形式單元存放相應(yīng)的實在參數(shù)的地址或值 （3）局部數(shù)據(jù)區(qū) 局部變量簡單變量 內(nèi)情向量局部數(shù)據(jù)的內(nèi)情向量

5、，即數(shù)組元素 臨時工作單元存放對表達式求值的結(jié)果,9.2運行時存儲器的劃分,三、存儲分配策略 1、靜態(tài)存儲分配策略 在編譯時對所有數(shù)據(jù)對象分配固定的存儲單元，且 在運行時始終保持不變。 2、棧式動態(tài)分配策略 在運行時把存儲器作為一個棧進行管理，運行時， 每當(dāng)調(diào)用一個過程，它所需要的存儲空間就動態(tài)地分配 于棧頂，一旦退出，它所占空間就予以釋放。 3、堆式動態(tài)分配策略 在運行時把存儲器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存 儲空間的申請與歸還（回收），凡申請者從堆中分 給一塊，凡釋放者退回給堆,9.3 靜態(tài)存儲分配 P246,9.4簡單的棧式存儲分配,1、前提：假設(shè)程序語言無分程序結(jié)構(gòu)，過程定義不允 許嵌套

6、，但允許過程的遞歸調(diào)用。 例如：C 語言 2、過程：運行時 每當(dāng)進入一個過程即一個過程的活動開始，就把其 它活動記錄壓入棧（置于棧頂），從而 形成過程工作時的數(shù)據(jù)區(qū) 當(dāng)活動結(jié)束即過程退出時，再把其活動記錄彈出 棧，這樣，它在棧頂上的數(shù)據(jù)區(qū)在隨即 不復(fù)存在,9.4簡單的棧式存儲分配,3、舉例 （1）主程序調(diào)用過程Q，而Q又調(diào)用R，在R進 入運行后的存儲結(jié)構(gòu) （2）主程序調(diào)用過程Q，Q遞歸調(diào)用自己，在Q 過程第二次進入運行后的存儲結(jié)構(gòu) （3）主程序先調(diào)用過程Q，然后主程序調(diào)用R， 且過程Q不調(diào)用Q和R Q和R進入運行后的存儲結(jié)構(gòu)如圖所示：,SP,TOP,靜態(tài)分配,9.4簡單的棧式存儲分配,4、指示

7、器SP總是指向現(xiàn)行過程活動記錄的 起點，用于訪問局部數(shù)據(jù) 指示器TOP始終指向（已占用）棧頂單元,9.4簡單的棧式存儲分配,一、C的活動記錄 1、C的活動記錄的項目 （1）連接數(shù)據(jù)A、老SP值: 即前一活動記錄的地址 B、返回地址 （2）參數(shù)個數(shù) （3）形式單元存放實在參數(shù)的值或地址 （4）過程的局部變量,9.4簡單的棧式存儲分配,2、（1）不允許過程嵌套非局部量僅能出現(xiàn)在源程 序頭，可采用靜態(tài)存儲分配，編譯時可確定其地址 （2）局部變量或形參在活動記錄中的位置確定 其地址是相對于活動記錄的基地址SP的 絕對地址=活動記錄基地址+相對地址 變址訪問XSPX代表相對數(shù)，即相對于活動記 錄起點的地

8、址，編譯時可完全確定下來,9.4簡單的棧式存儲分配,9.5嵌套過程語言的棧式實現(xiàn),前提：假定允許過程定義嵌套，如Pascal語言， 但去掉Pascal中的“文件”類型 程序舉例：課本P258 圖9.15,9.5嵌套過程語言的棧式實現(xiàn),一、非局部名字的訪問的實現(xiàn) 說明非局部名字的訪問 1、靜態(tài)鏈和活動記錄 A、靜態(tài)鏈活動記錄的一個域，從一個過程的當(dāng)前活 動記錄指向其靜態(tài)直接外層的最新活動記錄。 動態(tài)鏈活動記錄一個域，從一個過程的當(dāng)前活動 記錄指向調(diào)用該過程前正在運行的過程的最新 的活動記錄的基地址。 B、活動記錄結(jié)構(gòu)P259 圖9.16,program P; var a,x:integer; p

9、roc Q(b:integer); var i:integer; proc R(u:integer,var v:integer); var c,d:integer; begin end; begin end;,proc S; var c,i:integer; begin end; begin end.,proc P; proc Q; proc R; begin R(.,.); end; begin R(,) end; proc S; begin Q() end; begin S; end.,0,1,2,3,4,5,6,7,8,9,0,返回地址,0,a,x,0,返回地址,0,0（形參個數(shù)）,c,

10、i,10,C、程序運行時棧的變化過程舉例：,過程P中調(diào)用S時,過程S中調(diào)用Q時,過程Q中調(diào)用R時,32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17,16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0,過程R中遞歸調(diào)用R,9.5嵌套過程語言的棧式實現(xiàn),D、含義： 靜態(tài)鏈：通過其值可以找到當(dāng)前過程/活動可以引用的“非局部變量”的過程的活動記錄的基址，從而找到要引用的“非局部變量” 動態(tài)鏈：通過其值可以找到當(dāng)前過程/活動結(jié)束后，需要返回的上一層活動記錄的基址SP,9.5嵌套過程語言的棧式實現(xiàn),2、嵌套層次顯示表（displa

11、y）和活動記錄 A、嵌套層次顯示表：每進入一個過程后，在建立它的活動區(qū)的同時建立該表 B、表的內(nèi)容：假定現(xiàn)進行的過程的層數(shù)為i，則其display 含有i+1個單元。該表本身是一個小棧，自頂向 下每個單元依次存放現(xiàn)行層，直接外層,直 到最外層（0層主程序?qū)樱┑让恳粚舆^程的最新 活動記錄的基地址。 舉例：令過程R的外層為Q，Q的外層為P，則R運行時display表為,9.5嵌套過程語言的棧式實現(xiàn),C、“非局部量”地址的確定： 絕對地址= display靜態(tài)層數(shù)+相對地址 D、活動記錄結(jié)構(gòu)：,p1 調(diào)用 P2 的兩種不同嵌套：,P1,P2,P0,P2,P1,k-1,k,k-1,k,k,p1 調(diào)用

12、P2 的兩種不同嵌套：,P1,P2,k-1,k,Display K項,P1,P2,P1的display k項,p2的sp,top,sp,top,sp,p1 調(diào)用 P2 的兩種不同嵌套：,P0,P2,P1,k-1,k,k,Display K+1項,P1,P2,P1的display 前k項,p2的sp,top,sp,top,sp,0,0,返回地址,1,0（display),2,a,3,x,4,0,5,返回地址,6,2(全局display),7,0(形參個數(shù)),8,0,9,5,10,C,11,i,12,F、靜態(tài)鏈方法與顯示表方法的比較： 通過向示表訪問非局部量要比沿著靜態(tài)鏈訪問非局部量的速度快。 原

13、因：因為通過顯示表的一個域，可以確定任意 外層活動記錄的指針，再沿著這個指針便可 以找到處于外層活動記錄的非局部量。,9.5嵌套過程語言的棧式實現(xiàn),二、參數(shù)傳遞的實現(xiàn) 1、par TT為數(shù)組 （1）或者傳遞數(shù)組T的首地址 （2）或者傳遞數(shù)組T的內(nèi)情向量地址 2、Par TT為過程 假設(shè)：過程P把過程T作為實在參數(shù)傳遞過程Q，隨 后，Q又通過引用相應(yīng)的形式參數(shù)調(diào)用T。 3、Par T 為標(biāo)號,在進入T之后，為了建立T自己的display ，T必須知道它直接外層的display。 又P的display或者正好就是這個外層的display， 或者包含了這個外層display 而由于T的層數(shù)是已知的

14、只要知道P的display，T就可以用它來建立自己的display，即假定T的層數(shù)為1，則T的display乃是由P的display的前1個單元的內(nèi)容和SP的現(xiàn)行值所組成。,為了使得過程T工作時能夠知道過程P的display，必須在P把T作為使 參傳遞給Q的時候把P自身的display地址也傳過去 即：過程P中的par T 的作用可刻畫為建立如下所示的兩個相繼臨時單元： 第一個臨時單元B1：過程T的入口地址 第二個臨時單元B2：過程T的display地址。； 然后執(zhí)行（i+1）TOP:=addr(B1)把第一臨時單元B1的地址傳給Q,假定過程Q現(xiàn)在執(zhí)行到調(diào)用語句call Z,m Z形式參數(shù)，形

15、式單元Z中已含有上述B1的地址 故B1的內(nèi)容將用來作為轉(zhuǎn)子指令的目的地址 （即轉(zhuǎn)進過程T） B2的內(nèi)容將作為“全局display地址” （第三項連接數(shù)據(jù)）傳送給T,9.6堆式動態(tài)存儲分配,1、堆式動態(tài)存儲分配使用的情況 （1）允許用戶自由地申請數(shù)據(jù)空間和退還空間 （2）不僅有過程而且有進程的程序結(jié)構(gòu) 即空間的使用未必服從“先請后還，后請先還”的原則 例如：pascal語言中的標(biāo)準過程new-dispose 2、該種分配方法必須考慮的幾個主要問題 （1）當(dāng)運行程序要求一塊體積為N的空間時，我的應(yīng)該分 配那一塊給它？ （2）如果運行程序要求一塊體積為N的空間，但所有空閑 塊的總和也不夠N，那該怎么辦？,9.6堆式動態(tài)存儲分配,一、堆式動態(tài)存儲分配的實現(xiàn) 1、定長塊管理 （1）實現(xiàn)方法： （2）優(yōu)點： 2、變長塊管理 （1）實現(xiàn)方法 （2）實現(xiàn)的分配策略 首次滿足法 最優(yōu)滿足法 最差滿足法 （3）3種分配策略的比較 適用情況 時間比較,9.6堆