昆明理工大学信息工程与自动化学院学生实验报告

（ 20## — 2012学年   第二学期）

课程名称：操作系统             开课实验室：信自楼           20##年4月 10日

一、实验目的

通过编写进程管理的算法，要求学生掌握整个进程管理的各个环节，进程的数据结构描述，进程的各种状态之间的转换，以及进程的调度算法。以加深对进程的概念及进程调度算法的理解，并且提高链表的应用能力，达到提高编程能力的目的。

二、所用仪器、材料（设备名称、型号、规格等）。

计算机一台，VC++ 6.0。

三、源程序：

#include<iostream>

#include<cstdlib>

#include"assert.h"

using namespace std;

class Job{

public:

       int m_runtime;//作业运行时间

    int m_level;//优先级

       int m_arrivenum;//作业到达次序

       int m_start;//作业开始时间

       int m_end;//作业结束时间

       Job* m_next;//指向下一个结点

public:

       Job()

       {

              m_next=NULL;

              m_runtime=0;

              m_level=0;

              m_arrivenum=0;

              m_start=0;

              m_end=0;

       }

       ~Job()

       {

       }

};

class JobList{

public:

       JobList()

       {

              Head=new Job;

              assert(Head);

              length=0;

              int num,runtime,level,arrivenum;

              Job* pt,*st;

              st=Head;

              cout<<"请输入作业个数：";

              cin>>num;

              while(length<num)

              {

                     pt=new Job;

                     assert(pt);

                     cout<<"请输入第"<<length+1<<"个作业的运行时间，优先级，到达次序"<<endl;

                     cin>>runtime>>level>>arrivenum;

                     pt->m_runtime=runtime;

                     pt->m_level=level;

                     pt->m_arrivenum=arrivenum;

                     st->m_next=pt;

                     st=pt;

                     length++;

              }

       }

       ~JobList()//由于Job类调用自己的析构函数，故而此处不需要操作

       {

       }

       Job* GetHead()

       {

              return Head;

       }

       int GetLength()

       {

              return length;

       }

private:

       Job* Head;

       int length;

};

void FCFS( JobList joblist)

{

       int timetag=0,i=0;

       Job* pt;

       while(i<joblist.GetLength())

       {

              pt=joblist.GetHead()->m_next;//头结点不用

              while(pt->m_arrivenum!=i)

              {

                     pt=pt->m_next;

              }

              pt->m_start=timetag;

              timetag+=pt->m_runtime;

              pt->m_end=timetag;

              i++;//下一作业

       }

       int overtime=0;

       pt=joblist.GetHead()->m_next;

       while(pt!=NULL)

       {

              overtime+=(pt->m_end-pt->m_arrivenum);

              pt=pt->m_next;

       }

       cout<<"FCFS的平均作业周转时间为："<<(double)overtime/joblist.GetLength()<<endl;

}

void SJF( JobList joblist)

{

       int tag,i=0,timetag=0;

       Job *pt,*st;

       pt=joblist.GetHead()->m_next;

       //pt->m_start=timetag;

       timetag+=pt->m_runtime;

       pt->m_end=timetag;

       pt->m_runtime=100;

       while(i<(joblist.GetLength()-1))

       {

              st=pt->m_next;

              tag=100;

              while(st)//找到最小

              {

                     if(st->m_runtime<tag)

                            tag=st->m_runtime;

                     st=st->m_next;

              }

              st=pt->m_next;

              while(st->m_runtime!=tag)

                     st=st->m_next;

           st->m_start=timetag;

              timetag+=st->m_runtime;

              st->m_end=timetag;

              st->m_runtime=100;//重新标记

              i++;//下一作业

       }

       int overtime=0;

       while(pt)

       {

              overtime+=(pt->m_end);//-pt->m_arrivenum);

              pt=pt->m_next;

       }

       cout<<"SJF的平均周转时间为："<<(double)overtime/joblist.GetLength()<<endl;

}

void RR( JobList joblist)

