动态分区分配方式的模拟C语言代码和C++代码

《动态分区分配方式的模拟C语言代码和C++代码》由会员分享，可在线阅读，更多相关《动态分区分配方式的模拟C语言代码和C++代码（16页珍藏版）》请在装配图网上搜索。

1、实验三 使用动态分区分配方式的模拟1、实验目的 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管 理方式及其实现过程的理解。2、实验内容(1) 用 C 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程 alloc( ) 和回收过程 free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先 使用空闲区低端的空间。(2)假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB。作业2申请60KB。作业3申请100KB。作业2释放60KB。作业4申请200KB。作业3释放100KB。作业1释放130KB。作业5

2、申请140KB。作业6申请60KB。作业7申请50KB。作业6释放60KB。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和 回收后显示出空闲分区链的情况。程序代码一C语言实现#include#includestruct node/空闲分区链结点的定义node *before;node *after;int size;int address;int state;node L;struct usenodeusenode *next;int num;int add;int size;U,*n;void Init()/空闲分区链的初始化node *p;p=(node *

3、)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)prin tf(没有空闲的区域!)；p=NULL;return p;elsewhile(p!=NULL & ap-size) p=p-after;if(p=NULL)prin tf(没有找到合适的空闲空间！); p=NULL;return p;els

4、ereturn p;void recovery(int a,int b)/内存回收算法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=k-next;if(k=NULL)prin tf( 没有找到这样的作业!)；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

5、；break；elser=r-after；if(r=NULL)/若回收得到的空闲块的后面有空闲块合并此空闲块r=L.after；while(r!=NULL)if(k-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-a

6、fter-before=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-addressc-address)c-after=r; c-before=r-before;r-before-after=c;r-before=c;f

7、ree(k);return;elser=r-after;free(k);void alloc(int a ,int b) /分配内存算法node *p,*q=L.after;usenode *m;p=search(b);if(p=NULL)return;m=(usenode *)malloc(sizeof(usenode);/生成一个被占用链表的结点，并插入到该链表的尾部 m-add=p-address;m-size=b;m-num=a;m-next=n-next;n-next=m;n=m;/保证 n 始终指向被占用链表的尾部，方便以后新生成结点的插入if(p-sizeb)/如果申请空间的大小

8、小于找到空闲空间的大小的处理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);void sort()/对空闲链表进行排序int max;node *p,*q,*r,*s;node a;p=L.after;while(p!=NULL) /让指针 q 指向链表的最后一个结点 q=p;p=p-after;if(L.after-after=NULL)return;elsewhil

9、e(p!=q)s=r=p=L.after;max=r-size;while(s!=q-after)if(s-sizemax)max=s-size;r=s;s=s-after;else s=s-after;a.size=q-size;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;else q=q-before; void Print()node *p=L.after; usenode *q=U.next;

10、int i=1;printf (n空闲区域列表:n); printf(FREEID address sizen); while(p!=NULL)printf(%-10d,i); printf(%-10d,p-address);printf(%dn,p-size); p=p-after;i+;if(q=NULL) return;else printf(n已分配区域列表:n); printf(WORKID address sizen); while(q!=NULL)printf(%-10d,q-num); printf(%-10d,q-add);printf(%dn,q-size); q=q-ne

11、xt;void firstfit()/首次适应算法int a,b,i;Init();Print();while(1)prin tf(nl、申请空间n);prin tf(2、释放空间n);prin tf(3、退出首次适应算法n);prin tf(请输入你的选择:)； scanf(%d,&i);switch(i)case 1:prin tf(请输入申请空间的作业号:); scanf(%d,&a);prin tf(请输入申请空间的大小:);scanf(%d,&b); alloc(a,b);Print();break;case 2:prin tf(请输入释放空间的作业号:); scanf(%d,&a)

12、;prin tf(请输入释放空间的大小:)；scanf(%d,&b);recovery(a,b);Print();break;case 3:printf(n);return;void bestfit()int a,b,i;Init();Print();while(1)prin tf(nl、申请空间n);prin tf(2、释放空间n);prin tf(3、退出最佳适应算法n);prin tf(请输入你的选择:)； scanf(%d,&i);switch(i) case 1:prin tf(请输入申请空间的作业号:); scanf(%d,&a);prin tf(请输入申请空间的大小:); sca

