拆半記憶法對(duì)最佳適應(yīng)算法的優(yōu)化

黎波

(宜賓學(xué)院計(jì)算機(jī)與信息工程學(xué)院，四川宜賓644007)

拆半記憶法對(duì)最佳適應(yīng)算法的優(yōu)化

黎波

(宜賓學(xué)院計(jì)算機(jī)與信息工程學(xué)院，四川宜賓644007)

最佳適應(yīng)算法（BF）是內(nèi)存空閑塊分配的一種常用算法，現(xiàn)行BF算法的空閑塊查詢(xún)方法不當(dāng)從而導(dǎo)致工作效率低下.使用拆半法替代原有的BF算法在空閑塊查詢(xún)時(shí)所采用的線性順序比較法，同時(shí)增加分配記憶功能，對(duì)BF算法進(jìn)行優(yōu)化并加強(qiáng)算法功能，從而直接改善內(nèi)存的分配效率，對(duì)提高系統(tǒng)吞吐量起到積極的促進(jìn)作用.

內(nèi)存分配；最佳適應(yīng)算法；折半法；拆半記憶

當(dāng)前的多任務(wù)系統(tǒng)操作系統(tǒng)，進(jìn)程的數(shù)量多，內(nèi)存的使用頻率高、各進(jìn)程在內(nèi)存中駐留時(shí)間長(zhǎng)短不一，從而釋放內(nèi)存的時(shí)間先后不同，導(dǎo)致內(nèi)存空閑塊（以下簡(jiǎn)稱(chēng)空閑塊）在內(nèi)存中呈現(xiàn)出間隔不連續(xù)的狀態(tài)[1-2].因此，空閑塊的分配算法旨在對(duì)進(jìn)程的內(nèi)存請(qǐng)求進(jìn)行分配，使得進(jìn)程能獲得空閑塊而運(yùn)行，且分配算法的優(yōu)劣將直接影響內(nèi)存的分配效率高低[3].

在常見(jiàn)的空閑塊分配算法中，最佳適應(yīng)算法BF（Best Fit）最常用也最具代表性，其效率和性能表現(xiàn)良好.但是，隨著操作系統(tǒng)功能的不斷擴(kuò)展，系統(tǒng)中運(yùn)行的進(jìn)程數(shù)急劇增加，對(duì)內(nèi)存空閑塊的請(qǐng)求頻率和數(shù)量也大幅度提高，于是，進(jìn)程對(duì)內(nèi)存空閑塊的高需求和最佳適應(yīng)算法的內(nèi)存分配低效率之間的矛盾愈加凸顯，進(jìn)程的請(qǐng)求得不到及時(shí)的響應(yīng)而不能高效運(yùn)行.因此，需要優(yōu)化現(xiàn)有的最佳適應(yīng)算法在內(nèi)存塊分配方法，彌補(bǔ)其不足，以提高BF算法工作效率，且達(dá)到提高內(nèi)存的分配效率和系統(tǒng)的吞吐量的目的.

1 最佳適應(yīng)算法BF的缺陷分析

欲分析最佳適應(yīng)算法BF的缺陷，必須首先敘述最佳適應(yīng)算法BF的工作原理[4]，即操作系統(tǒng)將內(nèi)存的空閑塊按照容量從小到大的順序（B1＜B2＜B2＜B4＜B5＜ B6＜…Bn）鏈接起來(lái)，形成空閑塊隊(duì)列，如圖1所示.當(dāng)進(jìn)程請(qǐng)求內(nèi)存空閑塊時(shí)，操作系統(tǒng)從該空閑塊隊(duì)列首部向后開(kāi)始查詢(xún)各空閑塊，如果容量滿(mǎn)足便進(jìn)行分配，不滿(mǎn)足則訪問(wèn)下一個(gè)空閑塊，直到找到一個(gè)滿(mǎn)足其容量需求的空閑塊后便分配給進(jìn)程，當(dāng)訪問(wèn)到最后一個(gè)空閑塊都不能滿(mǎn)足進(jìn)程的要求時(shí)，則內(nèi)存分配失敗，對(duì)于后續(xù)所有進(jìn)程的空閑塊請(qǐng)求，方法相同，分配過(guò)程如圖2所示.

圖1 空閑塊隊(duì)列圖

圖2 空閑塊分配圖

據(jù)圖2所示，當(dāng)有新的內(nèi)存塊申請(qǐng)Ask出現(xiàn)時(shí)，系統(tǒng)便通過(guò)空閑塊隊(duì)列的頭指針head找到空閑塊隊(duì)列，然后將Ask和B1比較，如果Ask＜=B1，那么就將B1分配給ask對(duì)應(yīng)的進(jìn)程，如果不滿(mǎn)足，即Ask＞B1，則沿著隊(duì)列向后查詢(xún)B2是否滿(mǎn)足Ask＜=B2，如果滿(mǎn)足則分配，不滿(mǎn)足則繼續(xù)向后推進(jìn)，直到找到一個(gè)空閑塊滿(mǎn)足為止，然后分配，否則到最后一個(gè)空閑塊都不滿(mǎn)足其大小，那么分配失敗.

