操作系统中常用作业调度算法的分析
来源:用户上传
作者:
摘要：本文把案例教学方法应用在操作系统作业调度算法中，并对常用作业调度算法中的先来先服务调度算法、短作业优先调度算法和最高响应比优先调度算法以案例的形式做了对比，并对这三种算法进行了分析和评价。此教学方法把抽象的内容融入案例中，循序渐进、能够有效地调动学生的学习积极性和学习的主动性及热情。
关键词：操作系统;作业调度;最高响应比
中图分类号：TN402 文献标识码：A
文章编号：1009-3044（2019）18-0269-02
Abstract： This paper applies the case teaching method to the operating system job scheduling algorithm， and compares the first-come-first service scheduling algorithm， the short job priority scheduling algorithm and the highest response ratio priority scheduling algorithm in the common job scheduling algorithm. And the three algorithms were analyzed and evaluated. This teaching method integrates the abstract content into the case， step by step， and can effectively mobilize the students' enthusiasm for learning and the initiative and enthusiasm of learning.
Key words： operating system; job scheduling; highest response ratio
1 引言
“操作系統”这门课程属于理论性强，十分抽象，知识点琐碎，不好理解的一门计算机专业的专业课程。学生学习起来枯燥，老师讲解也增加了难度。如何提高学生的学习兴趣，激发学生的学习热情，使学生能更好地掌握这门课程成为各大学校老师们关注的问题。本文以案例的方式讲授作业调度，使学生能够直观的理解作业调度算法。常见的作业调度算法有：先来先服务调度算法（FCFS）、多作业优先调度算法（SJF）和最高响应比优先调度算法（HRRN）。
2 作业调度的主要任务
作业调度就是按一定的算法从后备队列中选择一个作业送入内存执行，并在作业完成后处理善后工作的过程。作业调度的工作主要由作业调度程序来完成。作业调度的任务有：
1）记录进入系统的各个作业情况，作业一旦进入系统，系统即为该作业分配作业控制块JCB。
2）从后备作业中挑选一些作业投入运行。一般而论，系统中后备状态作业较多，而在CPU中运行的不能很多，这就要求作业调度程序必须按规定的调度策略来选择若干作业进入运行状态。
3）为选中的作业做执行准备。作业从后备状态进入执行状态，需要建立相应的进程，分配进程所需的内存资源、外设资源，这些都交给调度程序。
4）善后工作处理。当作业因某种原因退出或执行完毕后，作业调度程序回收作业原先占用的资源，撤销进程及JCB，并输出结果。
3 常用作业调度算法
（1）FCFS算法
FCFS是最简单的调度算法，每次从就绪的队列中选择一个最先进入该队列的进程，分配处理机，运行进程。该进程直到运行完成或者阻塞，才让出处理机为其他进程服务。
（2）SJF 算法
该算法以作业运行时间为衡量标准，从所有作业中选取一个运行时间最短的作业，优先为它们创建进程和分配资源。
（3）HRRN算法
HRRN算法是FCFS和SJF的结合，克服了两种算法的缺点，该算法既考虑了作业的等待时间，又考虑了作业的运行时间。
周转时间=完成时间—提交时间带权周转时间=周转时间/运行时间响应比=（作业等待时间+作业运行时间）/作业运行时间=1+作业的等待时间/作业运行时间
4 三种算法案例对比
假设在单CPU环境下，作业提交时间及运行时间情况如下表所示：
[作业号 提交时间 运行时间（h） J1 1：00 2 J2 2：00 1.5 J3 2：30 0.5 J4 3：00 1 ]
（1） FCFS算法作业执行情况
[作业号 提交时间 运行时间（h） 开始时间 完成时间 周转时间（h） 带权周转时间 J1 1：00 2.0 1：00 3：00 2 1 J2 2：00 1.5 3：00 4：30 2.5 5/3 J3 2：30 0.5 4：30 5：00 2.5 5 J4 3：00 1.0 5：00 6：00 3.0 3 运行先后次序 1 2 3 4 平均周转时间T （2+2.5+2.5+3.0）/4=2.5 平均带权周转时间W （1+5/3+5+3）/4≈2.67 ]
当时间在1：00时，仅有作业1运行。当作业1在3：00时刻运行结束，此时，作业2、3、4全部到达内存，按照先来后到的原则，所以作业的运行次序为1、2、3、4。
（2） SJF算法执行情况
[作业号 提交时间 运行时间（h） 开始时间 完成时间 周转时间（h） 带权周转时间 J1 1：00 2.0 1：00 3：00 2 1 J2 2：00 1.5 4：30 6：00 4 8/3 J3 2：30 0.5 3：00 3：30 1 2 J4 3：00 1.0 3：30 4：30 1.5 1.5 运行先后次序 1 3 4 2 平均周转时间T （2+4+1+1.5）/4=2.125 平均带权周转时间W （1+8/3+2+1.5）/4≈1.79 ] 当时间在1：00时，仅有作业1运行。当作业1在3：00时刻运行结束，此时，作业2、3、4全部到达内存，按照短作业优先调度算法，由于作业3的运行时间最短，所以优先运行作业3，然后运行作业4和作业2。所以作业的运行次序为1、3、4、2。
（3） HRRN算法执行情况
5 三种算法性能评价
1）从实例分析来看FCFS算法，实现较为简单，但是只考虑了长作业，没有考虑短作业，此算法不利于短作业的运行。
2）同FCFS算法相比，SJF算法也易于实现，强调了资源的充分利用，保证了系统的最大吞吐量（单位时间里处理作业的个数），具有较短的平均周转时间和平均带权周转时间。但该算法对长作业不利，长作业往往得不到及时处理。
3）HRRN算法结合了FCFS算法和SJF算法，相对公平，系统的吞吐率增大。从实例中可以看出：
（1）如果作业的等待时间相同，则作业估计运行的时间愈短，其优先权愈高，因而该算法有利于短作业;
（2）当作业估计运行时间相同时，作业的优先权决定于其等待时间，因而实现了先来先服务;
（3）对于长作业，当其等待时间足够长时，其优先权便可升到很高，从而也可获得处理机，从而也避免了长作业长期等待这种现象的发生。
但HRRN算法每次都要计算作业的响应比，所以增大了系统的开销。
6 结语
对于讲授操作系统课程的老师来说，这种讲授方法言簡意赅，对于操作系统的学习者来说，采用案例的方式，把抽象的内容融入案例中，循序渐进、调动学生的学习积极性和学习的主动性及热情，实践表明此方法教学效果良好，深得学生好评。
参考文献：
[1]汤小丹等.计算机操作系统（第4版）[M].西安：西安电子科技大学出版社，2014：95-98.
[2]张尧学，史美林.计算机操作系统教程[M].北京：清华大学出版社，1993：83-87.
[3] 汤敏丽. “互联网+”环境下的《操作系统》课程教学改革探索——以凯里学院为例[J]. 凯里学院学报，2017（06）.
[4] 余久久. 基于MOOC的“软件工程”自主学习系统的设计与实现[J].西昌学院学报（自然科学版），2016（04）.
【通联编辑：王力】
转载注明来源:https://www.xzbu.com/8/view-14949927.htm
