常用作业调度算法的分析
2014-07-16雷华军王慧娟
雷华军 王慧娟
摘要：作业管理、作业调度是操作系统的重要课题，该文讨论了先来先服务作业调度算法、短作业优先调度算法、最高响应比优先调度算法等常用作业调度算法的基本思想，并结合实例进行了分析和评价。
关键词： 作业调度算法；先来先服务（FCFS）；短作业优先（SJF）；最高响应比优先（HRN）；平均周转时间
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）14-3212-02
Abstract： Job management and job scheduling is an important issue of the operating systems，this paper discusses the basic idea of the Common job scheduling algorithms including FCFS， SJF and HRN， and algorithms are analyzed and evaluated Combining with the instance.
Key words： job scheduling algorithm； First Come First Serve（FCFS）； Shortest Job First（SJF）； Highest Response-ratio Next（HRN）； average turnaround time
1 作业调度算法基础
在操作系统中，处理机的调度工作分成作业调度和进程调度。作业调度是根据作业控制块（JCB）信息，从后备作业队列中挑选哪些作业进入内存，并为它们创建进程，分配资源。进程调度是进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程。作业调度算法是作业调度中采用的某种规则、策略。
2 衡量算法的标准
2.1 CPU利用率
在多道程序设计环境下，CPU资源有限，尽可能让CPU满负荷工作，CPU利用率=CPU有效工作时间∕CPU总的运行时间。
2.2 系统的吞吐量
吞吐量是系统单位时间完成作业的多少，系统的吞吐量越高，系统单位时间内完成的作业数越多，说明系统采用的作业调度算法效率高，系统资源得到充分利用。对于系统来说，好的是调度算法能提高处理机的利用率，能够平衡使用系统的各类资源。
2.3 响应时间
响应时间，是指用户从提交第一个请求到产生第一个响应所用的时间。从用户的角度看，每个用户都希望自己的作业响应时间短，作业能够得到及时反映处理。
2.4 等待时间
等待时间是指作业从提交到开始运行的时间间隔。从用户的角度看，都希望自己作业的等待时间最短，对于系统来说平均等待时间越小，说明系统效率高。
2.5 周转时间
周转时间指作业从提交到完成的时间间隔。就整个系统而言，主要是考虑其平均周转时间。如果作业j提交给系统、进入输入井时间点为Sj，其运行完成、得到结果的时间点为Wj，则该作业的周转时间Tj为Tj=Wj?Sj，对于一批n个作业而言，它们的平均周转时间T为T=（T1+T2+…+Tn）/n。平均周转时间越短，系统的效率就越高，这能使多数用户感到满意。
3 常用作业调度算法的分析
3.1 先来先服务（First Come First Serve）调度算法
先来先服务调度算法的基本思想是，优先从后备队列中，选择队列头部的作业，把他们调入内存，投入运行，分配所需资源。该算法看起来对每个作业都是公平的。但是，当长作业排在后备作业队列前面时，排在它后面的短作业就会等待很久，所以该算法有利于长作业，不利于短作业，这样FCFS算法会使一批作业的平均周转时间变长。另外，该算法有利于CPU繁忙的作业，而不利于I/O繁忙的作业。现在先来先服务调度算法，一般与其他调度算法结合在一起使用，很少单独用作主要调度算法使用，尤其是在分时系统和实时系统中。
3.2 短作业优先（Shortest Job First）调度算法
短作业优先调度算法的基本思想是，作业调度程序总是从后备作业队列中选择预计运行时间少且内存能满足其需求的作业投入运行。
从系统的角度分析，短作业优先能使系统在同一时间段内完成更多的作业，能有效缩短平均等待时间，改善平均周转时间，提高系统的吞吐量。但是，从用户的角度分析，系统总是优先考虑调度短作业，如果不断有短作业进入后备作业队列，长作业将一直处于等待状态，这样对长作业的用户不公平。此外，该算法未能依据作业的紧迫程度来划分执行的优先级，难以保证紧迫性作业能够及时优先处理。
3.3最高响应比优先（Highest Response-ratio Next）调度算法
最高响应比优先调度算法同时考虑每个作业的等待时间和预计运行时间的长短，从中选出响应比最高的作业投入执行。当一个作业执行完成时，通过重新计算后备队列中每个作业的响应比来决定哪个作业被选中进入内存。
响应比定义为：响应比=1+已等待时间∕预计运行时间。
在该算法中，对于短作业，预计运行时间少，容易获得较高的响应比。对于长作业，随着等待时间的增加，响应比也相应的会增加，当增加到足够大时，就有机会获得CPU资源。所以，最高响应比优先调度算法，既考虑了短作业的利益，又考虑了长作业的利益，是FCFS和SJF折中的作业调度算法。由于每次调度前需要重新计算后备作业队列中作业的响应比，这样增加了系统开销。
4 举例分析
例如有四个作业 A，B，C，D，它们提交系统、进入输入井的时刻分别为6.0，6.5，7.0，7.5 （单位小时），估计执行时间分别为2.0，0.5，0.1，0.2（单位小时），现分别按三种调度算法调度，具体情况如表 1所示。
根据表 1做如下分析：采用最高响应比优先调度算法时，在作业A完成时，B、C、D的响应比分别为：4、11、3.5，所以作业C其次被选中，在C完成时，B、D的响应比分别为：4.2、4，所以作业B被选中，作业D最后被选中。在三种调度算法中 FCFS算法平均周转时间最长；SJF算法平均周转时间最短，有最大的系统吞吐量；HRN算法兼顾了长作业和短作业，是 FCFS和SJF之间的一种较好的折中。
5 结束语
综上所述，该文详细地分析了先来先服务调度算法、短作业优先调度算法、最高响应比优先调度算法等三种作业调度算法的基本思想和算法的优缺点，并通过实例进行分析、对比。在实际应用中我们通常要根据系统设计目标的不同而采取不同的调度算法，这就要求算法既要顾及用户的需要，又要充分提高系统效率。在确定采用作业调度算法时，应注意考虑以下目标：
1）合理公平的对待每一个作业，兼顾每个作业的利益。
2）尽量让CPU和I/O设备并行工作，始终处于忙碌状态，提高系统的利用率。
3）单位时间内为尽可能运行多的作业，提高整个系统的作业吞吐量。
参考文献：
[1] 宗大华，宗涛，陈吉人.操作系统[M].3版.北京：人民邮电出版社，2011：38-49.
[2] 崔帅，楚蓝天，高凯.作业调度算法[J].科技向导，2011（17）：110.
摘要：作业管理、作业调度是操作系统的重要课题，该文讨论了先来先服务作业调度算法、短作业优先调度算法、最高响应比优先调度算法等常用作业调度算法的基本思想，并结合实例进行了分析和评价。
关键词： 作业调度算法；先来先服务（FCFS）；短作业优先（SJF）；最高响应比优先（HRN）；平均周转时间
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）14-3212-02
Abstract： Job management and job scheduling is an important issue of the operating systems，this paper discusses the basic idea of the Common job scheduling algorithms including FCFS， SJF and HRN， and algorithms are analyzed and evaluated Combining with the instance.
Key words： job scheduling algorithm； First Come First Serve（FCFS）； Shortest Job First（SJF）； Highest Response-ratio Next（HRN）； average turnaround time
1 作业调度算法基础
在操作系统中，处理机的调度工作分成作业调度和进程调度。作业调度是根据作业控制块（JCB）信息，从后备作业队列中挑选哪些作业进入内存，并为它们创建进程，分配资源。进程调度是进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程。作业调度算法是作业调度中采用的某种规则、策略。
2 衡量算法的标准
2.1 CPU利用率
在多道程序设计环境下，CPU资源有限，尽可能让CPU满负荷工作，CPU利用率=CPU有效工作时间∕CPU总的运行时间。
2.2 系统的吞吐量
吞吐量是系统单位时间完成作业的多少，系统的吞吐量越高，系统单位时间内完成的作业数越多，说明系统采用的作业调度算法效率高，系统资源得到充分利用。对于系统来说，好的是调度算法能提高处理机的利用率，能够平衡使用系统的各类资源。
2.3 响应时间
响应时间，是指用户从提交第一个请求到产生第一个响应所用的时间。从用户的角度看，每个用户都希望自己的作业响应时间短，作业能够得到及时反映处理。
2.4 等待时间
等待时间是指作业从提交到开始运行的时间间隔。从用户的角度看，都希望自己作业的等待时间最短，对于系统来说平均等待时间越小，说明系统效率高。
2.5 周转时间
周转时间指作业从提交到完成的时间间隔。就整个系统而言，主要是考虑其平均周转时间。如果作业j提交给系统、进入输入井时间点为Sj，其运行完成、得到结果的时间点为Wj，则该作业的周转时间Tj为Tj=Wj?Sj，对于一批n个作业而言，它们的平均周转时间T为T=（T1+T2+…+Tn）/n。平均周转时间越短，系统的效率就越高，这能使多数用户感到满意。
3 常用作业调度算法的分析
3.1 先来先服务（First Come First Serve）调度算法
先来先服务调度算法的基本思想是，优先从后备队列中，选择队列头部的作业，把他们调入内存，投入运行，分配所需资源。该算法看起来对每个作业都是公平的。但是，当长作业排在后备作业队列前面时，排在它后面的短作业就会等待很久，所以该算法有利于长作业，不利于短作业，这样FCFS算法会使一批作业的平均周转时间变长。另外，该算法有利于CPU繁忙的作业，而不利于I/O繁忙的作业。现在先来先服务调度算法，一般与其他调度算法结合在一起使用，很少单独用作主要调度算法使用，尤其是在分时系统和实时系统中。
3.2 短作业优先（Shortest Job First）调度算法
短作业优先调度算法的基本思想是，作业调度程序总是从后备作业队列中选择预计运行时间少且内存能满足其需求的作业投入运行。
从系统的角度分析，短作业优先能使系统在同一时间段内完成更多的作业，能有效缩短平均等待时间，改善平均周转时间，提高系统的吞吐量。但是，从用户的角度分析，系统总是优先考虑调度短作业，如果不断有短作业进入后备作业队列，长作业将一直处于等待状态，这样对长作业的用户不公平。此外，该算法未能依据作业的紧迫程度来划分执行的优先级，难以保证紧迫性作业能够及时优先处理。
3.3最高响应比优先（Highest Response-ratio Next）调度算法
最高响应比优先调度算法同时考虑每个作业的等待时间和预计运行时间的长短，从中选出响应比最高的作业投入执行。当一个作业执行完成时，通过重新计算后备队列中每个作业的响应比来决定哪个作业被选中进入内存。
响应比定义为：响应比=1+已等待时间∕预计运行时间。
在该算法中，对于短作业，预计运行时间少，容易获得较高的响应比。对于长作业，随着等待时间的增加，响应比也相应的会增加，当增加到足够大时，就有机会获得CPU资源。所以，最高响应比优先调度算法，既考虑了短作业的利益，又考虑了长作业的利益，是FCFS和SJF折中的作业调度算法。由于每次调度前需要重新计算后备作业队列中作业的响应比，这样增加了系统开销。
4 举例分析
例如有四个作业 A，B，C，D，它们提交系统、进入输入井的时刻分别为6.0，6.5，7.0，7.5 （单位小时），估计执行时间分别为2.0，0.5，0.1，0.2（单位小时），现分别按三种调度算法调度，具体情况如表 1所示。
根据表 1做如下分析：采用最高响应比优先调度算法时，在作业A完成时，B、C、D的响应比分别为：4、11、3.5，所以作业C其次被选中，在C完成时，B、D的响应比分别为：4.2、4，所以作业B被选中，作业D最后被选中。在三种调度算法中 FCFS算法平均周转时间最长；SJF算法平均周转时间最短，有最大的系统吞吐量；HRN算法兼顾了长作业和短作业，是 FCFS和SJF之间的一种较好的折中。
5 结束语
综上所述，该文详细地分析了先来先服务调度算法、短作业优先调度算法、最高响应比优先调度算法等三种作业调度算法的基本思想和算法的优缺点，并通过实例进行分析、对比。在实际应用中我们通常要根据系统设计目标的不同而采取不同的调度算法，这就要求算法既要顾及用户的需要，又要充分提高系统效率。在确定采用作业调度算法时，应注意考虑以下目标：
1）合理公平的对待每一个作业，兼顾每个作业的利益。
2）尽量让CPU和I/O设备并行工作，始终处于忙碌状态，提高系统的利用率。
3）单位时间内为尽可能运行多的作业，提高整个系统的作业吞吐量。
参考文献：
[1] 宗大华，宗涛，陈吉人.操作系统[M].3版.北京：人民邮电出版社，2011：38-49.
[2] 崔帅，楚蓝天，高凯.作业调度算法[J].科技向导，2011（17）：110.
摘要：作业管理、作业调度是操作系统的重要课题，该文讨论了先来先服务作业调度算法、短作业优先调度算法、最高响应比优先调度算法等常用作业调度算法的基本思想，并结合实例进行了分析和评价。
关键词： 作业调度算法；先来先服务（FCFS）；短作业优先（SJF）；最高响应比优先（HRN）；平均周转时间
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）14-3212-02
Abstract： Job management and job scheduling is an important issue of the operating systems，this paper discusses the basic idea of the Common job scheduling algorithms including FCFS， SJF and HRN， and algorithms are analyzed and evaluated Combining with the instance.
Key words： job scheduling algorithm； First Come First Serve（FCFS）； Shortest Job First（SJF）； Highest Response-ratio Next（HRN）； average turnaround time
1 作业调度算法基础
在操作系统中，处理机的调度工作分成作业调度和进程调度。作业调度是根据作业控制块（JCB）信息，从后备作业队列中挑选哪些作业进入内存，并为它们创建进程，分配资源。进程调度是进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程。作业调度算法是作业调度中采用的某种规则、策略。
2 衡量算法的标准
2.1 CPU利用率
在多道程序设计环境下，CPU资源有限，尽可能让CPU满负荷工作，CPU利用率=CPU有效工作时间∕CPU总的运行时间。
2.2 系统的吞吐量
吞吐量是系统单位时间完成作业的多少，系统的吞吐量越高，系统单位时间内完成的作业数越多，说明系统采用的作业调度算法效率高，系统资源得到充分利用。对于系统来说，好的是调度算法能提高处理机的利用率，能够平衡使用系统的各类资源。
2.3 响应时间
响应时间，是指用户从提交第一个请求到产生第一个响应所用的时间。从用户的角度看，每个用户都希望自己的作业响应时间短，作业能够得到及时反映处理。
2.4 等待时间
等待时间是指作业从提交到开始运行的时间间隔。从用户的角度看，都希望自己作业的等待时间最短，对于系统来说平均等待时间越小，说明系统效率高。
2.5 周转时间
周转时间指作业从提交到完成的时间间隔。就整个系统而言，主要是考虑其平均周转时间。如果作业j提交给系统、进入输入井时间点为Sj，其运行完成、得到结果的时间点为Wj，则该作业的周转时间Tj为Tj=Wj?Sj，对于一批n个作业而言，它们的平均周转时间T为T=（T1+T2+…+Tn）/n。平均周转时间越短，系统的效率就越高，这能使多数用户感到满意。
3 常用作业调度算法的分析
3.1 先来先服务（First Come First Serve）调度算法
先来先服务调度算法的基本思想是，优先从后备队列中，选择队列头部的作业，把他们调入内存，投入运行，分配所需资源。该算法看起来对每个作业都是公平的。但是，当长作业排在后备作业队列前面时，排在它后面的短作业就会等待很久，所以该算法有利于长作业，不利于短作业，这样FCFS算法会使一批作业的平均周转时间变长。另外，该算法有利于CPU繁忙的作业，而不利于I/O繁忙的作业。现在先来先服务调度算法，一般与其他调度算法结合在一起使用，很少单独用作主要调度算法使用，尤其是在分时系统和实时系统中。
3.2 短作业优先（Shortest Job First）调度算法
短作业优先调度算法的基本思想是，作业调度程序总是从后备作业队列中选择预计运行时间少且内存能满足其需求的作业投入运行。
从系统的角度分析，短作业优先能使系统在同一时间段内完成更多的作业，能有效缩短平均等待时间，改善平均周转时间，提高系统的吞吐量。但是，从用户的角度分析，系统总是优先考虑调度短作业，如果不断有短作业进入后备作业队列，长作业将一直处于等待状态，这样对长作业的用户不公平。此外，该算法未能依据作业的紧迫程度来划分执行的优先级，难以保证紧迫性作业能够及时优先处理。
3.3最高响应比优先（Highest Response-ratio Next）调度算法
最高响应比优先调度算法同时考虑每个作业的等待时间和预计运行时间的长短，从中选出响应比最高的作业投入执行。当一个作业执行完成时，通过重新计算后备队列中每个作业的响应比来决定哪个作业被选中进入内存。
响应比定义为：响应比=1+已等待时间∕预计运行时间。
在该算法中，对于短作业，预计运行时间少，容易获得较高的响应比。对于长作业，随着等待时间的增加，响应比也相应的会增加，当增加到足够大时，就有机会获得CPU资源。所以，最高响应比优先调度算法，既考虑了短作业的利益，又考虑了长作业的利益，是FCFS和SJF折中的作业调度算法。由于每次调度前需要重新计算后备作业队列中作业的响应比，这样增加了系统开销。
4 举例分析
例如有四个作业 A，B，C，D，它们提交系统、进入输入井的时刻分别为6.0，6.5，7.0，7.5 （单位小时），估计执行时间分别为2.0，0.5，0.1，0.2（单位小时），现分别按三种调度算法调度，具体情况如表 1所示。
根据表 1做如下分析：采用最高响应比优先调度算法时，在作业A完成时，B、C、D的响应比分别为：4、11、3.5，所以作业C其次被选中，在C完成时，B、D的响应比分别为：4.2、4，所以作业B被选中，作业D最后被选中。在三种调度算法中 FCFS算法平均周转时间最长；SJF算法平均周转时间最短，有最大的系统吞吐量；HRN算法兼顾了长作业和短作业，是 FCFS和SJF之间的一种较好的折中。
5 结束语
综上所述，该文详细地分析了先来先服务调度算法、短作业优先调度算法、最高响应比优先调度算法等三种作业调度算法的基本思想和算法的优缺点，并通过实例进行分析、对比。在实际应用中我们通常要根据系统设计目标的不同而采取不同的调度算法，这就要求算法既要顾及用户的需要，又要充分提高系统效率。在确定采用作业调度算法时，应注意考虑以下目标：
1）合理公平的对待每一个作业，兼顾每个作业的利益。
2）尽量让CPU和I/O设备并行工作，始终处于忙碌状态，提高系统的利用率。
3）单位时间内为尽可能运行多的作业，提高整个系统的作业吞吐量。
参考文献：
[1] 宗大华，宗涛，陈吉人.操作系统[M].3版.北京：人民邮电出版社，2011：38-49.
[2] 崔帅，楚蓝天，高凯.作业调度算法[J].科技向导，2011（17）：110.