綜上所示，最佳適應(yīng)算法BF存在嚴(yán)重缺陷，如下所述：

1）空閑塊查詢(xún)時(shí)采用了“線性順序比較”的方法，查詢(xún)效率低.

每個(gè)進(jìn)程提出空閑塊請(qǐng)求Ask時(shí)，操作系統(tǒng)都從隊(duì)列的頭部開(kāi)始向后查詢(xún)比較空閑塊的大小，即：從頭到尾依次的、線性的查詢(xún)比較每一個(gè)空閑塊是否滿(mǎn)足ASK的大小，造成時(shí)間的浪費(fèi)，效率較低.

2）后進(jìn)程不參考前進(jìn)程分配，即缺乏記憶功能，所有進(jìn)程的請(qǐng)求都從隊(duì)列頭部開(kāi)始，依次向后線性查詢(xún)，導(dǎo)致了查詢(xún)的重復(fù)性，浪費(fèi)了大量的時(shí)間及計(jì)算機(jī)資源，導(dǎo)致了內(nèi)存分配效率低下.

尤其當(dāng)前操作系統(tǒng)中出現(xiàn)進(jìn)程數(shù)量眾多的情況，缺陷1和2的愈加明顯.所以，對(duì)最佳適應(yīng)算法進(jìn)行優(yōu)化改善，才能從算法本身提高內(nèi)存的分配效率，從而提供操作系統(tǒng)的吞吐量.

2 采用“拆半記憶法”對(duì)最佳適應(yīng)算法進(jìn)行優(yōu)化

由于最佳適應(yīng)算法BF存在上述的1和2的明顯缺陷，經(jīng)過(guò)全面的分析和深入的研究，在空閑塊的查詢(xún)分配時(shí)，采用折半法代替原本的線性比較法；同時(shí)，結(jié)合內(nèi)存塊分配記憶，即后進(jìn)程須參考前進(jìn)程的分配位置，再?zèng)Q定其向前查詢(xún)或者向后查詢(xún)，即查詢(xún)的方向，較好地提高空閑塊的查詢(xún)速度，提升空閑塊的工作效率，實(shí)現(xiàn)了對(duì)最佳適應(yīng)算法的優(yōu)化改進(jìn).具體的優(yōu)化改良措施如下所述：

第一，最小基本塊原則節(jié)約了內(nèi)存空閑塊，避免了內(nèi)存的浪費(fèi).

空閑塊以空間從小到大（容量遞增）的方式組成空閑塊隊(duì)列，同時(shí)遵循最小基本塊原則，最小基本塊的容量為Size，即當(dāng)分配后余下的空間大于Size時(shí)，剩余的空間將作為新的空閑塊插入到隊(duì)列中合適的位置；否則，將整個(gè)空閑塊全部分配給進(jìn)程.此舉能最大限度地節(jié)約內(nèi)存，不會(huì)出現(xiàn)過(guò)多的內(nèi)存浪費(fèi)現(xiàn)象.

第二，拆半法提高了空閑塊的查詢(xún)?cè)L問(wèn)效率.

當(dāng)進(jìn)程提出內(nèi)存請(qǐng)求Ask時(shí)，不再采用從隊(duì)列頭部Head向尾部線性順序比較法查詢(xún)內(nèi)存空閑塊，而是采用折半法高效地完成內(nèi)存空閑塊的查找[5].

1）將Ask和空閑塊隊(duì)列的中間空閑塊mid進(jìn)行比較，其中Mid=INT((low+high)/2)，如果該空閑塊大于等于進(jìn)程請(qǐng)求的容量，即Ask＜=med，說(shuō)明該空閑塊滿(mǎn)足Ask的需要，那么直接將mid空閑塊分配給Ask，完成分配.

當(dāng)Ask＞mid，即空閑塊太小不能滿(mǎn)足Ask的需要，則直接忽略1～mid間前半段所有空閑塊的比較，甩掉了一半的空閑塊進(jìn)行比較，實(shí)現(xiàn)了拆半.再以mid為開(kāi)頭到隊(duì)列尾部之間的空閑塊為新隊(duì)列，low=mid，med=INT ((low+high)/2)，在新隊(duì)列中，繼續(xù)采用折半比較法進(jìn)行比較，依次類(lèi)推，直到找到滿(mǎn)足Ask＜=med的空閑塊為止，完成分配，工作原理如圖3所示.

圖3 拆半記憶法優(yōu)化原理圖

從上述拆半法的工作原理可見(jiàn)，每次比較都能甩掉隊(duì)列中50%的空閑塊，極大地節(jié)約了空閑塊隊(duì)列的訪問(wèn)時(shí)間，提高了訪問(wèn)效率，從而提高了內(nèi)存塊的分配效率.

2）后續(xù)的空閑塊請(qǐng)求必須根據(jù)上次作業(yè)分配的位置，向隊(duì)列尾查找比較，其方法仍采用折半比較法，找到滿(mǎn)足其大小的空閑塊，完成分配.

