1、實驗三使用動態(tài)分區(qū)分配方式的模擬1、實驗?zāi)康牧私鈩討B(tài)分區(qū)分配方式中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法，并進一步加深對動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程的理解。2、實驗內(nèi)容(1) 用 C 語言分別實現(xiàn)采用首次適應(yīng)算法和最佳適應(yīng)算法的動態(tài)分區(qū)分配過程alloc( )和回收過程 free( )。其中，空閑分區(qū)通過空閑分區(qū)鏈來管理：在進行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。(2) 假設(shè)初始狀態(tài)下，可用的內(nèi)存空間為 640KB ，并有下列的請求序列：?作業(yè) 1 申請 130KB。?作業(yè) 2 申請 60KB。?作業(yè) 3 申請 100KB。?作業(yè) 2 釋放 60KB。?作業(yè) 4 申請 200KB。?作業(yè) 3 釋放

2、 100KB。?作業(yè) 1 釋放 130KB。?作業(yè) 5 申請 140KB。?作業(yè) 6 申請 60KB。?作業(yè) 7 申請 50KB。?作業(yè) 6 釋放 60KB。請分別采用首次適應(yīng)算法和最佳適應(yīng)算法，對內(nèi)存塊進行分配和回收，要求每次分配和回收后顯示出空閑分區(qū)鏈的情況。程序代碼 C 語言實現(xiàn)#include<stdio.h>#include<stdlib.h>struct node / 空閑分區(qū)鏈結(jié)點的定義node *before;node *after;int size;int address;int state;node L;struct usenodeusenode *

