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

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

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

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

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

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

6、quence調(diào)用者計(jì)算實(shí)在參數(shù)的值將返回地址和原top_sp存放到被調(diào)用者的活動(dòng)記錄中。調(diào)用者增加top_sp的值（越過(guò)了局部數(shù)據(jù)、臨時(shí)變量、被調(diào)用者的參數(shù)、機(jī)器狀態(tài)字段）被調(diào)用者保存寄存器值和其他狀態(tài)字段被調(diào)用者初始化局部數(shù)據(jù)、開(kāi)始運(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ì)象的生命期局限于過(guò)程活

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

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

9、}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)記錄,嵌套深度,嵌套深度是正文概念，可以根據(jù)源程序靜態(tài)地確定不內(nèi)嵌于任何其他過(guò)程中的過(guò)程，嵌套深度為1嵌套在深度為i的過(guò)程中的過(guò)程，深度為i+1.,深度為1sort深度為2readArray，exchange，quicksor

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

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

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

13、護(hù)調(diào)用過(guò)程p時(shí)，在p的活動(dòng)記錄中保存d[np]的值，并將d[np]設(shè)置為當(dāng)前活動(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)識(shí)符表項(xiàng)；假設(shè)x和y不是本地的局部數(shù)據(jù)，標(biāo)識(shí)符表保存了x和y的嵌套深度和偏移量使用顯示表時(shí)LDR1*(

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

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

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

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

18、擴(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è)塊和相鄰的塊接合起來(lái)，構(gòu)成更大的塊。有些管理方法，比如說(shuō)Lea，不需要進(jìn)行接合支持相鄰塊接合的數(shù)據(jù)結(jié)構(gòu)邊界標(biāo)記：在每一塊存儲(chǔ)塊的兩端，分別設(shè)置一個(gè)free/used位；相鄰的位置上存放字節(jié)總數(shù)。雙重鏈接的、嵌入式的

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

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

21、象的所有者；比如g=v可以把v的ownership傳遞給g要么需要在返回/賦值之前，執(zhí)行delete v操作；編程時(shí)需要了解各個(gè)指針在不同時(shí)刻是否owner。防止內(nèi)存泄漏，避免多次刪除對(duì)象。不能解決懸空指針問(wèn)題。,正確的編程模式（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ì)象；可以解決懸空指針問(wèn)題；但是在遞歸數(shù)據(jù)結(jié)構(gòu)中仍

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

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

24、的；對(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中原來(lái)的引用丟失?？赡苁沟胾原來(lái)指向的對(duì)象變得不可達(dá)，并且遞歸地使得更多對(duì)象變得不可達(dá)。

25、過(guò)程返回：活動(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過(guò)程返回：局部變量指向?qū)ο蟮囊糜?jì)數(shù)減1如

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

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

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