课 程  设 计

采用短作业优先调度算法调度程序

学    号：                          

姓    名：                          

专    业：                          

指导老师：                          

日    期：                           

摘要                

在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。       

在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。  本次课程设计主要是模拟短作业优先(SJF)调度算法。

一、实验题目

采用短作业优先算法的的进程调度程序

二、课程设计的目的

●操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，分析和解决实际问题的机会。

●进一步巩固和复习操作系统的基础知识。

●培养学生结构化程序、模块化程序设计的方法和能力。

●提高学生调试程序的技巧和软件设计的能力。

●提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。

三、设计内容

设计并实现一个采用短作业优先算的进程调度算法演示程序

四、设计要求

1.  每一个进程有一个PCB，其内容可以根据具体情况设定。  

2.  进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定  

3.  可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化  

4.  可以在运行中显示各进程的状态：就绪、执行 （由于不要求设置互斥资源与进程间同步关系，故只有两种状态）  

5.  采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列  

五、主要数据结构及其说明

算法的基本概念和原理：本次课程设计主要是采用短作业优先算法进程的进程调度过程。短作业优先调度算法，是指对短作业或短进程优先调度的算法。他们可以分别用于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给他，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再度重新调度。本程序采用了非抢占式短作业优先调度。而非抢占式这种方式，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。因此，在要求比较严格的实时系统中，不宜采用这种调度方式。本课程设计主要是在满足要求多道单处理机的情况下进行短作业的优先调度。

算法的简要说明：短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。优点是SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。缺点是该算法对长作业不利；完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）长期不被调度；由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业游戏那调度。

  该程序定义了一个进程数据块(struct Process_)，该数据块有进程名(name)、到达时间(arrivetime)、服务时间(servicetime)、开始执行时间(starttime)、完成时间(finishtime)、周转时间(zztime)、带权周转时间(dqzztime)、执行顺序（order）。用到的公式有：完成时间=到达时间+服务时间；周转时间=完成时间+到达时间；带权周转时间=周转时间/服务时间；(第一次执行的进程的完成时间=该进程的到达时间；下一个进程的开始执行时间=上一个进程的完成时间)。运行进程的顺序需要对进程的到达时间和服务时间进行比较。如果某一进程是从0时刻到达的，那么首先执行该进程；之后就比较进程的服务时间，谁的服务时间短就先执行谁（如果服务时间相同则看它们的到达时间，到达时间短的先执行）；如果到达时间和服务时间相同，则按先来先服务算法执行。

六、程序运行结果

1 进入操作界面如下

2输入进程的信息

3 各时刻进程的状态

4 进程信息

5 平均带权周转时间界面

七、流程图

本次课程设计主要是通过比较各个进程的优先级以及各进程所需要占用的CPU时间来确定哪个作业优先运行，短作业优先调度算法除了能保证优先级更高的作业优先运行外，还能使相同优先级的前提下，所需CPU时间最短的那个作业优先运行，次外，本次课程设计还增加了阻塞时间和被阻塞时间来对个进程的运行加以控制。 此次课程设计的总体流程图如下：

八、源程序文件

#include

#define MaxNum 100

using namespace std;

 struct Process_struct{

    int  Number;                 //进程编号

    char Name[MaxNum];           //进程名称

    int  ArrivalTime;    //到达时间

    int  ServiceTime;    //开始运行时间

    int  FinishTime;     //运行结束时间

    int  WholeTime;      //运行时间

    int run_flag;        //调度标志

    int order;           //运行次序

    double  WeightWholeTime;        //周转时间

    double AverageWT_FCFS,AverageWT_SJF;    //平均周转时间

    double AverageWWT_FCFS,AverageWWT_SJF;  //平均带权周转时间

}Process[MaxNum];

int N;    //实际进程个数

int SJF();    //短作业优先

