C++操作系统内存分配算法的实现详解

⽬录

⼀、实验⽬的⼆、实验内容三、实验要求四、代码实现五、测试样例

⼀、实验⽬的

通过本实验帮助学⽣理解在动态分区管理⽅式下应怎样实现主存空间的分配和回收。

⼆、实验内容

在动态分区管理⽅式下采⽤不同的分配算法实现主存分配和实现主存回收。

三、实验要求

（1）可变分区⽅式是按作业需要的主存空间⼤⼩来分割分区的。当要装⼊⼀个作业时，根据作业需要的主存量查看是否有⾜够的空闲空间，若有，则按需要量分割⼀个分区分配给该作业；若⽆，则作业不能装⼊。随着作业的装⼊、撤离、主存空间被分成许多个分区，有的分区被作业占⽤，⽽有的分区是空闲的。例如：

为了说明哪些区是空闲的，可以⽤来装⼊新作业，必须要有⼀张空区说明表，格式如下：

其中

起址——指出⼀个空闲区的主存起始地址。

长度——指出从起始地址开始的⼀个连续空闲区的长度。

状态——有两种状态，⼀种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另⼀种是“空表⽬”状态，表⽰表中对应的登记项⽬是空⽩（⽆效），可⽤来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找⼀个“空表⽬”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表⽬”的登记栏⽬，否则造成表格“溢出”⽆法登记。上述的这张说明表的登记情况是按提⽰

（1）中的例所装⼊的三个作业占⽤的主存区域后填写的

（2）当有⼀个新作业要求装⼊主存时，必须查空闲区说明表，从中找出⼀个⾜够⼤的空闲区。有时找到的空闲区可能⼤于作业需要量，这时应把原来的空闲区变成两部分：⼀个部分分给作业占⽤；另⼀部分⼜成为⼀个较⼩的空闲区。为了尽量减少由于分割造成的“碎⽚”，在作业请求装⼊时，尽可能地利⽤主存的低地址部分的空闲区，⽽尽量保存⾼地址部分有较⼤的连续空闲区域，以利于⼤型作业的装⼊。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是⽐前者⼤。为了⽅便查找还可使表格“紧缩”，总是让“空表⽬”栏集中在表格的后部。

（3）采⽤⾸次适应算法或循环⾸次算法或最佳适应算法分配主存空间。由于本实验是模拟主存的分配，所以当把主存区分配给作业后并不实际启动装⼊程序装⼊作业，⽽⽤输出“分配情况”来代替。（即输出当时的空闲区说明表及其内存分配表）

（4）当⼀个作业执⾏结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成⼀个较⼤的空闲区，登记在空闲区说明表中。例如，在提⽰（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区⼀起合成⼀个⼤的空闲区登记在空闲区说明表中。

（5）请分别按⾸次适应算法、循环⾸次算法和最佳适应算法设计主存分配和回收的程序。然后按（1）中假设主存中已装⼊三个作业，且形成两个空闲区，确定空闲说明表的初值。现有⼀个需要主存量为6K的作业4 申请装⼊主存；然后作业3 撤离；再作业2 撤离。请你为它们进⾏主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显⽰出来或打印出来。

四、代码实现

MemoryAllocation.cpp

#include #include #include #include #include using namespace std;int MemorySize = 0;int OSSize = 0;

int Memory[1000] = { 0 };