{

       Job* pt;

       int timetag=0,remaintime=0;

       bool tag=true;

    pt=joblist.GetHead()->m_next;

       while(pt)

       {

              remaintime+=pt->m_runtime;

              pt=pt->m_next;

       }

       while(tag)

       {

              pt=joblist.GetHead()->m_next;

              while(pt)

              {

                     if(pt->m_runtime==0)

                            pt=pt->m_next;

                     else

                     {

                            timetag+=2;

                            pt->m_runtime-=2;

                            remaintime-=2;

                            if(pt->m_runtime<0)//作业结束自行退出

                            {

                                   pt->m_runtime=0;

                                   timetag--;

                            }

                            if(pt->m_runtime==0)

                                   pt->m_end=timetag;

                            pt=pt->m_next;

                     }

              }

              if(remaintime==0)

                     tag=false;

       }

       pt=joblist.GetHead()->m_next;

       int overtime=0;

       while(pt)

       {

              overtime+=pt->m_end;

              pt=pt->m_next;

       }

       cout<<"RR的平均周转时间为："<<(double)overtime/joblist.GetLength()<<endl;

}

void HLF( JobList joblist)//优先级算法

{

       int timetag=0,i=0,leveltag;

       Job* pt;

       while(i<joblist.GetLength())

       {

              leveltag=0;

              pt=joblist.GetHead()->m_next;

              while(pt)//找到最高优先级别的

              {

                     if(pt->m_level>leveltag)

                            leveltag=pt->m_level;

                     pt=pt->m_next;

              }

              pt=joblist.GetHead()->m_next;

              while(pt->m_level!=leveltag)

              {

                     pt=pt->m_next;

              }

              pt->m_start=timetag;

              timetag+=pt->m_runtime;

              pt->m_end=timetag;

              pt->m_level=0;

              i++;

       }

    pt=joblist.GetHead()->m_next;

       int overtime=0;

       while(pt)

       {

              overtime+=pt->m_end;

              pt=pt->m_next;

       }

       cout<<"HLF的平均作业周转时间为："<<(double)overtime/joblist.GetLength()<<endl;

}

void main()

{

      

       int choice;

       cout<<"请选择调度算法"<<endl<<"0_退出程序"<<endl<<"1_先来先服务 "<<endl<<"2_优先数算法"

              <<endl<<"3_短作业优先算法"<<endl<<"4_时间片轮转算法"<<endl;

       cin>>choice;

       while(choice!=0)

       {

              switch(choice)

              {

              case 1:

                     {

                            cout<<"建立作业"<<endl;

                            JobList myjoblist;

                            FCFS(myjoblist);

                            break;

                     }

              case 2:

                     {

                            cout<<"建立作业"<<endl;

                            JobList myjoblist;

                            HLF(myjoblist);

                            break;

                     }

              case 3:

                     {

                            cout<<"建立作业"<<endl;

                            JobList myjoblist;

                            SJF(myjoblist);

                            break;

                     }

              case 4:

                     {

                            cout<<"建立作业"<<endl;

                            JobList myjoblist;

                            RR(myjoblist);

                            break;

                     }

              }

              cout<<"请选择调度算法"<<endl<<"0_退出程序"<<endl<<"1_先来先服务 "<<endl<<"2_优先数算法"

              <<endl<<"3_短作业优先算法"<<endl<<"4_时间片轮转算法"<<endl;

              cin>>choice;

       }

       //FCFS(joblist);

       //HLF(joblist);

       //SJF(joblist);

       //RR(joblist);

}

四、程序截图：

五、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸）

