存儲(chǔ)管理—動(dòng)態(tài)異長(zhǎng)存儲(chǔ)資源分配算法

1、存儲(chǔ)管理動(dòng)態(tài)異長(zhǎng)存儲(chǔ)資源分配算法一、設(shè)計(jì)目的理解動(dòng)態(tài)異長(zhǎng)存儲(chǔ)分區(qū)資源管理， 掌握所需數(shù)據(jù)結(jié)構(gòu)和管理程序， 了解各種 存儲(chǔ)分配算法的優(yōu)點(diǎn)和缺點(diǎn)。二、設(shè)計(jì)內(nèi)容(1) 分析UNIX最先適應(yīng)(First Fit,FF )存儲(chǔ)分配算法，即map數(shù)據(jù)結(jié)構(gòu)、 存儲(chǔ)分配函數(shù) malloc() 和存儲(chǔ)釋放函數(shù) mfree() ，找出與算法有關(guān)的成分。(2) 修改上述與算法有關(guān)的成分，使其分別體現(xiàn) BF( Best Fit, 最佳適應(yīng)) 分配原則和 WF(Worst Fit ，最環(huán)適應(yīng) ) 分配原則。三、設(shè)計(jì)準(zhǔn)備(理論、技術(shù))1. 最先適應(yīng)(First Fit , FF)算法指對(duì)于存儲(chǔ)申請(qǐng)命令，選取滿(mǎn)足申請(qǐng)長(zhǎng)度要

2、求且起始地址最小的空閑區(qū)域。在實(shí)現(xiàn)時(shí)，可以將系統(tǒng)中所有的空閑區(qū)域按照起始地址由小到大的次序依次記錄 于空閑區(qū)域表中。 當(dāng)進(jìn)程申請(qǐng)存儲(chǔ)空間時(shí)， 系統(tǒng)由表的頭部開(kāi)始查找， 取滿(mǎn)足要 求的第一個(gè)表目。 如果表目所對(duì)應(yīng)的區(qū)域長(zhǎng)度恰好與申請(qǐng)的區(qū)域長(zhǎng)度相同， 則將 該區(qū)域全部分配給申請(qǐng)者， 否則將該區(qū)域分割為兩部分， 一部分的長(zhǎng)度與申請(qǐng)長(zhǎng) 度相同，將其分配給申請(qǐng)者； 另一部分的長(zhǎng)度為原長(zhǎng)度與分配長(zhǎng)度之差， 將其記 錄在空閑區(qū)域表中2. 最佳適應(yīng)(Best Fit , BF)算法是為了克服最先適應(yīng)算法缺點(diǎn)提出的。 它在分配時(shí)取滿(mǎn)足申請(qǐng)要求且長(zhǎng)度最 小的空間區(qū)域。 在實(shí)現(xiàn)時(shí)，可以將系統(tǒng)中所有的空閑區(qū)域按照長(zhǎng)度

