《操作系统实验—动态分区分配算法》由会员分享,可在线阅读,更多相关《操作系统实验—动态分区分配算法(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;