第七章運(yùn)行時(shí)刻環(huán)境-計(jì)算機(jī)系主頁

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

2、時(shí)刻的情形全局變量動態(tài)分配棧式存儲：和過程的調(diào)用/返回同步進(jìn)行分配和回收，值的生命期和過程生命期相同堆存儲：數(shù)據(jù)對象比創(chuàng)建它的過程調(diào)用更長壽。手工進(jìn)行回收垃圾回收機(jī)制,棧式分配,內(nèi)容：活動樹活動記錄調(diào)用代碼序列棧中的變長數(shù)據(jù),活動樹,過程調(diào)用（過程活動）在時(shí)間上總是嵌套的：后調(diào)用的先返回因此用棧式分配來分配過程活動所需內(nèi)存空間。程序運(yùn)行的所有過程活動可以用樹表示每個(gè)結(jié)點(diǎn)對應(yīng)于一個(gè)過程活動根結(jié)點(diǎn)對應(yīng)于main

3、過程的活動過程p的某次活動對應(yīng)的結(jié)點(diǎn)的所有子結(jié)點(diǎn)：此次活動所調(diào)用的各個(gè)過程活動（從左向右，表示調(diào)用的先后順序）。,活動樹的例子（1）,程序：P277，圖7-2過程調(diào)用（返回）序列和活動樹的前序（后序）遍歷對應(yīng)假定當(dāng)前活動對應(yīng)結(jié)點(diǎn)N，那么所有尚未結(jié)束的活動對應(yīng)于N及其祖先結(jié)點(diǎn)。,活動記錄,過程調(diào)用和返回由控制棧進(jìn)行管理每個(gè)活躍的活動對應(yīng)于棧中的一個(gè)活動記錄活動記錄按照活動的開始時(shí)間，從棧底到棧頂排列,運(yùn)行時(shí)刻棧的例子,a[11]

4、為全局變量main沒有局部變量r有局部變量iq的局部變量i，和參數(shù)m,n。,調(diào)用代碼序列,調(diào)用代碼序列(calling sequence)為活動記錄分配空間，填寫記錄中的信息；返回代碼序列(return sequence)恢復(fù)機(jī)器狀態(tài)，使調(diào)用者繼續(xù)運(yùn)行。調(diào)用代碼序列會分割到調(diào)用者和被調(diào)用者中。根據(jù)源語言、目標(biāo)機(jī)器、操作系統(tǒng)的限制，可以有不同的分割方案把代碼盡可能放在被調(diào)用者中。,調(diào)用/返回代碼序列的要求,數(shù)據(jù)方面能夠把參

5、數(shù)正確地傳遞給被調(diào)用者能夠把返回值傳遞給調(diào)用者控制方面能夠正確轉(zhuǎn)到被調(diào)用過程的代碼開始位置能夠正確轉(zhuǎn)回調(diào)用者的調(diào)用位置（的下一條指令）調(diào)用代碼序列和活動記錄的布局相關(guān),活動記錄的布局原則,調(diào)用者和被調(diào)用者之間傳遞的值放在被調(diào)用者活動記錄的開始位置固定長度的項(xiàng)放在中間位置控制鏈、訪問鏈、機(jī)器狀態(tài)字段早期不知道大小的項(xiàng)在活動記錄尾部棧頂指針(top_sp)通常指向固定長度字段的末端,調(diào)用代碼序列的例子,Calling se

6、quence調(diào)用者計(jì)算實(shí)在參數(shù)的值將返回地址和原top_sp存放到被調(diào)用者的活動記錄中。調(diào)用者增加top_sp的值（越過了局部數(shù)據(jù)、臨時(shí)變量、被調(diào)用者的參數(shù)、機(jī)器狀態(tài)字段）被調(diào)用者保存寄存器值和其他狀態(tài)字段被調(diào)用者初始化局部數(shù)據(jù)、開始運(yùn)行。Return sequence被調(diào)用者將返回值放到和參數(shù)相鄰的位置恢復(fù)top_sp和寄存器，跳轉(zhuǎn)到返回地址。,調(diào)用者/被調(diào)用者的活動記錄,棧中的變長數(shù)據(jù),如果數(shù)據(jù)對象的生命期局限于過程活

