第九章運(yùn)行時(shí)空間組織

第九章運(yùn)行時(shí)空間組織第一頁，共三十一頁，2022年，8月28日程序單元 FORTRAN的子例程(subroutine) PASCAL的過程/函數(shù)(procedure/function) C的函數(shù)程序單元的激活（調(diào)用）與終止（返回）第二頁，共三十一頁，2022年，8月28日過程與活動(dòng)過程的每一次運(yùn)行(或執(zhí)行)被稱為一次活動(dòng)(activation)。活動(dòng)是一個(gè)動(dòng)態(tài)的概念，除了設(shè)計(jì)為永不停機(jī)的過程(如操作系統(tǒng)等)，或者是因設(shè)計(jì)錯(cuò)誤而出現(xiàn)死循環(huán)的過程之外，任何過程的活動(dòng)均有有限的生存期(lifetime)。程序單元的執(zhí)行需要： 代碼段＋活動(dòng)記錄（程序單元運(yùn)行所需的額外信息，如參數(shù)，局部數(shù)據(jù)，返回地址等）第三頁，共三十一頁，2022年，8月28日運(yùn)行時(shí)內(nèi)存劃分代碼段靜態(tài)數(shù)據(jù)區(qū)棧（stack）

堆（heap）

大小可以靜態(tài)確定全局/局部靜態(tài)變量活動(dòng)記錄棧動(dòng)態(tài)分配的數(shù)據(jù)第四頁，共三十一頁，2022年，8月28日活動(dòng)記錄

為了管理過程在一次執(zhí)行中所需要的信息，使用一個(gè)連續(xù)的存儲(chǔ)塊，這個(gè)連續(xù)的存儲(chǔ)塊稱為活動(dòng)記錄（Activationrecord）第五頁，共三十一頁，2022年，8月28日活動(dòng)記錄的結(jié)構(gòu)及內(nèi)容指針SP指向現(xiàn)行過程的活動(dòng)記錄在棧里的起始位置。TOP：活動(dòng)記錄的棧頂臨時(shí)單元內(nèi)情向量局部變量形式單元靜態(tài)鏈動(dòng)態(tài)鏈返回地址TOPSP編譯將數(shù)組的有關(guān)信息記錄在一些單元中，稱為數(shù)組的“內(nèi)情向量”。形式單元：存放相應(yīng)的實(shí)在參數(shù)的地址或值。動(dòng)態(tài)鏈：指向調(diào)用該過程前的最新活動(dòng)記錄地址的指針。運(yùn)行時(shí)，使運(yùn)行棧上各數(shù)據(jù)區(qū)按動(dòng)態(tài)建立的次序結(jié)成鏈。鏈頭為棧頂起始位置。靜態(tài)鏈：指向靜態(tài)直接外層最新活動(dòng)記錄地址的指針，用來訪問非局部變量。第六頁，共三十一頁，2022年，8月28日常見的存儲(chǔ)分配策略靜態(tài)分配策略動(dòng)態(tài)分配策略棧式動(dòng)態(tài)分配策略堆式動(dòng)態(tài)分配策略第七頁，共三十一頁，2022年，8月28日存儲(chǔ)分配策略靜態(tài)分配策略：如FORTRAN不允許過程遞歸不含可變體積的數(shù)據(jù)對象，或待定性質(zhì)的名稱因此編譯時(shí)能完全確定每個(gè)數(shù)據(jù)項(xiàng)存儲(chǔ)空間的位置情況動(dòng)態(tài)分配策略:如PASCAL,C允許過程遞歸允許動(dòng)態(tài)申請和釋放存儲(chǔ)空間因此，編譯時(shí)不能完全確定數(shù)據(jù)項(xiàng)的性質(zhì)，大小等，如,允許遞歸過程和可變數(shù)組，名字作用域和生存期滿足分程序結(jié)構(gòu)所限定的作用范圍.第八頁，共三十一頁，2022年，8月28日動(dòng)態(tài)分配策略棧式動(dòng)態(tài)分配策略內(nèi)存先申請先釋放堆式動(dòng)態(tài)分配策略內(nèi)存申請和釋放不遵循先請后放時(shí)，一般的處理方法是：讓運(yùn)行程序持有一個(gè)大存區(qū)（稱為堆），凡申請者從堆中分給一塊，凡釋放者歸還給堆第九頁，共三十一頁，2022年，8月28日動(dòng)態(tài)存儲(chǔ)分配---簡單棧式要求:1,沒有分程序結(jié)構(gòu);2,過程定義不允許嵌套;3,允許過程遞規(guī)調(diào)用;第十頁，共三十一頁，2022年，8月28日C程序結(jié)構(gòu)全局?jǐn)?shù)據(jù)說明main(?){main中的數(shù)據(jù)說明}voidR(?){R中的數(shù)據(jù)說明}voidQ(){Q中的數(shù)據(jù)說明}第十一頁，共三十一頁，2022年，8月28日C語言程序的存儲(chǔ)組織第十二頁，共三十一頁，2022年，8月28日C的活動(dòng)記錄連接數(shù)據(jù)(兩項(xiàng))：老SP值(即前一活動(dòng)記錄的起始地址)返回地址；(2)參數(shù)個(gè)數(shù)；(3)形式單元(存放實(shí)在參數(shù)的值或地址)；(4)過程的局部變量(簡單變量)、數(shù)組的內(nèi)情向量和臨臨時(shí)工作單元。第十三頁，共三十一頁，2022年，8月28日C的活動(dòng)記錄臨時(shí)工作單元內(nèi)情向量簡單變量形式單元參數(shù)個(gè)數(shù)返回地址老SP210TOPSP第十四頁，共三十一頁，2022年，8月28日堆式動(dòng)態(tài)存儲(chǔ)分配堆變量堆空間的管理策略減少碎片的技術(shù)空間的釋放第十五頁，共三十一頁，2022年，8月28日需求：

