第七章運行時刻環(huán)境

1、第七章 運行時刻環(huán)境趙建華南京大學計算機系運行時刻環(huán)境 運行時刻環(huán)境 為數(shù)據(jù)分配安排存儲位置 確定訪問變量時使用的機制 過程之間的連接 參數(shù)傳遞 和操作系統(tǒng)、輸入輸出設備相關(guān)的其它接口 主題 存儲管理：棧分配、堆管理、垃圾回收 對變量、數(shù)據(jù)的訪問存儲分配的典型方式 目標程序的代碼放置在代碼區(qū) 靜態(tài)區(qū)、堆區(qū)、棧區(qū)分別放置不同類型生命期的數(shù)據(jù)值靜態(tài)和動態(tài)存儲分配 靜態(tài)分配 編譯器在編譯時刻就可以做出存儲分配決定，不需要考慮程序運行時刻的情形 全局變量 動態(tài)分配 棧式存儲：和過程的調(diào)用/返回同步進行分配和回收，值的生命期和過程生命期相同 堆存儲：數(shù)據(jù)對象比創(chuàng)建它的過程調(diào)用更長壽。 手工進行回收 垃圾

2、回收機制棧式分配 內(nèi)容： 活動樹 活動記錄 調(diào)用代碼序列 棧中的變長數(shù)據(jù)活動樹 過程調(diào)用（過程活動）在時間上總是嵌套的： 后調(diào)用的先返回 因此用棧式分配來分配過程活動所需內(nèi)存空間。 程序運行的所有過程活動可以用樹表示 每個結(jié)點對應于一個過程活動 根結(jié)點對應于main過程的活動 過程p的某次活動對應的結(jié)點的所有子結(jié)點：此次活動所調(diào)用的各個過程活動（從左向右，表示調(diào)用的先后順序）。活動樹的例子（1） 程序：P277，圖7-2 過程調(diào)用（返回）序列和活動樹的前序（后序）遍歷對應 假定當前活動對應結(jié)點N，那么所有尚未結(jié)束的活動對應于N及其祖先結(jié)點。活動記錄 過程調(diào)用和返回由控制棧進行管理 每個活躍的活

3、動對應于棧中的一個活動記錄 活動記錄按照活動的開始時間，從棧底到棧頂排列運行時刻棧的例子 a11為全局變量 main沒有局部變量 r有局部變量i q的局部變量i，和參數(shù)m,n。調(diào)用代碼序列 調(diào)用代碼序列(calling sequence)為活動記錄分配空間，填寫記錄中的信息； 返回代碼序列(return sequence)恢復機器狀態(tài)，使調(diào)用者繼續(xù)運行。 調(diào)用代碼序列會分割到調(diào)用者和被調(diào)用者中。 根據(jù)源語言、目標機器、操作系統(tǒng)的限制，可以有不同的分割方案 把代碼盡可能放在被調(diào)用者中。調(diào)用/返回代碼序列的要求 數(shù)據(jù)方面 能夠把參數(shù)正確地傳遞給被調(diào)用者 能夠把返回值傳遞給調(diào)用者 控制方面 能夠正確

4、轉(zhuǎn)到被調(diào)用過程的代碼開始位置 能夠正確轉(zhuǎn)回調(diào)用者的調(diào)用位置（的下一條指令） 調(diào)用代碼序列和活動記錄的布局相關(guān)活動記錄的布局原則 調(diào)用者和被調(diào)用者之間傳遞的值放在被調(diào)用者活動記錄的開始位置 固定長度的項放在中間位置 控制鏈、訪問鏈、機器狀態(tài)字段 早期不知道大小的項在活動記錄尾部 棧頂指針(top_sp)通常指向固定長度字段的末端調(diào)用代碼序列的例子 Calling sequence 調(diào)用者計算實在參數(shù)的值 將返回地址和原top_sp存放到被調(diào)用者的活動記錄中。調(diào)用者增加top_sp的值（越過了局部數(shù)據(jù)、臨時變量、被調(diào)用者的參數(shù)、機器狀態(tài)字段） 被調(diào)用者保存寄存器值和其他狀態(tài)字段 被調(diào)用者初始化局部