3、由小到大的次 序依次記錄于空閑區(qū)域表中。 當(dāng)進(jìn)程申請(qǐng)存儲(chǔ)空間時(shí)， 系統(tǒng)由表的頭部開(kāi)始查找， 取滿(mǎn)足要求的第一個(gè)表目。3. 最壞適應(yīng)(Worst Fit ，WF算法是為了克服最佳適應(yīng)算法的缺點(diǎn)而提出的。 它在分配時(shí)取滿(mǎn)足申請(qǐng)要求且長(zhǎng) 度最大的空閑區(qū)域。 在實(shí)現(xiàn)時(shí)， 可以將系統(tǒng)中所有的空閑區(qū)域按照長(zhǎng)度由小到大 的次序依次記錄于空閑區(qū)域表中。當(dāng)進(jìn)程申請(qǐng)存儲(chǔ)空間時(shí)，取第一個(gè)表目。4. 程序設(shè)計(jì)技術(shù)分析按題目題目首先對(duì)存儲(chǔ)分配表進(jìn)行初始化；然后對(duì)用戶(hù)輸入的請(qǐng)求和釋放， 按照動(dòng)態(tài)更新存儲(chǔ)分配表，并將每次更新之后的存儲(chǔ)分配表在屏幕上顯示出來(lái)動(dòng)態(tài)分區(qū)分配需要解決三個(gè)問(wèn)題：A.對(duì)于請(qǐng)求表中的要求內(nèi)存長(zhǎng)度，從可用

4、 表或自由鏈尋找出合適的空閑區(qū)域分配程序。 B .分配空閑區(qū)后更新自由鏈或可用 表。C.進(jìn)程或作業(yè)釋放內(nèi)存資源時(shí)，合并相鄰空閑區(qū)并刷新可用表。四、設(shè)計(jì)過(guò)程(設(shè)計(jì)思想、代碼實(shí)現(xiàn))1 .設(shè)計(jì)思想(1)分析最先適應(yīng)算法，定義 map數(shù)據(jù)結(jié)構(gòu)；設(shè)置整形變量存儲(chǔ)存儲(chǔ)資源表信息 struct mapint m_addr;int m_size;(2) 分析UNIX最先適應(yīng)存儲(chǔ)分配算法編寫(xiě)最佳適應(yīng)算法BF_malloc();遍歷鏈表，取滿(mǎn)足申請(qǐng)要求且長(zhǎng)度最小的空間區(qū)域 for(bpp=bp;bpp-m_size;bpp+)/ 最佳適應(yīng)if(bpp-m_size=size&bpp-m_sizem_addr;s=

5、bpp-m_size; bp=bpp;(3) 根據(jù)最好適應(yīng)算法編寫(xiě)最壞適應(yīng)算法WF_malloc()，主要代碼如下：for(bpp=bp;bpp-m_size;bpp+)/ 最壞適應(yīng)if(bpp-m_sizes) a=bpp-m_addr; s=bpp-size; bp=bpp;(4) 存儲(chǔ)釋放函數(shù) mfree(); 被釋放的存儲(chǔ)區(qū)域 與前合并條件 :if(bpmp&(bp-1)-m_addr+(bp-1)-m_size=a) 與后合并條件 :if(a+size=bp-m_addr&bp-m_size) 無(wú)合并條件 :if(size)(5) showMap() 方法顯示存儲(chǔ)資源表;(6) 存儲(chǔ)

6、分配表進(jìn)行初始化方法 init()2. 代碼實(shí)現(xiàn)#ifdef HAVE_CONFIG_H #include/ 分配布局函數(shù)#endif#include #include #include#define MAPSIZE 100 struct map/ 存儲(chǔ)資源表結(jié)構(gòu)int m_addr;int m_size;struct map mapMAPSIZE;/ 存儲(chǔ)資源表/BF 存儲(chǔ)分配函數(shù)int BF_malloc(struct map *mp,int size) register int a,s;register struct map *bp,*bpp; for(bp=mp;bp-m_size;b

7、p+) if(bp-m_size=size) a=bp-m_addr;s=bp-m_size;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)dobp+; (bp-1)-m_addr=bp-m_addr; while(bp-1)-m_size=bp-m_size) return(a);return(1);/WF 存儲(chǔ)分配函數(shù)int WF_malloc(struct map *mp,in

8、t size)register int a,s;register struct map *bp,*bpp; for(bp=mp;bp-m_size;bp+) if(bp-m_size=size) a=bp-m_addr; s=bp-m_size; for(bpp=bp;bpp-m_size;bpp+)/ 最壞適應(yīng) if(bpp-m_sizes) a=bpp-m_addr; s=bpp-size;bp=bpp;bp-m_addr+=size;if(bp-size-=size)=0)dobp+; (bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_siz

9、e);return(a); return(-1);/ 存儲(chǔ)釋放函數(shù)void mfree(struct map *mp,int aa,int size) register struct map *bp;register int t;register int a;a=aa; for(bp=mp;bp-m_addrm_size!0;bp+) if(bpmp&(bp-1)-m_addr+(bp-1)-m_size=a)/ 與前合并 (bp-1)-m_size+=size;(bp-1)-m_size+=bp-m_size; while(bp-m-size) bp+;(bp-1)-m_addr=bp-m_