13、nf(%d,&b);alloc(a,b);sort(); Print();break;case 2:prin tf(请输入释放空间的作业号:); scanf(%d,&a);prin tf(请输入释放空间的大小:)； scanf(%d,&b);recovery(a,b);sort(); Print();break;case 3:printf(n);return;void main()int i;while(1) prin tf(l、首次适应算法n);prin tf(2、最佳适应算法n);prin tf(3、退出 n);prin tf(请输入你的选择:)； scanf(%d,&i);switch(

14、i)case 1:firstfit();break;case 2:bestfit();break;case 3:return;运行结果 开始界面 首次适应算法 最佳适应算法程序代码一C+语言实现/ / js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js/* 动态分区分配方式

15、的模拟 */ / js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js js#include#include#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_

16、length 640 /最大内存空间为 640KBtypedef int Status;typedef st ruct freearea/定义一个空闲区说明表结构int ID; /分区号long size; /分区大小long address; /分区地址int state; /状态ElemType;/ 线性表的双向链表存储结构 typedef struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趋指针struct DuLNode *next; /后继指针DuLNode,*DuLinkList;DuL

17、inkList block_first; /头结点DuLinkList block_last; /尾结点Status alloc(in t);/ 内存分配Status free(int); /内存回收Status First_fit(int,int) ;/首次适应算法Status Best_fit(int,int); /最佳适应算法 void show();/查看分配Status Ini tblock();/开创空间表Status Ini tblock()/开创带头结点的内存空间链表 block_first=(DuLinkList)malloc(sizeof(DuLNode); block_l

18、ast=(DuLinkList)malloc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_last; block_last-prior=block_first;block_last-next=NULL;block_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

19、;cout请输入作业(分区号)：；cinID;cout请输入需要分配的主存大小(单位:KB):;cinrequest；if(request0 |request=0)cout分配大小不合适，请重试！ endl;return ERROR;if(ch=2) /选择最佳适应算法f (Best_fit (ID,request)=OK) cout分配成功！ endl; else cout内存不足，分配失败！ endl; return OK;else /默认首次适应算法if(First_fit(ID,request)=OK) cout分配成功！ endl; else cout内存不足，分配失败！ endl;

20、 return OK;/首次适应算法Status Firs t_fi t(in t ID,int reques t)/传入作业名及申请量/为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request) /有大小恰好合适的空闲块p-data.state=

21、Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest) /有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.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;/ 最佳

22、适应算法 Status Best_fit(int ID,int request)int ch; /记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-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.sizerequest | p-data.size

23、=request) )q=p; ch=p-data.size-request; break;p=p-next;while(p)if(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.sizerequest) /空闲块大于分配需求if(p-da ta.size-reques t ch)/剩余空间比初值还小ch=p-da ta.size-reques t;/更新剩余最小值 q=p；/更新最佳位

24、置指向p=p-next;if(q=NULL) ret urn ERROR;/没有找到空闲块 else/找到了最佳位置并实现分配 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-data.ID=ID)p-data.state=

25、Free;p-data.ID=Free;if(p-prior-da ta.s tat e=Free)/与前面的空闲块相连 p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;辻(p-nex t-da ta.s tat e=Free)/与 后面的空闲块相连p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next;break;p=p-next;return OK;/ 显示主存分配情况 void show()cout+n; cou

26、t+ 主 存 分 配 情 况 +n; cout+n;DuLNode *p=block_first-next;while(p)cout分区号：；if(p-data.ID=Free) coutFreeendl;else coutp-data.IDendl;cout起始地址：p-data.addressendl;cout分区大小：p-data.size KBendl;cou t状态：；if(p-data.state=Free) cout空 闲endl;else cou t已分配endl;coutendl;p=p-next;/ 主 函 数void main()int ch;/算法选择标记cout 动态

27、分区分配方式的模拟 n; cout*n;cout* 1)首次适应算法 2)最佳适应算法 *n; coutch;Initblock(); /开创空间表int choice; /操作选择标记while(1) cout*n; cout* 1: 分配内存 2: 回收内存 *n;cout* 3: 查看分配 0: 退 出 *n; cout*n; cout请输入您的操作：；cinchoice; if(choice=1) alloc(ch); / 分配内存 else if(choice=2)/ 内存回收int ID;cou t请输入您要释放的分区号：； cinID;free(ID);else if(choice=3) show();/显示主存 else if(choice=0) break; /退出 else /输入操作有误cout输入有误，请重试！ endl; continue;