实验四存分配算法1.实验目的一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。

当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。

当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。

主存的分配和回收的实现是与主存储器的管理方式有关的，通过本实验帮助学生理解在动态分区管理方式下应怎样实现主存空间的分配和回收。

背景知识：可变分区方式是按作业需要的主存空间大小来分割分区的。

当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。

随着作业的装入、撤离、主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。

2.实验容采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。

由于本实验是模拟主存的分配，所以当把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。

（即输出当时的空闲区说明表及其存分配表）利用VC++6.0实现上述程序设计和调试操作。

3.实验代码#include<iostream>#include<list>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<Block> &, Project , list<Project> &);//声明首次适配算法函数int best_fit(list<Block> &, Project , list<Project> &);//声明最佳适配算法函数int next_fit(list<Block> &, Project , list<Project> &);//声明下次适配算法函数void swap_out(list<Block> &, Project , list<Project> &);//声明换出作业的函数void print_info(list<Block>, list<Project>);//声明打印存和作业函数int remain_length(list<Block>);//声明计算剩余存的函数int main(){list<Block> B_List;list<Project> 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<Block> &L1, Project p, list<Project> &L2){ list<Block>::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<Block> &L1, Project p, list<Project> &L2){list<Block>::iterator i, j;int min = 100000;for (i = L1.begin(); i != L1.end(); i++){if (i->length - p.length>-1 && i->length - p.length<min && i->busy == 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<Block> &L1, Project p, list<Project> &L2){int pnumber = L2.back().number;list<Block>::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<Block> &L1, Project p, list<Project> &L2){ int pnumber = p.number;list<Project>::iterator i2;for (i2 = L2.begin(); i2 != L2.end(); i2++){//根据作业号换出作业if ((*i2).number == pnumber){L2.erase(i2);break;}}list<Block>::iterator i,j,k;for (i = L1.begin(); i != L1.end(); i++){if (i->busy == pnumber){i->busy = 0;j = i;k = i;if (j != L1.begin()){j--;//换出作业后前一个空闲区正好能连接if (j->busy == 0){i->length += j->length;i->address = j->address;L1.erase(j);}}k++;//换出作业后后一个空闲区正好能连接if (k->busy == 0){i->length += ((*k).length);L1.erase(k);}break;}}}//计算剩余存int remain_length(list<Block>L1){list<Block>::iterator i;//当前所有作业占用的总存int len=0;for (i = L1.begin(); i != L1.end(); i++){if (i->busy != 0)len += i->length;}return SIZE-len;}void print_info(list<Block> L1, list<Project> L2){cout << "\n***********************************************" << endl;cout << "总存："<<SIZE <<"\t剩余存："<<remain_length(L1)<<endl;list<Block>::iterator i;for (i = L1.begin(); i != L1.end(); i++){if (i->busy == 0){cout << " 首地址：" << i->address << " 长度：" << i->length << " 空闲" << endl;}elsecout << " 首地址：" << i->address << " 长度：" << i->length << " 被作业" << i->busy << "占用" << endl;}cout << "***********************************************" << endl;cout << "作业明细(按进入顺序排)：" << endl;list<Project>::iterator j;for (j = L2.begin(); j!= L2.end(); j++){cout << " 作业号：" << j->number << " 长度：" << j->length << endl;}cout << "***********************************************" << endl;}4.运行截图1.初始时存情况：2.采用首次适配算法依次放入作业1（10），作业2（5）作业3（20）作业4（15）后的存情况：3.换出作业2后存情况：4.采用最佳适配算法放入作业5（3）后的存情况：5.换出作业3采用最佳适配算法放入作业6（13）存情况：6.采用下次适配算法装入作业7（1）存情况：5.实验中遇到的问题和解决方法实验的难点在于数据结构的选择和存分配算法的模拟。