實(shí)驗(yàn)四動(dòng)態(tài)分區(qū)分配算法實(shí)驗(yàn)報(bào)告及程序

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)報(bào)告四 動(dòng)態(tài)分區(qū)分配算法班級(jí) 學(xué)號(hào) 姓名 一、 實(shí)驗(yàn)?zāi)康膭?dòng)態(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間，而在分配時(shí)，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。在本實(shí)驗(yàn)中運(yùn)用了四種分配算法，分別是1.首次適應(yīng)算法，2.循環(huán)首次適應(yīng)算法，3.最壞適應(yīng)算法4.最佳適應(yīng)算法。二、 實(shí)驗(yàn)環(huán)境普通的計(jì)算機(jī)一臺(tái)，編譯環(huán)境Microsoft Visual C+ 6.0三、 算法思想1 數(shù)據(jù)結(jié)構(gòu)（1） 分區(qū)開始地址startaddress（2） 分區(qū)大小size（3） 分區(qū)狀態(tài)state2 功能介紹（1） 首次適應(yīng)算法在首次適應(yīng)算法中，是從已

2、建立好的數(shù)組中順序查找，直至找到第一個(gè)大小能滿足要求的空閑分區(qū)為止，然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空間令開辟一塊新的地址，大小為原來(lái)的大小減去作業(yè)大小，若查找結(jié)束都不能找到一個(gè)滿足要求的分區(qū)，則此次內(nèi)存分配失敗。（2） 循環(huán)首次適應(yīng)算法該算法是由首次適應(yīng)算法演變而成，在為進(jìn)程分配內(nèi)存空間時(shí)，不再是每次都從第一個(gè)空間開始查找，而是從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直至找到第一個(gè)能滿足要求的空閑分區(qū)，從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)，為實(shí)現(xiàn)本算法，設(shè)置一個(gè)全局變量f，來(lái)控制循環(huán)查找，當(dāng)f%N=0時(shí)，f=0；若查找結(jié)束都不能找到一個(gè)滿足要

3、求的分區(qū)，則此次內(nèi)存分配失敗。（3） 最壞適應(yīng)算法最壞適應(yīng)分配算法是每次為作業(yè)分配內(nèi)存時(shí)，掃描整個(gè)數(shù)組，總是把能滿足條件的，又是最大的空閑分區(qū)分配給作業(yè)。（4） 最佳適應(yīng)算法最壞適應(yīng)分配算法是每次為作業(yè)分配內(nèi)存時(shí)，掃描整個(gè)數(shù)組，總是把能滿足條件的，又是最小的空閑分區(qū)分配給作業(yè)。四、 源程序?qū)Ｐ?專注-專業(yè)#include <stdio.h>#define L 10typedef struct LNode int startaddress; int size; int state; LNode;LNode PL=0,128,0,200,256,0,500,512,0,1500,160

