作业调度算法模拟

一、课题内容和要求

   常见的作业调度算法有先来先服务算法、最短作业优先算法、响应比优先调度算法。

(1) 参考操作系统教材理解这3种算法。

(2) 实现这3个算法。

(3) 已知若干作业的到达时间和服务时间，用实现的算法计算对该组作业进行调度的平均周转时间Ttime和平均带权周转时间WTtime。

(4) 作业的到达时间和服务时间可以存放在文本文件record.txt中。

(5) 设计简单的交互界面，演示所设计的功能。(可以使用MFC进行界面的设计)

（6）可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。

二、需求分析

    模拟实现作业调度算法，包括：FCFS（先来先服务算法）、SJF（短作业优先算法）、HRN（最高响应比优先算法）、HPF（基于优先数调度算法）。

先来先服务算法：按照各个作业进入系统（输入井）的自然次序来调度算法。

短作业优先算法：优先调度并处理短作业。所谓的“短作业”并不是指物理作业                                                                                                                                                         长度短，而是指作业的运行时间短。

最高响应比优先算法：优先调度并处理响应比最高的作业。

三、概要设计

函数中一些类：

                              

主要功能函数的流程图

2、先来先服务：

                                

  3、最短作业优先：                          

4、最高响应比：

四、详细设计

1、程序代码

MFC头文件a.h内容：

const int defMaxJobNumber = 10;   //作业数量的最大值

class Time   //时间类

{

public:

            int hour;

            int minute;

};

class Job   //作业类

{

public:

            int ID;   //作业编号

            Time enter;   //进入时间

            int requesttime;   //估计运行时间

            int priority;   //优先数

            Time start;   //开始时间

            Time end;   //结束时间

            int Ttime;   //周转时间

            double WTtime;   //带权周转时间

};

class schedule   //调度类

{

public:

            int size;   //作业数

            Job *job;   //作业数组

            int *r;   //排序用数组

       int Differ(Time t1,Time t2)   //求两个时刻间的时间差t2-t1