操作系统是计算机系统中必不可少的系统软件，它是计算机系统中各种资源的管理者和各种活动的组织者、指挥者。操作系统采用时间片法调度进程，使系统资源得到充分利用，用户可以花更少的时间完成过多的工作。通过本次上机进程管理，对操作系统中的进程管理，整体上有了一定的了解，也对上学期所学的数据结构的知识进行了复习，巩固了基础知识， 通过编写进程管理的算法，掌握了整个进程管理的各个环节，进程的数据结构描述，进程的各种状态之间的转换，以及进程的调度算法。对进程中的PCB的数据结构模拟进程的控制，加深了对课本上的进程概念的理解，虽然有的时候还是错误还是很多，不过经过问老师、同学已经解决，自己编程能力还是很欠缺呢，我会继续好好的编写一些程序，看书，来提高自己的编程水平。

 

第二篇：操作系统作业调度实验报告-多道批处理

  计算机  学院  计算机科学与技术  专业  07 班

姓名    学号    教师评定_________________

实验题目                  作业调度                    

一、实验目的

本实验要求学生模拟作业调度的实现，用高级语言编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解。

二、实验内容和要求

1、为单道批处理系统设计一个作业调度程序

(1)、编写并调试一个单道处理系统的作业调度模拟程序。

(2)、作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）的调度算法。

(3)、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。

(4)、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。

(5)、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。

2、模拟批处理多道操作系统的作业调度

（1）写并调试一个作业调度模拟程序。

（2）作业调度算法：分别采用先来服务（FCFS）调度算法。

（3）在批处理系统中，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求，所需要的资源是否得到满足。

     作业调度程序负责从输入井选择若干个作业进入主存，为它们分配必要的资源，当它们能够被进程调度选中时，就可占用处理机运行。作业调度选择一个作业的必要条件是系统中现有的尚未分配的资源可满足该作业的资源要求。但有时系统中现有的尚未分配的资源既可满足某个作业的要求也可满足其它一些作业要求，那么，作业调度必须按一定的算法在这些作业中作出选择。当作业正常运行完毕或因发生错误非正常终止时，作业进入完成状态，此时，系统将收回该作业所占用的全部资源，并清除有关的JCB。并输出显示作业运行情况及作业输出结果。

三、实验设计方案及原理

假设在单道批处理环境下有四个作业JOB1、JOB2、JOB3、JOB4，已知它们进入系统的时间、估计运行时间。分别采用先来先服务（FCFS），最短作业优先（SJF）调度算法，计算出作业的平均周转时间和带权的平均周转时间 。

作业p的周转时间：p->ttime=p->ftime-p->atime

作业的平均周转时间：total=全部进程的周转时间/进程个数

    作业p的带权周转时间：p->wtime =p->ttime/p->ntime

    作业的平均带权周转时间：W=全部进程的带权周转时间/进程个数

1、先来先服务调度算法（FCFS）：每次调度都是从后备作业队列中，选择一个或多个最先进入   该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，这每次调度是从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件阻赛后，才放弃处理机。

2、最短作业优先（SJF）：每次从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。

对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。

3、多道作业调度算法：将作业按FCFS原则排好队，在输入井中按作业到达的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业时，那么顺序挑选后面的作业，把不能满足要求的放回输入井尾部等待，当作业执行结束进入完成状态时，做好释放资源等善后工作。

四、流程图

1、FCFS算法和SJF算法:

 

2.多道作业调度算法

五、给出程序中源程序名和执行程序名：

源程序名：FCFS and SJF,执行程序名：fcfs and sjf.cpp

源程序名：DUODAO      执行程序名：duodao.cpp

六、程序清单

1.FCFS和SJF算法

#include "stdio.h"

#include <stdlib.h>

#include <conio.h>

#define getpch(type) (type*)malloc(sizeof(type))

struct jcb{

   char name[10];

   char state;

   int atime;//作业到达时间

   int btime;//作业开始运行时间

   int ftime;//作业完成时间

   int ntime;//作业估计运行时间

   int rtime;//作业执行时间

   int ttime;//周转时间

   float wtime;//带权周转时间(周转时间/估计运行时间）

   struct jcb* link;

}*ready=NULL, *p;//ready指向队头，p指向正被调度的作业

typedef struct jcb JCB;

 int T=0; //初始化时间量

 float total;//记录所有作业的总时间

 double weight;//记录所有作业的带权周转时间

