實驗4主存空間的分配與回收

1、實驗四 主存空間的分配和回收1. 目的和要求1.1. 實驗?zāi)康挠酶呒壵Z言完成一個主存空間的分配和回收程序，以加深對動態(tài)分區(qū)分配方式及其算法的理解。1.2. 實驗要求/采用連續(xù)分配方式之動態(tài)分區(qū)分配存儲管理，使用首次適應(yīng)算法、/最佳適應(yīng)算法2種算法完成設(shè)計。（1）*設(shè)計一個作業(yè)申請隊列以及作業(yè)完成后的釋放順序，實現(xiàn) 主存的分配和回收。采用分區(qū)說明表進(jìn)行。（2）或在程序運行過程，由用戶指定申請與釋放。（3）設(shè)計一個空閑區(qū)說明表，以保存某時刻主存空間占用情況。把空閑區(qū)說明表的變化情況以及各作業(yè)的申請、釋放情況顯示。提示:（1）動態(tài)分區(qū)（可變分區(qū)方式）是按作業(yè)需要的主存空間大小來分割分區(qū)的。當(dāng)要裝入一

2、個作業(yè)時，根據(jù)作業(yè)需要的主存容量查看是否有足夠的空閑空間，若有,則按需分配，否則，作業(yè)無法裝入。假定內(nèi)存大小為256KB空閑區(qū)說明表格式為：起始地址一一指出空閑區(qū)的起始地址；長度一一一個連續(xù)空閑區(qū)的長度；狀態(tài)有兩種狀態(tài)，一種是“已分配”狀態(tài)；另一種是“空表目”狀態(tài)，表 示該表項目前沒有使用。（2）采用首次適應(yīng)算法分配回收內(nèi)存空間。 運行時，輸入一系列分配請求和回收 請求。要求能接受來自鍵盤的空間申請及釋放請求， 能顯示分區(qū)分配及回收后的內(nèi)存布 局情況。2、源程序代碼#include ""#include <>#include <>#include &

3、quot;"#define getjcb(type) (type*)malloc(sizeof(type)#define getsub(type) (type*)malloc(sizeof(type)#define NULL 0int num,num2; d:n",i);p=getjcb(JCB);printf("n輸入作業(yè)名:");scanf("%s",&p->name);printf("n輸入作業(yè)的大小:");scanf("%d",&p->size);printf

4、("n輸入作業(yè)所需運行時間：")；scanf("%d",&p->ntime);p_>state='w：p->link=NULL;firstsort(); /*調(diào)用 sort 函數(shù) */printf("n 按任一鍵繼續(xù)n");getch();void input2() | /* 建立要回收區(qū)域的函數(shù) */JCB *k;int has;q=getjcb(JCB);printf("n 輸入?yún)^(qū)域名(作業(yè)名):");scanf("%s", &q->name)