7、動的生命期，就可以分配在運(yùn)行時(shí)刻棧中。變長數(shù)組也可以放在棧中top指向?qū)嶋H的棧頂top_sp用于尋找頂層記錄的定長字段,非局部數(shù)據(jù)的訪問（無嵌套過程）,沒有嵌套過程時(shí)的數(shù)據(jù)訪問C語言中，每個(gè)函數(shù)能夠訪問的變量函數(shù)的局部變量：相對地址已知，且存放在當(dāng)前活動記錄內(nèi)，top_sp指針加上相對地址即可訪問全局變量：在靜態(tài)區(qū)，地址在編譯時(shí)刻可知很容易將C語言的函數(shù)作為參數(shù)進(jìn)行傳遞參數(shù)中只需包括函數(shù)代碼的開始地址。在函數(shù)中訪問非局

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

9、}voidC(){B();} C(); B();},A的活動記錄,C的活動記錄,B的活動記錄,當(dāng)A調(diào)用C，C又調(diào)用B時(shí):,當(dāng)A直接調(diào)用B時(shí):,A的活動記錄,B的活動記錄,嵌套深度,嵌套深度是正文概念，可以根據(jù)源程序靜態(tài)地確定不內(nèi)嵌于任何其他過程中的過程，嵌套深度為1嵌套在深度為i的過程中的過程，深度為i+1.,深度為1sort深度為2readArray，exchange，quicksor

10、t深度為3partition,訪問鏈,訪問鏈被用于訪問非局部的數(shù)據(jù)如果過程p在聲明時(shí)嵌套在過程q的聲明中，那么p的活動記錄中的訪問鏈指向最上層的q的活動記錄。從棧頂活動記錄開始，訪問鏈形成了一個(gè)鏈路，嵌套深度沿著鏈路逐一遞減。設(shè)深度為np的過程p訪問變量x，而變量x在深度為nq的過程中聲明，那么np-nq在編譯時(shí)刻已知；從當(dāng)前活動記錄出發(fā)，沿訪問鏈前進(jìn)np-nq次找到的活動記錄中的x就是要找的變量位置x相對于這個(gè)活動記

11、錄的偏移量在編譯時(shí)刻已知,訪問鏈的維護(hù)（直接調(diào)用過程）,當(dāng)過程q調(diào)用過程p時(shí)，訪問鏈的變化p的深度大于q：根據(jù)作用域規(guī)則，p必然在q中直接定義；那么p的訪問鏈指向當(dāng)前活動記錄s調(diào)用q(1,9)遞歸調(diào)用：p=q。新活動記錄的訪問鏈等于當(dāng)前記錄的訪問鏈q(1,9)調(diào)用q(1,3)）p的深度小于等于q的深度：此時(shí)必然有過程r，p直接在r中定義，而q嵌套在r中；p的訪問鏈指向棧最高的r的活動記錄。p調(diào)用exchange,訪問鏈的例子

12、,訪問鏈的維護(hù)（過程指針型參數(shù)）,在傳遞過程指針參數(shù)時(shí)，過程型參數(shù)中不僅包含過程的代碼指針，還包括正確的訪問鏈。,顯示表,用訪問鏈訪問數(shù)據(jù)時(shí)，訪問開銷和嵌套深度差有關(guān)使用顯示表可以提高效率，訪問開銷為常量顯示表：數(shù)組d為每個(gè)嵌套深度保留一個(gè)指針指針d[i]指向棧中最高的、嵌套深度為i的活動記錄。如果程序p中訪問嵌套深度為i的過程q中聲明的變量x，那么d[i]直接指向相應(yīng)的（必然是q的）活動記錄注意：i在編譯時(shí)刻已知顯示表的維