void sort() /* 建立对作业进行到达时间排列函数*/

{

    JCB *first, *second;

    int insert=0;

    if((ready==NULL)||((p->atime)<(ready->atime))) /*作业到达时间最短的,插入队首*/

    {

        p->link=ready;

        ready=p;

        T=p->atime; //更改时间量

    }

    else /* 作业比较到达时间,插入适当的位置中*/

    {

        first=ready;

        second=first->link;

        while(second!=NULL)

        {

            if((p->atime)<(second->atime)) /*若插入作业比当前队尾作业到达时间短,*/

            { /*插入到当前队尾作业前面*/

                p->link=second;

                first->link=p;

                second=NULL;

                insert=1;

            }

            else /* 插入作业到达时间最长,则插入到队尾*/

            {

                first=first->link;

                second=second->link;

            }

        }

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

    }

}

void shortjob() // 获取队列中的最短作业

{

       JCB *pr,*min,*qr;

        min=ready;//min指向作业对头

        qr=ready;

        pr=ready->link;

       while(pr!=NULL)

    {

       if((pr!=NULL)&&(T>=pr->atime)&&(pr->ntime)<(min->ntime))

        {//当插入作业到达时间要比时间量T小

           min=pr; //min指向pr

           qr->link=pr->link;//qr的下一个指向pr的下一个

           pr->link=ready;

           pr=pr->link;

        }

      else  //当pr的需要时间不小于min的需要时间

       { qr=pr;

        pr=pr->link;}

    ready=min;//把最终获取的min的需要时间赋给ready，开始执行

    }

}

void input() /*建立作业控制块函数*/

 {

  int i;

  printf("\n 请输入4个作业：");

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

  {

    printf("\n 请输入作业号NO.%d：\n",i);

    p = getpch(JCB);

    printf("输入作业名：");

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

    printf("\n输入作业到达时间：");

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

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

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

    printf("\n");

    p->rtime = 0;

    p->btime=0;

    p->ftime=0;

    p->ttime=0;

    p->wtime=0;

    p->state = 'W';

    p->link = NULL;

    sort();

   }

 }

int space() /*查看作业个数*/

{

  int l = 0;

  JCB *pr = ready;

  while(pr != NULL)

  {

   l++;

   pr = pr->link;

  }

  return(l);

}

void disp(JCB *pr) /*建立作业显示函数，用于显示当前作业*/

{

  printf("\n qname \t state \t atime \t ntime \t btime \t rtime \t ftime \t ttime \t wtime \n");

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

  printf(" |%c \t",pr->state);

  printf(" |%d \t",pr->atime);

  printf(" |%d \t",pr->ntime);

  printf(" |%d \t",pr->btime);

  printf(" |%d \t",pr->rtime);

  printf(" |%d \t",pr->ftime);

  printf(" |%d \t",pr->ttime);

  printf(" |%.2f \t",pr->wtime);

  printf("\n");

}

void check() /* 建立作业查看函数 */

{

    JCB* pr;

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

    disp(p);

    pr=ready;

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

    while(pr!=NULL)

    {

        disp(pr);

        pr=pr->link;

    }

}

void destroy()

{

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

  free(p);

}

void running(JCB *pr) //计算各个时间

{

    if(T>=pr->atime) pr->btime=T;//插入作业的到达时间比时间量小，T为该作业的开始时间

       else pr->btime=pr->atime;//否则该作业到达时间为它的开始时间

       pr->ftime=pr->btime+pr->ntime;

       pr->ttime=p->ftime-p->atime;

    pr->wtime=(float)pr->ttime/(float)pr->ntime;

       total+=pr->ttime;

    weight+=pr->wtime;

    T=pr->ftime;//T为该上一个作业的完成时间

}

void running1(JCB *pr)  //分离出要执行的当前作业

{

    if(T>=pr->atime) pr->btime=T;

       else pr->btime=pr->atime;

}

