时间轴法在操作系统作业调度算法教学中的应用

陈永丽陈美婕张光明王大为

（1.山西师范大学数学与计算机科学学院，山西 临汾 04100；2.重庆工商大学继续教育学院，重庆 400030；3.山西师范大学物理与信息工程学院，山西 临汾 041000）

时间轴法在操作系统作业调度算法教学中的应用

陈永丽1陈美婕2张光明3王大为3

（1.山西师范大学数学与计算机科学学院，山西 临汾 04100；2.重庆工商大学继续教育学院，重庆 400030；3.山西师范大学物理与信息工程学院，山西 临汾 041000）

针对操作系统中的作业调度算法在教学过程中存在的模糊性、难理解性等问题，引入时间轴法，以“先来先服务算法”和“计算时间短的作业优先算法”为例，对“时间轴法”在作业调度教学中的应用作了介绍，以时间演进顺序分析了何时存在资源竞争、需要采用调度算法进行资源分配，在教学实践中取得了显著的效果。

操作系统；作业调度；工程教学

1 引言

操作系统是管理计算机系统资源、控制程序执行、改善人机界面和为应用软件提供支持的一种系统软件，是计算机及其应用专业的重要教学内容[1,2]。同时，操作系统也是计算机及其相关专业课程教学中较难的课程[3,4]。尤其是其中的作业调度算法，当涉及到作业的随机退出与随机接入时，算法的理解难度大大增加，给教学和学生理解等都带来了一定的困扰。

时间轴是描述事物状态变化的有效方法。尤其是对于可用资源动态变化的问题，能够形象而准确地描述资源的分配与回收过程。本文将“时间轴法”应用于作业调度算法的教学，取得了较好的反响。

2 作业调度问题的描述

2.1 基本问题的描述

在多道程序设计系统中，允许同时将多个作业同时调入到计算机系统的主存储器并执行[5]。作业的执行分为两级：一级是作业调度，主要完成作业执行所需资源的分配，包括内存、外设等资源的分配；第二级是进程调度，主要是处理器使用权的分配，包括分配给哪个作业，使用多长时间等。在操作系统中，磁盘上用来存放作业信息的专门区域称之为输入井，而存放在其中的作业称之为后备作业。作业调度主要是完成将后备作业调入主存储器的过程。

2.2 作业调度应考虑的原则

从单个作业的角度，每一个作业都希望自己的作业能尽快地执行。但从计算机整体效益的角度来说，既应该考虑用户的要求，又要有利于系统整体效益的提高。因而，在设计调度算法时应该考虑如下原则[5]：

(1)公平性：不能让某个用户无限制地等下去，保证对各用户的公平性；

(2)资源的平衡使用：要尽可能地平衡资源的使用，使系统资源都处于忙碌状态；

(3)最大化吞吐量：要使单位时间内，系统服务的作业量尽可能多，保证系统的吞吐量。

对于不同的计算机系统应根据系统的设计目标来选择相应的调度算法。理想的算法应该兼具系统整体的吞吐量和用户间的公平性，通常用各用户的周转时间和用户平均周转时间来评价调度算法。设用户进入输入井的时间为Si，作业执行结束的时间为Ei，则作业的周转时间Ti计算如式，作业的平均周转时间T计算如式。

先来先服务算法和计算时间短的作业优先算法是两种典型的作业调度算法。它们的周转时间的计算是作业调度算法在教学中面临的难点，也是困扰广大学生学习的难点。下面将在具体问题中对时间轴法进行介绍。

3 “时间轴法”在作业调度中的应用

3.1 基本问题的描述

在一个多道程序系统中，设供作业使用的主存空间为100K，主存空间管理采用可变分区存储管理，在不考虑移动技术的情况下主存的分配与回收采用最先适应分配算法，今有如表1所示的作业序列需要处理[5]。

表1 等待处理的作业序列

从表1可以看出，五个作业所需要的内存总量为155K，而作业所能使用的主存空间仅为100K。显然，五个作业不能同时进入主存，当某一时刻输入井中同时存在多个后备作业时，需以一定策略选择合适的作业进入主存。下面分别采用先来先服务算法和计算时间短的作业优先算法完成作业调度，分析各个作业的开始执行时间、完成时间、周转时间及作业的平均周转时间。

3.2 先来先服务算法

先来先服务算法是最简单的调度算法，其基本思想如下：当某一时刻，输入井中同时存在多个后备作业需要调入主存执行时，优先选取先进入输入井的作业调入主存。但是，并不是先进入的就一定被先选中，只有满足必要条件的作业才能被选中。在可变分区管理策略下，可用存储空间动态变化，在不考虑移动技术的情况下，并不是可用资源的总和大于作业所需的资源量作业就能调入主存，特别是对于主存等资源，必须考虑当前是否为一个连续的空闲块。这种情况下，单靠空间想象能力去记忆和理解作业调度算法较为困难。于是，本文提出引入“时间轴法”，按照时间演进的顺序，记录资源被占用的情况。

对于表1所示例子，引入“时间轴法”进行描述，作业的执行过程如图1。图中，“开”表示开始执行；“完”表示执行结束；“入井”表示进入输入井；“入主”表示进入主存。按时间顺序，先来先服务下的作业调度过程描述如下：

1）10.1时刻，作业A进入输入井，当前输入井中的后备作业只有A，此时不存在资源竞争问题，A所需要的内存15K小于当前空闲量100K，作业A调入主存，并开始执行；