13、護(hù)調(diào)用過程p時(shí)，在p的活動記錄中保存d[np]的值，并將d[np]設(shè)置為當(dāng)前活動記錄。從p返回時(shí)，恢復(fù)d[np]的值。,顯示表的例子,q(1,9)調(diào)用q(1,3)時(shí)，q的深度為2,q(1,3)調(diào)用p，p的深度為3,q調(diào)用e，e的深度為2,顯示表的用途,生成機(jī)器代碼時(shí)使用三地址代碼：x=y+z這里的x，y，z實(shí)際上是標(biāo)識符表項(xiàng)；假設(shè)x和y不是本地的局部數(shù)據(jù)，標(biāo)識符表保存了x和y的嵌套深度和偏移量使用顯示表時(shí)LDR1*(

14、D+ny)LDR2Offy[R1]ADDR2Offz[sp]LDR1*(D+Nx)STOffx[R1]R2,堆管理,堆空間用于存放生命周期不確定、或生存到被明確刪除為止的數(shù)據(jù)對象例如：new生成的對象可以生存到被delete為止。malloc申請的空間生存到被free為止。存儲管理器分配/回收堆區(qū)空間的子系統(tǒng)根據(jù)語言而定C、C++需要手動回收空間Java可以自動回收空間（垃圾收集）,存儲管理

15、器,基本功能分配：為每個(gè)內(nèi)存請求分配一段連續(xù)的、適當(dāng)大小的堆空間。首先從空閑的堆空間分配；如果不行則從操作系統(tǒng)中獲取內(nèi)存、增加堆空間?；厥眨喊驯换厥盏目臻g返回空閑空間緩沖池，以滿足其他內(nèi)存需求。評價(jià)存儲管理器的特性：空間效率：使程序需要的堆空間最小，即減小碎片程序效率：充分運(yùn)用內(nèi)存系統(tǒng)的層次，提高效率低開銷：使分配/收回內(nèi)存的操作盡可能高效,堆空間的碎片問題,隨著程序分配/回收內(nèi)存，堆區(qū)逐漸被割裂成為若干空閑存儲塊（窗口

16、，hole）和已用存儲塊的交錯(cuò)。分配一塊內(nèi)存時(shí)，通常是把一個(gè)窗口的一部分分配出去，其余部分成為更小的塊。回收時(shí)，被釋放的存儲塊被放回緩沖池。通常要把連續(xù)的窗口接合成為更大的窗口。,,,,,,,碎片,已分配空間,堆空間分配方法,Best-Fit總是將請求的內(nèi)存分配在滿足請求的最小的窗口中。好處：可以將大的窗口保留下來，應(yīng)對更大的請求。First-Fit總是將對象放置在第一個(gè)能夠容納請求的窗口中。放置對象時(shí)花費(fèi)時(shí)間較少，但是總

17、體性能較差。但是first-fit的分配方法通常具有較好的數(shù)據(jù)局部性。同一時(shí)間段內(nèi)的生成的對象經(jīng)常被分配在連續(xù)的空間內(nèi)。,使用容器的堆管理方法,設(shè)定不同大小的空閑塊規(guī)格，相同規(guī)格的塊放在同一容器中。較小的（較常用的）尺寸設(shè)置較多的容器。比如GNU的C編譯器將所有存儲塊對齊到8字節(jié)邊界?？臻e塊的尺寸大小：16,24,32,40,…,512大于512的按照對數(shù)劃分：每個(gè)容器的最小尺寸是前一個(gè)容器的最小尺寸的兩倍?；囊皦K：可以