void running2(JCB *pr) //判断运行时间和需要运行时间的关系

{

 while(pr->rtime<pr->ntime)

 {

   pr->state = 'R';

   (pr->rtime)=(pr->ntime);

 }

 printf("\n\n ****该作业执行完毕时的状态：\n");

 pr->state='F';

 disp(pr);

 destroy();

}

int main()

{

   int i,len, h = 0;

   char ch;

   total=0;

   weight=0;

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

   printf("                            \n");

   printf("                 FCFS算法或SJF算法                     \n");

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

   input();

   len = space();

   printf("\n选择算法: ");

   scanf("%d",&i);

   switch(i)

   {

     case 1:

         printf("FCFS算法：\n");break;

     case 2:

         printf("SJF算法：\n");break;

     default:printf("FAULSE");

   }

  if(i==1||i==2)

  {

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

         {

        ch = getchar();

        if(i==2) shortjob();

        h++;

        printf("\n The execute number:%d\n",h);

        p = ready; /*将队首指针赋给p*/

        ready = p->link;  /*ready指向原p的下一个进程*/

        p->link = NULL;  /*p的link赋空*/

        p->state = 'R';

        p->btime=p->atime;

        running1(p);

        check();

        running(p);

        running2(p);

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

        ch = getchar();

         }

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

   ch = getchar();

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

   printf("\n平均周转时间：%f",total/(float)4);

   printf("\n平均带权周转时间：%lf",weight/(float)4);

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

  }

}

2.多道作业调度算法：

#include "stdio.h"

#include <stdlib.h>

#include <conio.h>

#define getpch(type) (type*)malloc(sizeof(type))

#define source 15

struct jcb{

   char username[10];

   char jobname[10];

   char state;

   int atime;//作业到达时间

   int ntime;//作业估计运行时间

   int rtime; //作业的运行时间

   int nsource;//作业所需系统资源

   int asource;//已分配的资源

   int need1;

   struct jcb* link;

}*ready=NULL, *p;//ready指向就绪队列的队头，p指向正被调度的作业

typedef struct jcb JCB;

 int rsource=15;//剩下资源

int num,i=0;//num为作业个数，i为记录不能满足作业要求调度的次数

void destroy(JCB *pr)

{

  free(pr);

}

void sort() /* 建立对作业进行到达时间排列函数*/

{

    JCB *first, *second;

    int insert=0;

   if((p->nsource<=source)&&(rsource>=0)&&(p->nsource>p->asource))

    {//需要资源要在系统资源范围内，分配资源要在需要资源范围内，剩下资源不能小于0

       if((ready==NULL)||((p->atime)<(ready->atime))) /*作业到达时间最短的,插入队首*/

      {

        p->link=ready;

        ready=p;

      }

     else /* 作业比较到达时间,插入适当的位置中*/

      {

        first=ready;

        second=first->link;

        while(second!=NULL)

        {

            if((p->atime)<(second->atime)) /*若插入作业比当前队尾作业到达时间短,*/

            { /*插入到当前队尾作业前面*/

                p->link=second;

                first->link=p;

                second=NULL;

                insert=1;

            }

            else /* 插入作业到达时间最长,则插入到队尾*/

            {

                first=first->link;

                second=second->link;

            }

        }

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

      }

      }

    else

    destroy(p);

}

void sort1() /*对作业进行排列函数 */

{

 JCB *first;

  if(ready==NULL) /*如果就绪队列为空*/

  {

   ready=p; /*将新建作业放入队列中，将ready指向队首作业 */

  }

  else /*队列中有作业在等待，将新建作业插入到队尾 */

 {

  first=ready; /*first指针指向队首作业 */

  while(first->link!=NULL) first=first->link; /*当first指针没有指向队尾时，指针后移 */

  first->link=p;/*将p指向的作业插入队尾*/

 }

}

