模拟实现可变分区存储管理

《操作系统》课程设计说明书题目：模拟实现可变分区存储管理班级：学号：姓名：指导老师：1．目的和要求在熟练掌握计算机分区存储管理方式的原理的基础上，利用一种程序设计语言模拟实现操作系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。2．设计内容设计合理的数据结构来描述存储空间：对于未分配出去的部分，可以用空闲分区队列或空闲分区链表来描述，对于已经分配出去的部分，由装入内存的作业占据，可以将作业组织成链表或数组。实现分区存储管理的内存分配功能，实现两种适应算法：首次适应算法，最坏适应算法。实现分区存储管理的内存回收算法：要求能够正确处理回收分区与空闲分区的四种邻接关系。当碎片产生时，能够进行碎片的拼接。3．设计环境Windows操作系统、DEVC++C语言4．程序概要（1）数据结构和全局变量inttype=0;//算法类型//空闲分区structfreelink{intlen;//len为分区长度intaddress;//address为分区起始地址structfreelink*next;};//占用分区structbusylink{charname;//作业或进程名,name='S'表示OS占用intlen;intaddress;structbusylink*next;};structfreelink*free_head=NULL;//自由链队首指针structbusylink*busy_head=NULL,//占用区队首指针*busy_tail=NULL;//占用区队尾指针（2）功能模块划分大体上可以将整个程序的模块划分成如下几个部分：1）主模块：主要是初始化（设置物理内存的用户区的大小，选取适应算法）和界面，界面参考如下：2）内存分配算法（实现两种适应算法：最坏适应算法，首次适应算法）3）内存回收算法（考虑四种邻接情况，尤其是采用最佳（坏）适应算法时的分区合并）4）碎片拼接算法5）空闲分区队列显示6）占用分区队列显示（3）各函数调用关系1------初始化2------作业进入内存3------作业完成4------显示当前自由分区5------显示当前作业占据分区6------碎片拼接7------退出（4）主要函数流程图allocateMemoByWF();//两种算法分配回收大致相同，在这里只列举一种compactMemo()freeMemoByWF()5.源代码#includestdio.h#includestdlib.h#defineMAX_SIZE512//系统能分配的最大内存#defineFALSE0#defineTRUE1inttype=0;//算法类型//空闲分区structfreelink{intlen;//len为分区长度intaddress;//address为分区起始地址structfreelink*next;};//占用分区structbusylink{charname;//作业或进程名,name='S'表示OS占用intlen;intaddress;structbusylink*next;};structfreelink*free_head=NULL;//自由链队列（带头结点）队首指针structbusylink*busy_head=NULL,//占用区队列队（带头结点）首指针*busy_tail=NULL;//占用区队列队尾指针//初始化voidinit(){structfreelink*p;structbusylink*q;free_head=(structfreelink*)malloc(sizeof(structfreelink));free_head-next=NULL;//创建自由链头结点busy_head=busy_tail=(structbusylink*)malloc(sizeof(structbusylink));busy_head-next=NULL;//创建占用链头结点p=(structfreelink*)malloc(sizeof(structfreelink));p-address=64;p-len=MAX_SIZE-64;//（OS占用了64K）p-next=NULL;free_head-next=p;q=(structbusylink*)malloc(sizeof(structbusylink));q-name='S';//S表示操作系统占用q-len=64;q-address=0;q-next=NULL;busy_head-next=q;busy_tail=q;}//紧凑structfreelink*compactMemo(intrequire){intsum=0;structfreelink*fNode=free_head-next;while(fNode!=NULL){sum+=fNode-len;fNode=fNode-next;}printf(\n);if(sumrequire){returnNULL;}//删除空闲区所有节点structfreelink*p=free_head-next;//让p一直指向第一个数据节点while(p!=NULL){free_head-next=p-next;free(p);p=free_head-next;}//创建新的分区structfreelink*node=(structfreelink*)malloc(sizeof(structfreelink));node-address=0;node-len=MAX_SIZE;free_head-next=node;node-next=NULL;//修改占用区作业内存地址structbusylink*q=busy_head-next;while(q!=NULL){q-address=node-address;node-len-=q-len;node-address+=q-len;q=q-next;}returnnode;}//最坏（佳）适应算法在分区合并和分割后需要调整分区位置intadjust(structfreelink*node){structfreelink*p=free_head;//合并后链表中只剩一个分区if(p-next==NULL){free_head-next=node;node-next=NULL;returnTRUE;}while(p-next!=NULL&&node-len=p-next-len){p=p-next;}if(p-next==NULL){p-next=node;node-next=NULL;}else{node-next=p-next;p-next=node;}returnTRUE;}//最坏适应算法intallocateMemoByWF(){intrequire;printf(请输入作业所需内存大小：);scanf(%d,&require);//判断第一个空闲分区大小是否满足需求structfreelink*p=free_head-next;if(p-lenrequire){printf(没有分区满足要求,正在尝试碎片拼接...\n);//判断所有分区容量总和是否满足要求if((p=compactMemo(require))==NULL){returnFALSE;}}//将第一个空闲分区切割require分配给该作业structbusylink*q=(structbusylink*)malloc(sizeof(structbusylink));printf(请输入作业名称：);getchar();//输入require之后有一个换行符，用getchar吃掉scanf(%c,&q-name);//检查是否重名structbusylink*temp=busy_head-next;while(temp!=NULL&&temp-name!=q-name){temp=temp-next;}if(temp!=NULL){printf(该作业名已存在！\n);returnFALSE;}q-len=require;q-address=p-address;q-next=NULL;//将作业按地址递增的顺序插入到作业队列中temp=busy_head;while(temp-next!=NULL&&q-addresstemp-next-address){temp=temp-next;}if(temp-next==NULL){temp-next=q;q-next=NULL;}else{q-next=temp-next;temp-next=q;}//分割空闲分区if(p-len==require){free(p);returnTRUE;}else{p-address+=require;p-len-=require;}//把第一个分区从空闲区中拿出来if(p-next!=NULL){free_head-next=p-next;}elsereturnTRUE;//空闲队列中是否只存在一个节点//将分割后的分区放到合适的位置adjust(p);returnTRUE;}//首次适应算法intallocateMemoByFF(){intrequire;printf(请输入作业所需内存大小：);scanf(%d,&require);structfreelink*p=free_head-next;structfreelink*pre=free_head;while(p!=NULL&&p-lenrequire){pre=p;p=p-next;}if(p==NULL){printf(没有分区满足要求,正在尝试碎片拼接...\n);//判断所有分区容量总和是否满足要求if((p=compactMemo(require))==NULL){returnFALSE;}}//将第一个满足条件的分区分割合适的内存分配给作业structbusylink*q=(structbusylink*)malloc(sizeof(structbusylink));printf(请输入作业名称：);getchar();//输入require之后有一个换行符，用getchar吃掉scanf(%c,&q-name);//检查是否重名structbusylink*temp=busy_head-next;while(temp!=NULL&&temp-name!=q-name){temp=temp-next;}if(temp!=NULL){printf(该作业名已存在！\n);returnFALSE;}q-len=require;q-address=p-address;q-next=NULL;//将作业按地址递增的顺序插入到作业队列中temp=busy_head;while(temp-next!=NULL&&q-addresstemp-next-address){temp=temp-next;}if(temp-next==NULL){temp-next=q;q-next=NULL;}else{q-next=temp-next;temp-next=q;}//分割空闲分区if(p-len==require){pre-next=p-next;free(p);returnTRUE;}else{p-address+=require;p-len-=require;returnTRUE;}}//匹配节点并创建回收分区structfreelink*matchName(charname){structbusylink*q=busy_head;structfreelink*