18、擴(kuò)展的內(nèi)存塊分配方法：對于小尺寸的請求，直接在相應(yīng)容器中找。大尺寸的請求，在適當(dāng)?shù)娜萜髦袑ふ疫m當(dāng)?shù)目臻e塊。可能需要分割內(nèi)存塊?？赡苄枰獜幕囊皦K中分割出更多的塊。,管理和接合空閑空間,當(dāng)回收一個(gè)塊時(shí)，可以把這個(gè)塊和相鄰的塊接合起來，構(gòu)成更大的塊。有些管理方法，比如說Lea，不需要進(jìn)行接合支持相鄰塊接合的數(shù)據(jù)結(jié)構(gòu)邊界標(biāo)記：在每一塊存儲塊的兩端，分別設(shè)置一個(gè)free/used位；相鄰的位置上存放字節(jié)總數(shù)。雙重鏈接的、嵌入式的

19、空閑塊列表：列表的指針存放在空閑塊中、用雙向指針的方式記錄了有哪些空閑塊。,例子,相鄰的存儲塊A、B、C當(dāng)回收B時(shí)，通過對free/used位的查詢，可以知道B左邊的A是空閑的，而C不空閑。同時(shí)還可以知道A、B合并為長度為300的塊。修改雙重鏈表，把A替換為A、B接合后的空閑塊注意：雙重鏈表中一個(gè)結(jié)點(diǎn)的前驅(qū)并不一定是它鄰近的塊,處理手工存儲管理,兩大問題：內(nèi)存泄露：未能刪除不可能再被引用的數(shù)據(jù)懸空指針引用：引用已被刪除的數(shù)據(jù)

20、其他問題空指針訪問/數(shù)組越界訪問解決方法：自動存儲管理正確的編程模式,正確的編程模式（1）,對象所有者（Object ownership）每個(gè)對象總是有且只有一個(gè)所有者（指向此對象的指針）；只有通過Owner才能夠刪除這個(gè)對象；當(dāng)Owner消亡時(shí)，這個(gè)對象要么也被刪除，要么已經(jīng)被傳遞給另一個(gè)owner。語句v=new ClassA；創(chuàng)建的對象的所有者為v；即將對v進(jìn)行賦值的時(shí)刻（v的值即將消亡）要么v已經(jīng)不是它所指對

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

22、然可能引起內(nèi)存泄漏；需要較大的運(yùn)行時(shí)刻開銷?；趨^(qū)域的分配將一些生命期相同的對象分配在同一個(gè)區(qū)域中；整個(gè)區(qū)域同時(shí)刪除。,垃圾回收,垃圾：狹義：不能被引用（不可達(dá)）的數(shù)據(jù)廣義：不需要再被引用的數(shù)據(jù)垃圾回收：自動回收不可達(dá)數(shù)據(jù)的機(jī)制，解除了程序員的負(fù)擔(dān)。使用的語言Java、Perl、ML、Modula-3、Prolog、Smalltalk,垃圾回收器的設(shè)計(jì)目標(biāo),基本要求：語言必須是類型安全的：保證回收器能夠知道數(shù)據(jù)元素是

23、否為一個(gè)指向某內(nèi)存塊的指針。類型不安全的語言：C，C++.性能目標(biāo)總體運(yùn)行時(shí)間：不顯著增加應(yīng)用程序的總運(yùn)行時(shí)間；空間使用：最大限度地利用可用內(nèi)存；停頓時(shí)間：當(dāng)垃圾回收機(jī)制啟動時(shí)，可能引起應(yīng)用程序的停頓。這個(gè)停頓應(yīng)該比較短；程序局部性：改善空間局部性和時(shí)間局部性。,可達(dá)性,直觀地講，可達(dá)性就是指一個(gè)存儲塊可以被程序訪問到。根集：不需要指針解引用就可以直接訪問的數(shù)據(jù)。Java：靜態(tài)成員、棧中變量；可達(dá)性根集的成員都是可達(dá)