void input() /*建立作业控制块函数*/

 {

  int i;

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

  scanf("%d",&num);

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

  {

    printf("\n 请输入作业号NO.%d：\n",i);

    p = getpch(JCB);

    printf("输入作业用户名:");

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

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

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

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

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

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

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

    printf("\n 输入作业所需资源:");

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

    printf("\n 输入作业已分配资源:");

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

    printf("\n");

    p->need1=p->nsource-p->asource;//还需要资源=需要资源-已分配资源

    p->state='W';

    p->link=NULL;

    sort();

   }

 }

int space() /*查看作业个数*/

{

  int l=0;

  JCB *pr=ready;

  while(pr!=NULL)

  {

   l++;

   pr=pr->link;

  }

  return(l);

}

void disp(JCB *pr) /*建立作业显示函数，用于显示当前作业*/

{

  printf("\n 用户N \t 作业N \t 状态S \t 到达T \t 服务T \t 所需S \t 已分S \t 还需S \n");

  printf(" |%s \t",pr->username);

  printf(" |%s \t",pr->jobname);

  printf(" |%c \t",pr->state);

  printf(" |%d \t",pr->atime);

  printf(" |%d \t",pr->ntime);

  printf(" |%d \t",pr->nsource);

  printf(" |%d \t",pr->asource);

  printf(" |%d \t",pr->need1);

  printf("\n");

}

void check()

{

  JCB *pr;

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

  disp(p);

  pr=ready;

  printf("\n****当前输入井队列状态为：\n"); /*显示就绪队列状态*/

  while(pr != NULL)

  {

   disp(pr);

   pr = pr->link;

  }

}

void running(JCB *p)//对输入井队列中满足资源要求的作业进行服务

{

   while(p->rtime<p->ntime)

         {

           (p->rtime)++;

         }

   p->state='F';     

   printf("\n****作业运行完成后状态:\n");

   disp(p);

   printf("\n 用户名[%s]的作业[%s] 已完成。\n",p->username,p->jobname);

}

void running1()// 计算剩下资源

{

 JCB *pr;

 for(pr=ready;pr!=NULL;pr=pr->link)

 {rsource=rsource-pr->asource;}

}

void running2(JCB *pr)

 {

      if(pr->need1<=rsource)

        {

           check();

           rsource-=pr->need1;

           pr->asource+=pr->need1;

           pr->need1 =0;

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

           printf("\n分配给作业后所剩的资源是：%d \n",rsource);

           running(pr);

           rsource = rsource + pr->nsource;

           printf("\n释放后的资源是：%d\n",rsource);

           destroy(pr);

           }

         else

         {

              printf("该作业不能满足要求，调度下一个作业");

              sort1();

              i++;

         }

}

void main()

{

   int len, h=0;//h表示执行的次数

   int flag=0;//用来记录排在前面却没被调用的作业个数

   char ch;

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

   printf("                             \n");

   printf("                  多道作业调度算法                       \n");

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

   input();

   len = space();

   running1();

   if(rsource>=0)

   {

    while((i<=2*num)&&(len!=0)&&(ready!=NULL))

    {

     ch=getchar();

     h++;

     printf("The execue number:%d\n",h);

     printf("\n系统可分配资源是：%d",rsource);

     ch=getchar();

     p=ready;

     ready=ready->link;

     p->link=NULL;         

     p->state ='R';

     running2(p);

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

     ch=getchar();       

    }

   if(i>2)

       {

         printf("\n******剩下系统资源不能满足作业需要要求了\n");

         printf("\n******退出程序");

       }

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

   ch=getchar();

  }

  else

   printf("\n\n****因为输入已分配的资源与系统资源不符合错误，所以退出程序****");

}

七、运行结果

1．FCFS算法

2.SJF算法

3.多道作业调度算法

八、结果分析与调试过程小结