3）當(dāng)后續(xù)作業(yè)在分配的過(guò)程中，已經(jīng)沒(méi)有空閑塊滿(mǎn)足其需求，此時(shí)，立刻進(jìn)行內(nèi)存中空閑塊的串聯(lián)組隊(duì)，串聯(lián)時(shí)仍然以空閑塊容量從小到大（即容量遞增）的方式組成空閑塊隊(duì)列.

算法圖見(jiàn)圖3.其中l(wèi)ow代表的是空閑隊(duì)列的第一個(gè)空閑塊，而high代表的是最后一個(gè)隊(duì)列，mid則表示折半法的中間點(diǎn)，通過(guò)以上算法，當(dāng)Ask(i)＜=mid且mid-Ask(i)＞=size，滿(mǎn)足分配條件，從mid中劃出Ask(i)所需要的空間給進(jìn)程，多余的size作為空閑塊回收，完成分配；繼續(xù)判斷有無(wú)新請(qǐng)求，如果有，則需要參考上次的分配點(diǎn)mid，如果Aski+1＞=mid，則以mid為隊(duì)首high為隊(duì)尾（后半段）進(jìn)行拆半查詢(xún)，反之，以low為隊(duì)首mid為隊(duì)尾（前半段）進(jìn)行拆半查詢(xún).如果整個(gè)隊(duì)列中都沒(méi)有空閑塊滿(mǎn)足Aski+1的需要，則重新組織隊(duì)列，再按照同樣的方法折半比較，該算法用偽碼表示如下：

3 優(yōu)化后的最佳適應(yīng)算法性能分析

在查詢(xún)空閑分區(qū)的時(shí)候，采用順序查找法和折半查找法，所耗的時(shí)間不同[6]，如果空閑塊數(shù)都為n，那么，順序查找法的時(shí)間消耗為k1=(n+1)/2，而折半記憶法可以表示成：

從以上結(jié)論可以看出，k2遠(yuǎn)小于k1，尤其是空閑塊數(shù)多，即n的值很大的情況下，折半法的效率比順序查找的效率高很多，如表1所示．

表1 算法對(duì)比表

從表1可以看出，采用折半記憶法的性能遠(yuǎn)優(yōu)于順序比較法，因此，在最佳適應(yīng)算法的基礎(chǔ)上，采用折半記憶法查詢(xún)空閑塊，優(yōu)化后的最佳適應(yīng)算法能極大地提高了內(nèi)存空閑塊的分配效率，對(duì)增加系統(tǒng)的吞吐量有明顯的改善效果.

4 總結(jié)

采用拆半記憶法優(yōu)化后的最佳適應(yīng)算法（BF），在查詢(xún)空閑塊時(shí)，不再采用順序比較，而采用折半法提高了查詢(xún)效率；同時(shí)后續(xù)進(jìn)程申請(qǐng)空閑塊的時(shí)候增加了記憶功能，后續(xù)進(jìn)程以前導(dǎo)進(jìn)程的位置為端點(diǎn)形成新的空閑塊隊(duì)列，進(jìn)一步縮小了查詢(xún)隊(duì)列長(zhǎng)度.更大程度地提高了比較查詢(xún)的效率，從根本上降低了最佳適應(yīng)算法原來(lái)的順序比較法較大的時(shí)間開(kāi)銷(xiāo)，加快了空閑塊的分配速度，從而提高了內(nèi)存的工作效率.

[1]程顯波.計(jì)算機(jī)的內(nèi)存管理與優(yōu)化[J].遼陽(yáng)石油化工高等專(zhuān)科學(xué)校學(xué)報(bào),1999(3):51-54.

[2]瞿朝成,祁建宏,海波,等.動(dòng)態(tài)分區(qū)管理中空閑分區(qū)的鄰接性判斷及合并算法研究[J].電腦編程技巧與維護(hù),2012(24):7-8.

[3]吳冰.計(jì)算機(jī)內(nèi)存管理的優(yōu)化[J].電腦技術(shù),1995,(2):41-43.

[4]湯小丹,湯子贏.計(jì)算機(jī)操作系統(tǒng)[M].第三版.西安:西安電子科技大學(xué)出版社,2007.

[5]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京:清華大學(xué)出版社, 1997.

[6]張瓊聲,劉冬萍.操作系統(tǒng)內(nèi)核內(nèi)存分配算法的分析與性能評(píng)價(jià)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2007(1):40-44.

【編校：王露】

Application of Half and Memory Method to Optimize Best Fit Algorithm

LI Bo
(Computer and Information Engineering Faculty,Yibin University,Yibin,Sichuan 644007,China)

Best Fit algorithm(BF)is a common way to cope with memory allocation;the current BF is inefficient especially in free memory block inquiring.Half and Memory method was applied to replace the linear query of BF in memory block requirement, moreover,distribution and memory strategy was added in the half and memory method to strengthen the function,which strengthens the efficiency in memory allocation and promotes the throughput of operating system.

memory allocation;best fit algorithm;half;half and memory algorithm

TP301.6

A

1671-5365(2014)06-0123-03

2013-05-15修回：2014-04-04

黎波(1977-)，男，講師，碩士研究生，研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)

時(shí)間：2014-04-16 16:51

http://www.cnki.net/kcms/detail/51.1630.Z.20140416.1651.009.html