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

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

堆（heap）

大小可以靜態(tài)確定全局/局部靜態(tài)變量活動記錄棧動態(tài)分配的數(shù)據(jù)第4頁，共31頁，2023年，2月20日，星期三活動記錄

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

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

經(jīng)一段運(yùn)行時間之后，這個大空間就必定被分劃成許多塊塊，有些占用，有些無用（空閑）--碎片問題第16頁，共31頁，2023年，2月20日，星期三堆式動態(tài)儲分配

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

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

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

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