操作系统实验动态分区分配算法.docx
《操作系统实验动态分区分配算法.docx》由会员分享,可在线阅读,更多相关《操作系统实验动态分区分配算法.docx(14页珍藏版)》请在冰点文库上搜索。
![操作系统实验动态分区分配算法.docx](https://file1.bingdoc.com/fileroot1/2023-4/30/9bf6b4dc-c3ca-4830-8dc6-02f8577a5aed/9bf6b4dc-c3ca-4830-8dc6-02f8577a5aed1.gif)
操作系统实验动态分区分配算法
操作系统实验报告
实验2 动态分区分配算法
报告日期:
2016-6-15
姓名:
学号:
班 级:
任课教师:
实验2动态分区分配算法
一、实验内容
编写一个内存动态分区分配模拟程序,模拟内存的分配和回收的完整过程。
二、实验目的
一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器,而且要能合理地分配和使用这些存储空间。
当用户提出申请存储器空间时,存储管理必须根据申请者的要求,按一定的策略分析主存空间的使用情况,找出足够的空闲区域分配给申请者。
当作业撤离或主动归还主存资源时,则存储管理要收回作业占用的主存空间或归还部分主存空间。
主存的分配和回收的实现与主存储器的管理方式有关的,通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。
三、实验原理
模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。
(1)可变分区方式是按作业需要的主存空间大小来分割分区的。
当要装入一个作业时,根据作业需要的主存量查看是否有足够的空闲空间,若有,则按需要量分割一个分区分配给该作业;若无,则作业不能装入。
随着作业的装入、撤离,主存空间被分成许多个分区,有的分区被作业占用,而有的分区是空闲的。
例如:
0
5k
10k
14k
26k
32k
512k
操作系统
作业1
作业3
空闲区
作业2
空闲区
为了说明哪些区是空闲的,可以用来装入新作业,必须要有一张空闲区说明表,格式如下:
起址
长度
状 态
第一栏
14K
12K
未分 配
第二栏
32K
96 K
未分 配
M
其中,起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态,一种是“未分配”状态,指出对应的由起址指出的某个长度的区域是空闲区。
(2)当有一个新作业要求装入主存时,必须查空闲区说明表,从中找出一个足够大的空闲区。
有时找到的空闲区可能大于作业需要量,这时应把原来的空闲区变成两部分:
一部分分给作业占用;另一部分又成为一个较小的空闲区。
为了尽量减少由于分割造成的空闲区,而尽量保存高地址部分有较大的连续空闲区域,以利于大型作业的装入。
为此,在空闲区说明表中,把每个空闲区按其地址顺序登记,即每个后继的空闲区其起始地址总是比前者大。
(3) 采用最先适应算法(顺序分配算法)分配主存空间。
按照作业的需要量,查空闲区说明表,顺序查看登记栏,找到第一个能满足要求的空闲区。
当空闲区大于需要量时,一部分用来装入作业,另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配,所以把主存区分配给作业后并不实际启动装入程序装入作业,而用输出“分配情况”来代替。
(4)当一个作业执行结束撤离时,作业所占的区域应该归还,归还的区域如果与其它空闲区相邻,则应合成一个较大的空闲区,登记在空闲区说明表中。
(5)请按最先适应算法设计主存分配和回收的程序。
假设初始时主存中没有作业,现按下面序列进行内存的申请与释放:
作业1申请300K,作业2申请100K,作业1释放300K,作业3申请150K,
作业4申请30K,作业5申请40K,作业6申请60K,作业4释放30K。
请你为它们进行主存分配和回收,把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
四、实验报告
1.画出算法流程图。
2.源代码
#define_CRT_SECURE_NO_WARNINGS1
#include<stdio.h>
#include<string.h>
#include
#include
#defineN 10000
intn1;//空闲分区的个数
intn2;//作业区的个数
structkongxian
{
ﻩintstart;//起址
ﻩintend;//结束
intlength;//长度
}kongxian[N];
structzuoye
{
ﻩint start;//起址
ﻩint end; //结束
ﻩintlength;//长度
}zuoye[N];
int cmp1(constvoid*a,constvoid *b)
{
return(*(struct kongxian*)a).start-(*(structkongxian*)b).start;
}
intcmp2(constvoid*a,constvoid*b)
{
ﻩreturn(*(structzuoye*)a).start-(*(structzuoye*)b).start;
}
void init()
{
n1= 1; //初始时只有一个空闲区
ﻩn2=0; //初始没有作业
kongxian[0].start=0;
kongxian[0].end =511;
kongxian[0].length = 512;
}
voidprint1() //打印空闲分区
{
inti;
ﻩfor(i = 0;iﻩprintf("空闲分区ID:
%d起止:
%d结束:
%d长度:
%d\n",i,kongxian[i].start,kongxian[i].end, kongxian[i].length);
}
voidprint2()//打印作业分区
{
ﻩinti;
ﻩfor(i=0; i<n2;i++)
ﻩﻩprintf("作业分区ID:
%d起止:
%d结束:
%d 长度:
%d\n",i, zuoye[i].start,zuoye[i].end,zuoye[i].length);
}
intmain()
{
int i, j,t,len, flag,id;
intfront, middle,behind;
int t1, t2;
init();
print1();
ﻩprintf("输入1装入新作业,输入0回收作业,输入-1结束\n");
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;
ﻩﻩ}
ﻩ}
if(!
flag)
ﻩﻩ{
ﻩprintf("内存分配失败\n");
ﻩ}
ﻩelse
ﻩ{
ﻩﻩﻩ//将该作业加入作业区里
ﻩﻩﻩ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ﻩﻩﻩﻩ{
ﻩkongxian[j].start=kongxian[j +1].start;
ﻩﻩﻩkongxian[j].end= kongxian[j+ 1].end;
ﻩﻩﻩﻩﻩﻩkongxian[j].length =kongxian[j+ 1].length;
ﻩﻩ}
ﻩﻩn1--;
ﻩ}
ﻩﻩelse//该空闲分区部分用于分配,剩余的留在空闲分区中
ﻩﻩﻩﻩ{
ﻩﻩﻩkongxian[i].start +=len;
ﻩﻩﻩkongxian[i].length-=len;
ﻩ}
ﻩ}
ﻩ}
elseif(t==0)
ﻩ{
ﻩprintf("输入要回收的作业ID ");
ﻩscanf("%d",&id);
ﻩfront=middle=behind =0;
ﻩfor(i = 0;iﻩﻩ{
ﻩﻩﻩﻩif(kongxian[i].start>zuoye[id].end)
ﻩﻩbreak;
ﻩﻩﻩﻩif(kongxian[i].end ==zuoye[id].start)//待回收的作业上面有空闲分区
ﻩ{
ﻩﻩﻩﻩfront =1;
ﻩﻩt1=i;
ﻩ}
ﻩif (kongxian[i].start ==zuoye[id].end) //待回收的作业下面有空闲分区
ﻩ{
ﻩﻩbehind=1;
ﻩﻩﻩﻩt2= i;
ﻩ}
ﻩﻩ}
ﻩﻩ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); //插入空闲分区后排序
ﻩfor(j= id;j<n2-1;j++)//在作业分区中删除该作业
ﻩﻩ{
ﻩﻩﻩzuoye[j].start= zuoye[j + 1].start;
ﻩﻩﻩﻩzuoye[j].end= zuoye[j+1].end;
zuoye[j].length=zuoye[j + 1].length;
ﻩﻩﻩﻩ}
ﻩﻩﻩn2--;
ﻩﻩ}
ﻩif (front&&behind) //待回收的作业上下均有空闲分区
ﻩmiddle=1;
if(front&&!
middle)//合并待回收的作业和上面的空闲分区
ﻩ{
ﻩﻩﻩkongxian[t1].end +=zuoye[id].length;
ﻩﻩkongxian[t1].length+=zuoye[id].length;
ﻩﻩfor(j=id;jﻩ{
ﻩﻩﻩzuoye[j].start=zuoye[j+1].start;
zuoye[j].end=zuoye[j +1].end;
ﻩﻩﻩzuoye[j].length=zuoye[j + 1].length;
ﻩﻩ}
ﻩﻩﻩn2--;
ﻩﻩ}
ﻩﻩif(middle) //合并待回收的作业和上下的空闲分区
ﻩ{
ﻩﻩkongxian[t1].end = kongxian[t2].end;
ﻩﻩkongxian[t1].length+=(zuoye[id].length+kongxian[t2].length);
ﻩﻩﻩﻩ//删除空闲分区t2
ﻩﻩﻩfor (j=t2;j{
ﻩkongxian[j].start= kongxian[j+1].start;
ﻩﻩﻩkongxian[j].end=kongxian[j +1].end;
ﻩkongxian[j].length=kongxian[j+1].length;
ﻩ}
n1--;
ﻩﻩfor(j=id;j<n2- 1;j++) //在作业分区中删除该作业
ﻩ{
ﻩﻩ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ﻩﻩﻩ{
ﻩﻩﻩzuoye[j].start =zuoye[j+ 1].start;
ﻩzuoye[j].end=zuoye[j+1].end;
ﻩzuoye[j].length=zuoye[j+1].length;
}
ﻩﻩﻩn2--;
ﻩ}
ﻩ}
ﻩelse
ﻩ{
ﻩﻩprintf("操作结束\n");
ﻩbreak;
}
print1();
print2();
}
ﻩreturn 0;
}
3. 程序运行时的初值和运行结果。
初始:
装入实验要求作业一:
装入作业二:
作业1释放300k:
作业三申请150k
作业4申请30k:
作业5申请40k:
作业6申请60k:
作业4释放30k:
5.如果在要申请一个100K的作业空间,能否满足?
可以满足!
五、实验小结
通过本次实验,我对操作系统中首次适应的内存分配方法有了深刻的理解,对理论学习有了很好的促进作用,本次的实验难度比实验一难一些,也对考验了我的编程能力,重要的还是要理解算法。