24、的；對于任意一個(gè)對象，如果指向它的一個(gè)指針被保存在可達(dá)對象的某字段中、或數(shù)組元素中，那么這個(gè)對象也是可達(dá)的。性質(zhì)：一旦一個(gè)對象變得不可達(dá)，它就不會再變成可達(dá)的。,改變可達(dá)對象集合的操作,對象分配：返回一個(gè)指向新存儲塊的引用；參數(shù)傳遞/返回值：對象引用從實(shí)在參數(shù)傳遞到形式參數(shù)，從返回值傳遞給調(diào)用者；引用賦值：u=v；v的引用被復(fù)制到u中，u中原來的引用丟失?？赡苁沟胾原來指向的對象變得不可達(dá)，并且遞歸地使得更多對象變得不可達(dá)。

25、過程返回：活動記錄出棧，局部變量消失，根集變?。豢赡苁沟靡恍ο笞兊貌豢蛇_(dá)。,垃圾回收方法分類,跟蹤相關(guān)操作，捕獲對象變得不可達(dá)的時(shí)刻，回收對象占用的空間在需要時(shí)，標(biāo)記出所有可達(dá)對象、回收其它對象,基于引用計(jì)數(shù)的垃圾回收器,每個(gè)對象有一個(gè)用于存放引用計(jì)數(shù)的字段，并按照如下方式維護(hù)對象分配：引用計(jì)數(shù)設(shè)為1參數(shù)傳遞：引用計(jì)數(shù)加1引用賦值：u=v：u指向的對象引用減1、v指向的對象引用加1過程返回：局部變量指向?qū)ο蟮囊糜?jì)數(shù)減1如

26、果一個(gè)對象的引用計(jì)數(shù)為0，在刪除對象之前，此對象中各個(gè)指針?biāo)笇ο蟮囊糜?jì)數(shù)減1回收器有缺陷，可能引起內(nèi)存泄漏開銷較大、但是不會引起停頓,引用計(jì)數(shù)的例子,考慮如下操作:y=xy是當(dāng)前函數(shù)f的局部變量,且f返回修改計(jì)數(shù)后總是先考慮是否釋放；釋放一個(gè)對象之前總是先處理對象內(nèi)部的指針,循環(huán)垃圾的例子,基于跟蹤的垃圾回收,標(biāo)記-清掃式垃圾回收標(biāo)記-清掃式垃圾回收的優(yōu)化標(biāo)記并壓縮垃圾回收拷貝垃圾回收,標(biāo)記-清掃式垃圾回收,一種直

27、接的、全面停頓的算法分成兩個(gè)階段標(biāo)記：從根集開始，跟蹤并標(biāo)記出所有可達(dá)對象；清掃：遍歷整個(gè)堆區(qū)，釋放不可達(dá)對象；如果我們把數(shù)據(jù)對象看作頂點(diǎn)，引用看作有向邊，那么標(biāo)記的過程實(shí)際上是從根集開始的圖遍歷的過程。,標(biāo)記-清掃垃圾回收算法,例子,假設(shè)x是全局變量，y是當(dāng)前函數(shù)活動的局部變量；當(dāng)前活動返回之后，進(jìn)行標(biāo)記清掃A，D，E，F(xiàn)，I，G，HB，C不可達(dá),基本抽象分類,每個(gè)存儲塊處于四種狀態(tài)之一空閑未被訪問待掃描已掃描

28、對存儲塊的操作會改變存儲塊的狀態(tài)應(yīng)用程序分配垃圾回收器訪問、掃描收回,標(biāo)記-清掃垃圾回收算法的優(yōu)化,基本算法需要掃描整個(gè)堆；優(yōu)化：用一個(gè)列表記錄所有已經(jīng)分配的對象；不可達(dá)對象等于已分配對象減去可達(dá)對象好處只需要掃描這個(gè)列表就可以完成清掃壞處需要維護(hù)這個(gè)列表,優(yōu)化后的算法,使用了四個(gè)列表：Scanned, Unscanned, Unreached, Free;,壓縮并標(biāo)記垃圾回收,對可達(dá)對象進(jìn)行重定位可以消除存儲碎片；