动态分区存储管理方式的主存分配回收

2011-2012-1操作系统课程实验报告实验名称动态分区存储管理方式的主存分配回收班级学号姓名成绩一、实验目的深入了解动态分区存储管理方式主存分配回收的实现。二、实验要求编写程序完成动态分区存储管理方式的主存分配回收的实现。实验具体包括：首先确定主存空间分配表；然后采用最优适应算法完成主存空间的分配和回收；最后编写主函数对所做工作进行测试。三、实验步骤实现动态分区的分配和回收，主要考虑的问题有三个：第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法：第三，在设计的数据表格基础上设计主存回收算法。首先，考虑第—个问题：设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域。由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，主存的分配和回收主要是对空闲区的操作。这样为了便于对主存空间的分配和回收，就建立两张分区表记录主存使用情况．一张表格记录作业占用分区的“已分配区表”一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种，一种是链表形式，一种是顺序表形式。在试验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须是提前固定，所以无论是“已分配区表”还是“空闲区表”都必须事先确定长度。他们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分配区表”还是“空闲区表”都有空闲栏目。已分配区表中除了分区起始地址、长度外，也至少还有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个空闲区的登记项，内容为“未分配”。在实际系统中，这两表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此，“已分配区表”和“空闲区表”可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。四、实验结果程序代码：#includeiostream.h#includeiomanip.hfloatminsize=5;intcount1=0;intcount2=0;#definem10#definen10struct{floataddress;floatlength;intflag;}used_table[n];struct{floataddress;floatlength;intflag;}free_table[m];voidinitialize(void);intdistribute(int,float);intrecycle(int);voidshow();voidinitialize(void){inta;for(a=0;a=n-1;a++)used_table[a].flag=0;free_table[0].address=1000;free_table[0].length=1024;free_table[0].flag=1;}intdistribute(intprocess_name,floatneed_length){inti,k=-1;floatads,len;intcount=0;i=0;while(i=m-1){if(free_table[i].flag==1&&need_length=free_table[i].length){count++;if(count==1||free_table[i].lengthfree_table[k].length)k=i;}i=i+1;}if(k!=-1){if((free_table[k].length-need_length)=minsize){free_table[k].flag=0;ads=free_table[k].address;len=free_table[k].length;}else{ads=free_table[k].address;len=need_length;free_table[k].address+=need_length;free_table[k].length-=need_length;}i=0;while(used_table[i].flag!=0){i=i+1;}if(i=n-1){used_table[i].address=ads;used_table[i].length=len;used_table[i].flag=process_name;count1++;}else{if(free_table[k].flag==0){free_table[k].flag=1;free_table[k].address=ads;free_table[k].length=len;}else{free_table[k].address=ads;free_table[k].length+=len;}cout内存分配区已满，分配失败！\n;return0;}}else{cout无法为该作业找到合适分区！\n;return0;}returnprocess_name;}intrecycle(intprocess_name){inty=0;floatrecycle_address,recycle_length;inti,j,k;intx;while(y=n-1&&used_table[y].flag!=process_name){y=y+1;}if(y=n-1){recycle_address=used_table[y].address;recycle_length=used_table[y].length;used_table[y].flag=0;count2++;}else{cout该作业不存在！\n;return0;}j=k=-1;i=0;while(!(i=m||(k!=-1&&j!=-1))){if(free_table[i].flag==1){if((free_table[i].address+free_table[i].length)==recycle_address)k=i;if((recycle_address+recycle_length)==free_table[i].address)j=i;}i=i+1;}if(k!=-1){if(j!=-1){free_table[k].length+=free_table[j].length+recycle_length;free_table[j].flag=0;}elsefree_table[k].length+=recycle_length;}elseif(j!=-1){free_table[j].length+=recycle_length;free_table[j].address=recycle_address;}else{x=0;while(free_table[x].flag!=0)x=x+1;if(x=m-1){free_table[x].length=recycle_length;free_table[x].flag=1;}else{used_table[y].flag=process_name;cout空闲区已满，回收失败！\n;return0;}}returnprocess_name;}voidshow(){cout空闲区\n;for(inti=0;i=count2;i++)cout地址：free_table[i].address作业长度：free_table[i].length状态：free_table[i].flagendl;cout已分配区\n;for(intj=0;jcount1;j++)cout地址：used_table[j].address作业长度：used_table[j].length作业名：used_table[j].flagendl;}voidmain(){intchoice;intjob_name;floatneed_memory;boolexitFlag=false;cout动态分区分配方式的模拟\n;initialize();while(!exitFlag){cout1:分配内存2:回收内存\n;cout3:查看分配0:退出\n;cinchoice;switch(choice){case0:exitFlag=true;break;case1:cout请输入作业名和所需内存：;cinjob_nameneed_memory;distribute(job_name,need_memory);break;case2:intID;cout请输入您要释放的分区号：;cinID;recycle(ID);break;case3:show();break;}}}内存分配回收实现截图(1)、假定系统内存分配表允许的最大作业项为10，当分配超过10时，提示“内存分配区已满，分配失败”。(2)、回收作业所占内存时，当输入的作业名不存在，回收失败，提示“该作业不存在”。(3)、当要释放某个作业时，将已分配表中此作业的标志置为‘0’，并在空闲区做相应登记。五、总结核心算法：//最优分配算法实现的动态分区intdistribute(intprocess_name,floatneed_length){inti,k=-1;//k用于定位在空闲表中选择的未分配栏floatads,len;intcount=0;i=0;//核心的查找条件，找到最优空闲区while(i=m-1)//循环找到最佳的空闲分区{if(free_table[i].flag==1&&need_length=free_table[i].length){count++;if(count==1||free_table[i].lengthfree_table[k].length)k=i;}i=i+1;}if(k!=-1){if((free_table[k].length-need_length)=minsize)//整个分配{free_table[k].flag=0;ads=free_table[k].address;len=free_table[k].length;}else{//切割空闲区ads=free_table[k].address;len=need_length;free_table[k].address+=need_length;free_table[k].length-=need_length;}i=0;//循环寻找内存分配表中标志为空栏目的项while(used_table[i].flag!=0){i=i+1;}if(i=n-1)//找到，在已分配区表中登记一个表项{used_table[i].address=ads;used_table[i].length=len;used_