int SJF(){       //短作业优先算法

    int temp_time=0;    //当期那时间

    int i=0,j;

    int number_schedul,temp_counter;      //进程编号，当前已执行进程个数

    float run_time;

    run_time=Process[i].WholeTime;

    j=1;

while((j    {

     if(Process[j].WholeTime        {

            run_time=Process[i].WholeTime;

            i=j;

        }

        j++;

    }

    //查找下一个被调度的进程

        //对找到的下一个被调度的进程求相应的参数

    number_schedul=i;

    Process[number_schedul].ServiceTime=Process[number_schedul].ArrivalTime;

    Process[number_schedul].FinishTime=Process[number_schedul].ServiceTime+Process[number_schedul].WholeTime;

    Process[number_schedul].run_flag=1;

    temp_time=Process[number_schedul].FinishTime;

    Process[number_schedul].order=1;

    temp_counter=1;

while(temp_counter    {

     for(j=0;j        {

         if((Process[j].ArrivalTime<=temp_time)&&(!Process[j].run_flag))

            {

                run_time=Process[j].WholeTime;

                number_schedul=j;

                break;

            }

        }

     for(j=0;j        {

         if((Process[j].ArrivalTime<=temp_time)&&(!Process[j].run_flag))

             if(Process[j].WholeTime                {

                    run_time=Process[j].WholeTime;

                    number_schedul=j;

                }

        }

        //查找下一个被调度的进程

        //对找到的下一个被调度的进程求相应的参数

        Process[number_schedul].ServiceTime=temp_time;

        Process[number_schedul].FinishTime=Process[number_schedul].ServiceTime+Process[number_schedul].WholeTime;

        Process[number_schedul].run_flag=1;

        temp_time=Process[number_schedul].FinishTime;

        temp_counter++;

        Process[number_schedul].order=temp_counter;

    }return 0;

}

int Pinput();  //进程参数输入

int Poutput();   //调度结果输出

void main()

{

    int option;

    printf("           ********************主菜单************************\\n");

    printf("           *             1    使用短作业优先                *\\n");

    printf("           *             0    退出                          *\\n");

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

//system("cls");

    system("color 1f");

    scanf("%d",&option);

    switch(option)

    {

    case 0:

        printf("运行结束。\\n");

        break;

    case 1:

        printf("对进程用短作业优先调度。\\n\\n");

        Pinput();

        SJF();    

        Poutput();

        break;

    }

    }

int Pinput()   //进程参数输入

{

    int i;

    printf("请输入进程个数:\\n");

    scanf("%d",&N);

for(i=0;i    {

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

        printf("请输入一个进程:\\n",i+1);

        printf("请输入进程名称:\\n");

        scanf("%s",Process[i].Name);

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

        scanf("%d",&Process[i].ArrivalTime);

        printf("请输入服务时间:\\n");

        scanf("%d",&Process[i].WholeTime);

        Process[i].ServiceTime=0;

        Process[i].FinishTime=0;

        Process[i].WeightWholeTime=0;

        Process[i].order=0;

        Process[i].run_flag=0;

        system("cls");

    }return 0;

}

int Poutput()   //调度结果输出

{

    int i;

    float turn_round_time=0,f1,w=0;

    printf("      进程名称 到达T 运行T 开始运行T 结束T 执行顺序  周转T  带权周转T\\n");

for(i=0;i    {

        Process[i].WeightWholeTime=Process[i].FinishTime-Process[i].ArrivalTime;

        f1=Process[i].WeightWholeTime/Process[i].WholeTime;

        turn_round_time+=Process[i].WeightWholeTime;

        w+=f1;

        printf("时刻%d :",Process[i].ServiceTime,Process[i].Name);

        printf("   %s    %d      %d       %d       %d       %d      %f       %f\\n",Process[i].Name,Process[i].ArrivalTime,Process[i].WholeTime,Process[i].ServiceTime,Process[i].FinishTime,Process[i].order,Process[i].WeightWholeTime,f1);

    }

    printf("average_turn_round_timer=%f\\n",turn_round_time/N);

    printf("weight_average_turn_round_timer=%f\\n",w/N);

    return 0;

}

九、实验体会

通过本次课程设计，使我对计算机操作系统短作业优先调度算法这一节的知识有了更深的了解 。短作业优先调度算法易于实现，并且效率很高，但是短作业只考虑到短作业的利益，而不顾长作业，这样就可能会使得长作业一直处于等待状态而不能运行。所以，短作业优先算法适用于系统中短作业较多的情况。此外，通过本次实验，进一步巩固和复习操作系统的基础知识，更进一步的了解了结构化模块化程序设计的方法，提高了调试程序的技巧，提高了自己的动手能力我对操作系统中的作业调度模拟和短作业优先算法有了更深的认识。并且发现，只看课本上的知识远远不够，只一味学习也根本没用，必须要动手亲自实践，才能真正掌握所学的东西。  虽然在这次课程设计过程中，我们也遇到了很多问题，但我们都能保持一个良好的心态，不急不躁，并且能通过请教老师，与同学们积极讨论，查看课外资料，反复实验，反复检查，将问题一个个解答，并最终成功的完成本次课程设计。课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去做一件事情，又如何完成一件事情的能力。 

通过模拟进程的调度问题，更加深了我对于操作系统理论的理解，在自己的动手操作过程中，能够体会成功的喜悦和遇到问题自己解决的能力，对于我来说是一次提高，让自己多多的在实践中可以加深对理论的理解，也让我明白了以后应该如何更好，更高效的学习，在以后，我会更加努力。

总之，本次课程设计让我们学到了很多东西，包括课本上的和课外的，是一个非常有意义的课程设计。

十、参考文献

1）宗大华，宗涛，陈吉人著  操作系统  北京：人民邮电出版社，2009

     2）李爱华，程磊著  面相对象程序设计（C++语言） 北京: 清华大学出版社，2010

     3）宋晓宇 ， windows操作系统核心编程实验教程  中国铁道出版社

     4）张丽芬 刘利雄 王金玉编著  操作系统实验教程  清华大学出版社下载本文