1、 運行時存儲組織第八章運行時存儲組織 運行時存儲組織的作用與任務(wù) 存儲分配策略 程序運行時存儲空間的布局 活動記錄 過程調(diào)用與參數(shù)傳遞 面向?qū)ο蟪绦蜻\行時組織（選講）運行時存儲組織 運行時存儲組織的作用與任務(wù) 代碼生成前如何安排目標機存儲資源的使用 幾個重要問題 數(shù)據(jù)表示 目標機中如何表示源語言中各類數(shù)據(jù)對象 表達式計算 如何組織表達式的計算 存儲分配 如何為不同作用域或不同生命周期的數(shù)據(jù) 對象分配存儲 過程實現(xiàn) 如何實現(xiàn)過程/函數(shù)調(diào)用以及參數(shù)傳遞運行時存儲組織 數(shù)據(jù)表示 源程序中數(shù)據(jù)對象在內(nèi)存或寄存器中的表示形式 源程序中數(shù)據(jù)對象的屬性 名字（name），類型（type），值（value）,

2、 復合數(shù)據(jù)對象（component）， 數(shù)據(jù)對象在內(nèi)存或寄存器中的表示形式 位、字節(jié)、字、字節(jié)序列、 有些機器要求數(shù)據(jù)存放時要按某種方式對齊（align） 如：要求數(shù)據(jù)存放的起始地址為能夠被4整除運行時存儲組織 數(shù)據(jù)表示舉例 基本類型數(shù)據(jù) char 數(shù)據(jù) 1 byte integer 數(shù)據(jù) 4 bytes float 數(shù)據(jù) 8 bytes boolean 數(shù)據(jù) 1 byte 指針 4 bytes 數(shù)組 一塊連續(xù)的存儲區(qū)（按行/列存放） 結(jié)構(gòu)/記錄 所有域（field)存放在一塊連續(xù)的存儲區(qū) 對象 實例變量像結(jié)構(gòu)的域一樣存放在一塊連續(xù)的存儲 區(qū)，操作例程（方法、成員函數(shù)）存放在其所屬 類的代碼區(qū)

3、運行時存儲組織 表達式的計算 在何處進行計算 在棧區(qū)計算 運算數(shù)/中間結(jié)果存放于當前活動記錄或通用寄存器中 在運算數(shù)棧計算 某些目標機采用專門的運算數(shù)棧用于表達式計算 對于普通表達式（無函數(shù)調(diào)用），一般可以估算出能 否在運算數(shù)棧上進行 使用了遞歸函數(shù)的表達式的計算通常在棧區(qū)運行時存儲組織 程序運行時存儲空間的布局（layout） 典型的程序布局 保留地址區(qū) 目標機體系結(jié)構(gòu)專用 代碼區(qū) 靜態(tài)存放目標代碼 靜態(tài)數(shù)據(jù)區(qū) 靜態(tài)存放全局數(shù)據(jù) 庫和分別編譯模塊區(qū) 靜態(tài)存放這些模塊的代碼和全局數(shù)據(jù) 動態(tài)數(shù)據(jù)區(qū) 運行時動態(tài)變化的堆區(qū)和棧區(qū)Reserved LocationsCodeStatic DataLib

4、rary and Separate ModulesStack Space Heap SpaceLowest addressHighest address運行時存儲組織 存儲分配策略 靜態(tài)分配 在編譯期間為數(shù)據(jù)對象分配存儲 動態(tài)分配 棧式分配 將數(shù)據(jù)對象的運行時存儲按照棧的方式來管理 堆式分配 從數(shù)據(jù)段的堆空間分配和釋放數(shù)據(jù)對象的運行時存儲運行時存儲組織 靜態(tài)存儲分配 在編譯期間就可確定數(shù)據(jù)對象的大小 不宜處理遞歸過程或函數(shù) 某些語言中所有存儲都是靜態(tài)分配 如匯編語言，早期的FORTRAN語言 多數(shù)語言只有部分存儲進行靜態(tài)分配 可靜態(tài)分配的數(shù)據(jù)對象如大小固定且在程序執(zhí)行期間 可全程訪問的全局變量