一個(gè)程序語言允許用戶自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間，或者不僅有過程而且有進(jìn)程（process）的程序結(jié)構(gòu)。操作：堆提供兩個(gè)操作，分配操作和釋放操作情況:

經(jīng)一段運(yùn)行時(shí)間之后，這個(gè)大空間就必定被分劃成許多塊塊，有些占用，有些無用（空閑）--碎片問題第十六頁，共三十一頁，2022年，8月28日堆式動(dòng)態(tài)儲(chǔ)分配

當(dāng)運(yùn)行程序要求一塊體積為N的空間時(shí)，我們應(yīng)該分配哪一塊給它呢？運(yùn)行程序要求一塊體積為N的空間，但發(fā)現(xiàn)沒有比N大的空閑塊了，然而所有空閑塊的總和卻要比N大得多。如果運(yùn)行程序要求一塊積為N的空間，但所有空閑塊的總和也不夠N，那又應(yīng)怎么辦呢？

有的管理系統(tǒng)采用一種叫做垃圾回收的辦法來對付這種局面。即尋找那些運(yùn)行程序己無用但尚未釋放的占用塊。第十七頁，共三十一頁，2022年，8月28日堆管理堆空間的管理策略減少碎片的技術(shù)空間的釋放第十八頁，共三十一頁，2022年，8月28日堆空間的管理策略1定長塊管理2變長塊管理第十九頁，共三十一頁，2022年，8月28日1定長塊管理堆式動(dòng)態(tài)儲(chǔ)分配最簡單的實(shí)現(xiàn)是按定長塊進(jìn)行。初始化時(shí)，將堆存儲(chǔ)空間分成長度相等的若干塊，每塊中指定一個(gè)鏈域，按照鄰塊的順序把所有塊鏈成一個(gè)鏈表，用指針available指向鏈表中的第一塊。分配時(shí)每次都分配指針available所指的塊，然后available指向相鄰的下一塊。歸還時(shí)，把所歸還的塊插入鏈表?？紤]插入方便，可以把所歸還的塊插在available所指的塊之前，然后available指向新歸還的塊。第二十頁，共三十一頁，2022年，8月28日2變長塊管理除了按定長塊進(jìn)行分配之外，還可以根據(jù)需要分配長度不同的存儲(chǔ)塊，可以隨要求而變。按這種方法，初始化時(shí)存儲(chǔ)空間是一個(gè)整塊。按照用戶的需要，分配時(shí)先是從一個(gè)整塊里分割出滿足需要的一小塊，以后，歸還時(shí)，如果新歸還的塊和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。再進(jìn)行分配時(shí)，從空閑塊鏈表中找出滿足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出去。若空閑塊表中有若干個(gè)滿足需要的空閑塊時(shí)，該分配哪一塊呢？通常有三種不同的分配策略

