存儲(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)命令，選取滿足申請(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)始查找， 取滿足要 求的第一個(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í)取滿足申請(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)始查找， 取滿足要求的第一個(gè)表目。3. 最壞適應(yīng)(Worst Fit ，WF算法是為了克服最佳適應(yīng)算法的缺點(diǎn)而提出的。 它在分配時(shí)取滿足申請(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ì)用戶輸入的請(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();遍歷鏈表，取滿足申請(qǐng)要求且長(zhǎng)度最小的空間區(qū)域 for(bpp=bp;bpp->m_size;bpp+)/ 最佳適應(yīng)if(bpp->m_size>=size&&am

5、p;bpp->m_size<s) a=bpp->m_addr;s=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_size>s) a=bpp->m_addr; s=bpp->size; bp=bpp;(4) 存儲(chǔ)釋放函數(shù) mfree(); 被釋放的存儲(chǔ)區(qū)域 與前合并條件 :if(bp>mp&&(bp-1)->m_addr+(bp-1)->m_si

6、ze=a) 與后合并條件 :if(a+size=bp->m_addr&&bp->m_size) 無(wú)合并條件 :if(size)(5) showMap() 方法顯示存儲(chǔ)資源表;(6) 存儲(chǔ)分配表進(jìn)行初始化方法 init()2. 代碼實(shí)現(xiàn)#ifdef HAVE_CONFIG_H #include<config.h>/ 分配布局函數(shù)#endif#include<stdio.h> #include<stdlib.h> #include<iostream.h>#define MAPSIZE 100 struct map/ 存儲(chǔ)資

7、源表結(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;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_size>=s

8、ize&&bpp->m_size<s) a=bpp->m_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,int size)register int a,s;register struc

9、t 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_size>s) 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-

10、1)->m_size=bp->m_size);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_addr<=a&&bp->m_size!0;bp+) if(bp>mp&&(bp-1)->m_addr+(bp-1)->m_size=a)/ 與前合并 (bp-1)->m

11、_size+=size;(bp-1)->m_size+=bp->m_size; while(bp->m-size) bp+;(bp-1)->m_addr=bp->m_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-

12、>m_size; bp->m_size=size; bp+; while(size=t);void init()/ 初始化該鏈表的指針 struct map *bp;int addr,size;int i=0; bp=map; cout<<"please input starting addr and total size"<<endl; cin>>addr>>size;bp->m_addr=addr;bp->m_size=size;(+bp)->m_size=0;/ 表尾void showMap

13、()/ 顯示存儲(chǔ)資源表int i=0;struct map *bp;bp=map;cout<<"nCurrent memory map."<<endl; while(bp->m_size!=0)cout<<"<"<<bp->m_addr<<"tt"<<bp->m_size<<">"<<endl; bp+; printf("n");void main()int a,s;/

14、地址，表長(zhǎng)int c;/ 選擇算法int i;/ 選擇需求init();cout<<"Please input,b for BF,w for WF:"<<endl;cin>>c;doshowMap();cout<<"Please input,1 for request,2 for release,0 for exit:"<<endl;cin>>i;switch(i)case 1:cout<<"Please input size"<<endl

15、;cin>>s; if(c='b') a=BF_malloc(map,s);else a=WF_malloc(map,s);if(a=-1)cout<<"request can't be satisfied"<<endl; elsecout<<"alloc memory at address:"<<a<<"size:"<<s<<endl; break;case 2:cout<<"Please i

16、nput addr and size"<<endl; cin>>a>>s;mfree(map,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) <0100>選擇要求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； 輸

17、入表長(zhǎng)；測(cè)試數(shù)據(jù)：15； 分配存儲(chǔ)器地址，長(zhǎng)度；測(cè)試數(shù)據(jù)：20, 15；顯示更新之后的存儲(chǔ)分配表 如圖所示：llsgubuntu./hepPl ease input starting addr mnd total 5 tre;01160Please nputrb for SFrw for WF:bCurrent nehory nap.*keiee>please input F1 for request,z for releasefor exit:1 Please nput size:20attoc memory at a<i(Jress:e&Current ocnory n

18、ap.<2«80>Please input f1 For request,2 for release,fl for exit:1 Please input sire：15illoc memory at address:20,size:isCurrent r>enory hap.«4fi5>繼續(xù)選擇要求；測(cè)試數(shù)據(jù)：2；輸入地址和表長(zhǎng)；測(cè)試數(shù)據(jù)16, 10；顯示更新之后的存儲(chǔ)分配表 繼續(xù)選擇要求；測(cè)試數(shù)據(jù)：2；輸入地址和表長(zhǎng)；測(cè)試數(shù)據(jù)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* .*<161&><275>C565>PleiS Input1