5、，以及程序中的常量（literals） 如 C+ 中的 static 變量運行時存儲組織 棧式存儲分配 用于有效實現(xiàn)可動態(tài)嵌套的程序結(jié)構(gòu) 如實現(xiàn)過程/函數(shù)，塊層次結(jié)構(gòu) 可以實現(xiàn)遞歸過程/函數(shù) 比較：靜態(tài)分配不宜實現(xiàn)遞歸過程/函數(shù) 運行棧中的數(shù)據(jù)單元是活動記錄（activation record) （專門介紹）運行時存儲組織 堆式存儲分配 從堆空間為數(shù)據(jù)對象分配/釋放存儲 靈活 數(shù)據(jù)對象的存儲分配和釋放不限時間和次序 顯式的分配或釋放（explicit allocation / dealocation） 程序員負責應(yīng)用程序的（堆）存儲空間管理（借助于 編譯器和運行時系統(tǒng)所提供的默認存儲管理機制）

6、 隱式的分配或釋放（implicit allocation / dealocation） （堆）存儲空間的分配或釋放不需要程序員負責，由 編譯器和運行時系統(tǒng)自動完成運行時存儲組織 堆式存儲分配 某些語言有顯式的堆空間分配和釋放命令 如：Pascal 中的 new , deposit C+ 中的 new , delete 比較：C 語言沒有堆空間管理機制，malloc() 和 free() 是標準庫中的函數(shù)，可以由 library vendor 提供 某些語言支持隱式的堆空間釋放 采用垃圾回收（garbage collection）機制 如：Java 程序員不需要考慮對象的析構(gòu)運行時存儲組織 堆

7、式存儲分配 不釋放堆空間的方法 只分配空間，不釋放空間，空間耗盡時停止 適合于堆數(shù)據(jù)對象多數(shù)為一旦分配，永久使用的情形 在虛存很大及無用數(shù)據(jù)對象不致帶來很大零亂的情形 也可采用運行時存儲組織 堆式存儲分配 顯式釋放堆空間的方法 用戶負責清空無用的數(shù)據(jù)空間（通過執(zhí)行釋放命令） 堆管理程序只維護可供分配命令使用的空閑空間 問題：可能導致災(zāi)難性的 dangling pointer 錯誤 例：Pascal 代碼片斷 C+ 代碼片斷var p,q: real; new(p);q:=p;dispose(p);q:=1.0; float * p,*q; p=new float;q=p;delete p;*q

8、:=1.0;運行時存儲組織 堆式存儲分配 隱式釋放堆空間的方法 主要技術(shù)： 垃圾回收（garbage collection）機制 （可以分專門的話題討論，超出本課程范圍）運行時存儲組織 堆式存儲分配 堆空間的管理 分配算法 面對多個可用的存儲塊，選擇哪一個 如：最佳適應(yīng)算法（選擇浪費最少的存儲塊） 最先適應(yīng)算法（選擇最先找到的足夠大的存儲塊） 循環(huán)最先適應(yīng)算法（起始點不同的最先適應(yīng)算法） 碎片整理算法 壓縮合并小的存儲塊，使其更可用（ 可以分專門的話題討論，超出本課程范圍）（ 部分內(nèi)容可參考數(shù)據(jù)結(jié)構(gòu)和操作系統(tǒng)課程）運行時存儲組織 活動記錄（activation record） 過程活動記錄 函

9、數(shù)/過程調(diào)用或返回時，在運行棧上創(chuàng)建或從運行棧 上消去的棧幀（frame） 包含局部變量，函數(shù)實參，臨時值（用于表達式計算的 中間單元）等數(shù)據(jù)信息以及必要的控制信息控制信息數(shù)據(jù)信息 活動記錄起始地址（通常存于某專用寄存器中）某個數(shù)據(jù)對象的地址= 活動記錄起始地址 + 偏移地址（offset）運行時存儲組織 活動記錄 過程活動記錄的棧式分配舉例main 的活動記錄void p( ) q( ); void q( ) q( ); int main p( );p 的活動記錄q 的活動記錄q 的活動記錄函數(shù) q 被第二次激活時運行棧上活動記錄分配情況運行時存儲組織 活動記錄 典型的過程活動記錄結(jié)構(gòu)控制信

10、息過程實際參數(shù)固定大小的局部數(shù)據(jù)區(qū)動態(tài)數(shù)組區(qū)臨時工作單元SP （基址寄存器）TOP（棧頂寄存器）TOP（棧頂指針寄存器）運行時存儲組織 活動記錄 過程活動記錄舉例控制信息void p( int a) float b; float c10; b=ca; abc函數(shù) p 的活動記錄Offset = 0Offset = 3Offset = 4Offset = 6Offset = 26運行時存儲組織 活動記錄 過程活動記錄舉例控制信息static int N；void p( int a) float b; float c10; float dN; float e; abc函數(shù) p 的活動記錄Offse