5、數(shù)據(jù)、開始運行。 Return sequence 被調(diào)用者將返回值放到和參數(shù)相鄰的位置 恢復top_sp和寄存器，跳轉(zhuǎn)到返回地址。調(diào)用者/被調(diào)用者的活動記錄棧中的變長數(shù)據(jù) 如果數(shù)據(jù)對象的生命期局限于過程活動的生命期，就可以分配在運行時刻棧中。 變長數(shù)組也可以放在棧中 top指向?qū)嶋H的棧頂 top_sp用于尋找頂層記錄的定長字段非局部數(shù)據(jù)的訪問（無嵌套過程） 沒有嵌套過程時的數(shù)據(jù)訪問 C語言中，每個函數(shù)能夠訪問的變量 函數(shù)的局部變量：相對地址已知，且存放在當前活動記錄內(nèi)，top_sp指針加上相對地址即可訪問 全局變量：在靜態(tài)區(qū)，地址在編譯時刻可知 很容易將C語言的函數(shù)作為參數(shù)進行傳遞 參數(shù)中只需

6、包括函數(shù)代碼的開始地址。 在函數(shù)中訪問非局部變量的模式很簡單，不需要考慮過程是如何激活的。非局部數(shù)據(jù)的訪問（嵌套聲明過程） PASCAL中，如果過程A的聲明中包含了過程B的聲明，那么B可以使用在A中聲明的變量。 當B的代碼運行時，如果它使用的是A中的變量。那么這個變量指向運行棧中最上層的同名變量。 但是，我們不能通過嵌套層次直接得到A的活動記錄的相對位置。必須通過訪問鏈訪問void A()intx,y;voidB()int b;x = b+y;voidC()B(); C(); B();A的活動記錄C的活動記錄B的活動記錄當A調(diào)用C，C又調(diào)用B時:當A直接調(diào)用B時:A的活動記錄B的活動記錄嵌套深

7、度 嵌套深度是正文概念，可以根據(jù)源程序靜態(tài)地確定 不內(nèi)嵌于任何其他過程中的過程，嵌套深度為1 嵌套在深度為i的過程中的過程，深度為i+1.深度為1sort深度為2readArray，exchange，quicksort深度為3partition訪問鏈 訪問鏈被用于訪問非局部的數(shù)據(jù) 如果過程p在聲明時嵌套在過程q的聲明中，那么p的活動記錄中的訪問鏈指向最上層的q的活動記錄。 從棧頂活動記錄開始，訪問鏈形成了一個鏈路，嵌套深度沿著鏈路逐一遞減。 設深度為np的過程p訪問變量x，而變量x在深度為nq的過程中聲明，那么 np-nq在編譯時刻已知； 從當前活動記錄出發(fā)，沿訪問鏈前進np-nq次找到的活動

8、記錄中的x就是要找的變量位置 x相對于這個活動記錄的偏移量在編譯時刻已知訪問鏈的維護（直接調(diào)用過程） 當過程q調(diào)用過程p時，訪問鏈的變化 p的深度大于q：根據(jù)作用域規(guī)則，p必然在q中直接定義；那么p的訪問鏈指向當前活動記錄 s調(diào)用q(1,9) 遞歸調(diào)用：p=q。新活動記錄的訪問鏈等于當前記錄的訪問鏈 q(1,9)調(diào)用q(1,3)） p的深度小于等于q的深度：此時必然有過程r，p直接在r中定義，而q嵌套在r中；p的訪問鏈指向棧最高的r的活動記錄。 p調(diào)用exchange訪問鏈的例子訪問鏈的維護（過程指針型參數(shù)） 在傳遞過程指針參數(shù)時，過程型參數(shù)中不僅包含過程的代碼指針，還包括正確的訪問鏈。顯示表

9、 用訪問鏈訪問數(shù)據(jù)時，訪問開銷和嵌套深度差有關(guān) 使用顯示表可以提高效率，訪問開銷為常量 顯示表：數(shù)組d為每個嵌套深度保留一個指針 指針di指向棧中最高的、嵌套深度為i的活動記錄。 如果程序p中訪問嵌套深度為i的過程q中聲明的變量x，那么di直接指向相應的（必然是q的）活動記錄 注意：i在編譯時刻已知 顯示表的維護 調(diào)用過程p時，在p的活動記錄中保存dnp的值，并將dnp設置為當前活動記錄。 從p返回時，恢復dnp的值。顯示表的例子q(1,9)調(diào)用q(1,3)時，q的深度為2q(1,3)調(diào)用p，p的深度為3q調(diào)用e，e的深度為2顯示表的用途 生成機器代碼時使用 三地址代碼：x=y+z 這里的x，

