作业调度算法实验报告

实验名称：  作业调度实验                     

一、实验目的  

模拟作业调度算法，学习作业在操作系统中的调度过程，加深对作业管理的理解。特别是作业调度的概念、作业调度与进程调度的区别。培养学生程序设计的方法和技巧，提高学生编制清晰、合理、可读性好的系统程序的能力，加深对操作系统课程的理解，拓宽学生的知识领域，锻炼学生的实践技能。

二、实验要求 

本实验模拟单处理器系统的作业调度，加深对作业调度算法的理解。用某种语言编写和调试一个作业调度的算法程序，有一些简单的界面，能够运行，仿真操作系统中作业调度的原理和过程。

 

1、 在后备作业队列中输入3道作业各自需要的时间及存储空间。数据输入格式如下：

作业编号 作业名称 提交时间 运行时间 存储空间 开始时间 完成时间 等待时间

0 a 2  2      

1 b 1  3    

2 c 3  2     

   

2、  按先来先服务（FCFS）的原则进行调度，输出作业调度的顺序及各自的等待时间。

3、  按最短作业优先（SJF）的原则进行调度，输出作业调度的顺序及各自的等待时间。

4、  按响应比最高优先的原则进行调度，输出作业调度顺序及各自的等待时间。

5、   按时间片轮转法进行调度，输出作业调度顺序及各自的等待时间。

6、  建立4个子函数对应4种算法，在主函数中调用它们并按格式输出相关信息；

7、   按调度顺序输出作业，输出格式为：

     作业编号、作业名、提交时间、运行时间、存储空间、等待时间

 

三、实验原理

作业调度算法和进程调度算法。其中作业调度算法主要有先来先服务法FCFS、短作业优先法SJF、最高响应比优先法HRN、定时轮转法和优先数法。在进程调度算法中主要介绍了先来先服务法FCFS、轮转法RR、多级反馈轮转法和优先数法。

   需要指出的是：（1）在作业调度和进程调度中同时出现的算法，如FCFS、RR、优先数法，其使用原理是基本相同的；（2）作业调度算法和进程调度算法应严格与存储管理中的“请求淘汰换页算法”相区别，注意不要混淆。

实验提示

1、  根据作业输入数据，定义JCB结构；

struct JCB{

char JobNum;

char JobName;

…

};

2、  定义数据结构装载后备作业

JCB JobArray[MaxNumber];

3、  三种调度算法的设计

4、  C++语言描述顺序

建立文件：jcb.h；其中存放：

最大作业数；

定义数据结构JCB；

四个作业调度函数；

建立主函数，其中包含：

#include<iostream.h>

#include”jcb.h”

void mian()

{

   JCB jobArray[MaxNumber];

   数据输入；

调用四种算法并输出调度结果；

}

 

 

 

 

 

作业调度模拟程序的系统功能结构如图1所示。

 

作 业 调 度 系 统

先来先服务算法

短作业优先算法

高响应比优先算法

时间片轮 转 算 法

初始化

运行作业

输出运行结果

初始化

运行作业

输出运行结果

输出运行结果

运行作业

初始化

 

 

 

 

 

 

 

 

 

 

 

 

 

图1 作业调度模拟程序系统功能结构图

 

作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。

（1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。流程图如图2所示。

 

空

结 束

计算并打印这组作业的平均周转时间及带权平均周转时间

等待队列空？

更改时间量times的值； times:=times+服务时间

计算并打印运行作业i的完成时刻finishtime，周转时间cycletime，带权周转时间cltime; 完成时间：=开始运行时间+服务时间 周转时间：=完成时间—到达时间 带权周转时间：=周转时间/服务时间

调度队首的作业投入运行； 更改队首指针，使作业的状态为R，记住作业运行的时刻starttime等

初始化所有的JBC 使JBC按作业提交的时刻的先后顺序排队 时间量times:=0

开 始

不空

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