10、addr; (bp-1)-m_size=bp-size; else if(a+size=bp-m_addr&bp-m_size)/ 與后合并 bp-m_addr-=size; bp-m_size+=size;else if(size)do/ 無(wú)合并 t=bp-m_addr; bp-m_addr=a; a=t; t=bp-m_size; bp-m_size=size; bp+; while(size=t);void init()/ 初始化該鏈表的指針 struct map *bp;int addr,size;int i=0; bp=map; coutplease input starting a

11、ddr and total sizeaddrsize;bp-m_addr=addr;bp-m_size=size;(+bp)-m_size=0;/ 表尾void showMap()/ 顯示存儲(chǔ)資源表int i=0;struct map *bp;bp=map;coutnCurrent memory map.m_size!=0)coutm_addrttm_sizeendl; bp+; printf(n);void main()int a,s;/ 地址，表長(zhǎng)int c;/ 選擇算法int i;/ 選擇需求init();coutPlease input,b for BF,w for WF:c;dosh

12、owMap();coutPlease input,1 for request,2 for release,0 for exit:i;switch(i)case 1:coutPlease input sizes; if(c=b) a=BF_malloc(map,s);else a=WF_malloc(map,s);if(a=-1)coutrequest cant be satisfiedendl; elsecoutalloc memory at address:asize:sendl; break;case 2:coutPlease input addr and sizeas;mfree(map

13、,a,s);break;case 0: exit(O);while(1);五、設(shè)計(jì)結(jié)果并分析根據(jù)提示輸入存儲(chǔ)資源表地址和表長(zhǎng)；測(cè)試數(shù)據(jù)：0, 100;選擇適應(yīng)算法：最好適應(yīng)算法輸入 b,最壞適應(yīng)算法輸入w;測(cè)試數(shù)據(jù)：b 初始化存儲(chǔ)資源表；顯示地址和表長(zhǎng) 選擇要求1.請(qǐng)求，2.釋放，0.退出；測(cè)試數(shù)據(jù)：1； 輸入表長(zhǎng)；測(cè)試數(shù)據(jù)：20； 分配存儲(chǔ)器地址，長(zhǎng)度；測(cè)試數(shù)據(jù)：0, 20；顯示更新之后的存儲(chǔ)分配表 繼續(xù)選擇要求；測(cè)試數(shù)據(jù)：1； 輸入表長(zhǎng)；測(cè)試數(shù)據(jù)：15； 分配存儲(chǔ)器地址，長(zhǎng)度；測(cè)試數(shù)據(jù)：20, 15；顯示更新之后的存儲(chǔ)分配表 如圖所示：lts|ubuntu:S JesdPlease inp

14、ut starting addr mnd total 51 re;0,100 Please nputrb for BFw for WF:biCurrent reh*ry nap.*Please Input Please xnput at lot prioryrl for requestfor releasefor exit:1 size:Z0at 園去Current ncnory nap. Please input Please input alloc meiroryf1 for request,2 for relsase0 for eitt:1 size:15at address:20,st

15、ze:15繼續(xù)選擇要求；測(cè)試數(shù)據(jù)： 輸入地址和表長(zhǎng)；測(cè)試數(shù)據(jù) 繼續(xù)選擇要求；測(cè)試數(shù)據(jù)： 輸入地址和表長(zhǎng)；測(cè)試數(shù)據(jù) 如圖所示：Current renory nap. k35fi52；16, 10；顯示更新之后的存儲(chǔ)分配表2；27, 5;顯示更新之后的存儲(chǔ)分配表Please input 11 for request for release.,6 for extt:2 Please input ddr and size:1G,1O匚 urrent menory ng* *1014Please Input ,i for request,2 for release.O for ex11;Z Please Input addr and size:27j5CurrentnenoryE$p* .*C565PleiS Input11forrequest,； for release for ett:|六、系統(tǒng)的結(jié)構(gòu)、原理框圖和