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

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

3、動(dòng)對(duì)應(yīng)于棧中的一個(gè)活動(dòng)記錄 活動(dòng)記錄按照活動(dòng)的開始時(shí)間，從棧底到棧頂排列運(yùn)行時(shí)刻棧的例子 a11為全局變量 main沒有局部變量 r有局部變量i q的局部變量i，和參數(shù)m,n。調(diào)用代碼序列 調(diào)用代碼序列(calling sequence)為活動(dòng)記錄分配空間，填寫記錄中的信息； 返回代碼序列(return sequence)恢復(fù)機(jī)器狀態(tài)，使調(diào)用者繼續(xù)運(yùn)行。 調(diào)用代碼序列會(huì)分割到調(diào)用者和被調(diào)用者中。 根據(jù)源語言、目標(biā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)用代碼序列和活動(dòng)記錄的布局相關(guān)活動(dòng)記錄的布局原則 調(diào)用者和被調(diào)用者之間傳遞的值放在被調(diào)用者活動(dòng)記錄的開始位置 固定長(zhǎng)度的項(xiàng)放在中間位置 控制鏈、訪問鏈、機(jī)器狀態(tài)字段 早期不知道大小的項(xiàng)在活動(dòng)記錄尾部 棧頂指針(top_sp)通常指向固定長(zhǎng)度字段的末端調(diào)用代碼序列的例子 Calling sequence 調(diào)用者計(jì)算實(shí)在參數(shù)的值 將返回地址和原top_sp存放到被調(diào)用者的活動(dòng)記錄中。調(diào)用者增加top_sp的值（越過了局部數(shù)據(jù)、臨時(shí)變量、被調(diào)用者的參數(shù)、機(jī)器狀態(tài)字段） 被調(diào)用者保存寄存器值和其他狀態(tài)字段 被調(diào)用者初始化局部

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

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

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

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

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

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

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

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

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

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

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

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

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

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