实验要求
1)实现一个完整的(可变)动态分区管理器,包括分配,回收,分区碎片整理等。希望同学们实现如下功能:
2)初始化功能:内存状态设置为初始状态。
3)分配功能:利用首次适应算法进行分配。
4)回收功能:对不用的作业进行回收。
5)空闲块的合并:即紧凑功能,用以消除碎片。当做碎片整理时,需要跟踪分配的空间,修改其引用以保证引用的正确性。
6)显示当前内存的使用状态,可以使用表格或图形。
设计思路
动态分区管理可以用两种数据结构实现,一种是已分配区表和空闲区表,也就是用预先定义好的系统空间来存放空间分配信息。设置了两个结构体分别来表示已分配区表和空闲区表,其中blanks用来表示空闲区表,其中有分区大小、起始地址两个参数。Job用来表示存放在内存中的作业,其中有作业名字、大小、起始地址三个参数。
实验结果与分析
设置内存总大小为1024KB,进入程序后有四种选项,插入作业请输入1,回收作业请输入0,紧凑请输入2, 查看内存信息请输入3,退出程序请输入4。
图1-1 程序选项图
输入1后,程序可作业进行内存分配

图1-2 内存分配
并且展示当前内存信息

图1-3 当前内存信息

插入a、b、c三个作业后,内存信息如下所示

图1-4 三个作业
此时输入0,将b作业收回,程序运行效果如下

图1-5 收回b作业
此时已经产生了碎片,输入2,进行紧凑操作,程序进行重定位,自动改变了当前内存中作业的起始地址

图1-6 紧凑效果
当内存各分区中都无大小大于该作业的可用区时,判断空闲分区总和是否大于该作业的大小,若满足条件,则在紧凑后放入。如下图所示,此时若插入一个大小为130KB的作业,则必须进行紧凑后才能放入

图1-7 当前内存信息
插入一个名字为jincou的作业,大小为130KB,根据程序运行结果可以发现是经过了紧凑的,说明程序运行正确。

图1-8 紧凑后插入成功
源程序
#include<iostream> using namespace std; const int N = 50, SIZE = 1024; int M, K;//M当前空闲分区数, K 当前内存中作业数 struct blank //用表来存储空闲分区 { int size;//分区大小 int start;//起始地址 }blanks[N]; struct job//用来存放内存中的作业 { string name;//作业名字 int size;//大小 int start;//起始地址 }jobs[N]; void init()//初始化 { blanks[0].size = SIZE; blanks[0].start = 0; M ++; } void tight()//紧凑 { int sum = 0;//空闲分区总和 for(int i = 0; i < M; i ++) sum += blanks[i].size; blanks[0].size = sum; blanks[0].start = SIZE - sum; M = 1; int address = 0;//动态重定位 for(int i = 0; i < K; i ++) { jobs[i].start = address; address += jobs[i].size; } } bool fenpei(string name, int size)//按动态分区方式进行分配,成功分配返回true,否则返回false { for(int i = 0; i < M; i ++) { if(size <= blanks[i].size)//找到可以放下该作业的空闲分区 { jobs[K].size = size; jobs[K].name = name; jobs[K ++].start = blanks[i].start;//将该作业调入内存,插入job表中 cout << "作业 " << name << " 被分配到第 " << i << " 分区" << endl; if(size == blanks[i].size)//如果大小相等就将该空白分区删除 { for(int j = i + 1; j < M; j ++)//覆盖法 blanks[j - 1] = blanks[j]; M --; } else//大小不相等,改变空白分区的大小和起始位置 { blanks[i].size = blanks[i].size - size; blanks[i].start = blanks[i].start + size; } tight();//紧凑 return true;//分配完成,返回 } } return false; } void add() { cout << "请输入作业名、作业大小" << endl; string name; int size; cin >> name >> size; if(fenpei(name, size)) return ; int sum = 0;//空闲分区总和 for(int i = 0; i < M; i ++) sum += blanks[i].size; if(sum < size)//空闲分区总和小于该作业大小 cout << "作业过大,无法分配" << endl; else { tight();//紧凑 fenpei(name, size); } } void recycle() { cout << "请输入作业名" << endl; string name; cin >> name; int i; bool flag = false;//是否找到该作业 for(i = 0; i < K; i ++) { if(jobs[i].name == name)//找到该作业的下标 { flag = true; break; } } if(!flag) { cout << "该作业不存在,输入有误!" << endl; return ; } int start = jobs[i].start, end = jobs[i].size + jobs[i].start;//该作业占用的开始点和结束点 flag = false;//该回收区是否有后邻接区 for(int j = 0; j < M; j ++) { int blank_start = blanks[j].start, blank_end = blanks[j].size + blanks[j].start; if(blank_start == end)//找到后邻接区 { flag = true; blanks[j].start = start; blanks[j].size = blanks[j].size + jobs[i].size;//更新后邻接区 if(j > 0 && start == blanks[j - 1].size + blanks[j - 1].start)//有前邻接区 { blanks[j].start = blanks[j - 1].start; blanks[j].size = blanks[j].size + blanks[j - 1].size; for(int j = i + 1; j < M; j ++)//覆盖法 blanks[j - 1] = blanks[j]; M --; } } } if(!flag)//没有后邻接区,检查是否有前邻接区 { for(int j = 0; j < M; j ++) { int blank_start = blanks[j].start, blank_end = blanks[j].size + blanks[j].start; if(start == blank_end)//找到前邻接区 { flag = true; blanks[j].size = blanks[j].start + blanks[j].size + jobs[i].size;//更新后邻接区 } } if(!flag)//既没前邻接区也没有后邻接区, 要插入一个新的空白区 { int k;//找到该作业该插入的位置 for(k = 0; k < M; k ++) if(start < jobs[k].start) break; k --; for(int j = M - 1; j >= k; j --) blanks[j + 1] = blanks[j]; blanks[k].size = jobs[i].size; blanks[k].start = jobs[i].start; M ++; } } for(int j = i + 1; j < K; j ++)//覆盖法,从内存中的作业队列中删除它 jobs[j - 1] = jobs[j]; K --; } void show() { cout << "----------------------当前内存信息----------------------" << endl; cout << "空白分区表:" << endl; for(int i = 0; i < M; i ++) cout << "第 " << i << " 空白分区 :" << "起始地址 " << blanks[i].start << " 分区大小 " << blanks[i].size << endl; cout << "已分配区表: " << endl; for(int i = 0; i < K; i ++) cout << "第 " << i << " 已分配分区 :" << "分配作业名 " << jobs[i].name << " 起始地址 " << jobs[i].start << " 分区大小 " << jobs[i].size << endl; cout << "----------------------当前内存信息----------------------" << endl; cout << endl; } int main() { cout << "首次适应算法的模拟,内存总大小为1024KB" << endl; init(); while(1) { int op; cout << "插入作业请输入1,回收作业请输入0,紧凑请输入2, 查看内存信息请输入3,退出程序请输入4" << endl; cin >> op; if(op == 4) return 0; if(op == 1) add();//插入作业 else if(op == 0) recycle();//回收作业 else if(op == 2) tight();//紧凑 else if(op == 3) show();//显示内存信息 show();//显示内存信息 } return 0; }
讯享网

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/77986.html