動(dòng)態(tài)內(nèi)存管理在面向嵌入式實(shí)時(shí)系統(tǒng)中的研究

　　為了提高內(nèi)存空間的利用率，采用按請(qǐng)求的實(shí)際大小來分配空間，而不是按塊的整數(shù)倍大小來分配空間。

　　基本方法就是將所有獨(dú)立塊（空閑塊和使用塊）按物理地址的先后順序組織成一個(gè)雙鏈表，每個(gè)塊中存放塊本身的一些獨(dú)立信息。分配空間時(shí)，需要查找整個(gè)鏈表以找到最優(yōu)適配的空閑塊，之后再將此空閑塊分裂成二塊，一塊用來滿足請(qǐng)求，另一塊則作為空閑塊插入鏈表?？臻g釋放時(shí)，只需根據(jù)鏈表便可以方便地找到與其相鄰的物理塊，在空間合并處理完成之后再將新的塊插入鏈表。

　　但事實(shí)上，由于在分配過程中只需要在空閑塊中查找最優(yōu)適配塊，所以可以采用一個(gè)單獨(dú)的鏈表將所有的空閑塊鏈接起來，這樣可以極大地加快空間分配時(shí)空閑塊的查找速度。

　　另外，從對(duì)伙伴系統(tǒng)的分析可知，將所有的內(nèi)存空閑區(qū)保留在一個(gè)或多個(gè)按空閑區(qū)大小排序的鏈表中將使內(nèi)存分配很快。所以借鑒伙伴系統(tǒng)的實(shí)現(xiàn)方式，可以將單個(gè)的空閑分區(qū)鏈組織成多個(gè)鏈表間有序的空閑分區(qū)鏈。在動(dòng)態(tài)內(nèi)存操作頻繁的情況下，這將會(huì)提高系統(tǒng)內(nèi)存分配的效率。

　　由于以上的方式容易產(chǎn)生許多小的不能繼續(xù)使用的空閑區(qū)，所以在進(jìn)行空間分配時(shí)，如果分配所得的空閑區(qū)小于某一特定值，則不再進(jìn)行空間分配，而是將整個(gè)空間作為請(qǐng)求結(jié)果返回。

　　綜上所述，可以將內(nèi)存塊組織成二個(gè)雙鏈表，即空閑塊鏈表和物理塊鏈表。

　?。?）空閑塊鏈表：將所有的空閑塊按鏈表間有序的方式組織成多個(gè)獨(dú)立的空閑鏈表?？臻g分配時(shí)，根據(jù)空間的大小選擇相應(yīng)的鏈表進(jìn)行查找。若查找成功，則在空間分配處理完成之后，將已分配空間返回給請(qǐng)求；若查找失敗，則在更大空間的鏈表中繼續(xù)查找；若直到全部鏈表查找完成仍未找到合適的空閑塊，則認(rèn)為此次分配操作失敗。

　?。?）物理塊鏈表：將所有獨(dú)立塊（空閑塊和使用塊）組織成一個(gè)雙鏈表，鏈表中各節(jié)點(diǎn)之間是按照物理地址的先后順序鏈接的，每個(gè)塊中存放塊本身的一些獨(dú)立信息?？臻g釋放時(shí)，可以不需查找，而直接根據(jù)這一鏈表找到與釋放塊相鄰的塊。再根據(jù)相鄰塊中的相關(guān)信息就可以方便地進(jìn)行內(nèi)存塊的合并操作。

　　具體實(shí)現(xiàn)時(shí)，可以將這二個(gè)鏈表的控制信息與用戶空間獨(dú)立存放，避免控制信息被意外地破壞。也可以利用物理塊本身來存放這些控制信息，得到更好的空間利用率和更好的靈活性。

　　3.4 連續(xù)的內(nèi)存分配工作方式

　　首先假定空間不再進(jìn)行分配的最小值為1KB,即當(dāng)空間分裂時(shí)所得的空閑區(qū)小于1KB時(shí)，將不再進(jìn)行空間分配。

　　分別保留大小為1KB、2KB、4KB、8KB字節(jié)等直到大于內(nèi)存總?cè)萘看笮〉逆湵?。例如?duì)于容量為1 024KB的內(nèi)存，有從1KB字節(jié)到2 048KB字節(jié)的12個(gè)鏈表。初始時(shí)，所有內(nèi)存都是空閑的，2 048KB的鏈表包含一個(gè)1 024KB的空閑區(qū)（每個(gè)鏈表存放所有小于鏈表本身字節(jié)數(shù)、大于等于前一鏈表的字節(jié)數(shù)的內(nèi)存塊，2 048KB的鏈表存放所有小于2 048KB大于等于1 024KB的內(nèi)存塊）。其他的鏈表均為空，內(nèi)存最初的情況如圖1所示。為表示方便，圖中使用單鏈表來表示鏈接關(guān)系。實(shí)線表示物理塊鏈表指針，短劃線表示空閑塊鏈表指針，虛線表示空指針。對(duì)于物理塊鏈表，灰色塊表示已分配塊，白色塊表示空閑塊。

　　當(dāng)有一個(gè)300KB的內(nèi)存請(qǐng)求（用A表示）產(chǎn)生時(shí)，系統(tǒng)找到512KB鏈表的表頭。因?yàn)檫@個(gè)鏈表中可能包含滿足請(qǐng)求所需的最小空間。之后按照最佳適配（best fit）算法，在鏈表中搜尋是否有夠用的最小空閑區(qū)。此時(shí)512KB的鏈表為空，1 024KB的鏈表也為空，所以最終在2 048KB的鏈表中找到1 024KB可用空間。將此空間分割成大小分別為300KB和700KB的塊，700KB的塊（大于最小塊1KB）插入到1 024KB的鏈表中，300KB的塊則返回給請(qǐng)求A.

　　接著，又有一個(gè)300KB（用B表示）和一個(gè)50KB（用C表示）的內(nèi)存請(qǐng)求。結(jié)果如圖2所示。

　　現(xiàn)在塊B被釋放。此時(shí)，根據(jù)物理塊鏈表，可以方便地找到與B鄰接的物理塊A和物理塊C.由于塊A和塊C都未被釋放，所以不需要進(jìn)行合并操作。因?yàn)閴KB的大小介于256KB和512KB之間，所以將塊B插入到512KB的空閑鏈表中，結(jié)果如圖3所示。

　　接著，塊C被釋放。此時(shí)根據(jù)物理塊鏈表可知與塊C鄰接的為塊B和塊F,并且二塊都為空閑狀態(tài)。將塊B和塊F從512KB空閑塊鏈表中刪除，再將三塊合并成一個(gè)700KB的塊（用F表示）插入到1 024KB的空閑鏈表中，結(jié)果如圖4所示。

　　最后當(dāng)塊A被釋放時(shí)，塊A與塊F合并成1 024KB的塊，回到最初只有1 024KB空閑區(qū)的情況。

　　4 結(jié) 論

　　動(dòng)態(tài)內(nèi)存管理一直是計(jì)算機(jī)領(lǐng)域的一項(xiàng)重要技術(shù)。動(dòng)態(tài)內(nèi)存管理給用戶提供了比較大的自由度，用戶可以從系統(tǒng)分區(qū)中申請(qǐng)內(nèi)存塊，也可以從用戶內(nèi)存區(qū)申請(qǐng)內(nèi)存塊。這樣增加了系統(tǒng)的靈活性，同時(shí)也限制了大量碎片產(chǎn)生的可能（在不頻繁刪除建立系統(tǒng)內(nèi)存分區(qū)的前提下）。也增加了部分c 代碼的可移植性。