1、第七章運(yùn)轉(zhuǎn)時(shí)辰環(huán)境湖南大學(xué)計(jì)算機(jī)與通訊學(xué)院軟件學(xué)院編譯器的一些問(wèn)題變量的存儲(chǔ)位置如何分配？名字的作用域如何實(shí)現(xiàn)？過(guò)程調(diào)用如何實(shí)現(xiàn)？參數(shù)傳送如何實(shí)現(xiàn)？這些問(wèn)題需求依托運(yùn)轉(zhuǎn)時(shí)環(huán)境來(lái)輔助處理。運(yùn)轉(zhuǎn)時(shí)辰環(huán)境運(yùn)轉(zhuǎn)時(shí)辰環(huán)境為數(shù)據(jù)分配安排存儲(chǔ)位置確定訪問(wèn)變量時(shí)運(yùn)用的機(jī)制過(guò)程之間的銜接參數(shù)傳送和操作系統(tǒng)、輸入輸出設(shè)備相關(guān)的其它接口主題存儲(chǔ)管理：棧分配、堆管理、渣滓回收對(duì)變量、數(shù)據(jù)的訪問(wèn)存儲(chǔ)分配的典型方式目的程序的代碼放置在代碼區(qū)，通常位于存儲(chǔ)的低端靜態(tài)區(qū)、堆區(qū)、棧區(qū)分別放置不同類型生命期的數(shù)據(jù)值,實(shí)際中棧向較低地址方向增長(zhǎng)堆向較高方向增長(zhǎng)。圖7-1編譯的結(jié)果全局/靜態(tài)變量共享*從如今開(kāi)場(chǎng)要留意，為使我們能在一

2、切的例子中方便地運(yùn)用正的偏移量,棧向較高地址方向增長(zhǎng)，即頂是在最下端。0X00H0XFFFFH.靜態(tài)和動(dòng)態(tài)存儲(chǔ)分配靜態(tài)分配編譯器在編譯時(shí)辰就可以做出存儲(chǔ)分配決議，不需求思索程序運(yùn)轉(zhuǎn)時(shí)辰的情形，如：靜態(tài)變量言語(yǔ)中static變量全局變量動(dòng)態(tài)分配棧式存儲(chǔ)：過(guò)程的部分名字采用棧式存儲(chǔ)和過(guò)程的調(diào)用/前往同步進(jìn)展分配和回收，值的生命期和過(guò)程生命期一樣堆heap存儲(chǔ)：有些數(shù)據(jù)生命期比相應(yīng)過(guò)程調(diào)用的生命期更長(zhǎng)，常分配在一個(gè)可重用存儲(chǔ)的“堆中。堆和渣滓回收堆是虛擬內(nèi)存的一個(gè)區(qū)域，它允許對(duì)象或其他數(shù)據(jù)元素在被創(chuàng)建時(shí)獲得存儲(chǔ)空間，并在數(shù)據(jù)變得無(wú)效時(shí)釋放該存儲(chǔ)空間渣滓回收：檢測(cè)出堆中無(wú)用的數(shù)據(jù)元素，釋放它們的空間手

3、工進(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)用的先前往(LIFO)因此可以用棧式分配來(lái)處置過(guò)程活動(dòng)所需求的內(nèi)存空間。程序運(yùn)轉(zhuǎn)的一切過(guò)程活動(dòng)可以用樹(shù)表示每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)過(guò)程活動(dòng)根結(jié)點(diǎn)對(duì)應(yīng)于main過(guò)程的活動(dòng)過(guò)程p的某次活動(dòng)對(duì)應(yīng)的結(jié)點(diǎn)的子結(jié)點(diǎn)對(duì)應(yīng)于此次活動(dòng)調(diào)用的各個(gè)過(guò)程活動(dòng)從左向右，表示調(diào)用的先后順序活動(dòng)樹(shù)的例子快速排序1活動(dòng)樹(shù)的例子快速排序程序：P260，圖7-2過(guò)程調(diào)用前往序列和活動(dòng)樹(shù)的前序后序遍歷對(duì)應(yīng)假定當(dāng)前活動(dòng)對(duì)應(yīng)結(jié)點(diǎn)N，那么一切尚未終了的結(jié)點(diǎn)對(duì)應(yīng)于N及其祖先結(jié)點(diǎn)。活動(dòng)記錄過(guò)程調(diào)用和前往由控制棧