10、y，z實際上是標識符表項； 假設x和y不是本地的局部數(shù)據(jù)，標識符表保存了x和y的嵌套深度和偏移量 使用顯示表時 LDR1*(D+ny) LDR2OffyR1 ADDR2Offzsp LDR1*(D+Nx) STOffxR1R2堆管理 堆空間 用于存放生命周期不確定、或生存到被明確刪除為止的數(shù)據(jù)對象 例如：new生成的對象可以生存到被delete為止。malloc申請的空間生存到被free為止。 存儲管理器 分配/回收堆區(qū)空間的子系統(tǒng) 根據(jù)語言而定 C、C+需要手動回收空間 Java可以自動回收空間（垃圾收集）存儲管理器 基本功能 分配：為每個內(nèi)存請求分配一段連續(xù)的、適當大小的堆空間。 首先從空

11、閑的堆空間分配； 如果不行則從操作系統(tǒng)中獲取內(nèi)存、增加堆空間。 回收：把被回收的空間返回空閑空間緩沖池，以滿足其他內(nèi)存需求。 評價存儲管理器的特性： 空間效率：使程序需要的堆空間最小，即減小碎片 程序效率：充分運用內(nèi)存系統(tǒng)的層次，提高效率 低開銷：使分配/收回內(nèi)存的操作盡可能高效堆空間的碎片問題 隨著程序分配/回收內(nèi)存，堆區(qū)逐漸被割裂成為若干空閑存儲塊（窗口，hole）和已用存儲塊的交錯。 分配一塊內(nèi)存時，通常是把一個窗口的一部分分配出去，其余部分成為更小的塊。 回收時，被釋放的存儲塊被放回緩沖池。通常要把連續(xù)的窗口接合成為更大的窗口。碎片已分配空間堆空間分配方法 Best-Fit 總是將請求

12、的內(nèi)存分配在滿足請求的最小的窗口中。 好處：可以將大的窗口保留下來，應對更大的請求。 First-Fit 總是將對象放置在第一個能夠容納請求的窗口中。 放置對象時花費時間較少，但是總體性能較差。 但是first-fit的分配方法通常具有較好的數(shù)據(jù)局部性。 同一時間段內(nèi)的生成的對象經(jīng)常被分配在連續(xù)的空間內(nèi)。使用容器的堆管理方法 設定不同大小的空閑塊規(guī)格，相同規(guī)格的塊放在同一容器中。 較小的（較常用的）尺寸設置較多的容器。 比如GNU的C編譯器將所有存儲塊對齊到8字節(jié)邊界。 空閑塊的尺寸大小： 16,24,32,40,512 大于512的按照對數(shù)劃分：每個容器的最小尺寸是前一個容器的最小尺寸的兩倍

13、。 荒野塊：可以擴展的內(nèi)存塊 分配方法： 對于小尺寸的請求，直接在相應容器中找。 大尺寸的請求，在適當?shù)娜萜髦袑ふ疫m當?shù)目臻e塊。 可能需要分割內(nèi)存塊。 可能需要從荒野塊中分割出更多的塊。管理和接合空閑空間 當回收一個塊時，可以把這個塊和相鄰的塊接合起來，構(gòu)成更大的塊。 有些管理方法，比如說Lea，不需要進行接合 支持相鄰塊接合的數(shù)據(jù)結(jié)構(gòu) 邊界標記：在每一塊存儲塊的兩端，分別設置一個free/used位；相鄰的位置上存放字節(jié)總數(shù)。 雙重鏈接的、嵌入式的空閑塊列表：列表的指針存放在空閑塊中、用雙向指針的方式記錄了有哪些空閑塊。例子 相鄰的存儲塊A、B、C 當回收B時，通過對free/used位的查

14、詢，可以知道B左邊的A是空閑的，而C不空閑。 同時還可以知道A、B合并為長度為300的塊。 修改雙重鏈表，把A替換為A、B接合后的空閑塊 注意：雙重鏈表中一個結(jié)點的前驅(qū)并不一定是它鄰近的塊處理手工存儲管理 兩大問題： 內(nèi)存泄露：未能刪除不可能再被引用的數(shù)據(jù) 懸空指針引用：引用已被刪除的數(shù)據(jù) 其他問題 空指針訪問/數(shù)組越界訪問 解決方法： 自動存儲管理 正確的編程模式正確的編程模式（1） 對象所有者（Object ownership） 每個對象總是有且只有一個所有者（指向此對象的指針）；只有通過Owner才能夠刪除這個對象； 當Owner消亡時，這個對象要么也被刪除，要么已經(jīng)被傳遞給另一個own

