实验二、作业调度模拟程序实验

专业：计算机科学与技术网络工程   姓名：陈玉婷  学号201306114132

一、实验目的

（1）加深对作业调度算法的理解；

（2）进行程序设计的训练。

二、实验内容和要求

    用高级语言编写一个或多个作业调度的模拟程序。

    作业调度算法：1)采用先来先服务（FCFS）调度算法，即按作业到达的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。2)短作业优先 (SJF) 调度算法，优先调度要求运行时间最短的作业。3)响应比高者优先(HRRN)调度算法，为每个作业设置一个优先权(响应比)，调度之前先计算各作业的优先权，优先数高者优先调度。RP (响应比)＝ 作业周转时间 / 作业运行时间=1+作业等待时间/作业运行时间

    每个作业由一个作业控制块JCB表示，JCB可以包含以下信息：作业名、提交（到达）时间、所需的运行时间、所需的资源、作业状态、链指针等等。

模拟数据的生成：允许用户指定作业的个数（2-24），默认值为5，允许用户选择输入每个作业的到达时间和所需运行时间。

   模拟程序的功能：1．按照模拟数据的到达时间和所需运行时间，执行FCFS, SJF和HRRN调度算法，程序计算各作业的开始执行时间，各作业的完成时间，周转时间和带权周转时间（周转系数）。2．动态演示每调度一次，更新现在系统时刻，处于运行状态和等待各作业的相应信息（作业名、到达时间、所需的运行时间等）对于HRRN算法，能在每次调度时显示各作业的响应比R情况。

三、实验方法、步骤及结果测试

   1. 源程序名：压缩包文件（rar或zip）中源程序名 实验二.c

     可执行程序名：实验二.exe

   2. 原理分析及流程图

     存储结构：用结构体数据类型表示一个进程，结构体成员包括：作业到达系统时间starttime，作业运行时间needtime，作业周转时间 runtime作业结束时间endtime，带权周转时间dqzztime，响应比xiangyingbi

     主要算法：

#include
     
      #include
      
       struct job{    char name[10];    int starttime;      //作业到达系统时间    int needtime;       //作业运行时间    int runtime;        //作业周转时间    int endtime;        //作业结束时间    double dqzztime;    //带权周转时间    double xiangyingbi;};void fcfs(struct job jobs[50],int n);void sjf(struct job jobs[50],int n);//void hrrf(struct job jobs[50],int n);void result(struct job jobs[50],int n); void main(){    struct job jobs[50];    int n,i; //n个作业    printf("输入作业个数:",n);    scanf("%d",&n);    printf("输入每个作业的作业名,到达时间,运行时间:\n");    for(i=0;i
       
        jobs[i-1].endtime){            //第i个进程到达系统时，第i-1个进程已运行完毕       jobs[i].runtime=jobs[i].needtime;         jobs[i].endtime=jobs[i].starttime+jobs[i].needtime;      }    else{                                                   //第i个进程到达系统时，第i-1个进程未运行完毕       jobs[i].runtime=jobs[i].needtime+jobs[i-1].endtime-jobs[i].starttime;        jobs[i].endtime=jobs[i].starttime+jobs[i].runtime;    }   jobs[i].dqzztime=jobs[i].runtime*1.0/jobs[i].needtime;   }}void result(struct job jobs[50],int n){    int i;    double averruntime;    double averdqzztime;    int sum_runtime=0;    double  sum_dqzztime=0.00;    printf("作业名\t到达系统时间\t运行时间\t完成时间\t周转时间  带权周转时间\n");    for(i=0;i
        
         jobs[i+1].starttime)          {              min=jobs[i].starttime;              jobs[i].starttime=jobs[i+1].starttime;              jobs[i+1].starttime=min;              min=jobs[i].needtime;              jobs[i].needtime=jobs[i+1].needtime;              jobs[i+1].needtime=min;              strcpy(temp,jobs[i].name);              strcpy(jobs[i].name,jobs[i+1].name);              strcpy(jobs[i+1].name,temp);          }      }                          //按作业到达系统时间进行排序，最早到达的排在最前面                  jobs[0].endtime=jobs[0].starttime+jobs[0].needtime;   jobs[0].runtime=jobs[0].needtime;   jobs[0].dqzztime=jobs[0].runtime*1.0/jobs[0].needtime;    for(i=1;i
         
          jobs[0].endtime) ;            else b=b+1;      //作业到达系统时，第0个作业还在运行  用b统计需等待作业0运行的作业个数    }    for(i=1;i<=b-1;i++)    {        if(jobs[i].needtime>jobs[i+1].needtime)        {           min=jobs[i].starttime;          jobs[i].starttime=jobs[i+1].starttime;          jobs[i+1].starttime=min;                            min=jobs[i].needtime;          jobs[i].needtime=jobs[i+1].needtime;          jobs[i+1].needtime=min;          strcpy(temp,jobs[i].name);             //将第二个参数的值复制给第一个参数，返回第一个参数          strcpy(jobs[i].name,jobs[i+1].name);          strcpy(jobs[i+1].name,temp);        }                 //按最短运行时间排序    }    for(i=1;i
          
           jobs[i-1].endtime) { //第i个进程到达系统时，第i-1个进程已运行完毕 jobs[i].endtime=jobs[i].starttime+jobs[i].needtime; jobs[i].runtime=jobs[i].needtime; } else { jobs[i].endtime=jobs[i-1].endtime+jobs[i].needtime; jobs[i].runtime=jobs[i].endtime-jobs[i].starttime; } jobs[i].dqzztime=jobs[i].runtime*1.0/jobs[i].needtime; }}
          
         
        
       
      
     

   3运行结果及分析

   FCFS算法按照进程提交的顺序调度执行，最先提交的最先调度处理。所以只要对进程实行到达时间的排序就可依次调度。SJF算法按照先调度运行时间最短的进程的顺序执行，所以要先对进程执行到达时间的排序，最先到达的进程排最前，然后对运行时间进行排序，最短运行时间的排在最前面，最先调度执行。HRRF算法要计算第一个进程调度后每一个进程的响应比，按照响应比高的先执行，要用到嵌套循环实现。

四、实验总结

心得体会：对算法的思路是清晰的，可是写起代码来就不会表达，归根到底还是基础差，对C语言的掌握不深。在参考网上的代码后进行理解，并查阅相关书籍后终于实现FCFS算法和SJF算法。对HRRF算法，因为每调度一次进程都要计算其它进程的响应比，而响应比的计算中等待时间会因所调度的进程的结束时间有关，所以感觉很吃力，没有能实现HRRF算法。

实验过程的难点问题及其解决的方法：不会用冒泡法对进程到达时间进行排序。解决：把第i个作业的到达时间看作是最先到达的作业时间（数值最小），依次比较剩余作业的到达时间，当遇到第i+1个作业的到达时间（数值更小），则利用一个临时变量min交换两个作业的到达时间。