实验二动态高优先权优先调度算法.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文档和程序文件.五个实验的文件夹再放到以"学号_"命名的文件夹中,压缩后提交。
实验次序:
实验一——作业调度
实验二——动态高优先权优先调度算法
实验三——时间片轮转调度算法
实验四——动态分区分配管理
实验五——基本分页存储管理
评语