4、0,0,5000,150,0;int N=5; int f=0;void print() int i; printf("起始地址 分區(qū) 狀態(tài)n"); for(i=0;i<N;i+) printf("%3d %8d %4dn",Pi.startaddress,Pi.size,Pi.state);void First() int i,l=0,m; printf("n輸入請(qǐng)求分配分區(qū)的大?。?quot;); scanf("%d",&m); for(i=0;i<N;i+) if(Pi.size<m) con

5、tinue; else if(Pi.size=m) Pi.state=1; l=1; break; else PN.startaddress=Pi.startaddress+m; PN.size=Pi.size-m; Pi.size=m;Pi.state=1; l=1; N+; break; if(l=1|i<N) printf("地址成功分配nn"); printf("地址分配成功后的狀態(tài)：n"); print(); else printf("沒有可以分配的地址空間n"); void CirFirst() int l=0,m,

6、t=0; printf("n輸入請(qǐng)求分配分區(qū)的大?。?quot;); scanf("%d",&m); while(f<N) if(Pf.size<m) f=f+1; if(f%N=0) f=0;t=1; continue; if(Pf.size=m && Pf.state!=1) Pf.state=1; l=1;f+; break; if(Pf.size>m && Pf.state!=1) PN.startaddress=Pf.startaddress+m; PN.size=Pf.size-m; Pf.si

7、ze=m; Pf.state=1; l=1; N+; f+; break; if(l=1) printf("地址成功分配nn"); printf("地址分配成功后的狀態(tài)：n"); print(); else printf("沒有可以分配的地址空間n"); void Worst() int i,t=0,l=0,m; int aL; printf("n輸入請(qǐng)求分配分區(qū)的大小："); scanf("%d",&m); for(i=0;i<N;i+) ai=0; if(Pi.size<

8、m) continue; else if(Pi.size=m) Pi.state=1; l=1; break; elseai=Pi.size-m; if(l=0) for(i=0;i<N;i+) if(ai!=0) t=i; for(i=0;i<N;i+) if(ai!=0 && ai>at) t=i; PN.startaddress=Pt.startaddress+m; PN.size=Pt.size-m; Pt.size=m;Pt.state=1; l=1; N+; if(l=1|i<N) printf("地址成功分配nn");

9、printf("地址分配成功后的狀態(tài)：n"); print(); else printf("沒有可以分配的地址空間n"); void Best() int i,t=0,l=0,m; int aL; printf("n輸入請(qǐng)求分配分區(qū)的大?。?quot;); scanf("%d",&m); for(i=0;i<N;i+) ai=0; if(Pi.size<m) continue; else if(Pi.size=m) Pi.state=1; l=1; break; elseai=Pi.size-m; if(

10、l=0) for(i=0;i<N;i+) if(ai!=0) t=i; for(i=0;i<N;i+) if(ai!=0 && ai<at) t=i; PN.startaddress=Pt.startaddress+m; PN.size=Pt.size-m; Pt.size=m;Pt.state=1; l=1; N+; if(l=1|i<N) printf("地址成功分配nn"); printf("地址分配成功后的狀態(tài)：n"); print(); else printf("沒有可以分配的地址空間n&quo

11、t;); void main() int k=0; printf("動(dòng)態(tài)分區(qū)分配算法："); while(k!=5) printf("n主菜單");printf("n1、首次適應(yīng)算法n2、循環(huán)首次適應(yīng)算法"); printf("n3、最壞適應(yīng)算法n4、最佳適應(yīng)算法"); printf("n5、退出n"); printf("請(qǐng)選擇算法："); scanf("%d",&k); switch(k) case 1: printf("n初始狀態(tài)為：

12、n"); print(); First(); continue; case 2: printf("n初始狀態(tài)為：n"); print(); CirFirst(); continue; case 3: printf("n初始狀態(tài)為：n"); print(); Worst(); continue; case 4: printf("n初始狀態(tài)為：n"); print(); Best(); continue; case 5: break; default:printf("選擇錯(cuò)誤，請(qǐng)重新選擇。n"); 五、 運(yùn)行

13、結(jié)果運(yùn)行效果如下所示，首先列出主菜單，如圖1所示，初始狀態(tài)為已定義好的數(shù)組，首先采用首次適應(yīng)算法，輸入的分區(qū)大小為500，從圖2可以看出，第一個(gè)滿足條件的起始地址為500，分區(qū)大小為512，分配后，起始地址為500的狀態(tài)設(shè)為1，將其余的分區(qū)令開辟空間存儲(chǔ)。 (1) (2)然后采用算法2即循環(huán)首次適應(yīng)算法，在第一次的分配作業(yè)大小為1500，則系統(tǒng)就會(huì)將地址為1500的分區(qū)進(jìn)行分配，剩余分區(qū)令開辟空間，如圖3所示；在第二次的分配作業(yè)大小為200，依照算法可得，地址為200的分區(qū)復(fù)合要求，則將其分配給作業(yè)，如圖4所示。 (3) (4) (5) (6)在算法3中，采用的是最壞適應(yīng)算法，設(shè)分配作業(yè)大小為

14、20，由初始狀態(tài)可知，分區(qū)最大且沒有被分配的起始地址為5000，大小為150，分配后的狀態(tài)如圖5所示。在算法4中，采用的是最優(yōu)適應(yīng)算法，設(shè)分配大小為10，由初始狀態(tài)可知，分區(qū)最小且沒有被分配的起始地址為1000，大小為12，分配后的狀態(tài)如圖6所示。最后選擇5，則結(jié)束程序的運(yùn)行，效果如圖7所示。(7) 六、 實(shí)驗(yàn)總結(jié)在一開始老師布置這次的實(shí)驗(yàn)題目時(shí)，自己根本不知道要干什么，因?yàn)樵谏险n時(shí)對(duì)動(dòng)態(tài)分區(qū)分配這節(jié)內(nèi)容不是太了解，所以在上機(jī)時(shí)不知道如何下手，后來(lái)，將本章內(nèi)容反復(fù)的看了幾遍之后，終于有了自己的思路。在程序的編寫過(guò)程中，我并沒有按照書上所說(shuō)的定義了雙向鏈表來(lái)實(shí)現(xiàn)各種算法的執(zhí)行，我只簡(jiǎn)單的運(yùn)用了結(jié)構(gòu)體數(shù)組，通過(guò)這種方法比較容易理解與編寫，在這幾個(gè)算法中，只有循環(huán)首次適應(yīng)算法