图2 先来先服务调度算法流程图

 

 

 

 

 

（2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。流程图如图3所示。

 

空

结 束

计算并打印这组作业的平均周转时间及带权平均周转时间

等待队列空？

更改时间量times的值； times:=times+服务时间

计算并打印运行作业i的完成时刻finishtime，周转时间cycletime，带权周转时间cltime; 完成时间：=开始运行时间+服务时间 周转时间：=完成时间—到达时间 带权周转时间：=周转时间/服务时间

调度队首的作业投入运行； 更改队首指针，使作业的状态为R，记住作业运行的时刻starttime等

初始化所有的JBC 使JBC按作业提交的时刻的先后顺序排队 时间量times:=0

开 始

不空

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

图3 短作业优先调度算法流程图

 

 

 

（3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。流程图如图4所示。

 

空

结 束

计算并打印这组作业的平均周转时间及带权平均周转时间

等待队列空？

更改时间量times的值； times:=times+服务时间

计算并打印运行作业i的完成时刻finishtime，周转时间cycletime，带权周转时间cltime; 完成时间：=开始运行时间+服务时间 周转时间：=完成时间—到达时间 带权周转时间：=周转时间/服务时间

先计算队列中所有作业的响应比，总是选择响应比最高的走也作为此刻要运行的作业，并修改相应的指针，记下starttime等

初始化所有的JBC 使JBC按作业提交的时刻的先后顺序排队 时间量times:=0

开 始

不空

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

图4响应比高者优先算法流程图

 

 

 

四、实验所需仪器、设备、材料

PC机

五、实验预习要求、实验条件、方法及步骤

1）熟练掌握作业相关的基本概念。

2）熟练掌握作业调度的有关算法。

3）熟练掌握作业调度算法所需的数据结构和算法流程；

4）熟练掌握某一门编程语言，如C、C＋＋或者Dephi等

  

作业调度算法源代码
#include<stdio.h>

#include <stdlib.h>

#include <conio.h>

#define getpch(type) (type*)malloc(sizeof(type))    //为进程创建一个空间

 

struct worktime{

    float Tb;             //作业运行时刻

    float Tc;             //作业完成时刻

    float Ti;             //周转时间

    float Wi;            //带权周转时间

};

 

struct jcb {              

    char name[10];        //作业名

    float subtime;        //作业到达时间

    float runtime;        //作业所需的运行时间

    char resource;        //所需资源

    float Rp;             //后备作业响应比

    char state;           //作业状态

    int worked_time;      //已运行时间   

    struct worktime wt;

    int need_time;       //要求运行时间

    int flag;             //进程结束标志

    struct jcb* link;     //链指针

}*ready=NULL,*p;

 

typedef struct jcb JCB;

float T=0;

int N;

JCB *front,*rear;        //时间轮转法变量

 

void sort()     

{

    JCB *first, *second;

    int insert=0;  //插入数

    if((ready==NULL)||((p->subtime)<(ready->subtime)))  

    {

        p->link=ready;

        ready=p;

        T=p->subtime;

        p->Rp=1;

    }

    else

    {

        first=ready;

        second=first->link;

        while(second!=NULL)

        {

            if((p->subtime)<(second->subtime))

            {

                p->link=second;

                first->link=p;

                second=NULL;

                insert=1;

            }

            else

            {

                first=first->link;

                second=second->link;

            }

        }

        if (insert==0) first->link=p;

    }

}

 

void SJFget()

{

    JCB *front,*mintime,*rear;

    int ipmove=0;

    mintime=ready;

    rear=mintime->link;

    while(rear!=NULL)

    {

        if ((rear!=NULL)&&(T>=rear->subtime)&&(mintime->runtime)>(rear->runtime))

        {

            front=mintime;

            mintime=rear;

            rear=rear->link;

            ipmove=1;

        }

        else

            rear=rear->link;

    }

    if (ipmove==1)

    {

        front->link=mintime->link;

        mintime->link=ready;

    }

    ready=mintime;

}

 

