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

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

2、wap(n,m:real); var j:real; begin j:=n; n:=m; m:=j; end;,若存在調用：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;,若存在調用：swap(i,k(i) (4) 得結果 swap(m,n) addr(i), i addr(k(i),K(i),9.2運行時存儲器的劃分,一、運行時存儲器的劃分 1、編譯器需要在存儲區(qū)保護的對象 （1）目標代碼

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

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

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

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

7、器SP總是指向現(xiàn)行過程活動記錄的 起點，用于訪問局部數(shù)據 指示器TOP始終指向（已占用）棧頂單元,9.4簡單的棧式存儲分配,一、C的活動記錄 1、C的活動記錄的項目 （1）連接數(shù)據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)鏈活動記錄的一個域，從一個過程的當前活 動記錄指向其靜態(tài)直接外層的最新活動記錄。 動態(tài)鏈活動記錄一個域，從一個過程的當前活動 記錄指向調用該過程前正在運行的過程的最新 的活動記錄的基地址。 B、活動記錄結構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中調用S時,過程S中調用Q時,過程Q中調用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中遞歸調用R,9.5嵌套過程語言的棧式實現(xiàn),D、含義： 靜態(tài)鏈：通過其值可以找到當前過程/活動可以引用的“非局部變量”的過程的活動記錄的基址，從而找到要引用的“非局部變量” 動態(tài)鏈：通過其值可以找到當前過程/活動結束后，需要返回的上一層活動記錄的基址SP,9.5嵌套過程語言的棧式實現(xiàn),2、嵌套層次顯示表（displa

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

12、P2 的兩種不同嵌套：,P1,P2,k-1,k,Display K項,P1,P2,P1的display k項,p2的sp,top,sp,top,sp,p1 調用 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的內情向量地址 2、Par TT為過程 假設：過程P把過程T作為實在參數(shù)傳遞過程Q，隨 后，Q又通過引用相應的形式參數(shù)調用T。 3、Par T 為標號,在進入T之后，為了建立T自己的display ，T必須知道它直接外層的display。 又P的display或者正好就是這個外層的display， 或者包含了這個外層display 而由于T的層數(shù)是已知的

14、只要知道P的display，T就可以用它來建立自己的display，即假定T的層數(shù)為1，則T的display乃是由P的display的前1個單元的內容和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í)行到調用語句call Z,m Z形式參數(shù)，形

15、式單元Z中已含有上述B1的地址 故B1的內容將用來作為轉子指令的目的地址 （即轉進過程T） B2的內容將作為“全局display地址” （第三項連接數(shù)據）傳送給T,9.6堆式動態(tài)存儲分配,1、堆式動態(tài)存儲分配使用的情況 （1）允許用戶自由地申請數(shù)據空間和退還空間 （2）不僅有過程而且有進程的程序結構 即空間的使用未必服從“先請后還，后請先還”的原則 例如：pascal語言中的標準過程new-dispose 2、該種分配方法必須考慮的幾個主要問題 （1）當運行程序要求一塊體積為N的空間時，我的應該分 配那一塊給它？ （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堆