操作系统实验二 作业调度

实验目的

1)  加深作业概念的理解；

2)  掌握选择作业调度算法的准则；

3)  掌握作业调度算法。

实验要求

1)  编写程序完成实验内容；

2)  对测试数据进行分析；

3)  撰写实验报告。

实验内容

1)  设计可用于该实验的作业控制块；

2)  动态或静态创建多个作业；

3)  模拟先来先服务调度算法和短作业优先调度算法。

4)  调度所创建的作业并显示调度结果（要求至少显示出各作业的到达时间，服务时间，开始时间，完成时间，周转时间和带权周转时间）；

5）比较两种调度算法的优劣。

实验原理

1.作业

作业(Job)是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。

2.作业控制块JCB(Job Control Block)

　　为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块，如同进程控制块是进程在系统中存在的标志一样，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在JCB中所包含的内容因系统而异，通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。

3.作业调度

作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。

4.选择调度算法的准则

1．面向用户的准则

(1) 周转时间短。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间。其中的后三项在一个作业的整个处理过程中可能会发生多次。

对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。可把平均周转时间描述为：

 

 

作业的周转时间T与系统为它提供服务的时间Ts之比，即W = T/Ts，称为带权周转时间，而平均带权周转时间则可表示为：

 

 

(2) 响应时间快。常把响应时间的长短用来评价分时系统的性能，这是选择分时系统中进程调度算法的重要准则之一。所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。它包括三部分时间：从键盘输入的请求信息传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间。

(3) 截止时间的保证。这是评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预料的后果。

(4) 优先权准则。在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则，以便让某些紧急的作业能得到及时处理。在要求较严格的场合，往往还须选择抢占式调度方式，才能保证紧急作业得到及时处理。

2．面向系统的准则

这是为了满足系统要求而应遵循的一些准则。其中，较重要的有以下几点：

(1) 系统吞吐量高。这是用于评价批处理系统性能的另一个重要指标，因而是选择批处理作业调度的重要准则。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度具有密切关系。对于大型作业，一般吞吐量约为每小时一道作业；对于中、小型作业，其吞吐量则可能达到数十道作业之多。作业调度的方式和算法对吞吐量的大小也将产生较大影响。事实上，对于同一批作业，若采用了较好的调度方式和算法，则可显著地提高系统的吞吐量

(2) 处理机利用率好。对于大、中型多用户系统，由于CPU价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法对处理机的利用率起着十分重要的作用。在实际系统中，CPU的利用率一般在40%(系统负荷较轻)到90%之间。在大、中型系统中，在选择调度方式和算法时，应考虑到这一准则。但对于单用户微机或某些实时系统，则此准则就不那么重要了。

(3) 各类资源的平衡利用。在大、中型系统中，不仅要使处理机的利用率高，而且还应能有效地利用其它各类资源，如内存、外存和I/O设备等。选择适当的调度方式和算法可以保持系统中各类资源都处于忙碌状态。但对于微型机和某些实时系统而言，该准则并不重要。

5.作业调度算法

1）．先来先服务调度算法

先来先服务(FCFS)调度算法是一种最简单的调度算法，每次调度都从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。

2）．短作业优先调度算法

短作业优先调度算法SJF，是指对短作业优先调度的算法。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

3）．最高优先权优先调度算法

为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。系统从后备队列中选择若干个优先权最高的作业装入内存。

以下代码在VC++6.0运行通过：

#include "stdio.h"
#define getjcb(type) (type*)malloc(sizeof(type))
#define NULL 0
int n=0,time=0;float eti,ewi;
struct jcb{ char name[10];
/* 作业名 */
char state;
/* 作业状态 */
int ts;
/* 提交时间 */
int tb;
/* 开始运行时间 */
int tc;
/* 完成时间 */
float ti;
/* 周转时间 */
float wi;
/* 带权周转时间 */
int ntime;
/* 作业所需运行时间 */
char resource[10];
/* 所需资源 */
struct jcb *link;
/* 结构体指针 */
} *p,*q,*head=NULL;
typedef struct jcb JCB;
initial(){
int i;
printf("nInput jcb numn");
scanf("%d",&n);
printf("Inputnnamettstntimetresourcen");
for(i=0;i<n;i++){
p=getjcb(JCB);
scanf("%st%dt%dt%s",&p->name,&p->ts,&p->ntime,&p->resource);
p->state='W';
p->link=NULL;
if(head==NULL) head=q=p;
else{
q->link=p;
q=p;
}
}
}
void print(JCB *pr){
JCB *p;
printf("ntime=%d",time);
printf("nnametstatettstntimetsourcettbttcttitwin");
printf("%st%ct%dt%dt%st%dt%dt%4.2ft%4.2fn",
pr->name,pr->state,pr->ts,pr->ntime,pr->resource,pr->tb,pr->tc,pr->ti,pr->wi);
p=head;
do{
if(p->state=='W')
printf("%st%ct%dt%dt%sn",
p->name,p->state,p->ts,p->ntime,p->resource);
p=p->link;
}while(p!=NULL);
p=head;
do{
if(p->state=='F')
printf("%st%ct%dt%dt%st%dt%dt%4.2ft%4.2fn",
p->name,p->state,p->ts,p->ntime,p->resource,p->tb,p->tc,p->ti,p->wi);
p=p->link;
}while(p!=NULL);
}
void last(){
eti/=n;ewi/=n;
printf("neti=%7.3ftewi=%7.3fn",eti,ewi);
}
void sjf(){
JCB *min;
int i,iden;
for(i=0;i<n;i++){
p=min=head;iden=1;
do{
if(p->state=='W'&&p->ts<=time)
if(iden){
min=p;iden=0;
}
else if(p->ntime<min->ntime) min=p;
p=p->link;
}while(p!=NULL) ;
if(iden) {
i--;printf("ntime=%d:tno JCB submib...wait...",time);time++;
if(time>100){printf("nruntime is too long...error");getch();}
}
else{
running(min);
}
}
}
fcfs(){
JCB *min;
int i,iden;
for(i=0;i<n;i++){
p=min=head;iden=1;
do{
if(p->state=='W'&&p->ts<=time)
if(iden){
min=p;iden=0;
}
else if(p->ts<min->ts) min=p;
p=p->link;
}while(p!=NULL) ;
if(iden) {
i--;printf("ntime=%d:tno JCB submib...wait...",time);time++;
if(time>100){printf("nruntime is too long...error");getch();}
}
else{
running(min);
}
}
}
running(JCB *p){
p->tb=time;p->state='R';
p->tc=p->tb+p->ntime;
p->ti=(float)(p->tc-p->ts);
p->wi=(float)(p->ti/p->ntime);
eti+=p->ti;
ewi+=p->wi;
print(p);
time+=p->ntime;
p->state='F';
printf("n%s has been finished!npress any key to continue...n",p->name);
getch();
}
void runjcb(int m){
printf("nnstart running jcb use algorithm %d.",m);
switch(m){
case 1:fcfs();break;
case 2:sjf();break;
default:printf("nrunjcb error...n");exit();
}
}
start(){
int m;
char str[100]="nselect algorithmn1.FCFSn2.SJFn" ;
printf("%s",str);
m=getch()-48;
initial();
if(1<=m&&m<=2) runjcb(m);
else {
printf("nselect error!try again...n");
start();
}
last();
}
main(){
start();
printf("nfinished!");
getch();
}