資源描述:
《存儲管理—動態(tài)異長存儲資源分配算法》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、存儲管理一動態(tài)異長存儲資源分配算法一、設(shè)計目的理解動態(tài)異長存儲分區(qū)資源管理,掌握所需數(shù)據(jù)結(jié)構(gòu)和管理程序,了解各種存儲分配算法的優(yōu)點和缺點。二、設(shè)計內(nèi)容(1)分析UNIX最先適應(yīng)(FirstFit,FF)存儲分配算法,即map數(shù)據(jù)結(jié)構(gòu)、存儲分配函數(shù)mall00()和存儲釋放函數(shù)mfreeO,找出與算法冇關(guān)的成分。(2)修改上述與算法有關(guān)的成分,使其分別體現(xiàn)BF(BestFit,最佳適應(yīng))分配原則和WE(WorstFit,最環(huán)適應(yīng))分配原則。三、設(shè)計準備(理論、技術(shù))1?最先適應(yīng)(FirstFit,FF)算法指對于存儲屮請命令,選取滿足屮請長度要求且起始地址最小的空閑區(qū)域。在實現(xiàn)時,可以將系統(tǒng)屮所
2、有的空閑區(qū)域按照起始地址由小到大的次序依次記錄于空閑區(qū)域表中。當(dāng)進程中請存儲空間時,系統(tǒng)由表的頭部開始查找,取滿足要求的第一個表口。如果表口所對應(yīng)的區(qū)域長度恰好與申請的區(qū)域長度相同,則將該區(qū)域全部分配給申請者,否則將該區(qū)域分割為兩部分,一部分的長度與申請長度相同,將其分配給屮請者;另一部分的長度為原長度與分配長度Z差,將其記錄在空閑區(qū)威表屮2?最佳適應(yīng)(BestFit,BF)算法是為了克服最先適應(yīng)算法缺點提出的。它在分配吋取滿足申請要求且長度最小的空間區(qū)域。在實現(xiàn)時,可以將系統(tǒng)中所冇的空閑區(qū)域按照長度出小到大的次序依次記錄丁空閑區(qū)域表中。當(dāng)進程屮請存儲空間時,系統(tǒng)由表的頭部開始杳找,取滿足耍求
3、的第一個表目。3?最壞適應(yīng)(WorstFit,WF)算法是為了克服最佳適應(yīng)算法的缺點而提出的。它在分配吋取滿足申請要求且長度最大的空閑區(qū)域。在實現(xiàn)時,可以將系統(tǒng)中所冇的空閑區(qū)域按照長度出小到大的次序依次記錄于空閑區(qū)域表中。當(dāng)進程屮請存儲空間時,取第一個表目。4.程序設(shè)計技術(shù)分析按題目題目首先對存儲分配表進行初始化;然后對用戶輸入的請求和釋放,按照動態(tài)更新存儲分配表,并將每次更新之后的存儲分配表在屏幕上顯示出來動態(tài)分區(qū)分配需要解決三個問題:A.對于請求表中的要求內(nèi)存長度,從可用表或口由鏈尋找出合適的空閑區(qū)域分配程序。B.分配空閑區(qū)后更新口由鏈或可用表。C.進程或作業(yè)釋放內(nèi)存資源時,合并相鄰空閑區(qū)
4、并刷新可用表。四、設(shè)計過程(設(shè)計思想、代碼實現(xiàn))1?設(shè)計思想(1)分析最先適應(yīng)算法,定義H13P數(shù)據(jù)結(jié)構(gòu);設(shè)置整形變量存儲存儲資源表信息structmap{intmaddr;intmsize;};(2)分析UNIX最先適應(yīng)存儲分配算法編寫最佳適應(yīng)算法BF_malloc();遍歷鏈表,取滿足申請要求月?長度最小的空間區(qū)域for(bpp=bp;bpp->m_size;bpp++){//最佳適應(yīng)if(bpp-〉m_size>二size&&bpp->m_sizem_addr;s=bpp->m_sizc;bp=bpp;}}(3)根據(jù)最好適應(yīng)算法編寫最壞適應(yīng)算法WF_malloc()
5、,主要代碼如下:for(bpp=bp;bpp->m_sizc;bpp++){//最壞適應(yīng)if(bpp->m_size>s){a=bpp->m_addr;s=bpp->size;bp二bpp;}}(4)存儲釋放函數(shù)mfreeO;被釋放的存儲區(qū)域與前合并條件:if(bp>mp&&(bp-1)->m_addr+(bp-1)->m_size二二a)與后合并條件:if(a+size==bp->m_addr&&bp->m_size)無合并條件:if(size)(5)showMap()方法顯示存儲資源表;(6)存儲分配表進行初始化方法init()2?代碼實現(xiàn)ttifdefHAVE_CONFTG_H#incl
6、udc//分配布局函數(shù)ttendif#include#includenclude#dcfincMAPSIZE100structmap//存儲資源表結(jié)構(gòu){intmaddr;intmsize;};structmapmap[MAPSIZE];//存儲資源表//BF存儲分配函數(shù)intBFmalloc(structmap*mp,intsize){registerinta,s;registerstructmap*bp,*bpp;for(bp=mp;bp->m_size;bp++){if(bp->m_size>=size){a
7、=bp->m_addr;s二bp-〉m_sizc;for(bpp二bp;bpp->m_size;bpp++){//最佳適應(yīng)if(bpp-〉m_size>二size&&bpp->m_sizem_addr;s=bpp->m_size;bp=bpp;}}bp->m_addr+=size;if((bp->m_size-二二size)=0)do{bp++;(bp-1)->m_addr=