C++ 主存分配与回收算法优化：最优分配算法实现
#include
struct use { float address; //已分分区起始地址 float length; //已分分区长度,单位为字节 string flag; //已分分区是否可用标志 char uname; //作业名 int next; //指向下一个已用分区的指针 } usetable[n]; //已分配区表
struct free { float address; //空闲区起始地址 float length; //空闲区长度单位为字节 string flag; //空闲区表登记栏标志 char fname; int next; //指向下一个空闲分区的指针 } freetable[m]; //空闲区表
struct ok { int uhead; //已分分区头指针 int utail; //已分分区尾指针 int fhead; //空闲区头指针 int ftail; //空闲区尾指针 } point; //定义指针结构
void allocate(char j, float xk) { //采用最优分配算法分配xk大小的空间 int i, k, p, c; float ad; k = -1; i = point.fhead; do { //寻找空间大于xk的最小空闲区登记项k if(freetable[i].length >= xk && freetable[i].flag == '可用') { if(k == -1 || freetable[i].length < freetable[k].length) { k = i; } } p = c; c = i; i = freetable[i].next; } while(i != -1); //寻找最优空闲区
if(k == -1) {
cout << '无可用空闲区' << endl;
return;
}
//找到可用空闲区,开始分配
//若空闲区大小与要求分配的空间差小于minisize, 则空闲区全部分配
//若空闲区大小与要求分配的空间差大于minisize,则从空闲区划出一部分分配
if(freetable[k].length - xk <= minsize) {
freetable[k].flag = '空表目';
xk = freetable[k].length;
ad = freetable[k].address;
freetable[k].fname = ' ';
freetable[k].length = 0;
freetable[k].address = 0;
if(k == point.fhead) {
point.fhead = freetable[k].next;
}
if(k == point.ftail) {
point.ftail = p;
}
if(k != point.fhead && k != point.ftail) {
freetable[p].next = freetable[k].next;
}
} else {
freetable[k].length = freetable[k].length - xk;
ad = freetable[k].address;
freetable[k].address = freetable[k].address + xk;
freetable[k].fname = ' ';
freetable[k].flag = '可用';
}
//修改已分配区表
i = 0;
while(usetable[i].flag != '空表目' && i < n) { //寻找空表目
i++;
if(i >= n) { //无表目填写已分分区
cout << '无表目填写已分分区，错误' << endl;
//修正空闲区表
if(freetable[k].flag == '空表目') { //前面找到的是整个空闲区
freetable[k].flag = '已分配';
} else { //前面找到的是某个空闲区的一部分
freetable[k].length = freetable[k].length + xk;
}
return;
} else { //修改已分配区表
usetable[i].address = ad;
usetable[i].length = xk;
usetable[i].flag = '已分配';
usetable[i].uname = j;
}
}
if(point.uhead == -1) {
point.uhead = point.utail = i;
} else {
usetable[point.utail].next = i;
usetable[i].next = -1;
point.utail = i;
}
}
void reclaim(char J) { int i, k, j, s, t, p; float S, L;
//寻找已分配区表中对应登记项
s = point.uhead;
t = s;
if(s == -1) {
cout << '没有找到该作业' << endl;
return;
}
while(s != -1) {
if(usetable[s].uname == J && s < n) {
p = t;
k = s;
break;
}
t = s;
s = usetable[s].next;
}
if(s == -1) { //在已分配区表中找不到名字为J的作业
cout << '找不到该作业' << endl;
return;
}
//修改已分配区表
usetable[s].flag = '空表目';
usetable[s].uname = ' ';
//取得归还分区的起始地址S和长度L
S = usetable[s].address;
L = usetable[s].length;
usetable[s].address = 0;
usetable[s].length = 0;
if(s == point.uhead) {
point.uhead = usetable[s].next;
usetable[s].next = -1;
}
if(s == point.utail) {
point.utail = p;
usetable[p].next = -1;
}
if(s != point.uhead && s != point.utail) {
usetable[p].next = usetable[s].next;
usetable[s].next = -1;
}
//寻找回收分区
j = -1; k = -1; i = 0;
while(i < m && (j == -1 || k == -1)) {
if(freetable[i].flag == '可用') {
if(freetable[i].address + freetable[i].length == S) k = i; //找到上邻
if(freetable[i].address == S + L) {
j = i; //找到下邻
i++;
}
}
i++;
} //查找符合条件的可用单元。
if(k != -1) {
if(j != -1) { // 上邻空闲区，下邻空闲区,三项合并
freetable[k].length = freetable[j].length + freetable[k].length + L;
freetable[k].flag = '可用';
freetable[k].fname = ' ';
freetable[j].length = freetable[j].address = 0;
freetable[j].fname = ' ';
} else { //上邻非空闲区，下邻为空闲区，与下邻合并
freetable[k].length = freetable[k].length + L;
freetable[k].fname = ' ';
}
} else {
if(j != -1) {
freetable[j].address = S;
freetable[j].length = freetable[j].length + L;
freetable[j].fname = ' ';
} else { //上下邻均为非空闲区,回收区域直接填入
//在空闲区表中寻找空栏目
t = 0;
while(freetable[t].flag == '可用' && t < m) {
t++;
}
if(t > m) { //空闲区表满,回收空间失败,将已分配区表复原
cout << '主空闲表没有空闲空间回收失败' << endl;
return;
}
freetable[t].address = S;
freetable[t].length = L;
freetable[t].flag = '可用';
freetable[t].fname = ' ';
freetable[point.ftail].next = t;
point.ftail = t;
freetable[t].next = -1;
return;
}
}
}
void main() { char name; float xk; //空闲区表初始化 freetable[0].address = 10240; //假定空闲区表内存起始地址 freetable[0].length = 102400; //假定空闲区表的空间大小 freetable[0].flag = '可用'; freetable[0].next = -1; int i, a; point.uhead = point.utail = -1; point.fhead = 0; point.ftail = 0; for(i = 1; i < m; i++) { freetable[i].flag = '空表目'; freetable[i].length = 0; freetable[i].address = 0; freetable[i].uname = ' '; freetable[i].next = -1; } //已分配区表初始化 for(i = 0; i < n; i++) { usetable[i].flag = '空表目'; usetable[i].length = 0; usetable[i].address = 0; usetable[i].uname = ' '; usetable[i].next = -1; } while(1) { cout << endl << '选择功能项(0-退出,1-分配主存,2-回收主存,3-显示主存)' << endl; cout << '选择功能项(0-3):'; cin >> a; switch(a) { case 0:exit(0); //a=0程序结束 case 1: //a=1分配主存空间 cout << '输入作业名和作业所需长度:'; cin >> name >> xk; allocate(name, xk); break; case 2: //a=2回收主存空间 cout << '输入要回收的作业名:'; cin >> name; reclaim(name); //回收主存空间 break; case 3: //a=3显示主存情况输出空闲区表和已分配区表 cout << endl << '输出空闲表区:' << endl << '项名起始地址分区长度标志' << endl; i = point.fhead; while(i != -1 && i < m) { cout << setiosflags(ios::left) << setw(7) << i << setw(8) << setiosflags(ios::left) << freetable[i].address << setw(8) << setiosflags(ios::left) << freetable[i].length << setw(8) << setiosflags(ios::left) << freetable[i].flag << endl; i = freetable[i].next; } cout << endl << '输出已分配区表:' << endl; cout << '项名起始地址分区长度标志' << endl; i = point.uhead; while(i != -1 && i < n) { cout << setiosflags(ios::left) << setw(7) << usetable[i].uname << setiosflags(ios::left) << setw(8) << usetable[i].address << setiosflags(ios::left) << setw(8) << usetable[i].length << setiosflags(ios::left) << setw(8) << usetable[i].flag << endl; i = usetable[i].next; } break; default:cout << '没有这个选项' << endl; } }
原文地址: https://www.cveoy.top/t/topic/nZBr 著作权归作者所有。请勿转载和采集!