主 存 的 分 配 回 收
班级：网络081 姓名：甘春泉 学号：200800824126 实验四: 主存的分配回收
一、实验目的 深入了解动态分区存储管理方式主存分配回收的实现。 二、实验主要内容 编写程序完成动态分区存储管理方式的主存分配回收的实现。实现 具体内容包括：首先确定主存空间分配表；然后采用最优适应算法完成 主存空间的分配与回收；最后编写主函数对所做工作进行测试。
表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此，“已 分配区表”和“空闲区表”在 实验中有如下的结构定义。 已分配区表的定义： #define n 10 //假定系统允许的最大作业数量为n struct{ float address; //已分分区起始地址 float length; //已分分区长度，单位为字节 int flag; //已分配表区登记栏标志，用0表示空栏目， }used_table[n]; //已分配区表 空闲区表的定义： #define m 10 //假定系统允许的空闲区表最大为m struct{ float address; //空闲区起始地址 float length; //空闲区长度，单位为字节 int flag; //空闲区表登记栏目用0表示空栏目，1表示未 分配? }free_table[m]; //空闲区表 其中分区起始地址和长度数值太大，超出了整形表达范围，所有采用 float类型。 2． 在设计的表格上进行主存分配 当要装入一个作业时，从空闲区表中查找标志为“未分配”的空闲 区，从中找一个能容纳该作业的空闲区。如果找到的空闲区正好等于该 作业的长度，则把该分区全部 分配给该作业。这时应该把该空闲区登 记栏中的标志改为“空”，同时在已分配区表中找到一个标志 为“空”的栏目登记新装入作业所占用分区的起始地址、长度和 作业 名。如果找到的空闲区大于作业长度，则把空闲区分成两部分，一部分 用来装入作业，另一部分你仍然为空闲区，这时只要修改空闲区的长 度，且把新装入的作 业登记到已分配区表中。 主存分配算法目前一般采用三种算法：首次适应算法、循环首次适 应算法、最佳适应算法。本实验中采用最佳适应算法为作业分配主存。 最佳适应算法会出现空闲分区分割后剩下的空闲分区很小以至于无法使 用的情况，为了在一定程度上解决这个问题，如果空闲分区的大小比作 业要求的长度略大一点，不再将空闲区分区分割成已分分区和空闲分区 两部分，而是将整个空闲区分配给作业。 在实现最佳适应算法时，可把空闲分区按长度递增方式登记在空闲 区表中。分配时顺序查找空闲表，查找到的第一个空闲区就是满足作业 要求的最小分区。这样查找 速度快，但是为使空闲区按照长度递增登
空闲区又无下邻空闲区。这时，应该在空闲区表中查找一个状态 为“空”的栏目（假定查到的是第t栏），则第t栏的内容修改如下： 第t栏起始地址＝S； 第t栏的长度＝L； 第t栏的状态＝“未分配”； 这样，第t栏指示的空闲区是归还区。 由于是实验，没有真正的主存要分配，所有在实验中，首先应建 立一张空闲区表，初始状态只有一个空闲登记项（假定的主存空闲区） 和一张所有状态都为“空”的 已分配区表，假定主存空间100KB，全部 为空闲区（实际上操作系统需要占用一部分）；然后，可以选择进行主 存分配或回收，如果是分配，要求输入作业名和 所需主存空间大小； 如果是回收，输入回收作业名；循环进行主存分配和回收后，如果需 要，则显示两张表的内容，以检查主存的分配和回收是否正确。 五、核心代码 void main(){ int i,a; float xk; char J; //空闲区表初始化 free_table[0].address=SADDRESS; //空闲分区表的起始地址 free_table[0].length=SLENGTH; //空闲分区表的长度 free_table[0].flag=1; //标志位置1表示未分配 for(i=1;i<m;i++) free_table[i].flag=0; //0表示空栏目 //已分区表初始化 for(i=0;i<n;i++) used_table[i].flag=0; while(1){ cout<<"请选择功能项："<<endl <<"1-分配主存"<<endl <<"2-回收主存"<<endl <<"3-显示主存"<<endl <<"0-退出"<<endl <<"选择功能项(0-3):"; cin>>a;cin.ignore (); switch(a){ case 0: //当选择0时退出程序
return; case 1: {//a=1 分配主存空间 cout<<" 请输入作业名J和作业所需长度xk(作业名为一个字符，长 度XK要小于"<<SLENGTH<<"):"<<endl; cin>>J>>xk; allocate(J,xk); //为作业J分配主存空间 break;} case 2:{// a=2 回收主存空间 cout<<" 请输入要回收分区的作业名："; cin>>J; reclaim(J);//回收作业J的主存空间 break; } case 3: {//a=3 显示主存情况，输出空闲区表和已分配区表 cout<<" 输出空闲区表："<<endl <<" 起始地址 分区长度 标志"<<endl; for(i=0;i<m;i++) cout<<setw(10) <<free_table[i].address<<setw(10)<<free_table[i].length <<setw(10)<<free_table[i].flag<<endl; cout<<" 按任意键，输出已分配区表……"; cin.get(); cout<<" 输出已分配区表："<<endl <<" 起始地址 分区长度 标志"<<endl; for(i=0;i<n;i++){ if(used_table[i].flag!=0)//输出已分配给作业的表目 cout<<setw(10)<<used_table[i].address<<setw(10) <<used_table[i].length <<setw(10)<<(char)used_table[i].flag<<endl; else //输出空表目 cout<<setw(10) <<used_table[i].address<<setw(10)<<used_table[i].length <<setw(10)<<used_table[i].flag<<endl; } break;} default:{ cout<<" 没有该选项！"<<endl; break;} } //switch }//while cin.get();
} //main/*采用最优分配算法为作业J分配xk大小的空间*/ void allocate(char J,float xk){ int i,k; float ad; k=-1; for(i=0;i<m;i++){ //找空间大于xk的最小空闲区登记项k if(free_table[i].length>=xk&&free_table[i].flag==1) if(k==-1||free_table[i].length<free_table[k].length) //保证 登记项k的空闲区最优 k=i;}//for if(k==-1){ //未找到可用空闲区，返回 cout<<"无可用空闲区！！"<<endl; return;} /*找到可用空闲区，开始分配：若空闲区大小与作业要求分配的空间差 小于minisize,则将找到的空闲区 全部分配给该作业；若空闲区大小与要求分配的空间的差大于 minisize,则从空闲区划出一部分分配给作业。*/ if(free_table[k].length-xk<=minisize){ free_table[k].flag=0; ad=free_table[k].address; xk=free_table[k].length;//将free_table[k].length长度空间全部 分配给J} else{ free_table[k].length=free_table[k].length-xk; ad=free_table[k].address+free_table[k].length;} /*修改已分配区表*/ i=0; while(used_table[i].flag!=0&&i<n) i++; //找空表目i if(i>=n){ cout<<"无表目填写已分分区，错误！"<<endl; //修正空闲分区表，将其恢复到未分配前 if(free_table[k].flag==0) //当free_table[k].lengthxk<minisize时，作业J应全部归还空间 free_table[k].flag=1; //将登记项中的标志位设为未分配标志1 则归还了空间 else free_table[k].length=free_table[k].length+xk; return; }//if