可变分区存储管理

沈阳工程学院学生实验报告（课程名称：操作系统）实验题目：可变分区存储管理班级计算机131学号2013414126姓名杨光成地点实训F608指导教师吕海华王黎明实验日期:2015年5月19日1一、实验题目主存储器空间分配实验。二、实验要求编写一段程序来模拟可变分区管理方法。要求能通过文件形式定义空闲区表；能随意输入作业及需要分配的空间；能分别使用首次适应算法、最佳适应算法和最坏适应算法对输入的作业进行空间分配；能显示系统空闲表和已分配空间表。三、实验目的通过首次适应算法、最佳适应算法和最坏适应算法实现主存空间的分配，可以使读者可好地理解存储分配算法。四、实验原理分析⑴可变分区方式是按作业需要的主存空间大小来分区。当装入一个作业时，首先要查看是否有足够的空闲空间来分配，若有则按指定的分配方式进行分配；否则作业不能装入。随着作业的装入和撤离主存空间被分为若干个大大小小的不连续的区间，为了表明各区间的状态可以用一个内存分区表如表1所示来表示。表1内存分区表起始地址长度标志120k20k作业1200k50k空闲这样我们可以定义一个如下的结构表示内存分区信息。typedefstructnode{intstart;//起始地址intlength;//长度chartag[20];//标志}job;⑵可变分区的三种算法就是为作业分配主存空间的方法。●首次适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入第一个满足条件的空间中去。●最佳适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入满足条件的空闲空间中最小的一个空间中去。●最坏适应算法：在空闲区间中查询满足作业需要的空间，并将作业装入满足条2件的空闲空间中最大的一个空间中去。从三种算法的说明可以看出，分配空间的过程主要可以分两步：●查询所有满足作业需求的空间块。●按照指定的算法将作业装入空间块中。⑶在操作的最初主存空间实际就是一个大的空闲区，不涉及到如何分配的问题。为直接模拟运行一段时间后主存中出现了多个空闲块的状态，题目要求从一个文件读入空闲区表。在这里我们可以设计一个空闲区表文件的结构为如表2所示：表2空闲区表起始地址长度200k50k……这样也可以方便地将空闲表一次读入程序中，而不必再一个个的输入。⑷主要变量及函数说明如表3所示。表3变量与函数说明表typedefstructnode内存块结构jobfrees空闲区表joboccupys已分配区表free_quantity空闲区数量occupy_quantity已分配区数量voidinitial()初始化函数intreadData()从文件读入空闲表函数voidsort()排序空闲表voidview()显示分区信息voidearliest()最先适应分配算法voidexcellent()最优适应分配算法voidworst()最坏适应算法mem.txt空闲表文件3五、实验代码清单1、主函数（如图1）voidmain(){intch;//算法选择标记cout请输入所使用的内存分配算法：\n;cout(1)首次适应算法\n(2)最佳适应算法\n(3)最差适应算法\n;cinch;while(ch1||ch3){cout输入错误，请重新输入所使用的内存分配算法：\n;cinch;}Initblock();//开创空间表intchoice;//操作选择标记while(1){show();cout请输入您的操作：;cout\n1:分配内存\n2:回收内存\n0:退出\n;cinchoice;if(choice==1)alloc(ch);//分配内存elseif(choice==2)//内存回收{intflag;cout请输入您要释放的分区号：;4cinflag;free(flag);}elseif(choice==0)break;//退出else//输入操作有误{cout输入有误，请重试！endl;continue;}}}图12、分配主存（如图2）Statusalloc(intch)5{intrequest=0;cout请输入需要分配的主存大小(单位:KB)：;cinrequest;if(request0||request==0){cout分配大小不合适，请重试！endl;returnERROR;}if(ch==2)//选择最佳适应算法{if(Best_fit(request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;}if(ch==3)//选择最差适应算法{if(Worst_fit(request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;}else//默认首次适应算法{if(First_fit(request)==OK)cout分配成功！endl;elsecout内存不足，分配失败！endl;returnOK;6}}图23、首次适应(如图3)StatusFirst_fit(intrequest){//为申请作业开辟新空间且初始化DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));temp-data.size=request;temp-data.state=Busy;DuLNode*p=block_first-next;while(p){if(p-data.state==Free&&p-data.size==request)7{//有大小恰好合适的空闲块p-data.state=Busy;returnOK;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;returnOK;break;}p=p-next;}returnERROR;}8图34、最佳适应（如图4和图5）StatusBest_fit(intrequest){intch;//记录最小剩余空间DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));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)){9if(q==NULL){q=p;ch=p-data.size-request;}elseif(q-data.sizep-data.size){q=p;ch=p-data.size-request;}}p=p-next;}if(q==NULL)returnERROR;//没有找到空闲块elseif(q-data.size==request){q-data.state=Busy;returnOK;}else{temp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;10q-prior=temp;q-data.address+=request;q-data.size=ch;returnOK;}returnOK;}图411图55、最差适应（如图6）StatusWorst_fit(intrequest){intch;//记录最大剩余空间DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode));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))12{if(q==NULL){q=p;ch=p-data.size-request;}elseif(q-data.sizep-data.size){q=p;ch=p-data.size-request;}}p=p-next;}if(q==NULL)returnERROR;//没有找到空闲块elseif(q-data.size==request){q-data.state=Busy;returnOK;}else{temp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;13q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;returnOK;}returnOK;}图614图76、主存回收和显示主存分配情况（如图8）Statusfree(intflag){DuLNode*p=block_first;for(inti=0;i=flag;i++)if(p!=NULL)p=p-next;elsereturnERROR;p-data.state=Free;if(p-prior!=block_first&&p-prior-data.state==Free)//与前面的空闲块相连{15p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;p=p-prior;}if(p-next!=block_last&&p-next-data.state==Free)//与后面的空闲块相连{p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next;}if(p-next==block_last&&p-next-data.state==Free)//与最后的空闲块相连{p-data.size+=p-next-data.size;p-next=NULL;}returnOK;}voidshow(){intflag=0;cout\n主存分配情况:\n;16cout++++++++++++++++++++++++++++++++++++++++++++++\n\n;DuLNode*p=block_first-next;cout分区号\t起始地址\t分区大小\t状态\n\n;while(p){coutflag++\t;coutp-data.address\t\t;coutp-data.sizeKB\t\t;if(p-data.state==Free)cout空闲\n\n;elsecout已分配\n\n;p=p-next;}cout++++++++++++++++++++++++++++++++++++++++++++++\n\n;}图817五、成绩评定优良中及格不及格出勤内容格式分析总评指导教师：年月日