操作系统内存动态分配模拟算法

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

2、足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离、主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。2. 实验内容采用首次适应算法或循环首次算法或最佳适应算法分配主存空间。由于本实验是模拟主存的分配，所以当把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。（即输出当时的空闲区说明表及其内存分配表）利用VC+6.0实现上述程序设计和调试操作。3. 实验代码#include<iostream>#include<list>using namespace std;/定义内存的大小co

3、nst int SIZE=64;/作业结构体，保存作业信息struct Projectint number;int length;/内存块结构体，保存内存块信息struct Blockint address;int length;int busy;int first_fit(list<Block> &, Project , list<Project> &);/声明首次适配算法函数int best_fit(list<Block> &, Project , list<Project> &);/声明最佳适配算法函数int

4、 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

5、<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 << "ntt1.装入作业" << endl << "tt2.换出作业" << endl << "tt3.退出n" << endl << "请选择操作："int c

6、hoice;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(

7、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;defau

8、lt:/退出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;/空闲分区比作业

9、内存大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 << "装入失败&qu

10、ot; << 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

11、)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(+

12、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;/找到前

13、一次装入的作业位置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.

14、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(li

15、st<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->bu

16、sy = 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)

17、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 <&l

18、t;"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>