【正文】 應(yīng)地置上指針 。 標(biāo)準(zhǔn)過(guò)程dispose是釋放空間 . new與 dispose不斷改變著堆存儲(chǔ)器的使用情況 。 C語(yǔ)言中有這些操作的若干個(gè)版本 ， 但最基本的是 m a l l o c和 f r e e， 它們都是標(biāo)準(zhǔn)庫(kù)（ ） 的一部分 堆式動(dòng)態(tài)存儲(chǔ)分配 需求： 一個(gè)程序語(yǔ)言允許用戶(hù)自由地申請(qǐng)數(shù)據(jù)空間和退還數(shù)據(jù)空間 ， 或者不僅有過(guò)程而且有進(jìn)程 （ process）的程序結(jié)構(gòu) ， 操作： 堆提供兩個(gè)操作 ， 分配操作和釋放操作 情況 : 經(jīng)一段運(yùn)行時(shí)間之后，這個(gè)大空間就必定被分劃成許多塊塊，有些占用，有些無(wú)用（空閑） 碎片問(wèn)題 堆式動(dòng)態(tài)儲(chǔ)分配 當(dāng)運(yùn)行程序要求一塊體積為 N的空間時(shí)，我們應(yīng)該分配哪一塊給它呢？ 運(yùn)行程序要求一塊體積為 N的空間，但發(fā)現(xiàn)沒(méi)有比 N大的空閑塊了，然而所有空閑塊的總和卻要比 N大得多 如果運(yùn)行程序要求一塊積為 N的空間，但所有空閑塊的總和也不夠 N，那又應(yīng)怎么辦呢？有的管理系統(tǒng)采用一種叫做垃圾回收的辦法來(lái)對(duì)付這種局面。即尋找那些運(yùn)行程序業(yè)己無(wú)用但尚未釋放的占用塊 堆管理 堆空間的管理策略 減少碎片的技術(shù) 空間的釋放 堆空間的管理策略 1 定長(zhǎng)塊管理 2 變長(zhǎng)塊管理 堆式動(dòng)態(tài)儲(chǔ)分配的實(shí)現(xiàn) 1 定長(zhǎng)塊管理 堆式動(dòng)態(tài)儲(chǔ)分配最簡(jiǎn)單的實(shí)現(xiàn)是按定長(zhǎng)塊進(jìn)行 。初始化時(shí) ， 將堆存儲(chǔ)空間分成長(zhǎng)度相等的若干塊 ， 每塊中指定一個(gè)鏈域 ， 按照鄰塊的順序把所有塊鏈成一個(gè)鏈表 ， 用指針 available指向鏈表中的第一塊 。 分配時(shí)每次都分配指針 available所指的塊 ， 然后available指向相鄰的下一塊 。 歸還時(shí) ， 把所歸還的塊插入鏈表 。 考慮插入方便 ， 可以把所歸還的塊插在 av a ilab le所指的塊之前 ， 然后available指向新歸還的塊 。 2 變長(zhǎng)塊管理 除了按定長(zhǎng)塊進(jìn)行分配之外，還可以根據(jù)需要分配長(zhǎng)度不同的存儲(chǔ)塊，可以隨要求而變。按這種方法，初始化時(shí)存儲(chǔ)空間是一個(gè)整塊。按照用戶(hù)的需要，分配時(shí)先是從一個(gè)整塊里分割出滿(mǎn)足需要的一小塊，以后，歸還時(shí)，如果新歸還的塊和現(xiàn)有的空間能合并，則合并成一塊；如果不能和任何空閑塊合并，則可以把空閑塊鏈成一個(gè)鏈表。再進(jìn)行分配時(shí)，從空閑塊鏈表中找出滿(mǎn)足需要的一塊，或者整塊分配出去，或者從該塊上分割一小塊分配出去。若空閑塊表中有若干個(gè)滿(mǎn)足需要的空閑塊時(shí)，該分配哪一塊呢？通常有三種不同的分配策略 不同的情況應(yīng)采用不同的方法。通常在選擇時(shí)需考慮下列因素：用戶(hù)的要求；請(qǐng)求分配量的大小分布；分配和釋放的頻率以及效率對(duì)系統(tǒng)的重要等等。 （ 1） 首次滿(mǎn)足法：只要在空閑塊鏈表中找到滿(mǎn)足需要的一塊 ，就進(jìn)行分配 。 （ 2） 最優(yōu)滿(mǎn)足法：將空閑塊鏈表中一個(gè)不小于申請(qǐng)塊且最接近于申請(qǐng)塊的空閑塊分配給用戶(hù) ， 則系統(tǒng)在分配前首先要對(duì)空閑塊鏈表從頭至尾描一遍 ， 然后從中找出一塊 ， 為避免每次分配都要掃描整個(gè)鏈表 ， 通常將空閑塊鏈表空間的大小從小到大排序 。 （ 3） 最差滿(mǎn)足法：將空閑塊表中不小于申請(qǐng)塊且是最大的空閑的一部全分配給用戶(hù) 。 此時(shí)的空閑塊鏈表按空閑的塊的大小從大到小排序 。 只需從鏈表中刪除第一個(gè)結(jié)點(diǎn) ， 并將其中一部分分配給用戶(hù) ， 而其它部分作為一個(gè)新的結(jié)點(diǎn)插入到空閑塊表的適當(dāng)置上去 。 減少碎片的技術(shù) 1分配時(shí)，找最小的足夠大的塊 需保持空閑塊的大小排序 2 釋放時(shí)，合并任何相鄰的塊 搜索全部空閑塊表，或其它算法 3 將堆變量緊縮在一起 空間的釋放 1顯式釋放 2隱式（自動(dòng)）釋放 顯式釋放 程序設(shè)計(jì)語(yǔ)言提供機(jī)制 如： pascal 的 dispose C 的 free 程序員必須編寫(xiě)分配和釋放存儲(chǔ)的明確的調(diào)用 注意的問(wèn)題 1 堆變量是不可訪(fǎng)問(wèn)的（垃圾） 2 懸掛（不安全）指針 堆式分配和釋放的 C語(yǔ)言描述 define NULL 0 define MEMSIZE 8096 /* change for different sizes */ typedef fdouble Align。 typedef union header {struct {union header *next。 unsigned usedsize。 unsigned freesize。 }s。 Align a。 }Header。//數(shù)據(jù)類(lèi)型 Header保存每個(gè)存儲(chǔ)塊的簿記信息 static Header mem [MEMSIZE]。 static Header *memptr= NULL。 void *malloc (unsigned nbytes) {Header *p, *newp。 unsigned nunits。 nunits= (nbytes+sizeof (Header)1/ sizeof (Header)+1。 if (memptr == NULL) {memptrs. next = memptr = mem。 memptrs. usedsize = 1。 memptrs. freesize = MEMSIZE1。 } for (p=memptr。 (ps. next!= memptr) (ps. freesize nunits)。 p=ps. next)。 if (ps. freesize nunits) return NULL。 /* no block big enough */ newp = p+ps. usedsize。 newps. usedsize= nunits。 newps. freesize = ps. freesizenunits。 newp = ps. next。 ps. freesize=0。 ps. next= newp。 memptr=newp。 return (void *)(newp+1)。 } void free (void *ap) {Header * bp, *p, *prev。 bp= (Header *) ap –1。 for (prev= memptr, p=memptrs. next。 (p!=bp) (p!= memptr)。 prev=p, p=ps. next)。 if (p!=bp) return。 /* corrupted list, do nothing */ prevs. freesize += ps. usedsize + ps. freesize。 prevs. next = ps. next。 memptr = prev。 } 堆的自動(dòng)管理 隱式存儲(chǔ)回收 在一種需要完全動(dòng)態(tài)的運(yùn)行時(shí)環(huán)境的語(yǔ)言（ OO語(yǔ)言 ， 函數(shù)式語(yǔ)言 Lisp,ML)中 ， 堆也必須類(lèi)似地自動(dòng)管理 。 自動(dòng)存儲(chǔ)器管理涉及到了前面分配的但不再使用的存儲(chǔ)器的回收 ， 可能是在它被分配的很久以后 ，而沒(méi)有明確的對(duì) free的調(diào)用 。 這個(gè)過(guò)程稱(chēng)作垃圾回收 （ grabage collection） 。 垃圾回收 垃圾回收程序 尋找可被引用的所有存儲(chǔ)器并釋所有未引用的存儲(chǔ)器。 在存儲(chǔ)塊不再引用時(shí)，無(wú)論是直接還是通過(guò)指針間接的引用，識(shí)別這些存儲(chǔ)塊是一項(xiàng)比維護(hù)堆存儲(chǔ) 的列表復(fù)雜得多的任務(wù)。 方法 對(duì) malloc的調(diào)用失敗，激活垃圾回收程序 垃圾回收算法 mark and sweep 隱式存儲(chǔ)回收 —mark and sweep算法 隱式存儲(chǔ)回收要求用戶(hù)程序和支持運(yùn)行的回收子程序并行工作，因?yàn)榛厥粘绦蛐枰婪峙浣o用戶(hù)程序的存儲(chǔ)塊何時(shí)不再使用。為了實(shí)現(xiàn)并行工作，在存儲(chǔ)塊中要設(shè)置回收子程序訪(fǎng)問(wèn)的信息。 存儲(chǔ)塊格式： 塊長(zhǎng)度 訪(fǎng)問(wèn)計(jì)數(shù)標(biāo)記 指針 用戶(hù)使用空間 回收過(guò)程 分為兩個(gè)階段 。 （ 1） 第一個(gè)階段為標(biāo)記階段 ， 對(duì)已分配的塊跟蹤程序中各指針的訪(fǎng)問(wèn)路徑 。 如果某個(gè)塊被訪(fǎng)問(wèn)過(guò) ， 就給這個(gè)塊加一個(gè)標(biāo)記 。 （ 2） 第二個(gè)階段為回收階段 ， 所有未加標(biāo)記的存儲(chǔ)塊回收到一起 ， 并插入空閑塊鏈表中 ， 然后消除在存儲(chǔ)塊中所加的全部標(biāo)記 。 面向?qū)ο蟮恼Z(yǔ)言中的動(dòng)態(tài)存儲(chǔ)器 面向?qū)ο蟮恼Z(yǔ)言在運(yùn)行時(shí)環(huán)境中要求特殊的機(jī)制以完成其增添的特性：對(duì)象 、 方法 、繼承以及動(dòng)態(tài)聯(lián)編 。 面向?qū)ο笳Z(yǔ)言在對(duì)運(yùn)行時(shí)方面的要求差異很大 。 Smalltalk要求與 LISP相似的完全動(dòng)態(tài)環(huán)境 C＋＋則保持 C的基于棧的環(huán)境 實(shí)現(xiàn)對(duì)象 實(shí)現(xiàn)對(duì)象的一個(gè)簡(jiǎn)單機(jī)制是，初始化代碼將所有當(dāng)前的繼承特征（和方法）直接地復(fù)制到記錄結(jié)構(gòu)中（將方法當(dāng)作代碼指針）。但這樣做極浪費(fèi)空間。 另外一種方法是在執(zhí)行時(shí)將類(lèi)結(jié)構(gòu)的一個(gè)完整的描述保存在每個(gè)點(diǎn)的存儲(chǔ)器中，并由超類(lèi)指針維護(hù)繼承性（有時(shí)這也稱(chēng)作繼承圖（ inheritance graph））。接著同用于它的實(shí)例變量的域一起，每個(gè)對(duì)象保持一個(gè)指向其定義類(lèi)的指針，通過(guò)這個(gè)類(lèi)就可找到所有（局部和繼承的）的方法。此時(shí)，只記錄一次方法指針（在類(lèi)結(jié)構(gòu)中），而且對(duì)于每個(gè)對(duì)象并不將其復(fù)制到存儲(chǔ)器中。由于是通過(guò)類(lèi)繼承的搜索來(lái)找到這個(gè)機(jī)制的，所以該機(jī)制還實(shí)現(xiàn)繼承性與動(dòng)態(tài)聯(lián)編。其缺 在于：雖然實(shí)例變量具有可預(yù)測(cè)的偏移量（正如在標(biāo)準(zhǔn)環(huán)境中的局部變量一樣），方法卻沒(méi)有，而且它們必須由帶有查詢(xún)功能的符號(hào)表結(jié)構(gòu)中的名字維護(hù)。這是對(duì)于諸如 Smalltalk的高度動(dòng)態(tài)語(yǔ)言的合理的結(jié)構(gòu)，因?yàn)轭?lèi)結(jié)構(gòu)可以在執(zhí)行中改變。 C++中選擇的方法 將整個(gè)類(lèi)結(jié)構(gòu)保存在環(huán)境中 ， 計(jì)算出每個(gè)類(lèi)的可用方法的代碼指針列表 ， 并將其作為一個(gè)虛擬函數(shù)表 （ virtual function table） 而存放在（ 靜態(tài) ） 存儲(chǔ)器 。 它的優(yōu)點(diǎn)在于：可做出安排以使每個(gè)方法都有一個(gè)可預(yù)測(cè)的偏移量 ，而且也不再需要用一系列表查詢(xún)遍歷類(lèi)的層次結(jié)構(gòu) 。 現(xiàn)在每個(gè)對(duì)象都包括了一個(gè)指向相應(yīng)的虛擬函數(shù)表而不是類(lèi)結(jié)構(gòu)的指針 （ 當(dāng)然 ，這個(gè)指針的位置必須也有可預(yù)測(cè)的偏移量 ） 。 例 C++類(lèi)聲明： class A {public: double x,y。 void f()。 virtual void g()。 }。 class B:public A {public: double z。 void f()。 virtual void h()。 }。 類(lèi) A的一個(gè)對(duì)象應(yīng)出現(xiàn)在存儲(chǔ)器中 （ 帶有它的虛擬函數(shù)表 ） 而類(lèi) B的一個(gè)對(duì)象則應(yīng)如下所示： x y vtp A::g B::h A::g X Y vtp z