2）10.3时刻，作业B进入输入井，当前输入井中的后备作业只有B，此时也不存在资源竞争问题，当前主存剩余量85K能够满足B的要求，作业B调入主存，并在A执行结束后开始执行；

3）10.5时刻，作业C进入输入井，当前输入井中的后备作业只有C，此时也不存在资源竞争问题，当前主存剩余量25K不能满足C的要求，作业C在输入井中等待；

4）10.6时刻，作业D进入输入井，当前输入井中的后备作业有C、D，但当前主存剩余量25K仅能满足D的要求，不存在竞争问题，作业D调入主存，并在B执行结束后开始执行；

5）10.7时刻，作业E进入输入井，当前输入井中的后备作业有C、E，此时主存剩余量15K不能够满足C、E的要求，不存在竞争问题，C、E在输入井中等待；

6）10.8时刻，作业A执行完成，回收A占用的所有资源，此时可用主存量为上下分别15K，虽然大于E要求的20K，但是不连续，C、E继续在输入井中等待，不存在资源竞争，作业B仅接着A开始执行；

7）11.3时刻，作业B执行结束，回收B占用的所有资源，此时可用主存量为上15K，下75K，能够同时满足C、E的请求，存在资源竞争问题，按先来先服务算法，作业C先进入主存，剩下内存量仍然满足E的需求，故E紧接着进入主存。C紧着D执行，E紧接着C执行；

8）按D、C、E顺序执行作业。

图1 先来先服务算法下的作业调度

图2给出了先来先服务算法下作业的调度顺序。从整个过程中，可以看出，仅在11.3时刻存在资源竞争问题，并采用了先来先服务算法，而其它时刻要么不存在资源竞争问题，要么资源不足；在10.8时刻，虽然总的剩余量30大于E所需的20K，但是由于两个15K的空闲区是分散的，任意一个都无法满足E的需求，可视为内存碎片，E仍然需要继续等待。在10.8时刻，时间轴的意义尤为明显，在未引入“时间轴法”时，学生往往认为10.8时刻，作业E已可以进入主存，但是实际上，这种理解是极其错误的。引入后，大部分学生都能正确理解整个作业调度过程。同时，根据图2很容易得到作业的执行情况如表2。

表2 先来先服务算法下的作业执行过程

根据表2可进一步计算平均周转时间如式，即平均周转时间为1.2小时。

3.3 计算时间短的作业优先算法

计算时间短的作业优先算法要求作业预估一个计算时间，作业调度是根据作业计算时间的长短，优先选取计算时间短的作业进入主存，从而降低作业整体的平均周转时间，提高系统的吞吐能力。同样，并不是计算时间短的作业就一定先被选中，只有满足必要条件的作业才能被选中。

从上一小节，先来先服务算法下的“时间轴法”分析中可知，仅11.3时刻需要根据调度算法进行作业调度，由于作业E的计算时间短于作业C，故在计算时间短的作业优先算法下，作业E先进入主存，从而该算法下的时间轴描述如图3。作业的执行顺序为A、B、D、E、C。

图2 计算时间短的作业优先算法下的作业调度

由图3很容易得到作业的执行情况如表3。平均周转时间计算如式，值为1.16小时。

表3 先来先服务算法下的作业执行过程

4 结束语

操作系统是计算机及其相关专业中一门比较难的基础课，涉及较多的资源分配算法，其存在的理解困难一直是困扰教学的重要问题。本文将“时间轴法”引入到作业调度算法的教学中，思路更为清晰，能够准确描述作业的执行情况，且易于学生接受，取得了较好的效果。未来，我们还需要引入更多的方法对操作系统这一门课程中的各类算法进行形象描述，以提高教学质量。

[1]唐作其，叶洁，武彤，等．面向信息安全专业的操作系统教学改革[J]．计算机教育，2012，(01)：83-85．

[2]刘晓平，陈欣，李琳，等．面向操作系统课程的“启发—探究式”教学方法初探[J]．计算机教育，2011，(02)：50-53．

[3]郑丽洁，陈利．操作系统教学中的计算思维能力培养[J]．计算机教育，2013，(15)：82-84．

[4]陆亿红，黄德才．操作系统教学方法的若干思考[J]．计算机教育，2011，(09)：80-82．

[5]谭耀铭．操作系统概论[M]．北京：经济科学出版社，2005：26-29.

Application of Time-axis Based on Method in Teaching Job Scheduling Algorithms of Operating System

Chen Yongli1Chen Meijie2Zhang Guangming3Wang Dawei3
(1.School of Mathematics and Computer Science,Shanxi Normal University,Linfen 041000,Shanxi; 2.Continuing Education School,Chongqing Technology and Business University,Chongqing 400067; 3.College of Physics and Information Engineering,Shanxi Normal University,Linfen 041000,Shanxi)

It’s a challenge to vividly introduce the job scheduling algorithms.To solve it,a method based on time-axis is introduced in the paper to describe them.Firstly,the allocation performance of system resources is shown clearly in the time axis.Secondly,the implementation procedure of“first come first served”scheduling algorithm and“shortest job first”scheduling algorithm are described visually in the time-axis.The results of teaching practice shows that this time-axis method is a useful way to teach the job scheduling algorithm in operating system.

operating system;job scheduling algorithm;engineering education

TP312

：B

：1008-6609(2015)12-0052-03

陈永丽，女，河南开封人，硕士，教师，研究方向：嵌入式网络。

山西师范大学校级品牌特色专业建设点，项目编号：SD2008PP2Y-02；2015年校级大学生创新创业训练项目，项目编号：SD2015CXXM-67。