《存储管理算法的模拟.doc》由会员分享，可在线阅读，更多相关《存储管理算法的模拟.doc（18页珍藏版）》请在三一文库上搜索。
1、存储管理算法的模拟 姓名：海日汗学号：20092106091、概述分区式存储管理算法主要有：首次适应算法，最佳适应算法，最坏适应算法。2、实验目的模拟实现分区存储管理算法中的首次、最佳、最坏适应算法。3、实验要求输入： 1）当前内存空闲分区的序列，包括起始地址、空闲分区大小。2）进程的分区请求序列。输出要求： 1） 三种算法的空闲分区队列2） 三种算法的分配结果4、实验代码#include iostreamusing namespace std;#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错
2、#define MAX_length 500 /最大内存空间为500KBint flag;typedef struct freeSpace /定义一个空闲区说明表结构 long size; /分区大小 long address; /分区地址 int state; /状态ElemType;/ 线性表的双向链表存储结构typedef struct DuLNode ElemType data; struct DuLNode *prior; /前趋指针 struct DuLNode *next; /后继指针DuLNode,*DuLinkList; DuLinkList head_Node; /头结点D
3、uLinkList end_Node; /尾结点int alloc(int); /内存分配int free(int); /内存回收int First_fit(int); /首次适应算法int Best_fit(int); /最佳适应算法int Worst_fit(int); /最差适应算法void show(); /查看分配int Initblock(); /开创空间表 int Initblock() /开创带头结点的内存空间链表 head_Node=(DuLinkList)malloc(sizeof(DuLNode); end_Node=(DuLinkList)malloc(sizeof(D
4、uLNode); head_Node-prior=NULL; /头结点的前驱指针指向空 head_Node-next=end_Node; /头结点的后继指针指向尾结点 end_Node-prior=head_Node; /尾结点的前驱指针指向头结点 end_Node-next=NULL; /尾结点的后继指针指向空 end_Node-data.address=0; /尾结点的地址是0 end_Node-data.size=MAX_length; /分区大小是最大分区 end_Node-data.state=Free; /状态是空 return OK;void main() int ch; /算法
5、选择标记cout*存储管理算法模拟*n; cout请输入所使用的内存分配算法：n; coutch;while(ch3)coutch; Initblock(); /开创空间表 int choice; /操作选择标记 while(1) show();cout请输入您的操作：; coutchoice; if(choice=1) alloc(ch); / 分配内存 else if(choice=2) / 内存回收 int flag; coutflag; free(flag); else if(choice=0) break; /退出 else /输入操作有误 cout输入有误，请重试!endl; co
6、ntinue; /分配主存int alloc(int ch) int need = 0; coutneed; if(need0 |need=0) cout请重新输入分配大小!endl; return ERROR; if(ch=2) /选择最佳适应算法 if(Best_fit(need)=OK) cout分配成功!endl; else cout内存不足，分配失败!endl; return OK; if(ch=3) /选择最差适应算法 if(Worst_fit(need)=OK) cout分配成功!endl; else cout内存不足，分配失败!endl; return OK; else /默认
7、首次适应算法 if(First_fit(need)=OK)cout分配成功!endl; else cout内存不足，分配失败!data.size=need; temp-data.state=Busy; DuLNode *p=head_Node-next; while(p) if(p-data.state=Free & p-data.size=need) /现有的空闲块正好等于需要的空间大小 p-data.state=Busy; return OK; break; if(p-data.state=Free & p-data.sizeneed) /现有的空闲块能满足需求且有剩余 temp-prio
8、r=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-=need; return OK; break; p=p-next; return ERROR;/最佳适应算法int Best_fit(int need) int ch; /记录最小剩余空间 DuLinkList temp=(DuLinkList)ma
9、lloc(sizeof(DuLNode); temp-data.size=need; temp-data.state=Busy; DuLNode *p=head_Node-next; DuLNode *q=NULL; /记录最佳插入位置 while(p) /初始化最小空间和最佳位置 if(p-data.state=Free & (p-data.size=need) if(q=NULL)q=p;ch=p-data.size-need;else if(q-data.size p-data.size)q=p;ch=p-data.size-need; p=p-next; if(q=NULL) retu
10、rn ERROR; /没有找到空闲块 else if(q-data.size=need) q-data.state=Busy; return OK; else temp-prior=q-prior; temp-next=q; temp-data.address=q-data.address; q-prior-next=temp; q-prior=temp; q-data.address+=need; q-data.size=ch; return OK; return OK; /最差适应算法int Worst_fit(int need) int ch; /记录最大剩余空间 DuLinkList
11、temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.size=need; temp-data.state=Busy; DuLNode *p=head_Node-next; DuLNode *q=NULL; /记录最佳插入位置 while(p) /初始化最大空间和最佳位置 if(p-data.state=Free & (p-data.size=need) ) if(q=NULL)q=p;ch=p-data.size-need;else if(q-data.size data.size)q=p;ch=p-data.size-need; p=p-ne
12、xt; if(q=NULL) return ERROR; /没有找到空闲块 else if(q-data.size=need) q-data.state=Busy; return OK; else temp-prior=q-prior; temp-next=q; temp-data.address=q-data.address; q-prior-next=temp; q-prior=temp; q-data.address+=need; q-data.size=ch; return OK; return OK;/主存回收int free(int flag) DuLNode *p=head_No
13、de;for(int i= 0; i next;elsereturn ERROR;p-data.state=Free; if(p-prior!=head_Node & p-prior-data.state=Free)/与前面的空闲块相连 p-prior-data.size+=p-data.size; p-prior-next=p-next; p-next-prior=p-prior;p=p-prior; if(p-next!=end_Node & p-next-data.state=Free)/与后面的空闲块相连 p-data.size+=p-next-data.size; p-next-ne
14、xt-prior=p; p-next=p-next-next; if(p-next=end_Node & p-next-data.state=Free)/与最后的空闲块相连 p-data.size+=p-next-data.size; p-next=NULL; return OK; /显示主存分配情况void show()int flag = 0; coutn主存分配情况:n; coutnext;cout分区号t起始地址t分区大小t状态nn; while(p) cout flag+t; cout data.addresstt; cout data.sizedata.state=Free) co
15、ut空闲nn; else coutnext; cout+nn;实验结果分析：1.首先适应算法的内存分配情况：内存分配顺序是：150KB，85KB, 62KB, 120KB, 15KB, 30KB（只有最后结果截图下来的！）下面是回收内存的情况：回收的内存分区号的顺序是：分区1 分区3 分区5； 下面是回收了1 3 5 分区之后的内存的情况。（说明的是回收分区5之后原来的分区6和现在新回收的分区5和在一起成为新的一个大的空闲内存！）再一次分配内存：因为这样才可以看出首次适应算法的分配内存的顺序。分配内存的大小是 65KB 75KB 95KB再一次分配65KB之后：分配75KB之后：分配95KB之
16、后：（找不到95KB的空闲内存，所以分配失败！）明显看的出来首次适应算法的主要思想是：当接到内存申请时，查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配。2.最佳适应算法分配65KB之后：分配75KB之后：分配95KB之后 我们能看出最佳适应算法的主要思想是：当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲区，将其分割并分配！3.最差适应算法分配65KB之后分配75KB之后分配95KB之后最差适应算法的主要思想是：当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。我的心得： 我通过本次实验深入了解了这三个算法！只实现内存分配情况的话，比较简单!本次试验中我还实现了回收内存的情况！回收内存要考虑下面几个情况：（1）回收分区的上邻分区是空闲的，需要将这两个相邻的空闲区合并成一个更大的空闲区，修改空闲区表。（2）回收分区的下邻分区是空闲的，需要将这两个相邻的空闲区合并成一个更大的空闲区，修改空闲区表。（3）回收分区的上邻分区和下邻分区是空闲的，需要将这三个相邻的空闲区合并成一个更大的空闲区，修改空闲区表。（4）回收分区的上邻和下邻分区都不是空闲的，则直接将空闲区记录在空闲区表中!还加深理解了双向链表的一些操作！