C++ 最优分配算法实现：内存分配与回收详解
#include
// 采用最优分配算法分配xk大小的空间 void allocate(char j, float xk) { int i, k, p, c; float ad; k = -1; i = point.fhead; c = i; 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; } if (freetable[k].length - xk <= minsize) // 空闲区大小与要求分配的空间差小于minisize,则空闲区全部分配 { 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; } } return; }
// 主存归还函数 void reclaim(char J) { int i, k, j, s, t, p; float S, L; // 寻找已分配区表中对应登记项 s = point.uhead; t = s; if (s == -1) { cout << '没有找到该作业\n' << endl; return; } while (s != -1) { if (usetable[s].uname == J && s < n) { p = t; k = s; break; } t = s; s = usetable[s].next; } s = k; if (s == -1) { cout << '没有找到该作业\n' << endl; return; } if (s >= n) // 在已分配区表中找不到名字为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; //usetable[s]. next= -1; if (s == point.uhead) { point.uhead = usetable[s].next; usetable[s].next = -1; } if (s == point.utail) { point.utail = p; usetable[s].next = -1; usetable[p].next = -1; } if (s != point.uhead && s != point.utail) { usetable[p].next = usetable[s].next; usetable[s].next = -1; } // 寻找回收分区的上下邻空闲区，上邻表目k,下邻表目j 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++; } // 查找符合条件的可用单元。 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; // 假定空闲区表内存起始地址 10240+102400 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].fname = ' '; 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: cout << '输入作业名和作业所需长度:'; cin >> name >> xk; allocate(name, xk); break; case 2: cout << '输人要回收的作业名:'; cin >> name; reclaim(name); break; case 3: cout << endl << '输出空闲表区:\n 项名 起始地址 分区长度 标志\n'; 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 << '输出已分配区表:\n'; cout << '项名 起始地址 分区长度 标志\n'; 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/n8wk 著作权归作者所有。请勿转载和采集!