《操作系统实验—动态分区分配算法》由会员分享，可在线阅读，更多相关《操作系统实验—动态分区分配算法（18页珍藏版）》请在金锄头文库上搜索。
1、操作系统实验一动态分区分配 算法SHAANXI UNIVERSITY OF SCIENCE & TECHNOLOGY操作系统实验报告实验2 动态分区分配算法报告日期:2016-6-15名:号:级:任课教师:.r-i实验 2 动态分区分配算法一、实验内容编写一个内存动态分区分配模拟程序,模拟内 存的分配和回收的完整过程。二、实验目的一个好的计算机系统不仅要有一个足够容量 的、存取速度高的、稳定可靠的主存储器，而且 要能合理地分配和使用这些存储空间。当用户提 出申请存储器空间时，存储管理必须根据申请者 的要求，按一定的策略分析主存空间的使用情 况,找出足够的空闲区域分配给申请者。当作业 撤离或主动
2、归还主存资源时，则存储管理要收回 作业占用的主存空间或归还部分主存空间。主存 的分配和回收的实现与主存储器的管理方式有 关的，通过本实验帮助学生理解在可变分区管理方式下应怎 样实现主存空间的分配和回收。三、实验原理模拟在可变分区管理方式下采用最先适应算 法实现主存分配和回收。(1) 可变分区方式是按作业需要的主存空间大 小来分割分区的。当要装入一个作业时，根据作 业需要的主存量查看是否有足够的空闲空间，若操作系 统 作业1 作业3 空闲区 作业2有，则按需要量分割一个分区分配给该作业；若 无，贝g作业不能装入。随着作业的装入、撤离， 主存空间被分成许多个分区，有的分区被作业占 用，而有的分区是
3、空闲的。例如：05k10k14k26k512k32k空闲区为了说明哪些区是空闲的，可以用来装入新作 业，必须要有一张空闲区说明表，格式如下：起址度状 态14 K12 K未分配其中，起址 址。32 K96 K未分配MMM第二栏M长度一一指出从起始地址开始的一个连续空闲的长度。状态有两种状态，一种是未分配” 状态，指出对应的由起址指出的某个长度的区域 是空闲区。(2) 当有一个新作业要求装入主存时，必须 查空闲区说明表，从中找出一个足够大的空闲 区。有时找到的空闲区可能大于作业需要量，这 时应把原来的空闲区变成两部分：一部分分给作 业占用；另一部分又成为一个较小的空闲区。为 了尽量减少由于分割造成
4、的空闲区，而尽量保存 高地址部分有较大的连续空闲区域，以利于大型 作业的装入。为此，在空闲区说明表中，把每个 空闲区按其地址顺序登记，即每个后继的空闲区 其起始地址总是比前者大。(3) 采用最先适应算法(顺序分配算法)分配 主存空间。按照作业的需要量，查空闲区说明表，顺序查 看登记栏，找到第一个能满足要求的空闲区。当 空闲区大于需要量时，一部分用来装入作业，另 一部分仍为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分配,所以把主存区 分配给作业后并不实际启动装入程序装入作业， 而用输出“分配情况”来代替。(4) 当一个作业执行结束撤离时，作业所占的 区域应该归还，归还的区域如果与其它空闲
5、区相 邻，则应合成一个较大的空闲区，登记在空闲区 说明表中。(5) 请按最先适应算法设计主存分配和回收 的程序。假设初始时主存中没有作业，现按下面 序列进行内存的申请与释放：作业1申请300K,作业2申请100K， 作业1释放300K，作业3申请150K，作业4申请30K，作业5申请40K，作 业6申请60K,作业4释放30K。请你为它们进行主存分配和回收，把空闲区 说明表的初值以及每次分配或回收后的变化显 示出来或打印出来。四、实验报告1. 画出算法流程图。2. 源代码#define _CRT_SECURE_NO_WARNINGS 1#include#include#include#incl
6、ude#define N 10000int n1;空闲分区的个数int n2;作业区的个数struct kongxianint start; 起址int end; 结束int length; 长度kongxianN;struct zuoyeint start; 起址int end;结束int length; 长度zuoyeN;int cmp1(const void *a, const void *b)return (*(struet kongxian *)a).start -(*(struet kongxian*) b).s tart;int cmp2(const void *a, const
7、 void *b)return (*(struet zuoye *)a).start -(*(struet zuoye *)b).start; void init()n1 = 1;初始时只有一个空闲区n2 = 0;/初始没有作业kongxian0.start = 0;kongxian0end = 511;kongxian0.length = 512;void print1() /打印空闲分区int i;for (i = 0; in1; i+)printf(空闲分区ID:%d起止:d结束:d长度:dn, i, kongxian i.st ar t, kongxian i end, kongxia
8、n il eng th);void print2() /打印作业分区int i;for (i = 0; in2; i+)printf (作业分区ID： %d起止:d结束:d长度:%dn, i, zuoyei.s tart, zuoyei.end, zuoyei.length);int main()int i, j, t, len, flag, id;int front, middle, behind;int t1, t2;ini t();prin t1();prin tf(输入1装入新作业，输入0回收作业，输入-1结束n);while (seanf(%d, &t) != EOF)if (t =
9、 1)装入新作业prin tf(请输入作业的占用空间的长度); seanf(%d, & len);flag = 0;for (i = 0; i= len) /首次适应算法flag = 1; break;if (!flag)printf(内存分配失败n);else将该作业加入作业区里zuoyen2.s tart = kongxiani.s tart; zuoyen2end = zuoyen2.start + len; zuoyen2.length = len;n2+;作业数加1if (kongxiani.length = len) /该分区全部用于分配，删 除该空闲分区for (j = i; j
10、n1 一 1; j+)kongxianj .start = kongxianj + 1.start; kongxianj.end = kongxianj + 1.end; kongxianj l eng th = kongxianj + 1.leng th;n1;else 该空闲分区部分用于分配，剩余的留在空闲分区中 kongxian i.start += len; kongxiani.length -= len;else if (t = 0)prin tf(输入要回收的作业ID );scanf(%d, &id);front = middle = behind = 0;for (i = 0;
11、i zuoyeid.end)break;if (kongxiani .end = zuoyeid.s tart) /待回收的作业上面有空闲分区front = 1;t1 = i;if (kongxiani.s tart = zuoyeid.end) /待回收的作业 下面有空闲分区behind = 1; t2 = i;if (!front&!behind) 待回收的作业上下均没有空闲分区 kongxian n1.st art = zuoyeid .st art; kongxiann1end = zuoyeidend; kongxian n1l ength = zuoyeid.leng th;n1+
12、;空闲分区增加一个qsort(kongxian, n1, sizeof(struct kongxian), cmpl); / 插入空闲分区后排序for (j = id; jn2 - 1; j+)在作业分区中删除该作业zuoyej.star t = zuoyej + 1.s tart; zuoyej. end = zuoyej + 1end; zuoyej.leng th = zuoyej + 1.leng th;n2；if (fron t &behind) 待回收的作业上下均有空闲分区 middle = 1;if (front&!middle) 合并待回收的作业和上面的空闲分区 kongxia
13、n t1 .end += zuoyeid l eng th; kongxiant1length += zuoyeid.length;for (j = id; jn2 - 1; j+)在作业分区中删除该作业zuoyej.s tart = zuoyej + 1.s tart; zuoyej.end = zuoyej + 1.end; zuoyej.leng th = zuoyej + 1.leng th;n2；if (middle) 合并待回收的作业和上下的空闲分区kongxian t1 .end = kongxian t 2.end;kongxian t1 .leng th += (zuoyeid.leng th + kongxian t 2.leng th);/删除空闲分区t2for (j = t2; jn1 一 1; j+) kongxianj.s tart = kongxianj + 1.s tart; kongxianj.end = kongxianj + 1.end; kongxianj.leng th = kongxianj + 1.leng th;n1一;for (j = id; jn2 - 1;
