实验四 内存分配算法 1. 实验目的 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现是与主存储器的管理方式有关的，通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。 背景知识： 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离、主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。

2. 实验内容 采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。 由于本实验是模拟主存的分配，所以当把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。（即输出当时的空闲区说明表及其内存分配表） 利用VC++6.0实现上述程序设计和调试操作。

3. 实验代码 #include #include using namespace std;

//定义内存的大小 const int SIZE=64;

//作业结构体，保存作业信息 struct Project{ int number; int length; };

//内存块结构体，保存内存块信息 struct Block{ int address; int length; int busy; };

int first_fit(list &, Project , list &);//声明首次适配算法函数 int best_fit(list &, Project , list &);//声明最佳适配算法函数 int next_fit(list &, Project , list &);//声明下次适配算法函数 void swap_out(list &, Project , list &);//声明换出作业的函数 void print_info(list, list);//声明打印内存和作业函数 int remain_length(list);//声明计算剩余内存的函数

int main(){ list B_List; list P_List; Block m1 = { 1, SIZE, 0 }; B_List.push_back(m1); print_info(B_List, P_List); while (true) { cout << "\n\t\t1.装入作业" << endl << "\t\t2.换出作业" << endl << "\t\t3.退出\n" << endl << "请选择操作："; int choice; cin >> choice; switch (choice) { case 1://装入作业 { cout << "请选择装入方式：(1.首次适配 2.最佳适配 3.下次适配)：\n"; int c1; cin >> c1; cout << "请输入作业号（作业号不能重复）："; int c2; cin >> c2; cout << "请输入作业所需内存："; int c3; cin >> c3; Project p = { c2, c3 }; if (c1 == 1){ first_fit(B_List, p, P_List); } else if (c1 == 2){ best_fit(B_List, p, P_List); } else if (c1 == 3){ next_fit(B_List, p, P_List); } print_info(B_List, P_List); break; } case 2://换出作业 { cout << "请选择需换出内存的作业："; int c3; cin >> c3; Project p = { c3, 5 }; swap_out(B_List, p, P_List); print_info(B_List, P_List); break; } default://退出 { return 0; }

} } }

//首次适配 int first_fit(list &L1, Project p, list &L2){ list::iterator i; //遍历列表查找空闲分区 for (i = L1.begin(); i != L1.end(); i++){ //空闲分区大小和作业相同 if (p.length == i->length && i->busy == 0){ i->busy = p.number; L2.push_back(p); return 1; } //空闲分区比作业内存大 if (p.length < i->length && i->busy == 0){ i->busy = p.number; int len= i->length-p.length; i->length = p.length; Block m = { i->address + p.length, len, 0 }; L1.insert(++i, m); i--; L2.push_back(p); return 1; } } cout << "内存不足，作业" << p.number << "装入失败" << endl; return 0; }

//最佳适配 int best_fit(list &L1, Project p, list &L2){ list::iterator i, j; int min = 100000; for (i = L1.begin(); i != L1.end(); i++){ if (i->length - p.length>-1 && i->length - p.lengthbusy == 0){ j = i; //找到大于或等于作业内存的最小空闲内存 min = i->length - p.length; } } i = j; //空闲分区大小和作业相同 if (min == 0){ i->busy = p.number; L2.push_back(p); return 1; } //空闲分区比作业内存大 else if (min != 100000){ i->busy = p.number; int len = i->length-p.length; i->length = p.length; Block m = { i->address + p.length, len, 0 }; L1.insert(++i, m); i--; L2.push_back(p); return 1; } if (i == --L1.end()){ cout << "内存不足，作业" << p.number << "装入失败" << endl; return 0; } } //下次适配 int next_fit(list &L1, Project p, list &L2){ int pnumber = L2.back().number; list::iterator i; //找到前一次装入的作业位置 for (i = L1.begin(); i != L1.end(); i++){ if (i->busy == pnumber){ break; } } for (; i != L1.end(); i++){ //空闲分区大小和作业相同 if (p.length == i->length && i->busy == 0){ i->busy = p.number; L2.push_back(p); return 1; } //空闲分区比作业内存大 if (p.length < i->length && i->busy == 0){ i->busy = p.number; int len = i->length-p.length; i->length = p.length; Block m = { i->address + p.length, len, 0 }; L1.insert(++i, m); i--; L2.push_back(p); return 1; } if (i == --L1.end()){ cout << "内存不足，作业" << p.number << "装入失败" << endl; return 0; } } return 0; }

//换出作业 void swap_out(list &L1, Project p, list &L2){ int pnumber = p.number; list::iterator i2; for (i2 = L2.begin(); i2 != L2.end(); i2++){ //根据作业号换出作业 if ((*i2).number == pnumber){