void HRNget()

{

    JCB *front,*mintime,*rear;

    int ipmove=0;

    mintime=ready;

    rear=mintime->link;

    while(rear!=NULL)

        if ((rear!=NULL)&&(T>=rear->subtime)&&(mintime->Rp)<(rear->Rp))

        {

            front=mintime;

            mintime=rear;

            rear=rear->link;

            ipmove=1;

        }

        else

            rear=rear->link;

    if (ipmove==1){

        front->link=mintime->link;

        mintime->link=ready;

    }

    ready=mintime;

}

 

void creatJCB() //为每个作业创建一个JCB并初始化形成一个循环链队列

{   

    JCB *p,*l;

    int i=0;

    l = (JCB *)malloc(sizeof(JCB));

    printf("\n 请输入作业的个数:");

    scanf("%d",&N);

    printf("\n 作业号No.%d:\n",i);

    printf("\n请输入作业的名字:");

    scanf("%s",l->name);

    printf("\n请输入作业的时间:");

    scanf("%d",&l->need_time);

    l->state = 'r';          //作业初始状态为就绪

    l->worked_time = 0;

    l->link=NULL;

    l->flag=0;

    front=l;

    for(i =1;i<N;i++)

    {

        p = (JCB *)malloc(sizeof(JCB));

        printf("\n 作业号No.%d:\n",i);

        printf("\n请输入作业的名字:");

        scanf("%s",p->name);

        printf("\n请输入作业的时间:");

        scanf("%d",&p->need_time);

        p->state='r';

        p->worked_time=0;

        p->flag=0;

        l->link=p;

        l=l->link;

    }

    rear=l;rear->link=front;

}  

 

void output()//进程输出函数

{  

    int j;

    printf("name runtime needtime state\n");

    for(j=1;j<=N;j++)

    {   printf(" %-4s\t%-4d\t%-4d\t%-c\n",front->name,front->worked_time,front->need_time,front->state);

        front=front->link;

    }

    printf("\n");

}

 

int judge(JCB *p) //判断所有进程运行结束

{

    int flag=1,i;

    for(i=0;i<N;i++)

    {

        if(p->state!='e')

        {

            flag = 0;

            break;}

        p=p->link;

    }

    return flag;

}

 

void RRget()//时间片轮转算法

{ 

    JCB *s;

    int flag1=0;

    s=(JCB *)malloc(sizeof(JCB));

    s=front;

    printf("\n--------------------------------------------\n");

    output();

    printf("请输入任意一键继续\n");

    getch();   //按任意键继续

    s=front;

    while(flag1 != 1)

    {

        if(s->state=='r')

        {

            s->worked_time++;

            s->need_time--;

            if(s->need_time==0)

                s->state='e';

            output();

            printf("请输入任意一键继续...\n");

            getch();

        }

        if(s->state=='e'&&s->flag==0)

        {

            printf("进程%s已经运行完成！\n\n",s->name);

            s->flag=1;

        }

        s=s->link;

        flag1=judge(s);

    }

    printf("--------------------------------------------\n");

}

 

void input()

{

    int i,num;

    printf("\n 请输入作业的个数:");

    scanf("%d",&num);

    for(i=0;i<num;i++)

    {

        printf("\n 作业号No.%d:\n",i);

        p=getpch(JCB);

        printf("\n 输入作业名:");

        scanf("%s",p->name);

        printf("\n 输入作业到达时刻:");

        scanf("%f",&p->subtime);

        printf("\n 输入作业运行时间:");

        scanf("%f",&p->runtime);

        printf("\n");

        p->state='w';

        p->link=NULL;

        sort();

    }

}

 

int space()

{

    int l=0; JCB* jr=ready;

    while(jr!=NULL)

    {

        l++;

        jr=jr->link;

    }

    return(l);

}

 

void disp(JCB* jr,int select)

