短作业优先的作业调度操作系统课程设计报告书.docx
《短作业优先的作业调度操作系统课程设计报告书.docx》由会员分享,可在线阅读,更多相关《短作业优先的作业调度操作系统课程设计报告书.docx(18页珍藏版)》请在冰点文库上搜索。
短作业优先的作业调度操作系统课程设计报告书
摘要
作业调度是对成批进入系统的用户作业,根据作业控制块的信息,按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。
而对每个用户来说总希望自己的作业的周转时间是最小的,短作业优先(SJF)便是其中一种调度方法。
本设计是为了加深对作业概念的理解,掌握短作业优先(SJF)算法,深入了解批处理系统如何组织作业、管理作业和调度作业,了解作业控制块的作用,以与作业控制块的容和组织方式。
为了将系统中的作业组织起来,需要为每个进入系统的作业建立档案以记录和作业相关的信息,例如作业名、作业所需资源、作业执行时间、作业进入系统的时间、作业信息在存储器中的位置、指向下一个作业控制块的指针等信息。
这个记录作业相关信息的数据块称为作业控制块(JCB),并将系统中等待作业调度的作业控制块组织成一个队列,这个队列称为后备队列。
一个作业全部信息进入系统后,就为其建立作业控制块,并挂入后备队列。
当进行作业调度时,从后备队列中查找选择作业。
在从后备队列中查找选择作业是,先根据作业控制块中的信息,选中一个短作业,也就是执行时间最短的作业,将它们调入存运行。
关键词:
作业;调度;短作业优先;SJF;JCB
Abstract
Batchjobschedulingproblemistoenterthesystemaccordingtotheuser,thejobcontrolblockofinformation,accordingtocertainstrategyselectionseveralassignmentsthattheycangotoobtainaprocessorruns.Foreachuserisalwayshopetheirjobcycletimeisthesmallest,shortj(SJF)whichisthepreferredmethodofakindofscheduling.
Thisdesignistodeepentheunderstandingoftheconceptofjobassignments,shortjobfirst(SJF)algorithmis,in-depthunderstandingofhowthesystemofbatchmanagementandorganization,scheduling,understandthejobassignments,aswellasthejobcontrolblocksofcontentandorganization.
Inordertoorganizetheassignmentsystemforeveryonetoenterthesystemtoestablisharchivesofjobassignmentsandrelatedinformationrecorded,forexample,jobassignments,resources,workintoexecutiontimeoftime,informationsysteminmemoryofjobassignments,pointingtoapositionjobcontrolblocketc.Therecordoftheinformationdatablockjobassignmentsjobcontrolblocks(called),andthesystemJCBwaitinginthejobassignmentsschedulingjobcontrolblockintoaqueue,thequeueasbackupqueue.Afullinformationintoasystemforitsestablishment,operationjobcontrolblock,andhungthebackupqueue.Whenschedulingproblem,fromthebacklogqueueforchoice.
Fromthebacklogqueueforjobfirstchoice,accordingtotheinformationandjobcontrolblockashortassignment,andselecttheshortesttimeisexecuted,theywouldrunintomemory.
Keywords:
Job;Scheduling;Shortjobfirst;SJF;JCB
第一章课题概述………………………………………………….………………………..1
1.1设计背景..……...……………………………………………………………………..1
1.2目的与要求……...……………………………………………………………………..1
1.3基本理论依据……………………………………………..………………………...…1
第二章设计简介与设计方案论述………………………………………………………..2
2.1设计简介………………………………………………..………………………….…2
2.2设计容………..………………………………………..………………………….…2
第三章详细设计…………………………………………………………..………………..3
3.1设计流程图……………………………………………..………………………….…3
3.2主要程序代码………………………………………………..…………………….…4
第四章设计结果与分析…………………………………………………..………………..7
4.1运行结果截图………………………………….………………………………..…...7
4.2运行结果分析…………………………………………..……………………………8
总结…….……………………………………………………..…………………………...9
致…….……………………………………………………..…………………………..10
参考文献…….………………..………………………………..…………………………..11
附录程序代码………...………………………………..……………………………..…12
第一章课题概述
1.1设计背景
在多道程序环境下,主存中有着多个进程,其数目往往多于处理机数目。
这就要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个进程,使之执行。
分配处理机的任务是由处理机调度程序完成的。
由于处理机是最重要的计算机资源,提高处理机的利用率与改善系统性能(吞吐量、响应时间),在很大程度上取决于处理机调度性能的好坏,因而,处理机调度便成为操作系统设计的中心问题之一。
在多道程序系统中,一个作业被提交后必须经过处理机调度后,方能获得处理机执行。
对于批量型作业而言,通常需要经历作业调度和进程调度两个过程后方能获得处理机。
本次设计就是模拟作业调度和短作业优先的设计。
1.2目的与要求
1.2.1目的
加深对作业概念的理解;
深入了解批处理系统如何组织作业、管理作业和调度作业;
1.2.2设计要求
1.加深对作业概念地理解。
2.掌握短作业优先调度算法。
3.深入了解批处理系统如何组织作业、管理作业和调度作业。
4.了解作业控制块的作用,以与作业控制块的容和组织方式。
1.3基本理论依据
根据作业控制块中的信息,审查系统能否满足用户作业的资源需求,以与按照一定的算法,从外存的后备队列中选取某些作业调入存,并为它们创建进程、分配必要的资源。
短作业优先调度算法,从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入存运行。
第二章设计简介与设计方案论述
2.1设计简介
在多道程序环境下,将系统中的作业组织起来,为每个进入系统的作业建立档案以记录和作业相关的信息,按要求输入作业名、到达时间和服务时间,并为其建立作业控制块(JCB)挂入后备队列。
进行作业调度时,在其后计算出各个作业的开始执行时间、完成时间、周转时间和平均周转时间,利用短作业优先算法进行作业调度,并按照由小到大的顺序显示出来。
2.2设计容
编写程序完成批处理系统中的作业调度,要求采用短作业优先的作业调度算法。
实验具体包括:
首先确定作业控制块的容,作业控制块的组成方式;然后完成作业调度;最后编写主函数对所作工作进程测试。
2.2.1创建JCB作业控制块
创建作业控制块JCB,定义为结构体,为进入系统的作业建立档案,其中定义了作业名,作业到达时间,作业服务时间,作业开始执行时间,作业完成时间,作业周转时间,作业平均周转时间。
2.2.2控制显示信息
输出文字提醒用户操作步骤;设定输入数据的格式与数量;运行完程序后显示输出实验结果。
2.2.3实现短作业优先选择
首先按各个作业完成时间由小到大排序。
再用输入的到达时间与服务时间按一定算法算出各个作业的开始执行时间、完成时间、周转时间和作业平均周转时间。
第三章详细设计
3.1设计流程图
是
否
否
是
图3-1
3.2主要程序代码
3.2.1采用数据结构定义作业控制块
structjcb
{
charname[10];//作业名
floatarrivetime;//作业到达时间
floatservicetime;//作业服务时间
floatstarttime;//作业开始执行时间
floatfinishtime;//作业完成时间
floatzztime;//作业周转时间
floatavezztime;//作业平均周转时间
};
jcb调度算法
voidjcbf(jcb*p,intN)
{
floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,
avezztime=0;
sort(p,N);//以到达时间从小到大排序
for(intm=0;m{
if(m==0)
p[m].finishtime=p[m].arrivetime+p[m].servicetime;
else
p[m].finishtime=p[m-1].finishtime+p[m].servicetime;
inti=0;
for(intn=m+1;n<=N-1;n++)
{
if(p[n].arrivetime<=p[m].finishtime)//查找下标m+1以后的作业中:
服务时间<=p[m].finishtime的作业个数
i++;
}
floatmin=p[m+1].servicetime;
intnext=m+1;//m+1=n
for(intk=m+1;k{
if(p[k+1].servicetime{
min=p[k+1].servicetime;
next=k+1;
}
}
jcbtemp;
temp=p[m+1];
p[m+1]=p[next];
p[next]=temp;
}
3.2.3主函数
intmain()
{
while
(1){
system("CLS");
intN;
printf("\t\t\t------短作业优先调度算法------\n");
printf("请输入作业数目:
");
scanf("%d",&N);
charch;
if(N>MAX){
printf("\t!
!
输入的作业数目太大,请输入不大于%d的整数\n",MAX);
printf("按Q或者q退出程序,按其他任意键继续测试...");
ch=getch();
if(ch=='Q'||ch=='q'){
break;
}
elsecontinue;
}
input(a,N);
jcb*b=a;
jcbf(b,N);
printf("按Q或者q退出程序,按其他任意键继续测试...");
ch=getch();
if(ch=='Q'||ch=='q'){
break;
}
}
return0;
}
第四章设计结果与分析
4.1运行结果截图
4.1.1初始化界面
图4-1初始化
4.1.2输入要调度的作业数目
图4-2输入作业数目
4.1.3输入作业名、到达时间、服务时间
图4-3输入各作业信息
4.1.4运行出的结果
图4-4运行结果
4.2运行结果分析
调度顺序为:
A-->D-->B-->E-->C
运行结果如表所示:
Name
作业名
Arrive
到达时间
Service
服务时间
Start
开始时间
Finish
完成时间
Zz
周转时间
Avezz
平均周转时间
A
0.00
4.00
0.00
4.00
4.00
1.00
D
3.00
2.00
4.00
6.00
3.00
1.50
B
1.00
3.00
6.00
9.00
8.00
2.67
E
4.00
4.00
9.00
13.00
9.00
2.25
C
2.00
5.00
13.00
18.00
16.00
3.20
表4-2结果
分析可知:
短作业优先法先由到达时间排序,执行作业,然后对后来进入系统的作业和系统中等待执行的作业进行计算、比较,以服务时间有小到大排序,并按此顺序进行调度。
总结
课程设计是培养学生综合运用所学知识,发现、提出、分析和解决实际问题,锻炼实践能力的重要环节,是对我们的实际工作能力的具体训练和考察过程。
我做的是作业调度模拟,一开始拿到题目时,实在不知道操作系统和c++如何联系在一起,经过翻阅资料、网上查询、讨论,最后终于完成了本次课程设计。
短作业优先调度算法易于实现,并且效率很高,但是短作业只考虑到短作业的利益,而不顾长作业,这样就可能会使得长作业一直处于等待状态而不能运行。
所以,短作业优先算法适用于系统中短作业较多的情况。
通过这次课程设计,我对操作系统中的作业调度模拟和短作业优先算法有了更深的认识。
并且发现,只看课本上的知识远远不够,只一味学习也根本没用,必须要动手亲自实践,才能真正掌握所学的东西。
致
本次课程设计能顺利完成,是在老师的精心指导和同学的互相帮助下完成的,无论从学习上还是实践上都使我受益匪浅。
感院系为我们提供实练的机会,感老师的细心指导,也感组员们的互相帮助互相探讨。
在本次设计中,自己动手,亲身经历了从学习、探讨、编写、调试的过程。
不仅使对书本上的知识点和理论有了更深一层的了解,使我学会如何利用所学知识,把理论结合于实践,更重要的是让我发散思路,提高实践动手能力。
此次的课程设计收获很多,虽然过程磕磕绊绊,但是最终还是完成了。
但是,单单完成还远远不够,还有许许多多的问题,自己仍然不懂,是在老师、同学的帮助下完成的,在这里再次对他们的帮助表示衷心的感。
参考文献
[1]汤小丹梁红兵哲凤屏等.计算机操作系统(第三版)[M].电子科技大学,2007年出版.91-95页.
[2]任爱华鹏方毅编著.操作系统实验指导[M].清华大学,2004年出版.134-157页.
[3]吕凤翥编著.C++语言基础教程[M].清华大学,2007年出版.
[4]谭浩强著.C程序设计(第三版)[M].清华大学,2005年出版.
附录程序代码
#include
#include
#include
#defineMAX100//最多能管理的作业数目
structjcb//作业控制块JCB,定义为结构体
{
charname[10];//作业名
floatarrivetime;//作业到达时间
floatservicetime;//作业服务时间
floatstarttime;//作业开始执行时间
floatfinishtime;//作业完成时间
floatzztime;//作业周转时间
floatavezztime;//作业平均周转时间
};
jcba[MAX];
voidinput(jcb*p,intN)
{
inti;
printf("请分别输入:
\n\t作业名,到达时间,服务时间(如:
JOB1510)\n\n");
for(i=0;i<=N-1;i++)
{
printf("请输入第%d个作业信息:
",i+1);
scanf("%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetime);
printf("\n");
}
}
voidPrint(jcb*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatavezztime,intN)
{
intk;
printf("调度顺序:
");
printf("%s",p[0].name);
for(k=1;k{
printf("-->%s",p[k].name);
}
printf("\n\n");
printf("\t\t\t作业信息:
\n");
printf("\nname\tarrive\tservice\tstart\tfinish\tzz\tavezz\n");
for(k=0;k<=N-1;k++)
{
printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n",p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].avezztime);
}
}
voidsort(jcb*p,intN)
{
for(inti=0;i<=N-1;i++)
for(intj=0;j<=i;j++)
if(p[i].arrivetime
{
jcbtemp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
voiddeal(jcb*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&avezztime,intN)
{
intk;
for(k=0;k<=N-1;k++)
{
if(k==0)
{
p[k].starttime=p[k].arrivetime;p[k].finishtime=p[k].arrivetime+p[k].servicetime;}
else
{
p[k].starttime=p[k-1].finishtime;p[k].finishtime=p[k-1].finishtime+p[k].servicetime;
}
}
for(k=0;k<=N-1;k++)
{
p[k].zztime=p[k].finishtime-p[k].arrivetime;p[k].avezztime=p[k].zztime/p[k].servicetime;
}
}
voidjcbf(jcb*p,intN)
{
floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,avezztime=0;
sort(p,N);
for(intm=0;m{
if(m==0)
p[m].finishtime=p[m].arrivetime+p[m].servicetime;
else
p[m].finishtime=p[m-1].finishtime+p[m].servicetime;
inti=0;
for(intn=m+1;n<=N-1;n++)
{
if(p[n].arrivetime<=p[m].finishtime)
i++;
}
floatmin=p[m+1].servicetime;
intnext=m+1;//m+1=n
for(intk=m+1;k{
if(p[k+1].servicetime{
min=p[k+1].servicetime;
next=k+1;
}
}
jcbtemp;
temp=p[m+1];
p[m+1]=p[next];
p[next]=temp;
}
deal(p,arrivetime,servicetime,starttime,finishtime,zztime,avezztime,N);
Print(p,arrivetime,servicetime,starttime,finishtime,zztime,avezztime,N);
}
intmain()
{
while
(1){
system("CLS");
intN;
printf("\t\t\t------短作业优先调度算法------\n");
printf("请输入作业数目:
");
scanf("%d",&N);
charch;
if(N>MAX){
printf("\t!
!
输入的作业数目太大,请输入不大于%d的整数\n",MAX);
printf("按Q或者q退出程序,按其他任意键继续测试...");
ch=getch();
if(ch=='Q'||ch=='q'){
break;
}
elsecontinue;
}
input(a,N);
jcb*b=a;
jcbf(b,N);
printf("按Q或者q退出程序,按其他任意键继续测试...");
ch=getch();
if(ch=='Q'||ch=='q'){
break;
}
}
return0;
}