可变分区首次适应算法.docx

可变分区首次适应算法-操作系统实验报告题 目 ：可变分区首次适应算法指导老师 ： 班 级 ： 姓 名 ： 学 号 ： 时 间 ： 实验三 可变分区首次适应算法一、实验目的模拟内存分配, 了解并掌握动态分区分配中所用的数据结构、分区分配算法。回顾链表的创建，插入，删除等基本操作； 深刻理解首次适应内存分配算法。二、实验内容编程实现首次适应内存分配算法，并上机验证。实验环境：Microsoft Visual Studio 2010三、算法描述该程序用一个链表来模拟内存的空间分布。从键盘输入链表长度和第一个结点的首地址、以及其他各个结点所占空间大小。然后进行申请空间，并判断所申请的大小是否符合要求，能不能进行分配。本程序主要包括两大模块，一是建立链表模块，二是申请并分配空间模块。开始程序流程图如下：初始化 输出内存分配情况输入申请内存空间大小是否可以进行分配否是是否继续内存分配并输出分配结果是否结束四、程序清单及简单注释/ 内存分配算法：#include#include#include using namespace std;int size=0,count=0,part1000,address1000,flag1000;/设定全局变量/*输出可视结果*/void Output()int j;cout 输出内存分配情况： endl;coutendl;cout | 分区号 | 分区大小 | 起始地址 | 状态 |endl;for(j=1;j=count;j+)cout | j ;cout | partj ;cout | addressj ;if(flagj=1)cout | 已分配;if(flagj=0)cout | 未分配;cout |;coutendl;/*创建原始环境*/void Create()/指明内存空间并初步地为作业分配内存int i=1,m=0,s=0,start=0;char contin=Y;coutsize;coutendl;cout开始为作业分配内存空间endl;coutendl;coutstart;coutendl;cout输入每个分区的大小，以Y继续操作，以N结束分区操作:endl;coutendl;while(contin!=N)count=i;cout请输入第iparti;addressi=start;start=start+parti;s=m;/m用来标记已分配内存的总的大小，s用来标记m之前的值m=m+parti;flagi=1;/标识内存已分配if(m=size)coutendl;cout已分配完所有内存空间，请结束操作！endl;coutendl;contin=N;if(msize)coutendl;coutcontin;coutendl;while(contin!=Y&contin!=N)coutendl;coutcontin;coutendl;if(contin=Y)i+;if(contin=N)/如果不继续分配内存，将剩余的空间定义为一个分区，但标记为未分配part+i=size-m;count=i;/分区总数addressi=start;/起始地址 /if(msize)coutendl;coutcontin;coutsize)/while/*分配内存*/void Distribute()int tag=0,space=0,i,j,situation=0;/situation用来表示分配是否成功coutendl;coutspace;coutendl;for(i=1;ispace&flagi=0)flagi=1;cout分配成功！endl;cout=i+2;j-) partj=partj-1;flagj=flagj-1;flagi+1=0;/多余的内存部分状态为未分配parti+1=parti-space;parti=space;/划出一部分内存空间分配给作业flagcount+1=0;+count; /重新定义分区的首地址for(j=1;jcount;j+)addressj+1=addressj+partj;Output();situation=1;break;if(situation=0)cout分配失败！endl;coutendl;for(j=1;j=count;j+)/判断是什么原因造成分配失败if(flagj=0)tag=1;break;if(tag=1)cout所有的空间大小都不足以分配！endlendl;if(tag=0)cout所有的空间均已分配！endlendl;Output();/*回收分配出去的内存*/void Restore()int tag=0,i,j,m=0,k;for(i=1;i=count;i+)if(flagi=1)tag=1;break;if(tag=0)/回收前进行判断内存是否已经被分配 coutendl; cout所有分区均未分配，不需要回收操作！endl; if(tag=1)coutendl;coutj;flagj=0;/回收分区/如果有几段连续的空闲分区，则将他们合并for(i=count;i1;i-)if(flagi=0&flagi-1=0)m+;/用以标记将被撤销的分区块数parti-1=parti-1+parti;parti=0; /先将后一个分区的大小和地址置空addressi=0; for(i=count;i=1;i-)if(addressi!=0) k=i; break;elsecount-;/处理末位连续的空闲分区for(i=k;i1;i-)/处理中间的连续的空闲分区if(addressi=0)for(j=i;jk;j+)partj=partj+1;addressj=addressj+1;flagj=flagj+1;-count;/撤销一个区分，总数减一 Output();/*主函数*/void main()int i;char ch=y,s;coutendlendlttt可变分区首次适应算法endlendl;coutendl;for(i=0;i1000;i+)parti=0;addressi=0;/初始化数组的值flagi=0;Create();Output();while(ch=y|ch=Y)coutendl;couts;while(s!=R&s!=D)coutendl;couts; if(s=R) Restore(); coutendl;if(s=D) Distribute(); coutendl; coutch;coutendl;cout本程序结束执行！endl;五、实验结果建立内存分配环境：剩余空间不足以分配：所有的空间均已分配：回收分区1：回收分区2，由于两个空闲分区连续，将合并区分1和分区2：六、实验小结本算法从链首开始查找可以满足请求申请的空间大小的第一个结点，然后按照请求的大小，从该结点空间中划分一块适当的空间分配，剩下的空间作为一个新的结点接到后面。如果所有的结点都已分配了，或者请求分配的空间