第九章運行時空間組織

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

堆（heap）

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

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

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

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

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

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

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

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