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

1、實(shí)驗(yàn)報(bào)告四動態(tài)分區(qū)分配算法班級 學(xué)號 姓名一、實(shí)驗(yàn)?zāi)康膭討B(tài)分區(qū)分配是根據(jù)進(jìn)程的實(shí)際需要，動態(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ī)一臺，編譯環(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)算法中，是從已建立好的數(shù)組中順序查找，直至找

2、到第一個(gè)大小能滿足要求的空閑分區(qū)為止，然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nè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ū)，從中劃出一塊與請求大小相等的內(nèi)存空間分配給作業(yè)，為實(shí)現(xiàn)本算法，設(shè)置一個(gè)全局變量 f,來控制循環(huán)查找，當(dāng)f%N=0時(shí)，f=0;若查找結(jié)束都不能找到一 個(gè)滿足要求的分區(qū)，則此次內(nèi)存分配失敗

3、。（ 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è)。四、 源程序#include <stdio.h>#define L 10typedef struct LNodeint startaddress;int size;int state;LNode;LNodePL=0,128,0,200,256,0,500,512,0,1500,1600,0,5000,150,0;int N=5; i

4、nt 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ū)的大小： ");scanf("%d",&m);for(i=0;i<N;i+) if(Pi.size<m) continue;else if(Pi.size=m) Pi

5、.state=1;l=1;break; elsePN.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(); elseprintf(" 沒有可以分配的地址空間 n"); void CirFirst() int l=0,m,t=0;printf("n 輸入請求分配分區(qū)的大?。?&q

6、uot;);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.size=m;Pf.state=1;l=1;N+;f+;break; if(l=1)

7、printf(" 地址成功分配nn");printf(" 地址分配成功后的狀態(tài)： n");print(); else printf(" 沒有可以分配的地址空間 n"); void Worst()int i,t=0,l=0,m;int aL;printf("n 輸入請求分配分區(qū)的大?。?"); 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;

8、 break; else ai=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");printf(" 地址分配成功后的狀態(tài)： n"); print(); elsepri

9、ntf(" 沒有可以分配的地址空間 n"); void Best() int i,t=0,l=0,m;int aL;printf("n 輸入請求分配分區(qū)的大?。?"); 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(l=0)for(i=0;i<N;i+)if(ai!=0)t=i;for(i=0;i<N;i+) i

10、f(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"）; void main（） int k=0;printf（" 動態(tài)分區(qū)分配算法： "）;while

11、(k!=5)printf("n主菜單printf（"n1 、 首次適應(yīng)算法n2、 循環(huán)首次適應(yīng)算法"）;printf（"n3 、 最壞適應(yīng)算法n4、 最佳適應(yīng)算法 "）;printf("n5 、退出 n");printf(" 請選擇算法： ");scanf("%d",&k);switch(k) case 1:printf("n 初始狀態(tài)為： n");print();First();continue;case 2:printf("n 初始狀態(tài)為： n

12、");print();printf("n 初始狀態(tài)為：n");CirFirst();print();continue;Best();case 3: continue;printf("n 初始狀態(tài)為：n");case 5:print();break;Worst();default:printf("選擇錯誤，請重新選擇。n");continue;case 4:五、運(yùn)行結(jié)果運(yùn)行效果如下所示，首先列出主菜單，如圖1所示，初始狀態(tài)為已定義好的數(shù)組，首先采用首次適應(yīng)算法，輸入的分區(qū)大小為 500,從圖2可以看出，第一個(gè)滿足條件的起始地址

13、 為500,分區(qū)大小為512,分配后，起始地址為 500的狀態(tài)設(shè)為1,將其余的分區(qū)令開辟空 間存儲。cl *ClXTTBfffl Debu®f enqu. exe0分區(qū)& 00128256眄51Z5 001600000150狀態(tài)地址分配成功后的狀態(tài);分區(qū)128狀態(tài)e(1)(2)然后采用算法2即循環(huán)首次適應(yīng)算法，在第一次的分配作業(yè)大小為1500,則系統(tǒng)就會將地址為1500的分區(qū)進(jìn)行分配，剩余分區(qū)令開辟空間，如圖3所示；在第二次的分配作業(yè)大小為200,依照算法可得，地址為200的分區(qū)復(fù)合要求，則將其分配給作業(yè)， 如圖4所示。% *C:ftB0LJn Debugenqu- exe氤

14、 *C= 付盼月,Debug'feifcqu. cxe請選擇算法：2狀態(tài)為;分區(qū)12S狀態(tài)Q初始狀態(tài)為e始地址分區(qū)128256.09500S901&0019108015000000 0 0 0 fl 0 0狀態(tài) 0 G 11 Q 0 0SBss分分求助1求分配分區(qū)的大小、200 及分配也址分配成功后的狀態(tài): 一一分區(qū)狀態(tài)5901工5E A15。121S0g -C:ebuf enqu. exeEQ態(tài)址 枕地 臺臺京 0 蘇巳區(qū)8分125的 150015Q1210056狀態(tài)Q 111 00 0工圭:：203QB0地址分配成功后的狀態(tài):分區(qū)12S狀態(tài)0Hi_M 0 0 B 0 0 0

15、 0 0 0 5 0-030500115001150B1201S00(4)cW "C= 付冊月 DebugTFenqu. exe請選擇算法：4初始狀態(tài)為： 起始地址分區(qū)01281SARM-H勘后的優(yōu)格分區(qū)決忐1292Q6 500 15U20121萌13F)(5)1111前人請求分配分區(qū)的大?。?0 斛t成功分配地址分配成功后的狀態(tài)回臺地址0>00 >00 L5B8S0B8 1000 )000 W0 汨20分區(qū)才優(yōu)態(tài)128020015Q01158B1201Q10Q56130110(6)在算法3中，采用的是最壞適應(yīng)算法，設(shè)分配作業(yè)大小為20,由初始狀態(tài)可知，分區(qū)最大且沒有被分

16、配的起始地址為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所示。*C:MJebucXf enqu. exe-ey n ao t法r匿次應(yīng)應(yīng) ，適首適適一 次壞量出一 首f:瞽再退六、實(shí)驗(yàn)總結(jié)在一開始老師布置這次的實(shí)驗(yàn)題目時(shí)， 自己根本不知道要干什么， 因?yàn)樵谏险n時(shí)對動態(tài) 分區(qū)分配這節(jié)內(nèi)容不是太了解， 所以在上機(jī)時(shí)不知道如何下手， 后來，將本章內(nèi)容反復(fù)的看 了幾遍之后，終于有了自己的思路。在程序的編寫過程中，我并沒有按照書上所說的定義了雙向鏈表來實(shí)現(xiàn)各種算法的執(zhí) 行，我只簡單的運(yùn)用了結(jié)構(gòu)體數(shù)組，通過這種方法比較容