实验二动态高优先权优先调度算法.docx
《实验二动态高优先权优先调度算法.docx》由会员分享，可在线阅读，更多相关《实验二动态高优先权优先调度算法.docx（16页珍藏版）》请在冰点文库上搜索。
实验二动态高优先权优先调度算法
《操作系统》课程实验报告
实验名称：
动态分区存储管理
姓名：
王子瑜
学号：
5
地点：
四教楼
指导老师：
放美
专业班级：
软件工程（测试技术14-02）
实验成绩：
一、实验要求：
熟悉并掌握动态分区分配的各种算法。
熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。
二、实验容：
用高级语言模拟实现动态分区存储管理，要求：
1、分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。
熟悉并掌握各种算法的空闲区组织方式。
2、分区的初始化——可以由用户输入初始分区的大小。
（初始化后只有一个空闲分区，起始地址为0，大小是用户输入的大小）
3、分区的动态分配过程：
由用户输入作业号和作业的大小，实现分区过程。
4、分区的回收：
用户输入作业号，实现分区回收，同时，分区的合并要体现出来。
（注意：
不存在的作业号要给出错误提示！
）
5、分区的显示：
任何时刻，可以查看当前存的情况（起始地址是什么，大小多大的分区时空闲的，或者占用的，能够显示出来）
要求考虑：
（1）存空间不足的情况，要有相应的显示；
（2）作业不能同名，但是删除后可以再用这个名字；
（3）作业空间回收是输入作业名，回收相应的空间，如果这个作业名不存在，也要有相应的提示。
三、实验代码
#include
#include
#defineSIZE640//存初始大小
#defineMINSIZE5//碎片最小值
enumSTATE{Free,Busy};
structsubAreaNode{
intaddr;//起始地址
intsize;//分区大小
inttaskId;//作业号
STATEstate;//分区状态
subAreaNode*pre;//分区前向指针
subAreaNode*nxt;//分区后向指针
}subHead;
//初始化空闲分区链
voidintSubArea（）
{
//分配初始分区存
subAreaNode*fir=（subAreaNode*）malloc（sizeof（subAreaNode））;
//给首个分区赋值
fir->addr=0;
fir->size=SIZE;
fir->state=Free;
fir->taskId=-1;
fir->pre=&subHead;
fir->nxt=NULL;
//初始化分区头部信息
subHead.pre=NULL;
subHead.nxt=fir;
}
//首次适应算法
intfirstFit（inttaskId,intsize）
{
subAreaNode*p=subHead.nxt;
while（p!
=NULL）
{
if（p->state==Free&&p->size>=size）{
//找到要分配的空闲分区
if（p->size-size<=MINSIZE）{
//整块分配
p->state=Busy;
p->taskId=taskId;
}else{
//分配大小为size的区间
subAreaNode*node=（subAreaNode*）malloc（sizeof（subAreaNode））;
node->addr=p->addr+size;
node->size=p->size-size;
node->state=Free;
node->taskId=-1;
//修改分区链节点指针
node->pre=p;
node->nxt=p->nxt;
if（p->nxt!
=NULL）{
p->nxt->pre=node;
}
p->nxt=node;
//分配空闲区间
p->size=size;
p->state=Busy;
p->taskId=taskId;
}
printf（"存分配成功！
\n"）;
return1;
}
p=p->nxt;
}
printf（"找不到合适的存分区，分配失败...\n"）;
return0;
}
//最佳适应算法
intbestFit（inttaskId,intsize）
{
subAreaNode*tar=NULL;
inttarSize=SIZE+1;
subAreaNode*p=subHead.nxt;
while（p!
=NULL）
{
//寻找最佳空闲区间
if（p->state==Free&&p->size>=size&&p->sizetar=p;
tarSize=p->size;
}
p=p->nxt;
}
if（tar!
=NULL）{
//找到要分配的空闲分区
if（tar->size-size<=MINSIZE）{
//整块分配
tar->state=Busy;
tar->taskId=taskId;
}else{
//分配大小为size的区间
subAreaNode*node=（subAreaNode*）malloc（sizeof（subAreaNode））;
node->addr=tar->addr+size;
node->size=tar->size-size;
node->state=Free;
node->taskId=-1;
//修改分区链节点指针
node->pre=tar;
node->nxt=tar->nxt;
if（tar->nxt!
=NULL）{
tar->nxt->pre=node;
}
tar->nxt=node;
//分配空闲区间
tar->size=size;
tar->state=Busy;
tar->taskId=taskId;
}
printf（"存分配成功！
\n"）;
return1;
}else{
//找不到合适的空闲分区
printf（"找不到合适的存分区，分配失败...\n"）;
return0;
}
}
//回收存
intfreeSubArea（inttaskId）
{
intflag=0;
subAreaNode*p=subHead.nxt,*pp;
while（p!
=NULL）
{
if（p->state==Busy&&p->taskId==taskId）{
flag=1;
if（（p->pre!
=&subHead&&p->pre->state==Free）
&&（p->nxt!
=NULL&&p->nxt->state==Free））{
//情况1：
合并上下两个分区
//先合并上区间
pp=p;
p=p->pre;
p->size+=pp->size;
p->nxt=pp->nxt;
pp->nxt->pre=p;
free（pp）;
//后合并下区间
pp=p->nxt;
p->size+=pp->size;
p->nxt=pp->nxt;
if（pp->nxt!
=NULL）{
pp->nxt->pre=p;
}
free（pp）;
}elseif（（p->pre==&subHead||p->pre->state==Busy）
&&（p->nxt!
=NULL&&p->nxt->state==Free））{
//情况2：
只合并下面的分区
pp=p->nxt;
p->size+=pp->size;
p->state=Free;
p->taskId=-1;
p->nxt=pp->nxt;
if（pp->nxt!
=NULL）{
pp->nxt->pre=p;
}
free（pp）;
}elseif（（p->pre!
=&subHead&&p->pre->state==Free）
&&（p->nxt==NULL||p->nxt->state==Busy））{
//情况3：
只合并上面的分区
pp=p;
p=p->pre;
p->size+=pp->size;
p->nxt=pp->nxt;
if（pp->nxt!
=NULL）{
pp->nxt->pre=p;
}
free（pp）;
}else{
//情况4：
上下分区均不用合并
p->state=Free;
p->taskId=-1;
}
}
p=p->nxt;
}
if（flag==1）{
//回收成功
printf（"存分区回收成功...\n"）;
return1;
}else{
//找不到目标作业，回收失败
printf（"找不到目标作业，存分区回收失败...\n"）;
return0;
}
}
//显示空闲分区链情况
voidshowSubArea（）
{
printf（"*********************************************\n"）;
printf（"**当前的存分配情况如下：
**\n"）;
printf（"*********************************************\n"）;
printf（"**起始地址|空间大小|工作状态|作业号**\n"）;
subAreaNode*p=subHead.nxt;
while（p!
=NULL）
{
printf（"**-----------------------------------------**\n"）;
printf（"**"）;
printf（"%dk|",p->addr）;
printf（"%dk|",p->size）;
printf（"%s|",p->state==Free?
"Free":
"Busy"）;
if（p->taskId>0）{
printf（"%d",p->taskId）;
}else{
printf（""）;
}
printf（"**\n"）;
p=p->nxt;
}
printf（"*********************************************\n"）;
}
intmain（）
{
intoption,ope,taskId,size;
//初始化空闲分区链
intSubArea（）;
//选择分配算法
while
（1）
{
printf（"请选择要模拟的分配算法：
0表示首次适应算法，1表示最佳适应算法\n"）;
scanf（"%d",&option）;
if（option==0）{
printf（"你选择了首次适应算法，下面进行算法的模拟\n"）;
break;
}elseif（option==1）{
printf（"你选择了最佳适应算法，下面进行算法的模拟\n"）;
break;
}else{
printf（"错误：
请输入0/1\n\n"）;
}
}
//模拟动态分区分配算法
while
（1）
{
printf（"\n"）;
printf（"*********************************************\n"）;
printf（"**1:
分配存2:
回收存0:
退出**\n"）;
printf（"*********************************************\n"）;
scanf（"%d",&ope）;
if（ope==0）break;
if（ope==1）{
//模拟分配存
printf（"请输入作业号：
"）;
scanf（"%d",&taskId）;
printf（"请输入需要分配的存大小（KB）：
"）;
scanf（"%d",&size）;
if（size<=0）{
printf（"错误：
分配存大小必须为正值\n"）;
continue;
}
//调用分配算法
if（option==0）{
firstFit（taskId,size）;
}else{
bestFit（taskId,size）;
}
//显示空闲分区链情况
showSubArea（）;
}elseif（ope==2）{
//模拟回收存
printf（"请输入要回收的作业号：
"）;
scanf（"%d",&taskId）;
freeSubArea（taskId）;
//显示空闲分区链情况
showSubArea（）;
}else{
printf（"错误：
请输入0/1/2\n"）;
}
}
printf（"分配算法模拟结束\n"）;
return0;
}运行结果：
五、实验总结
注意：
1.标题格式黑体4号加粗，正文宋体小四
2.实验结果给出你程序运行时的截图
3.实验总结是通过这次实验你学到的及不足的等方面的容。
每个实验一个文件夹,文件夹命名方式:
实验一等,里边至少两个文件,即实验报告的Word文档和程序文件.五个实验的文件夹再放到以"学号_"命名的文件夹中，压缩后提交。
实验次序：
实验一——作业调度
实验二——动态高优先权优先调度算法
实验三——时间片轮转调度算法
实验四——动态分区分配管理
实验五——基本分页存储管理
评语
升级会员 