5、;p=as;while(p!=NULL)if(strcmp(p->name,q->name)=O) /*在已分配作業(yè)隊列中尋找 */q->addr=p->addr;q->size=p->size;has=1; /*輸入作業(yè)名存在標(biāo)志位 */if(p=as) as=p->link; /*在已分配作業(yè)隊列中刪除該作業(yè)*/elsek=as;while(k->link!=p) k=k->link;k->link=k->link->link; /*刪除 */printf(" 輸出該作業(yè)首地址:%dn",q->

6、;addr);printf(”輸出該作業(yè)大?。篸nn",q->size);q->link=NULL;break;elsep=p->link; has=O; /*輸入作業(yè)名不存在標(biāo)志*/if(has=0)printf("n輸入作業(yè)名錯誤！請重新輸入!n");input2();void init_sub()/*初始化空閑分區(qū)表*/r=getsub(SUB);strcpy(r->name,"one"); r->addr=5; r->size=10; r->state='n'sub=r;s=ge

7、tsub(SUB);strcpy(s->name,"two"); s->addr=20; s->size=120; s->state='n'sub->link=s;r=s;s=getsub(SUB);strcpy(s->name,"three"); s->addr=160; s->size=40; s->state='n'r->link=s;r=s;s=getsub(SUB);strcpy(s->name,"four"); s->a

8、ddr=220; s->size=10; s->state='n'r->link=s;r=s;s=getsub(SUB);strcpy(s->name,"five"); s->addr=250; s->size=20; s->state='n'r->link=s;void disp() /*空閑分區(qū)表的顯示函數(shù) */printf("tt 分區(qū)首地址長度狀態(tài)n");r=sub;while(r!=NULL)printf("tt %stt%dtt%dtt%cn"

9、,r->name,r->addr,r->size,r->state);r=r->link;printf("n");void disp2() /*顯示已分配內(nèi)存的作業(yè)表函數(shù) */printf("tt 作業(yè)名首地址長度狀態(tài)n");p=as;while(p!=NULL)printf("tt %stt%dtt%dtt%cn",p->name,p->addr,p->size,p->state);p=p_>link;printf("nn");void perfit(J

10、CB *pr) /* 最佳適應(yīng)作業(yè)分區(qū) assign*/SUB *k;r=sub;while(r!=NULL)if(r->size)>(pr->size)&&(r->state='n') /*有空閑分區(qū)大于作業(yè)大小的情況 */pr->addr=r->addr;r->size-=pr->size;r->addr+=pr->size;if(r=sub) sub=r->link; /*刪除空閑分區(qū) */elses=sub;while(s->link!=r) s=s->link;s->l

11、ink=s->link->link; /*刪除空閑分區(qū) */flag=1; /*分配成功標(biāo)志位置1*/q=pr;lastsort(); /*插入已分配作業(yè)隊列*/n",p->name,r->name,pr->addr);break;else if(r->size)=(pr->size)&&(r->state='n') /*有空閑分區(qū)等于作業(yè)大小的情況 */pr->addr=r->addr;flag=1; /*分配成功標(biāo)志位置 1*/q=pr;lastsort();/*插入已分配作業(yè)隊列*/s=

12、sub; /*空閑分區(qū)已完成分配，應(yīng)刪除*/while(s->link!=r) s=s->link;s->link=s->link->link;/* 刪除空閑分區(qū) */printf(”作業(yè) $的分區(qū)為%s,首地址為 d.n",p->name,r->name,pr->addr);break;elser=r->link; flag=O;if(flag=0) /*作業(yè)過大的情況*/printf("作業(yè)$長度過大，內(nèi)存不足，分區(qū)分配出錯！n",p->name);is=1;void firstfit(JCB *pr

13、)/*首次適應(yīng)作業(yè)分區(qū)*/SUB *k;r=sub; /*從空閑表頭開始尋找*/while(r!=NULL)if(r->size)>(pr->size)&&(r->state='n') /*有空閑分區(qū)大于作業(yè)大小的情況*/pr->addr=r->addr;r->size-=pr->size;r->addr+=pr->size;flag=1; /*分配成功標(biāo)志位置1*/q=pr;q_>state='r：lastsort(); /*插入已分配作業(yè)隊列*/printf(" 作業(yè) $的分

14、區(qū)為%s,首地址為 %d.n",p->name,r->name,pr->addr);break;else if(r->size)=(pr->size)&&(r->state='n') /*有空閑分區(qū)等于作業(yè)大小的情況*/pr->addr=r->addr;flag=1; /*分配成功標(biāo)志位置 1*/q=pr;lastsort();/*插入已分配作業(yè)隊列*/s=sub; /*空閑分區(qū)已完成分配，應(yīng)刪除*/while(s->link!=r) s=s->link;s->link=s->li

15、nk->link;/* 刪除空閑分區(qū) */printf(" 作業(yè) $的分區(qū)為%s,首地址為 %d.n",p->name,r->name,pr->addr);break;elser=r->link; flag=O;if(flag=O) /*作業(yè)過大的情況*/printf(”作業(yè)$長度過大，內(nèi)存不足，分區(qū)分配出錯 ！n",p->name);is=1;void cyclefit(JCB *pr) /*循環(huán)首次適應(yīng)作業(yè)分區(qū)*/SUB *k;r=cur; /*從當(dāng)前指針開始尋找*/while(r!=NULL)if(r->size)&

16、gt;(pr->size)&&(r->state='n') /*有空閑分區(qū)大于作業(yè)大小的情況*/pr->addr=r->addr;r->size-=pr->size;r->addr+=pr->size;flag=1;/*分配成功標(biāo)志位置1*/cur=r;/*更新當(dāng)前指針*/q=pr;q_>state='r：lastsort();/*插入已分配作業(yè)隊列*/printf("作業(yè) $的分區(qū)為%s,首地址為 %d.n",p->name,r->name,pr->addr);

17、break;else if(r->size)=(pr->size)&&(r->state='n') /*有空閑分區(qū)等于作業(yè)大小的情況*/pr->addr=r->addr;flag=1; /* 分配成功標(biāo)志位置 1*/cur=r;q=pr;lastsort();/* 插入已分配作業(yè)隊列*/s=sub; /*空閑分區(qū)已完成分配，應(yīng)刪除*/while(s->link!=r) s=s->link;s->link=s->link->link;/* 刪除空閑分區(qū) */printf("作業(yè) $的分區(qū)為%s,

18、首地址為 %d.n",p->name,r->name,pr->addr);break;elser=r->link;if(r=NULL)/*當(dāng)前指針為空時，重新由空閑區(qū)隊列之首尋找 */k=cur; /*cur=sub;r=cur;if(k=r) /*cur=k;break;flag=0; /*if(flag=0)/*作保存當(dāng)前指針用*/又回到開始的指針時，確定為沒有空間滿足要求*/分配不成功標(biāo)志*/作業(yè)過大的情況*/printf（”作業(yè)$長度過大，內(nèi)存不足，分區(qū)分配出錯！n",p->name）;is=1;void less_to_more()

19、/*把分區(qū)按大小從小到大排序 */ r=sub;sub=NULL;while(r!=NULL)s=r;r=s->link;s->link=NULL;sort_sub(); /* 調(diào)用排序函數(shù)*/reclperfit(JCB *pr)SUB *k;/*r=sub;while(r!=NULL)if(r->addr=(pr->addr)+(pr->size)pr->size+=r->size;最佳適應(yīng)回收區(qū)域，按分區(qū)大小排列*/s=sub;isdown=1; /*下鄰標(biāo)志位置1*/while(s!=NULL)if(s->addr)+(s->siz

20、e)=(pr->addr) /*有下鄰又有上鄰*/s->size+=pr->size;k=sub;while(k->link!=r) k=k->link;k->link=k->link->link;上鄰標(biāo)志位置1*/isup=1;/*break;elses=s->link; isup=O; /*上鄰標(biāo)志位置0*/if(isup=0)/*有下鄰無上鄰*/r->addr=pr->addr;r->size=pr->size;break;elser=r->link; isdown=0; /*下鄰標(biāo)志位置0*/if(is

21、down=0)/*區(qū)域無下鄰*/s=sub;while(s!=NULL)if(s->addr)+(s->size)=(pr->addr) /*無下鄰但有上鄰*/s->size+=pr->size;isup=1;break;else s=s->link; isup=0;/*上鄰標(biāo)志位置0*/上鄰標(biāo)志位置1*/if(isup=0)/*k=getsub(SUB); /*無下鄰且無上鄰*/重新生成一個新的分區(qū)結(jié)點*/strcpy(k->name,pr->name);k_>addr=pr->addr;k->size=pr->size

22、;k->state='n'r=sub;while(r!=NULL)if(r->size)>(k->size) /*按分區(qū)大小排列，回收區(qū)域插在合適的位置*/if(r=sub) /*第一個空閑分區(qū)大于回收區(qū)域的情況*/ k->link=r; sub->link=k; else/ s=sub;while(s->link!=r) s=s->link;k->link=r;s->link=k;break;else r=r->link;if(r=NULL) /*所有空閑分區(qū)都大于回收區(qū)域的情況*/s=sub;while(s-

23、>link!=NULL) s=s->link;s->link=k;k->link=NULL; printf("n 區(qū)域s己回收.",pr->name);void reclfirst(JCB *pr)/*首次適應(yīng)與循環(huán)首次適應(yīng)區(qū)域回收*/SUB *k;r=sub;while(r!=NULL)if(r->addr=(pr->addr)+(pr->size) /*回收區(qū)域有下鄰 */pr->size+=r->size;s=sub;isdown=1; /*下鄰標(biāo)志位置 1*/while(s!=NULL)if(s->a

24、ddr)+(s->size)=(pr->addr) /*s->size+=pr->size;有下鄰又有上鄰*/k=sub;while(k->link!=r) k=k->link;k->link=k->link->link;上鄰標(biāo)志位置1*/isup=1;/*break;elses=s->link; isup=O; /*上鄰標(biāo)志位置0*/if(isup=0)/*有下鄰無上鄰*/r->addr=pr->addr;r->size=pr->size;elsebreak;if(isdown=0)r=r->link;

25、 isdown=0; /*下鄰標(biāo)志位置0*/*區(qū)域無下鄰*/s=sub;while(s!=NULL)if(s->addr)+(s->size)=(pr->addr) /*無下鄰但有上鄰*/s->size+=pr->size;isup=1;/*上鄰標(biāo)志位置1*/break;else s=s->link; isup=0;if(isup=0)/*k=getsub(SUB); /*上鄰標(biāo)志位置0*/無下鄰且無上鄰*/重新生成一個新的分區(qū)結(jié)點*/strcpy(k->name,pr->name);k_>addr=pr->addr;k->si

26、ze=pr->size;k->state='n'r=sub;while(r!=NULL)if(r->addr)>(k->addr) /*按分區(qū)首地址排列，回收區(qū)域插在合適的位置*/if(r=sub) /*第一個空閑分區(qū)首址大于回收區(qū)域的情況*/ k->link=r; sub->link=k; elses=sub;/ while(s->link!=r) s=s->link;k->link=r;s->link=k;break;else r=r->link;if(r=NULL) /*所有空閑分區(qū)的首址都大于回收區(qū)

27、域首址的情況*/s=sub;while(s->link!=NULL) s=s->link;s->link=k;k->link=NULL;printf("n 區(qū)域s己回收.",pr->name);void print()顯示空閑分區(qū)n");printf("ttt 2.分配作業(yè)n");printf("ttt 3.回收作業(yè)n");printf("ttt 0.返回菜單n");printf("ttt請選擇你要的操作:");firstfitf()Jelse print

28、f("n作業(yè)沒有全部被分配內(nèi)存.n");getch(); system("cls"); firstfitf(); break;case 3:system("cls");disp2();printf("nn按任意鍵進(jìn)行區(qū)域回收.");printf("n");while(as!=NULL)getch();input2();printf("按任意鍵繼續(xù).")；getch();printf("n");/ reclfirst(q);getch();printf(&q

29、uot;ntt回收后的空閑分區(qū)表n");disp();printf("ntt已分配作業(yè)表n");disp2();printf("n繼續(xù)回收.(Enter)");printf("n所有已分配作業(yè)已完成r)；printf("nPress any key to return.");getch();system("cls");firstfitf();break;system("cls");firstfitf();break;cyclefirstf();else printf(&quo

30、t;n作業(yè)沒有全部被分配內(nèi)存.n");getch();system("cls");cyclefirstf();break;case '3':system("cls");disp2();printf("nn按任意鍵進(jìn)行區(qū)域回收.")；while(as!=NULL)getch();printf("n");input2();printf("按任意鍵繼續(xù).")；getch();printf("n");reclfirst(q);getch();printf(&

31、quot;ntt回收后的空閑分區(qū)表n");disp();printf("ntt已分配作業(yè)表n");disp2();printf("n繼續(xù)回收.(Enter)");printf("n所有已分配作業(yè)已完成r)；getch();system("cls");cyclefirstf();break;case 'O':break;default:getch();system("cls");cyclefirstf();break;perfitf() ;else printf("n作業(yè)

32、沒有全部被分配內(nèi)存.n");getch();system("cls");perfitf();break;case '3':system("cls");disp2();printf("nn按任意鍵進(jìn)行區(qū)域回收.");while(as!=NULL)getch();printf("n");input2();printf(”按任意鍵繼續(xù).")；getch();printf("n");reclperfit(q);getch();printf("ntt回收后的空

33、閑分區(qū)表n");disp();printf("ntt已分配作業(yè)表n");disp2();printf("n繼續(xù)回收.(Enter)");printf("n所有已分配作業(yè)已完成r)；getch();system("cls");perfitf();break;case 'O':break;default:getch();system("cls");perfitf();break;void menu()/* 菜單函數(shù)*/int i;printf("nnntt*n")

34、;printf("ttt主存空間的分配與回收演示n");printf("tt*n");>printf("tttnn");printf("ttt 1.首次適應(yīng)算法n");printf("ttt 2.循環(huán)首次適應(yīng)算法nprintf("ttt 3.最佳適應(yīng)算法n");printf("ttt 0.退出n");printf("ttt請選擇你要的操作："）；switch(getchar()");case '1':system(

35、"cls");firstfitf();getch();system("cls"); menu();break;case '2':system("cls");cyclefirstf();getch();system("cls"); / menu();break;case 3:system("cls");perfitf();getch();system("cls");menu();break;case 'O':break;default:getch();system("cls");menu(); break;void main() /* 主函數(shù) */init_sub();print();menu();八、執(zhí)行結(jié)果和結(jié)果分析1進(jìn)入操作界面如下：課件'計算機操作系統(tǒng)嗓作垂統(tǒng)實螫1實螫住存主存空間的分配與回收演示KXHKHlOOIBKMHXHiH HN*弭HXH耗 KHiCIOIXZHK