第二十一頁，共三十一頁，2022年，8月28日不同的情況應(yīng)采用不同的方法。通常在選擇時(shí)需考慮下列因素：用戶的要求；請求分配量的大小分布；分配和釋放的頻率以及效率對系統(tǒng)的重要等等。（1）首次滿足法：只要在空閑塊鏈表中找到滿足需要的一塊，就進(jìn)行分配。（2）最優(yōu)滿足法：將空閑塊鏈表中一個(gè)不小于申請塊且最接近于申請塊的空閑塊分配給用戶，則系統(tǒng)在分配前首先要對空閑塊鏈表從頭至尾描一遍，然后從中找出一塊，為避免每次分配都要掃描整個(gè)鏈表，通常將空閑塊鏈表空間的大小從小到大排序。（3）最差滿足法：將空閑塊表中不小于申請塊且是最大的空閑的一部全分配給用戶。此時(shí)的空閑塊鏈表按空閑的塊的大小從大到小排序。只需從鏈表中刪除第一個(gè)結(jié)點(diǎn)，并將其中一部分分配給用戶，而其它部分作為一個(gè)新的結(jié)點(diǎn)插入到空閑塊表的適當(dāng)置上去。第二十二頁，共三十一頁，2022年，8月28日減少碎片的技術(shù)1分配時(shí)，找最小的足夠大的塊---需保持空閑塊的大小排序2釋放時(shí)，合并任何相鄰的塊---搜索全部空閑塊表，或其它算法3將堆變量緊縮在一起第二十三頁，共三十一頁，2022年，8月28日空間的釋放1顯式釋放2隱式（自動(dòng)）釋放第二十四頁，共三十一頁，2022年，8月28日顯式釋放程序設(shè)計(jì)語言提供機(jī)制如：pascal：disposeC：free程序員必須編寫分配和釋放存儲(chǔ)的明確的調(diào)用。第二十五頁，共三十一頁，2022年，8月28日堆式分配和釋放的C語言描述#defineNULL0#defineMEMSIZE8096/*changefordifferentsizes*/typedeffdoubleAlign;typedefunionheader{struct{unionheader*next;unsignedusedsize;unsignedfreesize;}s;Aligna;}Header;//數(shù)據(jù)類型Header保存每個(gè)存儲(chǔ)塊的簿記信息staticHeadermem[MEMSIZE];staticHeader*memptr=NULL;void*malloc(unsignednbytes){Header*p,*newp;unsignednunits;nunits=(nbytes+sizeof(Header)-1/sizeof(Header)+1;if(memptr==NULL)第二十六頁，共三十一頁，2022年，8月28日{(diào)memptr->s.next=memptr=mem;memptr->s.usedsize=1;memptr->s.freesize=MEMSIZE-1;}for(p=memptr;(p->s.next!=memptr)&&(p->s.freesize<nunits);p=p->s.next);if(p->s.freesize<>nunits)returnNULL;/*noblockbigenough*/newp=p+p->s.usedsize;newp->s.usedsize=nunits;newp->s.freesize=p->s.freesize-nunits;第二十七頁，共三十一頁，2022年，8月28日newp->s.next=p->s.next;p->s.freesize=0;p->s.next=newp;memptr=newp;return(void*)(newp+1);}voidfree(void*ap){Header*bp,*p,*prev;bp=(Header*)ap–1;for(prev=memptr,p=memptr->s.next;(p!=bp)&&(p!=memptr);prev=p,p=p->s.next);if(p!=bp)return;/*corruptedlist,donothing*/prev->s.freesize+=p->s.usedsize+p->s.freesize;prev->s.next=p->s.next;memptr=prev;}第二十八頁，共三十一頁，2022年，8月28日堆的自動(dòng)管理-----隱式存儲(chǔ)回收在一種需要完全動(dòng)態(tài)的運(yùn)行時(shí)環(huán)境的語言（OO語言，函數(shù)式語言Lisp,ML)中，堆也必須類似地自動(dòng)管理。自動(dòng)存儲(chǔ)器管理涉及到了前面分配的但不再使用的存儲(chǔ)器的回收，可能是在它被分配的很久以后，而沒有明確的對free的調(diào)用。這個(gè)過程稱作垃圾回收（grabagecollection）。第二十九頁，共三十一頁，2022年，8月28日垃圾回收

垃圾回收程序---尋找可被引用的所有存儲(chǔ)器并釋所有未引用的存儲(chǔ)器。在存儲(chǔ)塊不再引