15、er。 語句v=new ClassA；創(chuàng)建的對象的所有者為v； 即將對v進行賦值的時刻（v的值即將消亡） 要么v已經(jīng)不是它所指對象的所有者；比如g=v可以把v的ownership傳遞給g 要么需要在返回/賦值之前，執(zhí)行delete v操作； 編程時需要了解各個指針在不同時刻是否owner。 防止內(nèi)存泄漏，避免多次刪除對象。不能解決懸空指針問題。正確的編程模式（2） 引用計數(shù) 每個動態(tài)分配的對象附上一個計數(shù)：記錄有多少個指針指向這個對象； 在賦值/返回/參數(shù)傳遞時維護引用計數(shù)的一致性； 在計數(shù)變成0之時刪除這個對象； 可以解決懸空指針問題；但是在遞歸數(shù)據(jù)結(jié)構(gòu)中仍然可能引起內(nèi)存泄漏； 需要較大的運

16、行時刻開銷。 基于區(qū)域的分配 將一些生命期相同的對象分配在同一個區(qū)域中； 整個區(qū)域同時刪除。垃圾回收 垃圾： 狹義：不能被引用（不可達）的數(shù)據(jù) 廣義：不需要再被引用的數(shù)據(jù) 垃圾回收：自動回收不可達數(shù)據(jù)的機制，解除了程序員的負擔。 使用的語言 Java、Perl、ML、Modula-3、Prolog、Smalltalk垃圾回收器的設計目標 基本要求： 語言必須是類型安全的：保證回收器能夠知道數(shù)據(jù)元素是否為一個指向某內(nèi)存塊的指針。 類型不安全的語言：C，C+. 性能目標 總體運行時間：不顯著增加應用程序的總運行時間； 空間使用：最大限度地利用可用內(nèi)存； 停頓時間：當垃圾回收機制啟動時，可能引起應用

17、程序的停頓。這個停頓應該比較短； 程序局部性：改善空間局部性和時間局部性。可達性 直觀地講，可達性就是指一個存儲塊可以被程序訪問到。 根集：不需要指針解引用就可以直接訪問的數(shù)據(jù)。 Java：靜態(tài)成員、棧中變量； 可達性 根集的成員都是可達的； 對于任意一個對象，如果指向它的一個指針被保存在可達對象的某字段中、或數(shù)組元素中，那么這個對象也是可達的。 性質(zhì)： 一旦一個對象變得不可達，它就不會再變成可達的。改變可達對象集合的操作 對象分配：返回一個指向新存儲塊的引用； 參數(shù)傳遞/返回值：對象引用從實在參數(shù)傳遞到形式參數(shù)，從返回值傳遞給調(diào)用者； 引用賦值：u=v；v的引用被復制到u中，u中原來的引用丟

18、失。可能使得u原來指向的對象變得不可達，并且遞歸地使得更多對象變得不可達。 過程返回：活動記錄出棧，局部變量消失，根集變小；可能使得一些對象變得不可達。垃圾回收方法分類 跟蹤相關(guān)操作，捕獲對象變得不可達的時刻，回收對象占用的空間 在需要時，標記出所有可達對象、回收其它對象基于引用計數(shù)的垃圾回收器 每個對象有一個用于存放引用計數(shù)的字段，并按照如下方式維護 對象分配：引用計數(shù)設為1 參數(shù)傳遞：引用計數(shù)加1 引用賦值：u=v：u指向的對象引用減1、v指向的對象引用加1 過程返回：局部變量指向?qū)ο蟮囊糜嫈?shù)減1 如果一個對象的引用計數(shù)為0，在刪除對象之前，此對象中各個指針所指對象的引用計數(shù)減1 回收器有缺陷，可能引起內(nèi)存泄漏 開銷較大、但是不會引起停頓引用計數(shù)的例子 考慮如下操作: y=x y是當前函數(shù)f的局部變量,且f返回 修改計數(shù)后總是先考慮是否釋放； 釋放一個對象之前總是先處理對象內(nèi)部的指針循環(huán)垃圾的例子基于跟蹤的垃圾回收 標記-清掃式垃圾回收 標記-清掃式垃圾回收的優(yōu)化 標記并壓縮垃圾回收 拷貝垃圾回收標記-清掃式垃圾回收 一種直接的、全面停頓的算法 分成兩個階段 標記：從根集開始，跟蹤