11、t = 0Offset = 3Offset = 4Offset = 6Offset = 26/*d為動態(tài)數(shù)組*/指向 d 的指針內(nèi)情向量（N）edOffset = 27Offset = 28Offset = 30Offset = 30+2N運行時存儲組織 活動記錄 含嵌套過程說明語言的棧式分配 主要問題 解決對非局部量的引用（存?。?解決方案 采用 Display 表 為活動記錄增加靜態(tài)鏈域運行時存儲組織 活動記錄 嵌套過程語言的棧式分配 采用 Display 表 （或稱全局 Display 表） Display 表記錄各嵌套層當前過程的活動記錄在運行棧 上的起始位置（基地址） 當前激活過程的

12、層次為K（主程序的層次設(shè)為0）， 則對應(yīng)的 Display 表含有 K+1 個單元，依次存放著 現(xiàn)行層，直接外層直至最外層的每一過程的最新活 動記錄的基地址 嵌套作用域規(guī)則確保每一時刻Display 表內(nèi)容的唯一性 Display 表的大?。醋疃嗲短椎膶訑?shù)）取決于實現(xiàn)運行時存儲組織 活動記錄 嵌套過程語言的棧式分配 Display 表方案舉例program Main( I,O)；procedure P; procedure Q; procedure R; begin R; end; /*R*/ begin R; end; /*Q*/ begin Q; end; /*P*/procedure

13、S; begin P; end; /*S*/begin S; end. /*main*/main 的活動記錄P 的活動記錄Q 的活動記錄R 的活動記錄過程 R 被第一次激活后運行棧和Display 寄存器 Di 的情況S 的活動記錄TOPD0D1D2D3運行時存儲組織 活動記錄 嵌套過程語言的棧式分配 Display 表的維護（過程被調(diào)用和返回時的保存和恢復） 方法一 極端的方法是把整個 Display 表存入活動記錄 若過程為第 n 層，則需要保存 D0 Dn ） 一個過程（處于第 n 層）被調(diào)用時，從調(diào)用 過程的 Display 表中自下向上抄錄 n 個 SP 值，再加上本層的 SP 值方

14、法二 只在活動記錄保存一個的 Display 表項，在靜 態(tài)存儲區(qū)或?qū)Ｓ眉拇嫫髦芯S護全局 Display 表運行時存儲組織 活動記錄 嵌套過程語言的棧式分配 Display 表的維護舉例main 的活動記錄P 的活動記錄Q 的活動記錄Display 表活動記錄中保存完整的Display 表S 的活動記錄TOPD0D1D2D3R 的活動記錄program Main( I,O)；procedure P; procedure Q; procedure R; begin R; end; /*R*/ begin R; end; /*Q*/ begin Q; end; /*P*/procedure S;

15、begin P; end; /*S*/begin S; end. /*main*/運行時存儲組織 活動記錄 嵌套過程語言的棧式分配 Display 表的維護舉例program Main( I,O)；procedure P; procedure Q; procedure R; begin P; end; /*R*/ begin R; end; /*Q*/ begin Q; end; /*P*/procedure S; begin P; end; /*S*/begin S; end. /*main*/saved S _ _ P Q RD2 _ Q Q Q Q QD3 _ _ R R R R只保存一

16、個Display 表項D0 Main Main Main Main Main Maincalls P Q R P Q RD1 P P P P P P運行時存儲組織 活動記錄 嵌套過程語言的棧式分配 采用靜態(tài)鏈（static link） Display 表的方法要用到多個存儲單元或多個寄存器， 有時并不情愿這樣做，一種可選的方法是采用靜態(tài)鏈 所有活動記錄都增加一個靜態(tài)鏈（如在offset 為 0 處） 的域，指向定義該過程的直接外過程（或主程序）運 行時最新的活動記錄 在過程返回時當前 AR 要被撤銷，為回卷（unwind） 到調(diào)用過程的AR（恢復SP）需要用到動態(tài)鏈域運行時存儲組織 活動記錄

17、嵌套過程語言的棧式分配 采用靜態(tài)鏈的方法舉例main 的活動記錄P 的活動記錄Q 的活動記錄過程 R 被第一次激活后運行棧的情況S 的活動記錄TOPR 的活動記錄靜態(tài)鏈動態(tài)鏈program Main( I,O)；procedure P; procedure Q; procedure R; begin R; end; /*R*/ begin R; end; /*Q*/ begin Q; end; /*P*/procedure S; begin P; end; /*S*/begin S; end. /*main*/運行時存儲組織 活動記錄 嵌套程序塊的非局部量訪問 一些語言（如 C 語言）支持嵌套