4、進(jìn)展管理過(guò)程活動(dòng)記錄：當(dāng)調(diào)用過(guò)程或函數(shù)時(shí)，為其部分?jǐn)?shù)據(jù)動(dòng)態(tài)分配的存儲(chǔ)區(qū)活動(dòng)記錄按照活動(dòng)的開(kāi)場(chǎng)時(shí)間，從棧底到棧頂陳列圖活動(dòng)記錄框架計(jì)算中間結(jié)果部分變量活動(dòng)記錄控制鏈：指向調(diào)用者的活動(dòng)記錄固定長(zhǎng)度部分訪問(wèn)鏈：活動(dòng)記錄中指向上一級(jí)活動(dòng)記錄(包含嵌套的環(huán)境定義的活動(dòng)記錄)的指針保管的機(jī)器形狀：此次調(diào)用前的機(jī)器形狀信息，如：前往地址及一些存放器的值運(yùn)轉(zhuǎn)時(shí)辰棧的例子例：快速排序a11為全局變量main沒(méi)有部分變量r有部分變量iq的部分變量i，和參數(shù)m,n。Main的活動(dòng)記錄調(diào)用序列調(diào)用序列(calling sequence)為活動(dòng)記錄分配空間，填寫記錄中的信息；前往序列(return sequence)恢

5、復(fù)機(jī)器形狀，使調(diào)用者繼續(xù)運(yùn)轉(zhuǎn)。調(diào)用序列會(huì)分割到調(diào)用者和被調(diào)用者中。根據(jù)源言語(yǔ)、目的機(jī)器、操作系統(tǒng)的限制，可以有不同的分割方案把代碼盡能夠放在被調(diào)用者中。調(diào)用/前往序列的要求數(shù)據(jù)方面可以把參數(shù)正確地傳送給被調(diào)用者可以把前往值傳送給調(diào)用者控制方面可以正確轉(zhuǎn)到被調(diào)用者的代碼的開(kāi)場(chǎng)位置可以正確轉(zhuǎn)回調(diào)用者的調(diào)用位置的下一條指令調(diào)用序列和活動(dòng)記錄的規(guī)劃相關(guān)活動(dòng)記錄的規(guī)劃原那么調(diào)用者和被調(diào)用者之間傳送的值放在被調(diào)用者記錄的開(kāi)場(chǎng)位置固定長(zhǎng)度的項(xiàng)放在中間位置控制鏈、訪問(wèn)鏈、機(jī)器形狀字段早期不知道大小的項(xiàng)在活動(dòng)記錄尾部干脆將固定長(zhǎng)度的部分變量也放入該段棧頂指針通常指向固定長(zhǎng)度字段的末端top_sp調(diào)用代碼序列的例

