操作系统---动态分区存储管理方式的主存分配回收
程序员文章站
2022-07-12 14:50:36
...
一.实验目的
深入了解动态分区存储管理方式主存分配回收的实现。
二.实验要求
1.使用动态分区存储管理方式分配回收内存。
2.使用最优适应算法完成主存空间的分配。
3.输出空闲表，分配表，内存的分配情况。
三.实验设计
-
算法思想： 利用最优适应算法分配内存，使用合并内存进行回收内存。
-
最优适应算法： 每次为作业分配主存时，总把能满足要求的，又是最小的空闲的主存分配给作业，避免“大材小用”。
-
具体实现: 通过第一次遍历空闲表时，查找满足作业大小的主存空间(所谓的满足，不是指空间大小必须相等，而是主存的空间大小与作业的大小差值小于系统规定的值（这样可以避免分割碎片）)，若找到满足的主存空间，即对作业进行分配主存空间，修改空闲表和分配表；若没有找到满足主存空间，则进行第二次遍历空闲表，查找第一个大于作业的大小的主存空间，对主存空间进行分割，修改空闲表和分配表。
-
合并空间回收内存： 进行内存回收时，分为四种情况：
1.回收区与前一个空闲区F1相邻，仅修改空闲区的大小。
2.回收区与后一个空闲区F2相邻，修改空闲区的起始地址和空闲区的地址。
3.回收区既与前一个空闲区F1相邻，又与后一个空闲区F2相邻，修改空闲区的起始地址 和空间大小，将空闲区F2的信息从空闲表中删除。
4.回收区既不与前一个空闲区F1相邻，又不与后一个空闲区F2相邻，直接在空闲表加入回收区的信息。 -
具体实现： 通过输入作业名，进行对作业的回收。首先，在分配表中查找作业名，若找到，则在空闲表中进行遍历查看符合以上四种情况的哪一种，执行回收区回收后，要在分配表中将该作业删除。若没找到，则输出作业名不存在。
-
算法流程图
-
最优适应算法
-
内存回收
四.代码设计：
1.空闲表结构：
struct free_table{
int address;
int size;
int flag;//空闲时为0,分配时为1
};
2.分配表结构：
struct used_table{
string process;//作业名
int address;
int size;
int flag;
};
3.空闲表：
free_table a[1]={0,100,0};
vector<free_table> vec_free(a,a+1);//空闲表初始化
使用向量存放空闲表，对内存空闲表初始化,每次回收或分配一个作业，空闲表变动一次。
4.分配表：
vector<used_table> vec_used;
使用向量存放分配表，开始时分配表为空，每次分配或回收一个作业，分配表变动一次。
5.内存：
vector<used_table> vec;
使用向量存放分配表，开始时内存和空闲表相同，每次分配或回收一个作业，
内存变动一次。
代码实现：
#include<iostream>
#include<algorithm>
#include<windows.h>
#include<string>
#include<vector>
#define MIN 5
using namespace std;
struct free_table{
int address;
int size;
int flag;//空闲时为0,分配时为1
};
struct used_table{
string process;//作业名
int address;
int size;
int flag;
};
free_table a[1]={0,100,0};
vector<free_table> vec_free(a,a+1);//空闲表初始化
vector<used_table> vec_used;//分配表
vector<used_table> vec;//内存
vector<free_table>::iterator it_f;//空闲表指针
vector<used_table>::iterator it_u;//分配表指针
void Output_free(vector<free_table> vec_free);//输出空闲表
void Output_used(vector<used_table> vec_used);//输出分配表
void Output(vector<used_table> vec);//输出内存分配
void Input();//进程分配输入
void findsize(vector<free_table> &vec_free,vector<used_table> &vec_used,int size,string process);//最优适应算法分配
void recycle();//内存回收输入
void Refindsize(vector<free_table> &vec_free,vector<used_table> &vec_used,string process);//内存回收算法
void Memory(vector<free_table> &vec_free,vector<used_table> &vec_used,vector<used_table> &vec);//查看总内存分配
void menu();
bool cmp(free_table &a,free_table &b){//用于排序的比较
return a.address<b.address;
}
bool cmp1(used_table &a,used_table &b){//用于排序的比较
return a.address<b.address;
}
int main(){
menu();
}
void menu(){
int chose;
cout<<"\t\t\t"<<"请选择您要进行的操作"<<endl;
cout<<"\t\t\t"<<"退出运行------------0"<<endl;
cout<<"\t\t\t"<<"进程分配------------1"<<endl;
cout<<"\t\t\t"<<"进程回收------------2"<<endl;
cout<<"\t\t\t"<<"查看空闲表----------3"<<endl;
cout<<"\t\t\t"<<"查看分配表----------4"<<endl;
cout<<"\t\t\t"<<"查看内存分配--------5"<<endl;
cout<<"请输入要操作编号"<<endl;
cin>>chose;
switch(chose){
case 0:
exit(1);
break;
case 1:
Input();
system("pause");
system("cls");
menu();
break;
case 2:
recycle();
system("pause");
system("cls");
menu();
break;
case 3:
Output_free(vec_free);
system("pause");
system("cls");
menu();
break;
case 4:
Output_used(vec_used);
system("pause");
system("cls");
menu();
break;
case 5:
Output(vec);
system("pause");
system("cls");
menu();
break;
default:
cout<<"请输入正确的编号"<<endl;
system("cls");
menu();
break;
}
}
void Output_free(vector<free_table> vec_free){
cout<<"输出空闲表:"<<endl;
cout<<"起始地址"<<" "<<"空间大小"<<" "<<"标志位"<<endl;
for(it_f=vec_free.begin();it_f!=vec_free.end();it_f++){
cout<<it_f->address<<"\t\t"<<it_f->size<<"\t\t"<<it_f->flag<<endl;
}
}
void Output_used(vector<used_table> vec_used){
cout<<"输出分配表:"<<endl;
cout<<"作业名称"<<" "<<"起始地址"<<" "<<"空间大小"<<" "<<"标志位"<<endl;
for(it_u=vec_used.begin();it_u!=vec_used.end();it_u++){
cout<<it_u->process<<"\t\t"<<it_u->address<<"\t\t"<<it_u->size<<"\t\t"<<it_u->flag<<endl;
}
}
void Output(vector<used_table> vec){
Memory(vec_free,vec_used,vec);
cout<<"输出内存分配:"<<endl;
cout<<"作业名称"<<" "<<"起始地址"<<" "<<"空间大小"<<" "<<"标志位"<<endl;
for(it_u=vec.begin();it_u!=vec.end();it_u++){
cout<<it_u->process<<"\t\t"<<it_u->address<<"\t\t"<<it_u->size<<"\t\t"<<it_u->flag<<endl;
}
}
void Input(){
int num;
string pro;//输入的进程名
int size;//输入的进程申请空间大小
cout<<"请输入待分配进程的个数"<<endl;
cin>>num;
for(int i=0;i<num;i++){
cout<<"请输入待分配进程名称，空间大小"<<endl;
cin>>pro>>size;
findsize(vec_free,vec_used,size,pro);
sort(vec_used.begin(),vec_used.end(),cmp1);
}
}
void findsize(vector<free_table> &vec_free,vector<used_table> &vec_used,int size,string process){
int flag=0;//若第二次遍历也未找到空间分配，表明没有空间为其分配
int tag=0;//用于标识第一次循环没有找到合适的分配空间
for(it_f=vec_free.begin();it_f!=vec_free.end();){
int space=it_f->size-size;
if(space>MIN||space<0){
it_f++;
}
else{//刚好有小于MIN空间进行分配
tag=1;
used_table record;
record.process=process;
record.size=it_f->size;
record.address=it_f->address;
record.flag=1;
vec_free.erase(it_f);//从空闲表中删除该块
vec_used.push_back(record);//向分配表中加入该块
break;
}
}
if(tag==0){//循环一次没有找到地址对他进行分配
vector<free_table>::iterator it_t;//临时指针
for(it_t=vec_free.begin(),it_f=vec_free.begin();it_f!=vec_free.end();it_t++){
int space=it_f->size-size;
if(space>0){//按照需要进行分割
flag=1;
used_table record;
record.process=process;
record.size=size;
record.address=it_f->address;
record.flag=1;
vec_used.push_back(record);
it_f->size=space;
it_f->address=it_f->address+size;
it_f->flag=0;
break;
}
else{
it_f++;
}
}
}
if(flag==0&&tag==0){//第一轮和第二轮都没有对其进行空间分配
cout<<"空间已满！"<<endl;
}
}
void recycle(){//回收
int num;
string pro;
cout<<"请输入要回收的进程个数"<<endl;
cin>>num;
for(int i=0;i<num;i++){
cout<<"请输入要回收的进程名"<<endl;
cin>>pro;
Refindsize(vec_free,vec_used,pro);
}
}
void Refindsize(vector<free_table> &vec_free,vector<used_table> &vec_used,string process){
vector<free_table>::iterator it;
int num=vec_used.size();
int flag=0;
int tag=0;
for(it_u=vec_used.begin();it_u!=vec_used.end();){
flag++;
if(it_u->process==process){
for(it_f=vec_free.begin();it_f!=vec_free.end();){
it=it_f+1;
//回收区与前一个相邻，又与后一个相邻
if(it_f->address+it_f->size==it_u->address&&it_u->address+it_u->size==it->address){
cout<<"回收区与前一个相邻，又与后一个相邻"<<endl;
it_f->size=it_f->size+it_u->size+it->size;//将三个空闲区合并，删除后一个空闲区
vec_free.erase(it);
vec_used.erase(it_u);
tag=1;
break;
}
//回收区与前一个相邻
else if(it_f->address+it_f->size==it_u->address){
cout<<"回收区与前一个相邻"<<endl;
it_f->size=it_f->size+it_u->size;//起址不变，修改空闲区变大
vec_used.erase(it_u);
tag=1;
break;
}
//回收区与后一个相邻
else if(it_f->address==it_u->address+it_u->size){
cout<<"回收区与后一个相邻"<<endl;
it_f->address=it_u->address;//修改起址，修改空闲区
it_f->size=it_u->size+it_f->size;
vec_used.erase(it_u);
tag=1;
break;
}
//回收区没有与之相邻
else{
it_f++;
}
}
if(tag==0){
cout<<"回收区没有与之相邻 "<<endl;
free_table record;
record.size=it_u->size;
record.address=it_u->address;
record.flag=0;
vec_free.push_back(record);
sort(vec_free.begin(),vec_free.end(),cmp);
vec_used.erase(it_u);
}
}
else{
it_u++;
}
}
if(flag>num){//遍历一遍没有找到
cout<<"没有找到该进程名"<<endl;
}
}
void Memory(vector<free_table> &vec_free,vector<used_table> &vec_used,vector<used_table> &vec){
if(vec_free.size()==0){//全部分配完
it_u=vec_used.begin();
while(it_u!=vec_used.end()){
used_table record;
record.size=it_u->size;
record.address=it_u->address;
record.flag=0;
record.process=it_u->process;
vec.push_back(record);
it_u++;
}
}
else if(vec_used.size()==0){//全部没有分配
it_f=vec_free.begin();
while(it_f!=vec_free.end()){
used_table record;
record.size=it_f->size;
record.address=it_f->address;
record.flag=0;
record.process="#";
vec.push_back(record);
it_f++;
}
}
else{
for(it_f=vec_free.begin(),it_u=vec_used.begin();it_f!=vec_free.end()&&it_u!=vec_used.end();){
if(it_f->address<it_u->address){
used_table record;
record.size=it_f->size;
record.address=it_f->address;
record.flag=0;
record.process="#";//表示内存空间为空,没有分配作业
vec.push_back(record);
it_f++;
}
else{
used_table record;
record.size=it_u->size;
record.address=it_u->address;
record.flag=1;
record.process=it_u->process;
vec.push_back(record);
it_u++;
}
}
while(it_f==vec_free.end()&&it_u!=vec_used.end()){
used_table record;
record.size=it_u->size;
record.address=it_u->address;
record.flag=1;
record.process=it_u->process;
vec.push_back(record);
it_u++;
}
while(it_f!=vec_free.end()&&it_u==vec_used.end()){
used_table record;
record.size=it_f->size;
record.address=it_f->address;
record.flag=0;
record.process="#";
vec.push_back(record);
it_f++;
}
}
}
五.实验结果
- 主界面
- 输入作业
- 回收作业
- 查看空闲表
- 查看分配表
- 查看内存分配
推荐阅读
-
操作系统-在分页式管理方式下采用位示图来表示主存分配情况，实现主存空间的分配和回收。
-
操作系统---动态分区存储管理方式的主存分配回收
-
采用可变式分区管理，使用首次适应算法实现主存的分配与回收（C++实现）
-
采用可变式分区管理，使用空闲区链实现主存的分配与回收（C++实现）
-
【操作系统实验 / C++】在分页管理方式下采用位示图来表示主存分配情况，实现主存分配和回收（附代码）
-
PHP5.3的垃圾回收机制(动态存储分配方案)深入理解
-
PHP5.3的垃圾回收机制(动态存储分配方案)深入理解_PHP教程
-
PHP5.3的垃圾回收机制(动态存储分配方案)深入理解_php技巧
-
PHP5.3的垃圾回收机制(动态存储分配方案)深入理解_PHP
-
PHP5.3的垃圾回收机制(动态存储分配方案)深入理解_PHP教程