18、的塊，在這些塊的內(nèi) 部也允許聲明局部變量，同樣要解決依嵌套層次規(guī)則進 行非局部量使用（訪問）的問題 方法一 將每個塊看作為內(nèi)嵌的無參過程，為它創(chuàng)建一 個新的活動記錄，稱為塊級活動記錄 該方法代價很高 方法二 由于每個塊中變量的相對位置在編譯時就能確 定下來，因此可以不創(chuàng)建塊級活動記錄，僅需 要過程級的活動記錄就可解決問題（見下例）運行時存儲組織 活動記錄 嵌套程序塊的非局部量訪問 采用過程級活動記錄的方法舉例int p（） int A; int B,C; int D,E,F; int G; /*here*/ 存放 A 的空間存放 D，E，F(xiàn) 的空間運行至/*here*/時p的活動記錄形如：曾存

19、放過 B,C 的空間TOP存放 G 的空間SP運行時存儲組織 過程調(diào)用與參數(shù)傳遞 活動記錄中與過程/函數(shù)調(diào)用相關(guān)的信息 典型的活動記錄形式舉例寄存器保存區(qū)過程實際參數(shù)固定大小的局部數(shù)據(jù)區(qū)動態(tài)數(shù)組區(qū)活動記錄起始點活動記錄的固定大小部分結(jié)束點調(diào)用程序返回地址其它控制信息返回值（僅適于函數(shù)）運行時存儲組織 過程調(diào)用與參數(shù)傳遞 最常見的參數(shù)傳遞方式 傳值 call-by-value 傳遞的是實際參數(shù)的右值（r-value） 傳地址 call-by-reference（-address, -location） 傳遞的是實際參數(shù)的左值（l-value） 注 表達式的左值代表存儲該表達式值的地址 表達式的右

20、值代表該表達式的值運行時存儲組織 過程調(diào)用與參數(shù)傳遞 參數(shù)傳遞方式 call-by-value 舉例 調(diào)用s) 過程將不 會影響a和b的值，其結(jié)果 等價于執(zhí)行下列語句序列：x :=a；y :=b；temp :=x；x :=y；y :=tempprocedure s); var temp:integer; begin temp:=x; x:=y； y:=temp end；運行時存儲組織 過程調(diào)用與參數(shù)傳遞 參數(shù)傳遞方式 實現(xiàn) call-by-value 形式參數(shù)當作過程的局部變量處理，即在被調(diào)過程 的活動記錄中開辟了形參的存儲空間，這些存儲位 置用以存放實參 調(diào)用過程計算實參的值，將其放于對應(yīng)的

21、存儲空間 被調(diào)用過程執(zhí)行時，就像使用局部變量一樣使用這 些形式單元運行時存儲組織 過程調(diào)用與參數(shù)傳遞 參數(shù)傳遞方式 call-by-reference 舉例 調(diào)用s) 過程將交 換 a 和 b 的值procedure s x,y:integer); var temp:integer; begin temp:=x; x:=y； y:=temp end；運行時存儲組織 過程調(diào)用與參數(shù)傳遞 參數(shù)傳遞方式 實現(xiàn) call-by-reference 把實在參數(shù)的地址傳遞給相應(yīng)的形參，即調(diào)用過程把一個指向 實參的存儲地址的指針傳遞給被調(diào)用過程相應(yīng)的形參： 若實在參數(shù)是一個名字，或具有左值的表達式，則傳遞左

22、值 若實在參數(shù)是無左值的表達式，則計算該表達式的值，放入一 存儲單元，傳此存儲單元地址面向?qū)ο蟪绦蜻\行時組織 理解“類”和“對象”的角色 類扮演的角色是程序的靜態(tài)定義 對象扮演的角色是程序運行時的動態(tài)結(jié)構(gòu) 類是一組運行時對象的共同性質(zhì)的靜態(tài)描述 類的特征（feature）成員: 屬性（attribute）和 例程（routine） 每個對象都必定是某個類的一個實例（instance）， 而一個類可以創(chuàng)建有許多個對象 實例對象是在程序運行時，根據(jù)該對象所屬類的屬性 動態(tài)地構(gòu)造的 面向?qū)ο蟪绦蜻\行時的特征 對象是類的一個實例，是系統(tǒng)動態(tài)運行時一個物理 結(jié)構(gòu)的模塊，是按需要創(chuàng)建、而不是預(yù)先分配的 對