6、子Calling sequence調(diào)用序列調(diào)用者計(jì)算真實(shí)參數(shù)的值將前往地址和原top_sp控制鏈存放到被調(diào)用者的活動(dòng)記錄中。調(diào)用者添加top_sp的值越過(guò)了調(diào)用者的部分?jǐn)?shù)據(jù)、暫時(shí)變量、被調(diào)用者的參數(shù)、機(jī)器形狀字段被調(diào)用者保管存放器值和其他形狀字段被調(diào)用者初始化部分?jǐn)?shù)據(jù)、開(kāi)場(chǎng)運(yùn)轉(zhuǎn)。Return sequence 前往序列被調(diào)用者將前往值放到和參數(shù)相鄰的位置恢復(fù)top_sp和存放器，跳轉(zhuǎn)到前往地址。棧中的變長(zhǎng)數(shù)據(jù)假設(shè)數(shù)據(jù)對(duì)象的生命期局限于過(guò)程活動(dòng)的生命期，就可以分配在運(yùn)轉(zhuǎn)時(shí)辰棧中。top指向?qū)嵺`的棧頂top_sp用于尋覓頂層記錄的定長(zhǎng)字段框架指針例 利用Euclid算法的簡(jiǎn)單遞歸算法，計(jì)算兩個(gè)非負(fù)

7、整數(shù)的最大公約數(shù)。程序清單 C代碼#include int x, y;int gcd(int u, int v) if (v=0) return u; else return gcd(v, u%v);main() scanf(“%d%d, &x, &y); printf(“%dn, gcd(x,y); return 0; 假設(shè)輸入為，試畫出運(yùn)轉(zhuǎn)的活動(dòng)樹(shù)試畫出運(yùn)轉(zhuǎn)時(shí)棧變化過(guò)程main()gcd(15,10)gcd(10,5)gcd(5,0)第3個(gè)調(diào)用時(shí)的環(huán)境如圖7-2所示。x:15y:10u:15v:10控制鏈前往地址部分變量u:10v:5控制鏈前往地址部分變量u:5v:0控制鏈前往地址部分變量

8、自在空間Top_sptop全局靜態(tài)區(qū)域main的活動(dòng)記錄第一次調(diào)用gcd時(shí)的活動(dòng)記錄第二次調(diào)用gcd時(shí)的活動(dòng)記錄第三次調(diào)用gcd時(shí)的活動(dòng)記錄棧的生長(zhǎng)方向基于棧的環(huán)境main()gcd(15,10)gcd(10,5)gcd(5,0)前往值為基于棧的運(yùn)轉(zhuǎn)時(shí)環(huán)境留意：同一個(gè)過(guò)程的不同活動(dòng)對(duì)應(yīng)的活動(dòng)記錄的大小完全一樣；新的活動(dòng)記錄總是在棧頂參與；其控制鏈總是指向先前的活動(dòng)記錄的控制鏈；top_sp指向當(dāng)前活動(dòng)記錄的控制鏈；調(diào)用前往時(shí)，將按順序從棧中刪去每個(gè)活動(dòng)記錄；當(dāng)在main中執(zhí)行printf語(yǔ)句時(shí)，環(huán)境中只保管了main的活動(dòng)記錄和全局/靜態(tài)區(qū)域。7.3 棧中非部分?jǐn)?shù)據(jù)的訪問(wèn)7.3.1無(wú)嵌套過(guò)程時(shí)

9、的數(shù)據(jù)訪問(wèn)無(wú)嵌套過(guò)程時(shí)的數(shù)據(jù)訪問(wèn)例：言語(yǔ)不允許嵌套過(guò)程聲明，變量要么在函數(shù)內(nèi)定義，要么全局地定義C言語(yǔ)中函數(shù)對(duì)變量的訪問(wèn)部分變量：在當(dāng)前活動(dòng)記錄內(nèi)，可經(jīng)過(guò)top_sp指針加上相對(duì)地址來(lái)訪問(wèn)全局/靜態(tài)變量：在靜態(tài)區(qū)，地址在編譯時(shí)可知C言語(yǔ)允許函數(shù)參數(shù)參數(shù)中只需求包括函數(shù)代碼的起始地址。在函數(shù)中訪問(wèn)變量的方式很簡(jiǎn)單，不需求思索過(guò)程是如何激活的。C言語(yǔ)中活動(dòng)記錄中無(wú)需訪問(wèn)鏈7.3 基于棧的運(yùn)轉(zhuǎn)時(shí)環(huán)境1) 對(duì)稱號(hào)的訪問(wèn)在基于棧的環(huán)境中，要訪問(wèn)參數(shù)和部分變量，可用當(dāng)前框架指針(top_sp)的偏移量實(shí)現(xiàn)。在大多數(shù)的言語(yǔ)中，每個(gè)部分聲明的偏移量可由編譯程序靜態(tài)地計(jì)算出來(lái)。由于過(guò)程的聲明在編譯時(shí)是固定的，而

10、且為每個(gè)聲明分配的存儲(chǔ)器大小也根據(jù)其數(shù)據(jù)類型而固定。例 思索C過(guò)程void f(int x, char c) int a10; double y; . . . 對(duì)f調(diào)用的活動(dòng)記錄ya9a1a0前往地址控制鏈cxx偏移量top_spc偏移量a偏移量y偏移量*此處在前往地址下省略了被保管的形狀等信息整型4個(gè)字節(jié)、地址4個(gè)字節(jié)、字符1個(gè)字節(jié)、雙精度浮點(diǎn)數(shù)8個(gè)字節(jié)，那么偏移量為：稱號(hào)偏移量 x-9 c-8 a+0 y+40 ai的地址為：0+4*i+ top_sp。在基于棧的環(huán)境中，非部分的和靜態(tài)的名字的地址都是固定的靜態(tài)地址，可以直接訪問(wèn)。*留意在本章內(nèi)，棧是往下面大端生長(zhǎng)的。非部分?jǐn)?shù)據(jù)的訪問(wèn)嵌套過(guò)

11、程PASCAL言語(yǔ)允許過(guò)程嵌套定義，且遵照靜態(tài)作用域規(guī)那么代碼運(yùn)轉(zhuǎn)時(shí)，對(duì)變量的訪問(wèn)應(yīng)指向運(yùn)轉(zhuǎn)棧中最上層的同名變量。問(wèn)題：變量不一定在當(dāng)前活動(dòng)記錄中，如何確定其位置？思索：符號(hào)表中存儲(chǔ)了變量的偏移量，因此只需求確定的活動(dòng)記錄。子問(wèn)題：用嵌套層次可以完全處理這個(gè)問(wèn)題嗎？非部分?jǐn)?shù)據(jù)的訪問(wèn)嵌套過(guò)程問(wèn)題：用調(diào)用層次可以完全處理這個(gè)問(wèn)題嗎？void A()intx,y;voidB()int b;x = b+y;voidC()B(); C();B的活動(dòng)記錄C的活動(dòng)記錄A的活動(dòng)記錄當(dāng)A調(diào)用C，C又調(diào)用B時(shí):不能！A,B的層次差是，但B的控制鏈并沒(méi)有直接指向A處理方法：引入訪問(wèn)鏈指向過(guò)程的定義環(huán)境7.3.3 一

12、個(gè)支持嵌套過(guò)程聲明的言語(yǔ)最新的支持嵌套過(guò)程的典型言語(yǔ)之一：MLML是一種函數(shù)式言語(yǔ)，變量一旦聲明并初始化就不會(huì)再改動(dòng)有少數(shù)例外，如：數(shù)組元素可經(jīng)過(guò)特殊的函數(shù)調(diào)用改動(dòng)變量定義并初始化為不可更改的值的語(yǔ)句方式： =函數(shù)定義的語(yǔ)法：Fun ()=函數(shù)體(body)定義的語(yǔ)法：Let in end嵌套深度嵌套深度是正文概念，可根據(jù)源程序靜態(tài)地確定不內(nèi)嵌于任何其他過(guò)程中的過(guò)程，嵌套深度為1嵌套在深度為i的過(guò)程中的過(guò)程，深度為i+1.深度為1sort深度為2readArray，exchange，quicksort深度為3partition圖7-10 一個(gè)運(yùn)用嵌套函數(shù)聲明的ML風(fēng)格的quicksort訪問(wèn)鏈

13、顯式表顯式表訪問(wèn)鏈引入訪問(wèn)鏈的目的：訪問(wèn)非部分?jǐn)?shù)據(jù)假設(shè)過(guò)程p在聲明時(shí)嵌套在過(guò)程q的聲明中，那么p的活動(dòng)記錄中的訪問(wèn)鏈指向最上層最新的q的活動(dòng)記錄。從棧頂活動(dòng)記錄開(kāi)場(chǎng)，訪問(wèn)鏈構(gòu)成了一個(gè)鏈路，嵌套深度逐一遞減。設(shè)深度為np的過(guò)程p訪問(wèn)變量x，而變量x在深度為nq的過(guò)程中聲明，那么從當(dāng)前活動(dòng)記錄出發(fā)，沿訪問(wèn)鏈前進(jìn)np-nq次找到活動(dòng)記錄其中的x就是要找的變量位置x相對(duì)于該活動(dòng)記錄的偏移量在編譯時(shí)辰知np和-nq在編譯時(shí)辰知；訪問(wèn)鏈的例子P270圖7-11 用來(lái)查找非部分?jǐn)?shù)據(jù)的訪問(wèn)鏈sort活動(dòng)記錄訪問(wèn)鏈的處置明確調(diào)用過(guò)程與聲明嵌套深度的關(guān)系當(dāng)過(guò)程q調(diào)用過(guò)程p時(shí)，P訪問(wèn)鏈如何設(shè)置？把p的聲明嵌套深度n

14、p與nq的關(guān)系分為大于，等于，小于三種情況思索p的聲明嵌套深度大于q，p必然在q中直接定義，否那么不滿足作用域規(guī)那么，那么p的訪問(wèn)鏈指向當(dāng)前活動(dòng)記錄(即父親直接調(diào)用孩子)遞歸調(diào)用：p=q 。p的活動(dòng)記錄的訪問(wèn)鏈等于q當(dāng)前記錄的訪問(wèn)鏈(即本身等于本身)p的聲明嵌套深度小于q的深度：此時(shí)必然有過(guò)程r，p直接在r中定義，而q嵌套在r中。此時(shí)應(yīng)讓p的訪問(wèn)鏈指向r的活動(dòng)記錄。(即q是p的侄子系的，r是p的父親)rpq.7.3.6 過(guò)程型參數(shù)的訪問(wèn)鏈有些言語(yǔ)允許過(guò)程作為參數(shù)，如：言語(yǔ)例：tiny編譯器中語(yǔ)義分析程序analyze.c的transverse函數(shù)聲明如下：static void travers

15、e( TreeNode * t, void (* preProc) (TreeNode *), void (* postProc) (TreeNode *) )構(gòu)建符號(hào)表前序遍歷語(yǔ)法樹(shù)traverse(syntaxTree,insertNode,nullProc);類型檢查時(shí)后序遍歷語(yǔ)法樹(shù)traverse(syntaxTree,nullProc,checkNode);7.3.6 過(guò)程型參數(shù)的訪問(wèn)鏈當(dāng)一個(gè)過(guò)程作為參數(shù)傳送給另一個(gè)過(guò)程，并且隨后調(diào)用了這個(gè)參數(shù)，有能夠并不知道在程序中出現(xiàn)的上下文后果：不知道如何設(shè)置的訪問(wèn)鏈處理方法： 在傳送過(guò)程指針參數(shù)時(shí)，過(guò)程型參數(shù)中不僅包含過(guò)程的代碼指針(IP)，

16、還包括正確的訪問(wèn)鏈AL)。7.3.6 過(guò)程型參數(shù)的訪問(wèn)鏈圖-12 運(yùn)用函數(shù)參數(shù)的ML程序的概要f是一個(gè)函數(shù)參數(shù)對(duì)的援用d被用作函數(shù)參數(shù)7.3.6 過(guò)程型參數(shù)的訪問(wèn)鏈由于d在c中定義7.3.8 顯示表display)用訪問(wèn)鏈訪問(wèn)數(shù)據(jù)時(shí)，假設(shè)嵌套深度大，那么訪問(wèn)的效率差。顯示表：運(yùn)用數(shù)組d為每個(gè)嵌套深度保管一個(gè)指針指針di指向棧中最高的對(duì)應(yīng)于嵌套深度為i的的活動(dòng)記錄。假設(shè)程序p中訪問(wèn)嵌套深度為i的過(guò)程q中變量x，那么di直接指向相應(yīng)的q活動(dòng)記錄；顯示表的維護(hù)調(diào)用過(guò)程p時(shí)，在p的活動(dòng)記錄中保管原dnp的值，并將dnp設(shè)置為p的該次活動(dòng)記錄。從p前往時(shí)，恢復(fù)dnp的值。顯示表舉例q(1,9)調(diào)用q(1

17、,3)時(shí)，q的深度為2例： ML風(fēng)格的quicksort顯示表舉例q(1,3)調(diào)用p，p的深度為3q調(diào)用e，e的深度為2例： ML風(fēng)格的quicksort嵌套層次構(gòu)造分析偽代碼Display(1)main-(2)P-(3)Q-(4)R主程序的活動(dòng)記錄 d1display棧頂1主程序的活動(dòng)記錄P 的活動(dòng)記錄 d1d2display棧頂2棧棧主程序-P-Q-R主程序的活動(dòng)記錄P 的活動(dòng)記錄 Q 的活動(dòng)記錄R 的活動(dòng)記錄主程序的活動(dòng)記錄 P 的活動(dòng)記錄Q 的活動(dòng)記錄 displayd1d2d3 d1d2d3 display34棧頂棧棧棧頂堆管理堆空間用于存放生命周期不確定、或者生存到被顯式刪除為止的

18、數(shù)據(jù)對(duì)象，例：new生成的對(duì)象可以生存到被delete為止Malloc懇求的空間生存到被free為止存儲(chǔ)管理器分配/回收堆區(qū)空間的子系統(tǒng)根據(jù)言語(yǔ)而定C、C+需求手動(dòng)回收空間Java可以自動(dòng)回收空間渣滓搜集存儲(chǔ)管理器的根本功能分配：為每個(gè)內(nèi)存懇求分配一段延續(xù)的、適當(dāng)大小的堆空間。首先從空閑堆空間分配；假設(shè)沒(méi)有可分配的堆空間，那么從操作系統(tǒng)中獲得延續(xù)的虛擬內(nèi)存來(lái)添加堆空間；如空間已用完，那么將空間耗盡的音訊反響給運(yùn)用程序回收：把被回收的空間前往空閑空間緩沖池，以滿足以后的分配懇求。期望的存儲(chǔ)管理器特性空間效率使程序所需堆空間最小實(shí)現(xiàn)手段：最小化存儲(chǔ)碎片程序效率充分利用存儲(chǔ)子系統(tǒng)，提高程序運(yùn)轉(zhuǎn)效率在

19、存儲(chǔ)子系統(tǒng)中，不同的層次訪問(wèn)速度不一樣盡能夠多的利用高訪問(wèn)速度的存儲(chǔ)器件，可大幅度提高效率低開(kāi)銷最小化分配/收回內(nèi)存的開(kāi)銷即破費(fèi)在分配和回收上的執(zhí)行時(shí)間在總運(yùn)轉(zhuǎn)時(shí)間中所占的比例注：分配的開(kāi)銷由小型懇求決議，管理大型對(duì)象的開(kāi)銷相對(duì)不重要 一次內(nèi)存訪問(wèn)中，機(jī)器首先在最低層的存儲(chǔ)中尋覓數(shù)據(jù)，假設(shè)數(shù)據(jù)不在那里那么到上一層中尋覓。程序的部分性大部分程序呈現(xiàn)高度的部分性即程序的大部分運(yùn)轉(zhuǎn)時(shí)間破費(fèi)在相對(duì)較小的一部分代碼時(shí)間部分性假設(shè)一個(gè)程序訪問(wèn)的存儲(chǔ)位置很能夠?qū)⒃谝粋€(gè)很短的時(shí)間段內(nèi)被再次訪問(wèn)，稱其具有時(shí)間部分性空間部分性假設(shè)被訪問(wèn)的存儲(chǔ)位置的臨近位置很能夠?qū)⒃谝粋€(gè)很短的時(shí)間段內(nèi)被再次訪問(wèn)，稱其具有空間部分性

20、程序的部分性程序把90的時(shí)間用于執(zhí)行10的代碼，緣由如下：程序常包含許多從不被執(zhí)行的指令如：運(yùn)用組件和庫(kù)構(gòu)建的程序只運(yùn)用了它們提供的一小部分功能隨需求變化和程序演化，遺留系統(tǒng)中經(jīng)常包含許多不再被運(yùn)用的指令有大量容錯(cuò)和調(diào)試代碼在正常運(yùn)轉(zhuǎn)時(shí)不執(zhí)行執(zhí)行最內(nèi)層循環(huán)和最緊湊遞歸環(huán)破費(fèi)了程序執(zhí)行的大部分時(shí)間堆空間的碎片問(wèn)題程序運(yùn)轉(zhuǎn)前，堆是一個(gè)延續(xù)的自在空間隨著程序分配/回收內(nèi)存，堆區(qū)逐漸被分割成空閑存儲(chǔ)塊窗口，hole和已用存儲(chǔ)塊分配內(nèi)存時(shí)，通常是把一個(gè)窗口的一部分分配出去，其他部分成為更小的塊。回收時(shí)，被釋放的存儲(chǔ)塊被放回緩沖池。通常會(huì)把延續(xù)的窗口接合成為更大的窗口。堆空間分配方法Best-Fit最正確

21、順應(yīng)優(yōu)先在滿足懇求的最小窗口中分配內(nèi)存優(yōu)點(diǎn)：可將大窗口保管下來(lái)以應(yīng)對(duì)更大的懇求First-Fit最先順應(yīng)優(yōu)先在第一個(gè)滿足懇求的窗口中分配內(nèi)存優(yōu)點(diǎn)：快，常具有較好數(shù)據(jù)部分性同一段時(shí)間內(nèi)的對(duì)象分配延續(xù)空間缺陷：總體性能較差運(yùn)用容器的管理方法設(shè)定不同大小的空閑塊，并將同樣大小的塊放在容器中。較小的較常用的尺寸設(shè)置較多的容器。比如GNU的C編譯器gcc運(yùn)用存儲(chǔ)管理器lea將一切存儲(chǔ)塊對(duì)齊到8字節(jié)邊境。空閑塊的尺寸大小：16,24,32,40,512相鄰間相差8大于512的按照對(duì)數(shù)值劃分(每個(gè)容器的最小尺寸是前一個(gè)容器的最小尺寸的兩倍。)荒野塊：可以擴(kuò)展的內(nèi)存塊分配方法：對(duì)于小尺寸的懇求，直接在相應(yīng)容器中找。大尺寸的懇求，在適當(dāng)?shù)娜萜髦袑ひ掃m當(dāng)?shù)目臻e塊。能夠需求分割內(nèi)存塊。能夠需求從荒野塊中分割更多的塊。管理和接合空閑空間當(dāng)回收一個(gè)塊時(shí)，能夠可以把這個(gè)塊和相鄰的塊接合起來(lái)，構(gòu)成更大的塊。有些管理方法，比如說(shuō)Lea中，不一定需求進(jìn)展接合。(小于512的)支持相鄰塊接合的數(shù)據(jù)構(gòu)造需求如下兩點(diǎn)邊境標(biāo)志：在每一塊存儲(chǔ)塊的兩端，分別設(shè)置一個(gè)free/used位(兼當(dāng)邊境)；相鄰的位置上存放字節(jié)總數(shù)。雙重鏈接的、嵌入式的空閑塊列表：列表的指針存放在空閑塊中、用雙向指針的方式記錄了有哪些空閑塊。例子相鄰的存儲(chǔ)塊A、B、C當(dāng)回收B時(shí)