{

    if (select==3) printf("\n 作业   到达时间    服务时间   响应比   运行时刻   完成时刻   周转时间   带权周转时间 \n");

    else printf("\n 作业   到达时间    服务时间   运行时刻   完成时刻   周转时间   带权周转时间 \n");

    printf(" |%s\t",jr->name);

    printf(" |%.2f\t  ",jr->subtime);

    printf("  |%.2f\t",jr->runtime);

    if (select==3&&p==jr) printf("|%.2f    ",jr->Rp);

    if (p==jr){

        printf("|%.2f\t ",jr->wt.Tb);

        printf("  |%.2f   ",jr->wt.Tc);

        printf("  |%.2f\t",jr->wt.Ti);

        printf("  |%.2f",jr->wt.Wi);

    }

    printf("\n");

}

 

int destroy()

{

    printf("\n 作业 [%s] 已完成.\n",p->name);

    free(p);

    return(1);

}

 

void check(int select)

{

    JCB* jr;

    printf("\n **** 当前正在运行的作业是:%s",p->name);

    disp(p,select);

    jr=ready;

    printf("\n ****当前就绪队列状态为:\n");

    while(jr!=NULL)

    {

        jr->Rp=(jr->runtime+T-jr->subtime)/jr->runtime;

        disp(jr,select);

        jr=jr->link;

    }

    destroy();

}

 

void running(JCB* jr)

{

    if (T>=jr->subtime) jr->wt.Tb=T;

    else jr->wt.Tb=jr->subtime;

    jr->wt.Tc=jr->wt.Tb+jr->runtime;

    jr->wt.Ti=jr->wt.Tc-jr->subtime;

    jr->wt.Wi=jr->wt.Ti/jr->runtime;

    T=jr->wt.Tc;

}

 

int main()

{

    int select=0,len,h=0;

    float sumTi=0,sumWi=0;

    printf("\t---*****************---\n");

    printf("请选择作业调度算法的方式:\n");

    printf("\t1.FCFS 2.SJF 3.HRN 4.RR\n\n");

    printf("\t---*****************---\n");

    printf("请输入作业调度算法序号(1-4):");

    scanf("%d",&select);

    if (select==4)

    {   creatJCB();

        RRget();}

    else

    {

    input();

    len=space();

   

     

    while((len!=0)&&(ready!=NULL))

    {

        h++;

        printf("\n 执行第%d个作业 \n",h);

        p=ready;

        ready=p->link;

        p->link=NULL;

        p->state='R';

        running(p);

        sumTi+=p->wt.Ti;

        sumWi+=p->wt.Wi;

        check(select);

        if (select==2&&h<len-1) SJFget();

        if (select==3&&h<len-1) HRNget();

        printf("\n 按任意一键继续......");

        getchar();

        getchar();

    }

    printf("\n\n 作业已经完成.\n");

    printf("\t 此组作业的平均周转时间：%.2f\n",sumTi/h);

    printf("\t 此组作业的带权平均周转时间：%.2f\n",sumWi/h);

    getchar();}

}

    

 

六、程序运行情况

1、  按先来先服务（FCFS）的原则进行调度，输出作业调度的顺序及各自的等待时间。

（1）数据输入：

 

 

 

 

 

 

 

 

 

 

（2）.运行情况：

 

 

 

 

 

2、  按最短作业优先（SJF）的原则进行调度，输出作业调度的顺序及各自的等待时间。

（1）、数据输入

 

 

 

 

 

 

 

 

 

 

 

（2）、运行结果

 

 

 

 

 

 

 

 

 

 

 

 

3、  按响应比最高优先的原则进行调度，输出作业调度顺序及各自的等待时间。

 

（1）、数据输入

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

（2）、运行结果

 

 

 

 

 

4、按时间片轮转法进行调度，输出作业调度顺序及各自的等待时间。

 

（1）、数据输入

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

（2）、运行结果