实验四 最先适应算法

综合实验报告

( 2011-- 2012 年度第 1 学期)

名 称：操作系统原理综合实验B 题 目： 最先适应算法 院 系： 计算机系 班 级： 网络工程0902 学 号： 200909030221 学生姓名： 王沙沙 指导教师： 王德文 设计周数： 1周

成 绩：

日期： 2011年 11月 26 日

一、综合实验的目的与要求

1．实验目的

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

本实验模拟在两种存储管理方式下的主存分配和回收。 二、综合实验正文

1.问题描述：

在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。

可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：

0 5k 10k 14k 26k 32k 128k 操作系统 作业1 作业3 空闲区 作业2 空闲区

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

第一栏 第二栏 ? ?

起 址 14 K 32 K 其中，起址——指出一个空闲区的主存起始地址。 长度——指出从起始地址开始的一个连续空闲的长度。

状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来

1

长 度 12 K 96 K 状 态 未 分 配 未 分 配 空 表 目 空 表 目 ? ? 登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。

上述的这张说明表的登记情况是按提示（1）中的例所装入的三个作业占用的主存区域后填写的。

(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

(3) 采用最先适应算法（顺序分配算法）分配主存空间。

按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。

由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图4-1。

(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业2撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图4-2。

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

图4-1 最先适应分配模拟算法

2

图4-2 主存回收算法

2.程序设计： #include using namespace std;

typedef struct SNode { // Space Node int start,end; // 起始，结束 int length; // 长度大小

struct SNode *next; // 指向下一结点的指针 }* SP;

SP Head=(SP)malloc(sizeof(SNode)); // 全局变量，内存空间头结 void DispSpace() { // 显示内存空间分配情况 SP p=Head->next;

cout<<\ 空闲区说明表 \\n\ <<\地址--长度---\\n\ while (p) {

cout<<\ \

<<\ \ p=p->next; }

3

cout<<\}

void Initial() { // 初始化说明表 SP p,q;

p=(SP)malloc(sizeof(SNode)); q=(SP)malloc(sizeof(SNode)); p->start=14; p->length=12; p->end=26;

q->start=32; q->length=96; q->end=128; // 指导书上的作业分配 Head->next=p; // 与头结点连接 p->next=q; q->next=NULL; DispSpace(); }

void Allocation(int len) { // 分配内存给新作业 SP p=Head->next,q; while (p)

{

if (p->length < len) p=p->next; else if (p->length > len)

{

p->start=p->start+len; p->length=p->length-len; cout<<\分配成功!\\n\ DispSpace(); return; } else

{//当两者长度相等

q=p->next; p->next=q->next; cout<<\分配成功!\\n\

4

DispSpace(); return; } }

cout<<\分配失败!\\n\ DispSpace(); return; }

void CallBack(int sta,int len) { // 回收内存 SP p=Head,q=p->next,r; // 开始地址和长度 p->end=0; int en=sta+len; while (q) {

if (sta == 0) { // 初始地址为0 if (en == q->start) { // 正好回收 q->start=0; q->length=q->end; return; } else {

r=(SP)malloc(sizeof(SNode)); r->start=sta; r->length=len; r->end=en; p->next=r; r->next=q; return; } }

else if ((p->end < sta) && (q->start > en)) { // 上邻区 r=(SP)malloc(sizeof(SNode)); r->start=sta; r->length=len; r->end=en; p->next=r; r->next=q; return; }

5

else if ((p->end < sta) && (q->start == en)) { // 邻区相接 q->start=sta; q->length=q->end-sta; return; }

else if ((p->end == sta) && (q->start < en)) { // 下邻区 p->end=en;

p->length=en-p->start; return; }

else if (p->end==sta && q->start==en) { // 邻区相接 p->end=q->end;

p->length=p->end-p->start; p->next=q->next; return; } else {

p=p->next; q=q->next; } } }

void main() { Initial();

cout<<\现在分配大小为 6K 的作业 4 申请装入主存: \ Allocation(6); // 分配时参数只有长度 //--------指导书测试数据演示---------- cout<<\现回收作业 3 (起址10,长度4)\\n\ CallBack(10,4); DispSpace();

cout<<\现回收作业 2 (起址26,长度6)\\n\ CallBack(26,6); DispSpace();

6

//---------------演示结束------------- system(\}

3. 程序运行结果：

三、综合实验总结或结论

通过本次实验，自己的编程能力有所提高，对操作系统内存的分配，存储空间的回收都有了全新的认识。

在这次操作系统实验中我使用了C++编写系统软件，对OS中可变分区存储管理有了深刻的理解，通过验证，可以说是做出了结果，但是过程中遇到了很多困难，只能边做边查资料，问同学，通过实验对C++有了比较多的理解。

实验中遇到不少问题，浪费了很多的时间，总而言之，究其原因是自己平时的学习不牢固，不扎实，会在以后得学习中扬长避短加以改善，来学到更多的知识。

7

本文来源：https://www.bwwdw.com/article/q4r7.html