struct Struct1{ int begin; int length;

string state;//值为未分配或者空条⽬};

queue WORK;//作业集合queue EMPTY;//空区集合//更新EMPTY队列，空区集合void UpdateEMP(){

while (!EMPTY.empty()) { EMPTY.pop(); }

for (int i = 0; i < MemorySize; i++) { if (Memory[i] == 0) {

for (int j = i + 1; j < MemorySize; j++) {

if (Memory[j] == 1 || j == MemorySize - 1) { Struct1 emp1; emp1.begin = i;

if (j == MemorySize - 1) { emp1.length = j - i + 1; }

else {

emp1.length = j - i; }

emp1.state = \"未分配\"; EMPTY.push(emp1); i = j; break; } } } }

cout << \"现有的空区说明表为：\" << endl; int s = EMPTY.size();

cout << s << \"块空区\" << endl; for (int i = 0; i < s; i++) { Struct1 emp1;

emp1 = EMPTY.front(); EMPTY.push(emp1); EMPTY.pop();

cout << \" 起始：\" << emp1.begin << \" 长度：\" << emp1.length << \" 状态：\" << emp1.state << endl; }}

//⾸次适应算法(FF)

void FF(int applyNum) { if (EMPTY.empty()) {

cout << \"没有⾜够的主存空间！！\" << endl; exit(0); }

bool flag = false;

while (!EMPTY.empty()) {

Struct1 emp1 = EMPTY.front(); if (emp1.length > applyNum) {

for (int i = emp1.begin; i< applyNum + emp1.begin ;i++) { Memory[i] = 1; }

Struct1 work3;

work3.begin = emp1.begin; work3.length = applyNum; work3.state = \"作业4\"; WORK.push(work3); UpdateEMP(); flag = true; break; }

EMPTY.pop();

}

if (!flag) {

cout << \"没有⾜够的主存空间！！\" << endl; exit(0); }

Sleep(2000); //作业三撤离

for (int i = 0; i < WORK.size(); i++) { Struct1 work1;

work1 = WORK.front();

if (work1.state == \"作业3\") {

for (int i = work1.begin; i < work1.begin+ work1.length;i++) { Memory[i] = 0; }

WORK.pop();

cout << endl << \"作业三撤离！\" << endl; UpdateEMP(); break; }

else {

WORK.pop();

WORK.push(work1); } }

Sleep(2000); //作业⼆撤离

for (int i = 0; i < WORK.size(); i++) { Struct1 work1;

work1 = WORK.front();

if (work1.state == \"作业2\") {

for (int i = work1.begin; i < work1.begin + work1.length; i++) { Memory[i] = 0; }

WORK.pop();

cout << endl << \"作业⼆撤离！\" << endl; UpdateEMP(); break; }

else {

WORK.pop();

WORK.push(work1); } }}

//循环⾸次适应算法（NF）void NF(int applyNum) { if (EMPTY.empty()) {

cout << \"没有⾜够的主存空间！！\" << endl; exit(0); }

bool flag = false;

while (!EMPTY.empty()) {

Struct1 emp1 = EMPTY.front(); if (emp1.length > applyNum) {

for (int i = emp1.begin; i < applyNum + emp1.begin; i++) { Memory[i] = 1;

}

Struct1 work3;

work3.begin = emp1.begin; work3.length = applyNum; work3.state = \"作业4\"; WORK.push(work3); UpdateEMP(); flag = true; break; }

EMPTY.pop();

}

if (!flag) {

cout << \"没有⾜够的主存空间！！\" << endl; exit(0); }

Sleep(2000); //作业三撤离

for (int i = 0; i < WORK.size(); i++) { Struct1 work1;

work1 = WORK.front();

if (work1.state == \"作业3\") {

for (int i = work1.begin; i < work1.begin + work1.length; i++) { Memory[i] = 0; }

WORK.pop();

cout << endl << \"作业三撤离！\" << endl; UpdateEMP(); break; }

else {

WORK.pop();

WORK.push(work1); } }

Sleep(2000); //作业⼆撤离

for (int i = 0; i < WORK.size(); i++) { Struct1 work1;

work1 = WORK.front();

if (work1.state == \"作业2\") {

for (int i = work1.begin; i < work1.begin + work1.length; i++) { Memory[i] = 0; }

WORK.pop();

cout << endl << \"作业⼆撤离！\" << endl; UpdateEMP(); break; }

else {

WORK.pop();

WORK.push(work1); } }}

//最佳适应算法(BF)

void BF(int applyNum) { if (EMPTY.empty()) {

cout << \"没有⾜够的主存空间！！\" << endl; exit(0); }

bool flag = false;

int col = 10000000;//记录每⼀个空区与请求⼤⼩的差值 string e = \"\";

int em = EMPTY.size()*2; for (int i = 0; i < em; i++) {

Struct1 emp1 = EMPTY.front(); if (emp1.length > applyNum) {

if (col == (emp1.length - applyNum) && e==emp1.state) { for (int i = emp1.begin; i < applyNum + emp1.begin; i++) { Memory[i] = 1; }

Struct1 work3;

work3.begin = emp1.begin; work3.length = applyNum; work3.state = \"作业4\"; WORK.push(work3); UpdateEMP(); flag = true; break; }

if (col > (emp1.length - applyNum)) { col = (emp1.length - applyNum); e = emp1.state; } }

EMPTY.pop();

EMPTY.push(emp1); }

if (!flag) {

cout << \"没有⾜够的主存空间！！\" << endl; exit(0); }

Sleep(2000); //作业三撤离

for (int i = 0; i < WORK.size(); i++) { Struct1 work1;

work1 = WORK.front();

if (work1.state == \"作业3\") {

for (int i = work1.begin; i < work1.begin + work1.length; i++) { Memory[i] = 0; }

WORK.pop();

cout << endl << \"作业三撤离！\" << endl; UpdateEMP(); break; }

else {

WORK.pop();

WORK.push(work1); } }

Sleep(2000); //作业⼆撤离

for (int i = 0; i < WORK.size(); i++) { Struct1 work1;

work1 = WORK.front();

if (work1.state == \"作业2\") {

for (int i = work1.begin; i < work1.begin + work1.length; i++) { Memory[i] = 0; }

WORK.pop();

cout << endl << \"作业⼆撤离！\" << endl; UpdateEMP(); break; }

else {

WORK.pop();

WORK.push(work1); } }}

//主函数int main() {

//打印提⽰信息

cout << \"************************************************\\n\"; cout << \" 操作系统实验内存分配算法\\n\";

cout << \" 作者：CSDN Carmelo_7 主页： https://blog.csdn.net/Carmelo_7?spm=1000.2115.3001.5343 \\n\"; cout << \"************************************************\\n\"; ifstream inFile;

inFile.open(\"MemoryAllocation.dat\"); if (!inFile.is_open())

cout << \"⽂件打开时候出错！！\" << endl; inFile >> MemorySize >> OSSize;

cout << \"请输⼊主存的现有状态\" << endl; cout << \"正在读取数据⽂件...\" << endl; Sleep(2000);

//打印空闲区说明表的初始状态

cout << \"主存总⼤⼩：\" << MemorySize << endl <<\"操作系统占⽤空间：\" << OSSize <int n = 0;

while (!inFile.eof()) { n++;

Struct1 work1;

inFile >> work1.begin >> work1.length; work1.state = \"作业\"+to_string(n); WORK.push(work1); }

int s = WORK.size(); for (int i = 0; i < s; i++) { Struct1 work2;

work2 = WORK.front(); WORK.push(work2); WORK.pop();

cout << work2.state << \" 起始：\" << work2.begin << \" 长度：\" << work2.length << endl; for (int i = work2.begin; i < work2.length + work2.begin; i++) { Memory[i] = 1; } }

/*for (int i : Memory) { cout << i; }*/

UpdateEMP();

cout << \"请输⼊新的作业的申请主存数量：\" << endl; //打印作业4的申请量 int applyNum = 0; cin >> applyNum;

cout << \"作业\" << n << \"申请了\"<< applyNum <<\"主存空间\" << endl;

cout << \"===================================================================================\" << endl;

cout << \"1.⾸次适应算法(FF) :将所有空闲分区按照地址递增的次序链接，在申请内存分配时，从链⾸开始查找，将满⾜需求的第⼀个空闲分区分配给作业。\" << endl;

cout << \"2.循环⾸次适应算法（NF）：将所有空闲分区按照地址递增的次序链接，在申请内存分配时，总是从上次找到的空闲分区的下⼀个空闲分区开始查找，将满⾜需求的第⼀个空闲分区分配给作业\" << endl; cout << \"3.最佳适应算法(BF) : 将所有空闲分区按照从⼩到⼤的顺序形成空闲分区链，在申请内存分配时，总是把满⾜需求的、最⼩的空闲分区分配给作业。\" << endl; cout << \"===================================================================================\" << endl; cout << \"请输⼊对应的序号选择算法：\" << endl; int choose = 0; cin >> choose; switch (choose) { case 1:

FF(applyNum); break; case 2:

NF(applyNum); break; case 3:

BF(applyNum); break; default:

cout << \"你输⼊的序号有误\" << endl; exit(0); break;

}

}

MemoryAllocation.dat

128 55 526 610 4

五、测试样例

到此这篇关于C++ 操作系统内存分配算法的实现详解的⽂章就介绍到这了,更多相关操作系统内容请搜索以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！