            {

                        int borrow = (t2.minute

                        return ((t2.hour-t1.hour-borrow)*60+(borrow*60+t2.minute-t1.minute));

            }

public:

            schedule()   //构造函数

            {

                        size = 0;

         job = new Job[defMaxJobNumber];        

            r = new int[defMaxJobNumber-1];

            }

            void readFile()   //从文件读信息

            {

                        ifstream txtfile;

                        txtfile.open("record.txt");

                        int i = 0;

                        int entertime;

                        while(!txtfile.eof())

                        {

                                    txtfile＞＞job[i].ID＞＞entertime＞＞job[i].requesttime＞＞job[i].priority;

                                    job[i].enter.hour = entertime / 100;      //取小时

                                    job[i].enter.minute = entertime % 100;   //取分钟

                                    i++;

                                    size++;

                        }

                        txtfile.close();

         }

            void FCFS()   //先来先服务(First Come First Serve)

            {

                        int hour,minute,carry;

                        job[0].start = job[0].enter;

                        hour = job[0].requesttime / 60;

                        minute = job[0].requesttime % 60;

                        job[0].end.minute = (job[0].start.minute + minute) % 60;

                        carry = (job[0].start.minute + minute) / 60;          //carry是分钟累积超过60商

                        job[0].end.hour = job[0].start.hour + hour + carry;

                        job[0].Ttime = job[0].requesttime;

                        job[0].WTtime = ((double)job[0].Ttime) / job[0].requesttime;

                        for(int i=1;i

                        {

                                    job[i].start = job[i-1].end;

                                    hour = job[i].requesttime / 60;

                                    minute = job[i].requesttime % 60;

                                    job[i].end.minute = (job[i].start.minute + minute) % 60;

                                    carry = (job[i].start.minute + minute) / 60;

                                    job[i].end.hour = job[i].start.hour + hour + carry;

                                    job[i].Ttime = Differ(job[i].enter,job[i].end);      //周转时间

                                    job[i].WTtime = ((double)job[i].Ttime) / job[i].requesttime; //带权周转时间

                        }

            }

       void SJF()   //短作业优先(Shortest Job First)

            {

                        int hour,minute,carry;

                        job[0].start = job[0].enter;

                        hour = job[0].requesttime / 60;

                        minute = job[0].requesttime % 60;

                        job[0].end.minute = (job[0].start.minute + minute) % 60;

                        carry = (job[0].start.minute + minute) / 60;      //carry是分钟累积超过60的商

                        job[0].end.hour = job[0].start.hour + hour + carry;

                        job[0].Ttime = job[0].requesttime;               //周转时间

                        job[0].WTtime = ((double)job[0].Ttime) / job[0].requesttime;  //带权周转时间

              for(int i=1;i

                                    r[i] = i;

                        for(i=1;i

                        {

                                    int index = i;

                                    for(int j=i+1;j

                                                if(job[r[j]].requesttime

                                                            index = j;

                                    if(index!=i)

                                    {

                                                int w = r[i];

                                                r[i] = r[index];

                                                r[index] = w;

                                    }

                        }

              int dest=0;

                        for(i=1;i

                        {

                                    int index = r[i];

                                    job[index].start = job[dest].end;

                                    hour = job[index].requesttime / 60;

                                    minute = job[index].requesttime % 60;

                                    job[index].end.minute = (job[index].start.minute + minute) % 60;

                                    carry = (job[index].start.minute + minute) / 60;

                                    job[index].end.hour = job[index].start.hour + hour + carry;

                                    job[index].Ttime = Differ(job[index].enter,job[index].end);

                                    job[index].WTtime = ((double)job[index].Ttime) / job[index].requesttime;

                                    dest = index;

                        }

            }

            void HRN()   //最高响应比优先(Highest Response_ratio Next)

            {

                        int hour,minute,carry;

                        job[0].start = job[0].enter;

                        hour = job[0].requesttime / 60;

                        minute = job[0].requesttime % 60;

                        job[0].end.minute = (job[0].start.minute + minute) % 60;

                        carry = (job[0].start.minute + minute) / 60;    //carry是分钟累积超过60的商

                        job[0].end.hour = job[0].start.hour + hour + carry;

                        job[0].Ttime = job[0].requesttime;           //周转时间

                        job[0].WTtime = ((double)job[0].Ttime) / job[0].requesttime;  带权周转时间

                        int dest=0;

                        for(int i=1;i

                                    r[i] = i;

                        for(i=1;i

                        {

                                    int index = i;

                                    for(int j=i+1;j

                                                if(((double)Differ(job[r[j]].enter,job[dest].end))/job[r[j]].requesttime＞

                                                            ((double)Differ(job[r[index]].enter,job[dest].end))/job[r[index]].requesttime)                                                                                              //响应比=作业周转时间/作业处理时间

                                                            index = j;

                                    if(index!=i)

                                    {

                                                int w = r[i];

                                                r[i] = r[index];

                                                r[index] = w;

                                    }

                   //按排序后的作业序继续执行

                                    index = r[i];

                                    job[index].start = job[dest].end;

                                    hour = job[index].requesttime / 60;

                                    minute = job[index].requesttime % 60;

                                    job[index].end.minute = (job[index].start.minute + minute) % 60;

                                    carry = (job[index].start.minute + minute) / 60;

                                    job[index].end.hour = job[index].start.hour + hour + carry;

                                    job[index].Ttime = Differ(job[index].enter,job[index].end);

                                    job[index].WTtime = ((double)job[index].Ttime) / job[index].requesttime;

                                    dest = index;

                        }

            }

};

五、测试数据及其结果分析

   

从文本文件中读取数据（书上的例子）：

1 800 120 2

2 850 50 3

3 900 10 1

4 950 20 4

输出的平均周转时间、平均带权周转时间结果正确。

六、调试过程中的问题

    调试过程中，对于MFC里面许多函数不熟悉，所以经常编译失败，我通过老师的帮助以及上网查询解决方法来不断修改错误，完善代码。这个程序没有考虑一些特殊情况，如：若有作业5的到达时间为11：10，执行时间是5分钟，则是否先于其它作业调入内存执行。

七、参考文献和查阅的资料

    （1）黄刚、徐小龙、段卫华 《操作系统教程》 人民邮电出版社

（2）陈向群、杨芙清  《操作系统教程》  北京大学出版社

（3）沈显君、杨进才、张勇  《C++语言程序设计教程》  清华大学出版社

八、程序设计总结

 1、首先要学会打开一个MFC文件，打开VC环境左上角“文件”--＞“打开工作空间”，搜寻文件夹里面的.daw文件，直接打开就行。

2、在以往的程序设计实验中我一直都只能局限于DOS界面，这次在老师的帮助下我终于摆脱了编程的黑框框，进入了图形界面设计，对与我来是这是我编程领域的一个新的开始，对MFC简单操作的了解是我这次实验最大的收获。

3、进一步加深了对作业调度的理解，基本掌握了批处理作业调度算法的核心思想。同时，加强了自己的算法设计能力和编码能力。