在调试FCFS算法中重要的是怎么按到达时间先后插入就绪队列，其中还要考虑到当前有进程在运行的情况的。但由于进程是先来先服务的，所以需要定义另一指针first来确定要进来的进程插入的位置。在调试SJF算法中，它是基于FCFS算法的基础上，利用shortjob()来查询已排好队的作业中所需运行时间最短的作业，从而把把它指向ready指针的，但由于一开始遗忘了C语言中指针的链接，导致程序出现了了一系列的问题，如无法出现JCB控制块等等。在多道作业调度中我总共想到了三个问题，第一个是输入的信息中要防止出错，就用来if((p->nsource<=source)&&(rsource>=0)&&(p->nsource>p->asource))来判断，如果有错就不让它进入输入井；第二个是当第一个先到作业因为不能满足要求而不能执行时如何处置，怎么再次调用它，就再调用一次sort()函数；第三个是在第二问题上因为调用了sort(),会导致不能满足要求的作业一直重复着判断作业这一步骤，也就出现了死循环。我想了很久只找到了个愚蠢的办法，就是每次调用作业若不能满足要求，都用i来记录着，然后给定条件（i<=2*作业个数）来缩短循环次数。

十、思考题

1、  写出每种算法的调度策略，最后比较各种算法的优缺点。

答：先来先服务算法是根据作业的到达时间先后来排序,到达时间短的先运行，优点是实现简单，利于长作业，缺点是运行时间慢，不利于短作业。

短作业优先算法是先根椐作业的到达时间先后来排序，然后查找所需运行时间短的先运行，优点是运行时间快,缺点是实现起来比较复杂，对长作业不利。

2、  选择调度算法的依据是什么？

答：如果作业要求的速度不高，而且作业比较小型，那就最好用先来先服务算法。

如果作业要求的速度高，作业流程复杂，那就最好用短作业优先算法。

附加：

关键函数：

对于FCFS算法来说其关键函数是sort()//按到达时间先后顺序排列，和running()//当前作业执行情况，还有各种时间的计算。其中sort()中需要考虑当前就绪队列为空，还是有作业正在运行的情况，而running()中，我把它分成了三部分，一部分是先将每一个要执行的作业分离出来，好让它在执行check()的当前执行作业时能显示出开始运行时间（btime），而其它非输入类时间显示为’0’，直到运行完毕状态才把所有各类时间打印出来；第二部分进行各类时间的计算；第三部分用来判断运行时间是否达到它所需要运行的时间。对于SJF算法来说，因为它是基于FCFS算法的基础上的，所以FCFS中的关键函数也是SJF的关键函数，但是SJF中还有一个关键函数，那就是shortjob()//获取最短作业，这是在sort()中排好的作业中再次查找所需运行时间最短的作业，然后调度它。对于多道作业调度算法来说，sort()函数、sort1()函数、三个running()函数，第一个sort()是用来判断输入作业信息的正确性，正确了就按照作业到达时间先后顺序排列；第二个sort1()是在输入井中判断的作业不能满足要求时，利用该函数来把它插在输入井队尾；第三个是running函数，它分三部分，第一部分是running1()用来计算剩下可分配资源，第二部分是running()用来判断运行时间是否达到作业所需时间，如果没达到就继续运行，直到达到才释放资源，第三部分是running2()用来执行满足资源要求的作业。

数据结构：

   在FCFS和SJF算法中，均采用一个队列来实现作业的调度，首先先判断对头ready是否为空，为空时直接插入作业，否则还要判断就绪队列中是否有正在执行的作业，有的话得把要插进来的进程插入到适当的位置中，等所有进程排好队好，就按照队列先进先出的特点，总是执行对头的作业，直到队列为空。但在SJF算法中，因为它是短作业优先执行，那么在按到达时间先后排好的队列中，采用shortjob()函数调用所需时间最短的作业，就相当于有一个虚构的队列将作业按所需运行时间重新排列，而其本身并不存在。在多道作业调度算法中，每个作业由作业控制块JCB表示，包含有如下信息：用户名、运行状态、到达时间、需要的资源，分配的资源等，首先作业按作业到达时间先后排成一个队列，也就是运用到了队列先进先出的原则，使作业能顺利完成。