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

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

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

3、体，保存作业信息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 &);/声明

4、换出作业的函数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 ntt1.装入作业 endl tt2.换出作业 endl tt3.退出n endl choice; switch (choice) case 1:/装入作业 cout c1; co

5、ut c2; cout 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 c3; Project p = c3, 5 ; swap_out(B_List, p, P_List); print_info(B_List, P_Li

6、st); 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 length & i-busy = 0) i-bus

7、y = 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()

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

9、 = 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 !=

10、 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 length & i-busy = 0) i-busy = p.number; int len = i-length-p.length; i-length = p.length; Block m = i-address

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

12、r = pnumber) L2.erase(i2); break; list: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-l

13、ength += (*k).length); L1.erase(k); break; /计算剩余存int remain_length(listL1) list: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 L1, list L2) cout n* endl; cout 总存：SIZE t剩余存：remain_length(L1)endl; list:

14、iterator i; for (i = L1.begin(); i != L1.end(); i+) if (i-busy = 0) cout 首地址： address 长度： length 空闲 endl; else cout 首地址： address 长度： length 被作业 busy 占用 endl; cout * endl; cout 作业明细(按进入顺序排)： endl; list:iterator j; for (j = L2.begin(); j!= L2.end(); j+) cout 作业号： number 长度： length endl; cout * endl;4.

15、运行截图1.初始时存情况：2.采用首次适配算法依次放入作业1（10），作业2（5）作业3（20）作业4（15）后的存情况：3.换出作业2后存情况：4.采用最佳适配算法放入作业5（3）后的存情况：5.换出作业3采用最佳适配算法放入作业6（13）存情况：6.采用下次适配算法装入作业7（1）存情况：5.实验中遇到的问题和解决方法实验的难点在于数据结构的选择和存分配算法的模拟。由动态存的分配涉及到频繁的作业的装入和换出，且不一定发生在首尾，感觉不适合数组和向量。由此也想到了用链表，首先想到自己写链表但是感觉比较麻烦，而且实现的效率感觉也不高。想到c+STL里有链表，便调用了。但是对于其中的操作方法例如insert(),erase()等等不是很熟悉，网上也查询了相关的关于STL中List的介绍，直到熟悉了方法的使用。对于算法的模拟，感觉就是先用数据结构模拟存，然后用list的方法模拟整个过程作业装入，换出等整个过程。