操作系统实验报告
实验2 动态分区分配算法
报告日期：2016-6-15
姓 名：
.
学 号： 班 级： 任课教师：
实验2 动态分区分配算法
一、实验容
编写一个存动态分区分配模拟程序，模拟存的分配和回收的完整过程。
二、实验目的
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理式有关的，通过本实验帮助学生理
解在可变分区管理式下应怎样实现主存空间的分配和回收。
三、实验原理
模拟在可变分区管理式下采用最先适应算法实现主存分配和回收。
(1)可变分区式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成多个分区，有的分区被作业占用，而有的分区是空闲的。例如： 0
操作系统 作业1 作业3 空闲区 作业2 空闲区 5k 10k 14k 26k 32k
512k
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一空闲区说明表，格式如下：
Word 资料
.
第一栏 第二栏
起 址 14 K 32 K 长 度 12 K 96 K 状 态 未 分 配 未 分 配 其中，起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。
(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。
(3) 采用最先适应算法（顺序分配算法）分配主存空间。
按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。
(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。
(5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行存的申请与释放：
作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K， 作业4申请30K， 作业5申请40K， 作业6申请60K， 作业4释放30K。 请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
四、实验报告
1. 画出算法流程图。
Word 资料
.
2. 源代码
#define _CRT_SECURE_NO_WARNINGS 1 #include int start; //起址 int end; //结束 int length; //长度 }kongxian[N]; Word 资料 . struct zuoye { int start; //起址 int end; //结束 int length; //长度 }zuoye[N]; int cmp1(const void *a, const void *b) { } int cmp2(const void *a, const void *b) { } void init() { } n1 = 1; //初始时只有一个空闲区 n2 = 0; //初始没有作业 kongxian[0].start = 0; kongxian[0].end = 511; kongxian[0].length = 512; return (*(struct zuoye *)a).start - (*(struct zuoye *)b).start; return (*(struct kongxian *)a).start - (*(struct kongxian *)b).start; Word 资料 . void print1() //打印空闲分区 { int i; for (i = 0; i kongxian[i].end, kongxian[i].length); } void print2() //打印作业分区 { int i; for (i = 0; i zuoye[i].end, zuoye[i].length); } int main() { int i, j, t, len, flag, id; int front, middle, behind; int t1, t2; init(); print1(); printf(\"输入1装入新作业，输入0回收作业，输入-1结束\\n\"); Word 资料 . while (scanf(\"%d\", &t) != EOF) { if (t == 1) //装入新作业 { printf(\"请输入作业的占用空间的长度 \"); scanf(\"%d\", &len); flag = 0; for (i = 0; i if (kongxian[i].length >= len) //首次适应算法 { } flag = 1; break; Word 资料 . 闲分区 } } Word 资料 zuoye[n2].start = kongxian[i].start; zuoye[n2].end = zuoye[n2].start + len; zuoye[n2].length = len; n2++; //作业数加1 if (kongxian[i].length == len) //该分区全部用于分配，删除该空 { for (j = i; j } else //该空闲分区部分用于分配，剩余的留在空闲分区中 { kongxian[i].start += len; kongxian[i].length -= len; } . else if (t == 0) { printf(\"输入要回收的作业ID \"); scanf(\"%d\", &id); front = middle = behind = 0; for (i = 0; i break; if (kongxian[i].end == zuoye[id].start) 闲分区 { front = 1; t1 = i; } if (kongxian[i].start == zuoye[id].end) 闲分区 { behind = 1; t2 = i; } } Word 资料 //待回收的作业上面有空 //待回收的作业下面有空 . if (!front&&!behind) //待回收的作业上下均没有空闲分区 { kongxian[n1].start = zuoye[id].start; kongxian[n1].end = zuoye[id].end; kongxian[n1].length = zuoye[id].length; n1++; //空闲分区增加一个 qsort(kongxian, n1, sizeof(struct kongxian), cmp1); //插入空闲分 区后排序 } if (front &&behind) //待回收的作业上下均有空闲分区 middle = 1; for (j = id; j if (front&&!middle) //合并待回收的作业和上面的空闲分区 { kongxian[t1].end += zuoye[id].length; kongxian[t1].length += zuoye[id].length; Word 资料 . } for (j = id; j if (middle) //合并待回收的作业和上下的空闲分区 { kongxian[t1].end = kongxian[t2].end; kongxian[t1].length += (zuoye[id].length + kongxian[t2].length); //删除空闲分区t2 for (j = t2; j Word 资料 . } } } zuoye[j].start = zuoye[j + 1].start; zuoye[j].end = zuoye[j + 1].end; zuoye[j].length = zuoye[j + 1].length; n2--; if (behind &&!middle) //合并待回收的作业和下面的分区 { } kongxian[t2].start -= zuoye[id].length; kongxian[t2].length += zuoye[id].length; for (j = id; j else { printf(\"操作结束\\n\"); Word 资料 . } } } break; print1(); print2(); return 0; 3. 程序运行时的初值和运行结果。 初始： 装入实验要求作业一： Word 资料 . 装入作业二： 作业1释放300k： Word 资料 . 作业三申请150k 作业4申请30k： 作业5申请40k： Word 资料 . 作业6申请60k： 作业4释放30k： Word 资料 . 5. 如果在要申请一个100K的作业空间，能否满足？ 可以满足！ 五、实验小结 通过本次实验，我对操作系统中首次适应的存分配法有了深刻的理解，对理论学习有了很好的促进作用，本次的实验难度比实验一难一些，也对考验了我的编程能力，重要的还是要理解算法。 Word 资料 因篇幅问题不能全部显示，请点此查看更多更全内容