23、象是在類實例化過程中，由類的屬性定義所確定 的一組域動態(tài)地組成，每個域?qū)?yīng)類中的一個屬性 執(zhí)行一個面向?qū)ο蟪绦蚓褪莿?chuàng)建系統(tǒng)根類的一個實 例，并調(diào)用該實例的創(chuàng)建過程 創(chuàng)建對象的過程即為實現(xiàn)該對象初始化，對于根類而 言，創(chuàng)建其對象即執(zhí)行該系統(tǒng) 創(chuàng)建根對象相當于通常軟件啟動 main，在非純面向 對象方式下，通常也用啟動 main的方式創(chuàng)建根對象面向?qū)ο蟪绦蜻\行時組織 創(chuàng)建根對象時的存儲結(jié)構(gòu)堆式存儲區(qū)棧式存儲區(qū)根對象的函數(shù)工作區(qū)中主要是運行該程序的啟動參數(shù)，它們大都是根對象的成員。因而，根對象的函數(shù)工作區(qū)中主要存放對根對象的引用。創(chuàng)建的根對象存放在堆式存儲區(qū)中。引用根對象根對象構(gòu)造例程的工作區(qū)根對象

24、面向?qū)ο蟪绦蜻\行時組織 面向?qū)ο蟪绦蜻\行時的特征 例程運行時的特征 每個例程都必定是某個類的成員，且每個例程都只能 把它的計算施加在它所屬類所創(chuàng)建的對象上。因而在 一個例程執(zhí)行前，首先要求它所施加計算的對象已經(jīng) 存在，否則要求先創(chuàng)建該對象。 一個例程執(zhí)行時，其參數(shù)除實參外，還用到它所施加 計算的對象，它們與該例程的局部量及返回值一起組 成一個該例程的工作區(qū)（放在棧式存儲區(qū)中）。 例程工作區(qū)中的局部量若是較為復雜數(shù)據(jù)結(jié)構(gòu)，則在 工作區(qū)中存放對該復雜數(shù)據(jù)結(jié)構(gòu)的一個引用，并在堆 式存儲區(qū)中創(chuàng)建一個該復雜數(shù)據(jù)結(jié)構(gòu)的對象。面向?qū)ο蟪绦蜻\行時組織 面向?qū)ο蟪绦蜻\行時的特征 對象的存儲組織 一個簡單機制是，

25、初始化代碼將所有當前的繼承特 征（屬性和例程）直接地復制到對象存儲區(qū)中（將 例程當作代碼指針）。 但這樣做較浪費空間。面向?qū)ο蟪绦蜻\行時組織 另一種方法是在執(zhí)行時將類結(jié)構(gòu)的一個完整的描述保 存在每個類的存儲中，由超類指針維護繼承性（形成 所謂的繼承圖）。每個對象保存一個指向其定義類的 指針，作為一個附加的域和它的屬性變量放在一起， 通過這個類就可找到所有（局部和繼承的）的例程。 此時，只記錄一次例程指針（在類結(jié)構(gòu)中），且對于 每個對象并不將其復制到存儲器中。 其缺點在于：雖然屬性變量具有可預(yù)測的偏移量（如 在標準環(huán)境中的局部變量一樣），但例程卻沒有， 它 們必須由帶有查詢功能的符號表結(jié)構(gòu)中的名

26、字來維護。 這是對于諸如 Smalltalk 等強動態(tài)性語言的合理的結(jié)構(gòu)， 因為類結(jié)構(gòu)可以在執(zhí)行中改變。面向?qū)ο蟪绦蜻\行時組織 對象的存儲組織 一種折衷方案：計算出每個類的可用例程的代碼指針列 表（稱為例程索引表，如 C+ 的 Vtable，簡稱虛表）。 其優(yōu)點在于：可做出安排以使每個例程都有一個可預(yù)測 的偏移量，而且也不再需要用一系列表查詢遍歷類的層 次結(jié)構(gòu)。這樣，每個對象不僅包括屬性變量，還包括了 一個相應(yīng)的例程索引表的指針（不是類結(jié)構(gòu)的指針）。面向?qū)ο蟪绦蜻\行時組織 對象的存儲組織 某個單繼承O-O語言的對象存儲示例 class A int x; void f () class B ex

27、tends A void g() class C entends B void g() class D extends Cbool y; void f () class A a; class B b; class C c; class D d1,d2;xxy對象c對象d1對象d2xyx對象bx對象aA_f類AB_gA_f類BC_gA_f類CC_gD_f類D例程索引表this面向?qū)ο蟪绦蜻\行時組織 某個單繼承O-O語言的對象存儲示例string day;class Fruit int price; string name; void init(int p,string s)price=p; name=s; void print() Print(On ,day, the price of ,name, is ,price,n);class Apple extends Fruit string color; void setcolor(string c)color=c; void print() Print(On ,day, the price of ,color, ,name, is , price,n); void foo() c