3、next;int num;int add;int size;U,*n;void Init()/ 空閑分區(qū)鏈的初始化node *p;p=(node *)malloc(sizeof(node);p->before=&L;p->after=NULL;p->size=640;p->address=0;p->state=0;L.after=p;L.before=NULL;L.size=0;U.next=NULL;n=&U;node *search(int a)node *p=L.after;if(p=NULL)printf(" 沒有空閑的區(qū)域!&q

4、uot;);p=NULL;return p;elsewhile(p!=NULL && a>p->size)p=p->after;if(p=NULL)printf(" 沒有找到合適的空閑空間!");p=NULL;return p;elsereturn p;void recovery(int a,int b)/內(nèi)存回收算法node *c,*s,*r=L.after;node *d=L.after,*e;usenode *k=U.next,*h=&U;while(k!=NULL && a!=k->num)h=k;k=

5、k->next;if(k=NULL)printf(" 沒有找到這樣的作業(yè)!");elseh->next=k->next;if(h->next=NULL)n=h;while(r!=NULL)/ 若回收得到的空閑塊的前方有空閑塊合并此空閑塊if(k->add=r->address+r->size)r->size=r->size+k->size;break;elser=r->after;if(r=NULL)/若回收得到的空閑塊的后面有空閑塊合并此空閑塊r=L.after;while(r!=NULL)if(k->

6、;add+k->size=r->address)r->address=k->add;r->size=r->size+k->size;break;elser=r->after;while(d!=NULL)/保證空閑鏈表中沒有相鄰的空閑空間if(d->after!=NULL)e=d->after;elsebreak;if(d->address+d->size=e->address)d->after=e->after;while(e->after!=NULL)e->after->before=

7、d;d->size=d->size+e->size;free(e);break;elsed=d->after;if(r=NULL)r=L.after;c=(node *)malloc(sizeof(node);c->size=b;c->address=k->add;if(L.after=NULL)c->after=L.after;c->before=&L;L.after=c;elser=L.after;while(r!=NULL)if(r->address>c->address)c->after=r;c-&g

8、t;before=r->before;r->before->after=c;r->before=c;free(k);return;elser=r->after;free(k);void alloc(int a ,int b)/分配內(nèi)存算法node *p,*q=L.after;usenode *m;p=search(b);if(p=NULL)return;m=(usenode *)malloc(sizeof(usenode);/ 生成一個被占用鏈表的結(jié)點,并插入到該鏈表的尾部m->add=p->address;m->size=b;m->num

9、=a;m->next=n->next;n->next=m;n=m;/ 保證 n 始終指向被占用鏈表的尾部，方便以后新生成結(jié)點的插入if(p->size>b)/如果申請空間的大小小于找到空閑空間的大小的處理p->size=p->size-b;p->address=p->address+b;else/ 如果申請空間的大小等于找到空閑空間的大小的處理p->before->after=p->after;if(p->after!=NULL)p->after->before=p->before;free(p);

10、void sort()/對空閑鏈表進行排序int max;node *p,*q,*r,*s;node a;p=L.after;while(p!=NULL)/讓指針 q 指向鏈表的最后一個結(jié)點q=p;p=p->after;if(L.after->after=NULL)return;elsewhile(p!=q)s=r=p=L.after;max=r->size;while(s!=q->after)if(s->size>max)max=s->size;r=s;s=s->after;elses=s->after;a.size=q->size

11、;a.address=q->address;q->size=r->size;q->address=r->address;r->size=a.size;r->address=a.address;if(q->before->before=&L)return;elseq=q->before;void Print()node *p=L.after;usenode *q=U.next;int i=1;printf("n空閑區(qū)域列表:n");printf("FREEIDaddresssizen");

12、while(p!=NULL)printf("%-10d",i);printf("%-10d",p->address);printf("%dn",p->size);p=p->after;i+;if(q=NULL)return;elseprintf("n 已分配區(qū)域列表:n");printf("WORKIDaddresssizen");while(q!=NULL)printf("%-10d",q->num);printf("%-10d"

13、,q->add);printf("%dn",q->size);q=q->next;void firstfit()/首次適應(yīng)算法int a,b,i;Init();Print();while(1)printf("n1 、申請空間 n");printf("2 、釋放空間 n");printf("3 、退出首次適應(yīng)算法n");printf(" 請輸入你的選擇:");scanf("%d",&i);switch(i)case 1:printf(" 請輸

14、入申請空間的作業(yè)號:");scanf("%d",&a);printf(" 請輸入申請空間的大小:");scanf("%d",&b);alloc(a,b);Print();break;case 2:printf(" 請輸入釋放空間的作業(yè)號:");scanf("%d",&a);printf(" 請輸入釋放空間的大小:");scanf("%d",&b);recovery(a,b);Print();break;case 3

15、:printf("n");return;void bestfit()int a,b,i;Init();Print();while(1)printf("n1 、申請空間 n");printf("2 、釋放空間 n");printf("3 、退出最佳適應(yīng)算法n");printf(" 請輸入你的選擇:");scanf("%d",&i);switch(i)case 1:printf(" 請輸入申請空間的作業(yè)號:");scanf("%d"

16、,&a);printf(" 請輸入申請空間的大小:");scanf("%d",&b);alloc(a,b);sort();Print();break;case 2:printf(" 請輸入釋放空間的作業(yè)號:");scanf("%d",&a);printf(" 請輸入釋放空間的大小:");scanf("%d",&b);recovery(a,b);sort();Print();break;case 3:printf("n");r

17、eturn;void main()int i;while(1)printf("1 、首次適應(yīng)算法n");printf("2 、最佳適應(yīng)算法n");printf("3 、退出 n");printf(" 請輸入你的選擇:");scanf("%d",&i);switch(i)case 1:firstfit();break;case 2:bestfit();break;case 3:return;運行結(jié)果 開始界面 首次適應(yīng)算法 最佳適應(yīng)算法程序代碼 C+語言實現(xiàn)/*/*動態(tài)分區(qū)分配方式的模擬*

18、/*#include<iostream.h>#include<stdlib.h>#define Free 0 /空閑狀態(tài)#define Busy 1 / 已用狀態(tài)#define OK 1/ 完成#define ERROR 0 / 出錯#define MAX_length 640 / 最大內(nèi)存空間為640KBtypedef int Status;typedef struct freearea/ 定義一個空閑區(qū)說明表結(jié)構(gòu)int ID;/ 分區(qū)號long size;/ 分區(qū)大小long address; /分區(qū)地址int state;/ 狀態(tài)ElemType;/-線性表的雙向

19、鏈表存儲結(jié)構(gòu)typedef struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趨指針struct DuLNode *next; / 后繼指針DuLNode,*DuLinkList;DuLinkList block_first; / DuLinkList block_last; /頭結(jié)點尾結(jié)點Status alloc(int);/ 內(nèi)存分配Status free(int); / 內(nèi)存回收Status First_fit(int,int);/ 首次適應(yīng)算法Status Best_fit(int,int)

20、; / 最佳適應(yīng)算法void show();/ 查看分配Status Initblock();/ 開創(chuàng)空間表Status Initblock()/ 開創(chuàng)帶頭結(jié)點的內(nèi)存空間鏈表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first->prior=NULL;block_first->next=block_last;block_last->prior=block_first;block_last->next=NULL;blo

21、ck_last->data.address=0;block_last->data.size=MAX_length;block_last->data.ID=0;block_last->data.state=Free;return OK;/-分配主存-Status alloc(int ch)int ID,request; cout<<" 請輸入作業(yè) cin>>ID;(分區(qū)號 )： "cout<<" 請輸入需要分配的主存大小cin>>request;if(request<0 |request=

22、0)(單位 :KB) ： "cout<<" 分配大小不合適，請重試！"<<endl;return ERROR;if(ch=2) / 選擇最佳適應(yīng)算法if(Best_fit(ID,request)=OK) cout<<"分配成功！"<<endl;else cout<<" 內(nèi)存不足，分配失?。?quot;<<endl;return OK;else /默認(rèn)首次適應(yīng)算法if(First_fit(ID,request)=OK) cout<<"分配成功！

23、 "<<endl;else cout<<" 內(nèi)存不足，分配失?。?quot;<<endl;return OK;/-首次適應(yīng)算法-Status First_fit(int ID,int request)/傳入作業(yè)名及申請量/為申請作業(yè)開辟新空間且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first-&

24、gt;next;while(p)if(p->data.state=Free && p->data.size=request)/ 有大小恰好合適的空閑塊p->data.state=Busy;p->data.ID=ID;return OK;break;if(p->data.state=Free && p->data.size>request)/ 有空閑塊能滿足需求且有剩余"temp->prior=p->prior;temp->next=p;temp->data.address=p->d

25、ata.address;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=request;return OK;break;p=p->next;return ERROR;/-最佳適應(yīng)算法-Status Best_fit(int ID,int request)int ch; / 記錄最小剩余空間DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp-

26、>data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; /記錄最佳插入位置while(p) / 初始化最小空間和最佳位置if(p->data.state=Free &&(p->data.size>request | p->data.size=request) )q=p;ch=p->data.size-request;break;p=p->next;while(p)if(

27、p->data.state=Free && p->data.size=request)/ 空閑塊大小恰好合適p->data.ID=ID;p->data.state=Busy;return OK;break;if(p->data.state=Free && p->data.size>request)/ 空閑塊大于分配需求if(p->data.size-request<ch)/ 剩余空間比初值還小ch=p->data.size-request;/ 更新剩余最小值q=p;/ 更新最佳位置指向p=p->n

28、ext;if(q=NULL) return ERROR;/沒有找到空閑塊else/ 找到了最佳位置并實現(xiàn)分配temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return OK;/-主存回收-Status free(int ID)DuLNode *p=block_first;while(p)if(p-

29、>data.ID=ID)p->data.state=Free;p->data.ID=Free;if(p->prior->data.state=Free)/ 與前面的空閑塊相連p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;if(p->next->data.state=Free)/ 與后面的空閑塊相連p->data.size+=p->next->data.size;p-&

30、gt;next->next->prior=p;p->next=p->next->next;break;p=p->next;return OK;/-顯示主存分配情況-void show()cout<<"+n"cout<<"+主 存 分 配 情 況+n"cout<<"+n"DuLNode *p=block_first->next;while(p)cout<<" 分 區(qū) 號： "if(p->data.ID=Free) cout<<"Free"<<endl;else cout<<p->data.ID<<endl;cout<<" 起始地址： "<&