淺談內(nèi)存分配方式 避免內(nèi)存浪費(fèi)問(wèn)題

說(shuō)到內(nèi)存的分配方式，就不得不提連續(xù)分配方式。這種方式是指為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間，它曾被廣泛的用于20世紀(jì)60~70年代的OS中，至今仍被使用。連續(xù)分配方式可以進(jìn)一步分為單一連續(xù)分配、固定分配方式、動(dòng)態(tài)分區(qū)分配以及動(dòng)態(tài)重定位分配。

單一連續(xù)分配，是最簡(jiǎn)單的一種存儲(chǔ)管理方式，只能用于單用戶、單任務(wù)的OS中。它將內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)僅提供給OS使用，除了系統(tǒng)區(qū)之外的內(nèi)存空間全部都是用戶區(qū)，用戶區(qū)通常放在高址部分，系統(tǒng)區(qū)則放在低址部分。

固定分區(qū)分配，這是在多道程序環(huán)境下最簡(jiǎn)單的存儲(chǔ)管理方式。將內(nèi)存分成多個(gè)固定大小的區(qū)域，每個(gè)區(qū)域只裝入一道作業(yè)，便能允許幾道作業(yè)并發(fā)運(yùn)行。有空閑分區(qū)時(shí)，就能從后備隊(duì)列選擇一個(gè)裝入該分區(qū)。

固定分區(qū)分配有兩種劃分分區(qū)的方式：分區(qū)大小相等，不過(guò)由于缺乏靈活性，程序過(guò)小會(huì)浪費(fèi)內(nèi)存，過(guò)大則無(wú)法運(yùn)行。不過(guò)在控制多個(gè)相同的對(duì)象的場(chǎng)合還說(shuō)可以使用的;分區(qū)大小不等，則是將分區(qū)劃分時(shí)含有多個(gè)較小的分區(qū)、適量的中等分區(qū)以及少量大分區(qū)，可根據(jù)程序大小分配適當(dāng)?shù)姆謪^(qū)。

我們?yōu)榱吮阌趦?nèi)存分配，通常將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，表項(xiàng)報(bào)告各分區(qū)的初始地址、大小及狀態(tài)。固定分區(qū)是最早的多道程序的存儲(chǔ)管理方式，現(xiàn)在雖然過(guò)時(shí)了，不過(guò)在某些控制多個(gè)相同對(duì)象的系統(tǒng)中還會(huì)使用。

動(dòng)態(tài)分區(qū)分配，這是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。主要涉及分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法和分區(qū)的分配與回收這三個(gè)問(wèn)題。

分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)，主要用來(lái)描述空閑分區(qū)和已分配分區(qū)的情況，為分配提供依據(jù)。常用的數(shù)據(jù)結(jié)構(gòu)有兩種形式：空閑分區(qū)表，用于記錄每個(gè)空閑分區(qū)的全靠，每個(gè)空閑分區(qū)占一個(gè)表目;空閑分區(qū)鏈，也是為了方便使用空閑分區(qū)，在每個(gè)分區(qū)的起始位置和尾部添加前向和后向指針。

分區(qū)分配算法，將一個(gè)新罪業(yè)裝入內(nèi)存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一空閑分區(qū)給該作業(yè)。目前大致有五種分配算法。

首次適應(yīng)算法，將空閑分區(qū)鏈以地址遞增的次序鏈接，分配內(nèi)存時(shí)從頭開(kāi)始查找，只要找到一塊空閑區(qū)域滿足作業(yè)大小要求，就將其分配，余下的空閑分區(qū)仍留在空閑鏈。由于此算法傾向利用低址部分的空閑分區(qū)，所以低址部分會(huì)不斷被劃分，留下許多難以利用的空閑分區(qū)。

循環(huán)首次適應(yīng)算法，在首次適應(yīng)算法的基礎(chǔ)上，不會(huì)每次都從鏈?zhǔn)组_(kāi)始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開(kāi)始查找。需要設(shè)置起始查尋指針，指示下一次起始查詢的空閑分區(qū)，并采用循環(huán)查找方式。這種算法雖然減少了查找空閑分區(qū)時(shí)的開(kāi)銷，但是會(huì)缺乏大的空閑分區(qū)。

最佳適應(yīng)算法，總是能把滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。為實(shí)現(xiàn)此算法，需要將空閑分區(qū)按從小到大的順序形成一空閑分區(qū)鏈。但是，每次分割所留下的剩余部分總是最小的，最后會(huì)留下許多難以利用的小空閑區(qū)。

最壞適應(yīng)算法，會(huì)掃描整個(gè)空閑分區(qū)表，總是挑選最大的空閑分區(qū)分割給作業(yè)，要求空閑區(qū)按從大到小排列。優(yōu)點(diǎn)是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，同時(shí)查找效率最高。缺點(diǎn)是會(huì)使存儲(chǔ)器缺乏大的空閑分區(qū)。

以上四種算法被稱為順序搜索法，而下面這個(gè)算法被稱為分類搜索法。

快速適應(yīng)算法，先將空閑分區(qū)按容量大小分類，每一類單獨(dú)設(shè)立空閑分區(qū)鏈表。同時(shí)在內(nèi)存中設(shè)立一張管理索引表，每一表項(xiàng)對(duì)應(yīng)一種空閑分區(qū)類型。而且空閑分區(qū)的分類是根據(jù)進(jìn)程常用的空間大小劃分的，方便分配空閑分區(qū)。此算法的優(yōu)點(diǎn)是查找效率高，而且不會(huì)對(duì)分區(qū)產(chǎn)生分割，能保留大的分區(qū)，也不會(huì)產(chǎn)生內(nèi)存碎片。缺點(diǎn)是分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開(kāi)銷較大。另外此算法分配時(shí)以進(jìn)程為單位，一個(gè)分區(qū)屬于一個(gè)進(jìn)程，在分配的一個(gè)分區(qū)中，或多或少存在一定的浪費(fèi)?？臻e分區(qū)劃分越細(xì)，浪費(fèi)越嚴(yán)重。

分區(qū)的分配與回收，系統(tǒng)利用某種分配算法從空閑分區(qū)表找到所需大小的分區(qū)，裝入空閑分區(qū)的作業(yè)占用空間后，剩余的部分很小則不再切割，反之則將其劃分出去。當(dāng)作業(yè)或者進(jìn)程運(yùn)行完畢后釋放內(nèi)存，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈表中找到相應(yīng)的插入點(diǎn)，將其與相鄰空閑區(qū)合并。