优秀课件笔记之处理机调度

本章小结1、本文所以内容来自 著名高校课件和学生笔记（校园里面经常见到有人高价买笔记）
2、任课教师不会提供参考文献，所以只能对作者表示感谢，如果引用了您的作品，可以用回复方式补充参考文献。
3、我不对文章无关问题进行解答，文章内容也比较难，我也很难解答您遇到的问题，如果发现BUG可以用回复方式帮我修正。
4、本课 计算机操作系统
，适用于计算机操作系统课、考研

本课其他部分的导航条见页面底部

§
4.1
分级调度
§
4.2
作业调度
§
4.3
进程调度
§
4.4
调度算法
§
4.5
算法评价
§
4.6
实时系统调度方法
本章小结

引
言
3
衡量调度策略的最常用的几个指标是：周转时间、吞吐
率、响应时间以及设备利用率等。周转时间是指将一个作业
提交给计算机系统后到该作业的结果返回给用户所需要的时
间。吞吐率是指在给定的时间内，一个计算机系统所完成的
总工作量。响应时间则是指从用户向计算机发出一个命令到
计算机把相应的执行结果返回给用户所需要的时间。设备利
用率主要指输入输出设备的使用情况。
本章将以CPU
管理为核心，讨论管理、控制用户进程执
行的方法。主要包括：
(1)
作业与进程的关系；(2)
作业调度策略与算法；(3)
进程
调度策略与算法；(4)
几种调度策略的评价。
另外，还介绍实时调度系统。
引
言
(
续
)
4
4.1.1
作业的状态及其转换
在第2
章中，介绍了用户如何利用操作系统提供的
手段与工具去组织和控制自己的作业运行。但是，一个
作业从用户提交开始到真正占有处理机而被执行，则要
由系统经过多级调度才能实现（在有些系统，例如分时
系统中，也可以由单级调度实现），下面以批处理系统
为例看一个作业处理的大致过程。
如图4.1
所示，一个作业从提交给计算机系统到执
行结束退出系统，一般都要经历提交、收容、执行和完
成等4
个状态。
§4.1
分
级
调
度
5
图4.1
作业的状态及其转换
4.1.1
作业的状态及其转换(
续)
6
一个作业在其处于从输入设备进入外部存储设备
的过程称为提交状态。处于提交状态的作业，因其信
息尚未全部进入系统，所以不能被调度程序选取。
收容状态也称为后备状态。输入管理系统不断地
将作业输入到外存中对应部分（或称输入井，即专门
用来存放待处理作业信息的一组外存分区）。若一个
作业的全部信息已全部被输入进输入井，那么，在它
还未被调度去执行之前，该作业处于收容状态。
4.1.1
作业的状态及其转换(
续)
7
作业调度程序从后备作业中选取若干个作业到内存投入
运行。它为被选中作业建立进程并分配必要的资源，这时，
这些被选中的作业处于执行状态。从宏观上看，这些作业正
处在执行过程中，但从微观上看，在某一时刻，由于处理机
总数少于并发执行的进程数，因此，不是所有被选中作业都
占有处理机，其中的大部分处于等待资源或就绪状态中。那
么，究竟哪个作业的哪个进程能获得处理机而真正在执行，
要依靠进程调度来决定。
当作业运行完毕，但它所占用的资源尚未全部被系统回
收时，该作业处于完成状态。在这种状态下，系统需做诸如
打印结果、回收资源等类的善后处理工作。
4.1.1
作业的状态及其转换(
续)
8
处理机调度问题实际上也是处理机的分配问题。显
然，只有那些参与竞争处理机所必需的资源都已得到满
足的进程才能享有竞争处理机的资格。这时，它们处于
内存就绪状态。这些必需的资源包括内存、外设及有关
数据结构等。从而，在进程有资格竞争处理机之前，作
业调度程序必须先调用存储管理、外设管理程序，并按
一定的选择顺序和策略从输入井中选择出几个处于后备
状态的作业，为它们分配内存等资源和创建进程，使它
们获得竞争处理机的资格。
4.1.2
调度的层次
9
另外，由于处于执行状态下的作业一般包含有多个进
程，而在单机系统中，每一时刻只能有一个进程占有处理机。
那么，其他进程就只能处于准备抢占处理机的就绪状态或等
待得到某种新资源的等待状态。为了提高资源的利用率，在
有些操作系统中把一部分在内存中处于就绪状态或等待状态
而在短时期内又得不到执行的进程、作业换出内存，以让其
他作业的进程竞争处理机。这样，在外存中，除了处于后备
状态的作业外，还存在有处于就绪状态而等待得到内存的作
业。这就需要有一定的方法和策略为这部分作业分配空间。
一般来说，处理机调度可以分为4
级：
4.1.2
调度的层次(
续)
10
一般来说，处理机调度可以分为4
级：
(1)
作业调度：又称宏观调度，或高级调度。其主要任务是按一定的
原则对外存输入井上的大量后备作业进行选择，给选出的作业分配
内存、输入输出设备等必要的资源，并建立相应的进程，以使该作
业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，还
负责回收系统资源。
(2)
交换调度：又称中级调度。其主要任务是按照给定的原则和策
略，将处于外存交换区中的就绪状态或就绪等待状态的进程调入内
存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换
区。交换调度主要涉及到内存管理与扩充。
(3)
进程调度：又称微观调度或低级调度。其主要任务是按照某种策
略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用
处理机的进程后，系统必须进行进程上下文切换以建立与占用处理
机进程相适应的执行环境。
(4)
线程调度。
上述4
级调度的关系如图4.1
。
4.1.2
调度的层次(
续)
11
在多道批处理系统中，存在着作业调度和进程调
度。但是，在分时系统和实时系统中，一般不存在作
业调度，而只有进程调度、交换调度和线程调度。这
是因为在分时系统和实时系统中，为了缩短响应时间
或为了满足用户需求的截止时间，作业不是建立在外
存，而是直接建立在内存中。在这些系统中，一旦用
户和系统的交互开始，用户马上要进行控制。因而，
这些系统中没有作业提交状态和后备状态。它们的输
入信息经过终端缓冲区为系统所接收，或者立即处
理，或者经交换调度暂存外存中。
4.1.2
调度的层次(
续)
12
作业可被看作是用户向计算机提交任务的任务实体，
例如一次计算、一个控制过程等。反过来，进程则是计算
机为了完成用户任务实体而设置的执行实体，是系统分配
资源的基本单位。显然，计算机要完成一个任务实体，必
须要有一个以上的执行实体。也就是说，一个作业总是由
一个以上的多个进程组成的。那么，作业怎样分解为进程
呢？首先，系统必须为一个作业创建一个根进程。然后，
在执行作业控制语句时，根据任务要求，系统或根进程为
其创建相应的子进程，然后，为各子进程分配资源和调度
各子进程执行以完成作业要求的任务。
4.1.3
作业与进程的关系
13
作业调度主要是完成作业从后备状态到执行状态的转
变，以及从执行状态到完成状态的转变。本节主要介绍作
业调度的功能及调度性能的评价方法。
4.2.1
作业调度功能（4
点）
(1)
记录系统中各作业的状况。
作业调度程序要能挑选出一个作业投入执行，并且在执行中对其
进行管理，它就必须掌握作业在各个状态，包括执行阶段的有关情况。
通常，系统为每个作业建立一个作业控制表JCB
记录这些有关信息。
系统通过JCB
而感知作业的存在。系统在作业进入后备状态时为该作
业建立它的JCB
，从而使得该作业可被作业调度程序感知。当该作业
执行完毕进入完成状态之后，系统又撤消其JCB
而释放有关资源并撤
消该作业。
§4.2
作
业
调
度
14
对于不同的批处理系
统，其JCB
的内容也有所不
同。图4.2
给出了JCB
的主
要内容。它包括作业名、作
业类型、资源要求、当前状
态、资源使用情况以及该作
业的优先级等。
（详细内容见下页） 其他
当前状态
优先级(数)
资源使用情况
资源要求
作业类型
作业名
图4.2
作业控制块JCB
4.2.1
作业调度功能(
续)
15
其中，作业名由用户提供并由系统将其转换为系统可识
别的作业标识符。作业类型指该作业属于计算型（要求CPU
时间多）还是管理型（要求输入／输出量大）,
或图形设计型
（要求高速图形显示）等。而资源要求则包括：该作业估计
执行时间、要求最迟完成时间、要求的内存量和外存量、要
求的外设类型及台数以及要求的软件支持工具库函数等。资
源要求均由用户提供。资源使用情况包括有：作业进入系统
时间、开始执行时间、已执行时间、内存地址、外设台数等。
优先级则被用来决定该作业的调度次序。优先级既可以由用
户给定，也可以由系统动态计算产生。状态是指该作业当前
所处的状态。显然，只有当作业处于后备状态时，该作业才
可以被调度。
4.2.1
作业调度功能(
续)
16
(2)
从后备队列中挑选出一部分作业投入执行。作业调度程序
根据选定的调度算法，从后备作业队列中挑选出若干作业
去投入执行。
(3)
为被选中作业做好执行前的准备工作。作业调度程序为选
中的作业建立相应的进程，并为这些进程分配它们所需要
的系统资源，如分配给它们内存、外存、外设等。
(4)
在作业执行结束时做善后处理工作。主要是输出作业管理
信息，例如执行时间等。再就是回收该作业所占用的资
源，撤消与该作业有关的全部进程和该作业的作业控制块
等等。
作业从后备状态到执行状态，又从执行状态到完成状
态的转换过程如图4.3
所示。
4.2.1
作业调度功能(
续)
17
图4.3
作业
调度中状态
的转换过程
18
作业调度的功能最主要的是从后备作业队列中选取一批
作业进入执行状态。根据不同的目标，将会有不同的调度算
法。这里先介绍调度目标。
一般来说，调度目标主要是以下4
点：
(1)
对所有作业应该是公平合理的；
(2)
应使设备有高的利用率；
(3)
每天执行尽可能多的作业；
(4)
有快的响应时间。
由于这些目标的相互冲突，任一调度算法要想同时满足
上述目标是不可能的。
4.2.2
作业调度目标与性能衡量
19
必须指出，如果考虑的因素过多，调度算法就会变
得非常复杂。其结果是系统开销增加，资源利用率下降。
因此，大多数操作系统都根据用户需要，采用兼顾某些
目标的简单调度算法。
那么，怎样来衡量一个作业调度算法是否满足系统
设计的要求呢？对于批处理系统，由于主要用于计算，
对于作业的周转时间要求较高。因此，作业的平均周转
时间或平均带权周转时间，被作为衡量调度算法优劣的
标准。但是，对于分时系统和实时系统来说，外加平均
响应时间被作为衡量调度策略优劣的标准。
4.2.2
作业调度目标与性能衡量(
续)
20
1.
周转时间：
作业i
的周转时间T
i
为:
T
i
=
T
ei
-T
si
其中T
ei
为作业i
的完成时间，T
si
为作业的提交时间。
对于被测定作业流所含有的n
（n>=1
）个作业来说，其平均
周转时间为：
一个作业的周转时间说明了该作业在系统内停留的时间，包
含两部分：等待时间；执行时间，即： T
i
=
T
wi
＋T
ri
这里，T
wi
主要指作业i
由后备状态到执行状态的等待时
间，它不包括作业进入执行状态后的等待时间。
ån
n
i
i = 1
1
T = T
n
4.2.2
作业调度目标与性能衡量(
续)
21
2.
带权周转时间
作业的周转时间包含了两个部分，即等待时间和执行时
间。为了更进一步反映调度性能，使用带权周转时间的概念。
带权周转时间是作业周转时间与作业执行时间的比：
W
i
=T
i
/T
ri
对于被测定作业流所含有的几个作业来说，其平均带权
周转时间为：
对于分时系统，除了要保证系统吞吐量大、资源利用率
高之外，还应保证有用户能够容忍的响应时间。因此，在分
时系统中，仅仅用周转时间或带权周转时间来衡量调度性能
是不够的。
ån
n
i
i = 1
1
W = W
n
4.2.2
作业调度目标与性能衡量(
续)
22
无论是在批处理系统还是分时系统中，用
户进程数一般都多于处理机数，这将导致用户
进程互相争夺处理机。另外，系统进程也同样
需要使用处理机。这就要求进程调度程序按一
定的策略，动态地把处理机分配给处于就绪队
列中的某一个进程，以使之执行。本节介绍进
程调度的功能、进程调度发生的时机以及由进
程调度引起的进程上下文切换等。
§4.3
进
程
调
度
23
进程调度的具体功能可总结如下(3
点)
：
(1)
记录系统中所有进程的执行情况
作为进程调度的准备，进程管理模块必须将系统中各进程的执行情
况和状态特征记录在各进程的PCB
表中。并且，进程管理模式根据各进程
的状态特征和资源需求，将各进程的PCB
表排成相应的队列并进行动态队
列转接。进程调度模块通过PCB
变化来掌握系统中所有进程的执行情况和
状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。
(2)
选择占有处理机的进程
进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进
程，使其获得处理机执行。根据不同的系统设计目的，有各种各样的选择
策略，例如系统开销较少的静态优先数调度法，适合于分时系统的轮转法
和多级反馈轮转法等。这些选择策略决定了调度算法的性能。
4.3.1
进程调度的功能
24
(3)
进行进程上下文切换
一个进程的上下文（context
）包括进程的状态、
有关变量和数据结构的值、硬件寄存器的值和PCB
以及
有关程序等。一个进程的执行是在进程的上下文中执行。
当正在执行的进程由于某种原因要让出处理机时，系统
要做进程上下文切换，以使另一个进程得以执行。当进
行上下文切换时，系统要首先检查是否允许做上下文切
换。然后，系统要保留有关被切换进程的足够信息，以
便以后切换回该进程时，顺利恢复该进程的执行。在系
统保留了CPU
现场之后，调度程序选择一个新的处于就
绪状态的进程，并装配该进程的上下文，使CPU
的控制
权转换到被选中进程中。
4.3.1
进程调度的功能(
续)
25
进程调度发生在什么时机呢？这与引起进程调度的
原因以及进程调度的方式有关。
引起进程调度的原因有以下几类(7
类)
：
(1)
正在执行的进程执行完毕。这时，如果不选择新的就绪
进程执行，将浪费处理机资源。
(2)
执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠
等待状态。
(3)
执行中进程调用了P
原语操作，从而因资源不足而被阻
塞；或调用了V
原语操作激活了等待资源的进程队列。
(4)
执行中进程提出I
／O
请求后被阻塞。
(5)
在分时系统中时间片已经用完。
4.3.2
进程调度的时机
26
(6)
在执行完系统调用，在系统程序返回用户进程时，可认为系
统进程执行完毕，从而可调度选择一新的用户进程执行。
以上都是在CPU
执行不可剥夺方式下所引起进程调度的
原因。在CPU
执行方式是可剥夺时，还有：
(7)
就绪队列中的某进程的优先级变得高于当前执行进程的优先
级，从而也将引发进程调度。
所谓可剥夺方式，即就绪队列中一旦有优先级高于当前执
行进程优先级的进程存在时，便立即发生进程调度，转让处理
机。而非剥夺方式或不可剥夺方式即使在就绪队列存在有优先
级高于当前执行进程时，当前进程仍将继续占有处理机，直到
该进程自己因调用原语操作或等待I
／O
而进入阻塞、睡眠状
态，或时间片用完时才重新发生调度让出处理机。
4.3.2
进程调度的时机(
续)
27
操作系统将在以上几种原因之一发生的情况下进行进程
调度。例如，UNIX
SystemV
就是在以下5
种情况之一发生
时进行进程调度的：
(1)
当前进程自己调用sleep
，wait
等进入睡眠状态时。
(2)
当前进程从系统调用执行结束后返回用户态时，它的优先
级已低于其他就绪状态进程，或调度标志被置位。
(3)
当前进程在完成中断和陷阱处理后返回用户态时，它的优
先级已低于其他就绪状态进程；或调度标志被置位。
(4)
时间片用完，而且当前进程的优先级低于其他就绪进程。
(5)
当前进程调用exit
，自我终止时。
4.3.2
进程调度的时机(
续)
28
进程上下文由正文段、数据段、硬件寄存器的内
容以及有关数据结构等组成。硬件寄存器主要包括存
放CPU
将要执行的下条指令虚拟地址的程序计数器
PC
，指出机器与进程相关联的硬件状态的处理机状
态寄存器PS
，存放过程调用（或系统调用）时所传
递参数的通用寄存器R
以及堆栈指针寄存器S
等。数
据结构则包括PCB
等在内的所有与执行该进程有关的
管理和控制用表格、数组、链等。在发生进程调度
时，系统要做进程上下文切换。
进程上下文切换包括4
个步骤：(
见下页)
4.3.3
进程上下文切换
29
进程上下文切换包括4
个步骤：
(1)
决定是否做上下文切换以及是否允许做上下文切换。包括对进程
调度原因的检查分析，以及当前执行进程的资格和CPU
执行方式
的检查等。
(2)
保存当前执行进程的上下文。这里所说的当前执行进程，实际上
是指调用上下文切换程序之前的执行进程。如果上下文切换程序
不是被那个当前执行进程所调用，且不属于该进程，则所保存的
上下文应是先前执行进程的上下文，或称为“
老”
进程上下文。显
然，上下文切换程序不能破坏“
老”
进程的上下文结构。
(3)
使用4.
4
节中所述进程调度算法，选择一个处于就绪状态进程。
(4)
恢复或装配所选进程的上下文，将CPU
控制权交给所选进程。
4.3.3
进程上下文切换(
续)
30
进程调度虽然是系统内部的低级调度，但进程调度的优劣直接
影响作业调度的性能。反映作业调度优劣的周转时间和平均周转时
间只在某种程度上反映了进程调度的性能，例如，其执行时间部分
中实际上包含有进程等待（包括就绪状态时的等待）时间，而进程
等待时间的多少是要依靠进程调度策略和等待事件何时发生来决定
的。因此，进程调度性能的衡量是操作系统设计的一个重要指标。
进程调度性能的衡量方法可分为定性和定量两种。在定性衡量
方面，首先是调度的可靠性。另外，简洁性也是衡量进程调度的一
个重要指标。
进程调度的定量评价包括CPU
的利用率评价、进程在就绪队列
中的等待时间与执行时间之比等。实际上，由于进程进入就绪队列
的随机模型很难确定，而且进程上下文切换等也将影响进程的执行
效率，从而对进程调度进行解析是很困难的。一般情况下，大多利
用模拟或测试系统响应时间的方法来评价进程调度的性能。
4.3.4
进程调度性能评价
31
本节讨论各种常用的进程调度算法和作业调度算法。
1.
先来先服务（FCFS
）调度算法
将用户作业和就绪进程按提交顺序或变为就绪状态的先
后排成队列，并按照先来先服务的方式进行调度处理，是一
种最普遍和最简单的方法。在没有特殊理由要优先调度某类
作业或进程时，从处理的角度来看，FCFS
方式是一种最合适
的方法，无论是追加还是取出一个队列元素在操作上都是最
简单的。
直观看，该算法在一般意义下是公平的。即每个作业或
进程都按照它们在队列中等待时间长短来决定它们是否优先
享受服务。不过对于那些执行时间较短的作业或进程来说，
如果它们在某些执行时间很长的作业或进程之后到达，则它
们将等待很长时间。
§4.4
调
度
算
法
32
在实际操作系统中，尽管很少单独使用FCFS
算法，但和
其他一些算法配合起来，FCFS
算法还是使用得相当多的。例
如基于优先级的调度算法就是对具有同样优先级的作业或进
程采用的FCFS
方式。
2.
轮转法（round robin
）
轮转法的基本思路是让每个进程在就绪队列中的等待时
间与享受服务的时间成比例。轮转法的基本概念是将CPU
的
处理时间分成固定大小的时间片。如果一个进程在被调度选
中之后用完了系统规定的时间片，但未完成要求的任务，则
它自行释放自己所占有的CPU
而排到就绪队列的末尾，等待
下一次调度。同时，进程调度程序又去调度当前就绪队列中
的第一个进程或作业。
轮转法的原理见图4.4
。(
见下页)
§4.4
调
度
算
法(
续)
33
图4.4
轮转法调度
显然，轮转法只能用来调度分配那些可以抢占的资源。
将它们随时剥夺再分配给别的进程。CPU
是可抢占资源的一
种。但如打印机等资源是不可抢占的。由于作业调度是对除
了CPU
之外的所有系统硬件资源的分配，其中包含有不可抢
占资源，所以作业调度不使用轮转法。
§4.4
调
度
算
法(
续)
34
在轮转法中，时间片长度的选取非常重要。首先，时间
片长度的选择会直接影响系统开销和响应时间。如果时间片
长度过短，则调度程序剥夺处理机的次数增多。这将使进程
上下文切换次数也大大增加，从而加重系统开销。反过来，
如果时间片长度选择过长，比方说一个时间片能保证就绪队
列中所需执行时间最长的进程能执行完毕，则轮转法变成了
先来先服务法。
时间片长度的选择是根据系统对响应时间的要求R
和就绪
队列中所允许的最大进程数Nmax
确定的。它可表示为：
q=R/
Nmax
§4.4
调
度
算
法(
续)
35
在q
为常数的情况下，如果就绪队列中的进程数发生远小
于Nmax
的变化，则响应时间R
看上去会大大减小。但是，就
系统开销来说，由于q
值固定，从而进程上下文切换的时机不
变，系统开销也不变。通常，系统开销也是处理机执行时间
的一部分。CPU
的整个执行时间等于各进程执行时间加上系
统开销。在进程执行时间大幅度减少的情况下，如果系统开
销也随之减少的话，系统的响应时间有可能更好一点。例
如，在一个用户进程的情况下，如果q
值增大到足够该进程
执行完毕的话，则进程调度所引起的系统开销就没有了。一
种可行的办法是，每当一轮调度开始时，系统便根据就绪队
列中已有进程数目计算一次q
值，作为新一轮调度的时间片。
这种方法得到的时间片随就绪队列中的进程数变化。
§4.4
调
度
算
法(
续)
36
3.
多级反馈轮转法
在轮转法中，加入到就绪队列的进程有三种情况，一种是分给它的
时间片用完，但进程还未完成，回到就绪队列的末尾等待下次调度去继续
执行。另一种情况是分给该进程的时间片并未用完，只是因为请求I
／O
或
由于进程的互斥与同步关系而被阻塞。当阻塞解除之后再回到就绪队列。
再有一种情况就是新创建进程进入就绪队列。如果对这些进程区别对待，
给予不同的优先级和时间片，从直观上看，可望进一步改善系统服务质量
和效率。例如，可把就绪队列按照进程到达就绪队列的类型和进程被阻塞
时的阻塞原因分成不同的就绪队列，每个队列按FCFS
原则排列，各队列
之间的进程享有不同的优先级，但同一队列内优先级相同。
这样，当一个进程在执行完它的时间片之后，或从睡眠中被唤醒以及
被创建之后，将进入不同的就绪队列。多级反馈轮转法与优先级法在原理
上的区别是，一个进程在它执行结束之前，可能需要反复多次通过反馈循
环执行，而不是优先级法中的一次执行。
§4.4
调
度
算
法(
续)
37
4.
优先级法
优先级法可被用作作业或进程的调度策略。首先，系统
或用户按某种原则为作业或进程指定一个优先级来表示该作
业或进程所享有的调度优先权。该算法的核心是确定进程或
作业的优先级。
确定优先级的方法可分为静态法和动态法。静态法根据
作业或进程的静态特性，在作业或进程开始执行之前就确定
它们的优先级，一旦开始执行之后就不能改变。动态法则不
然，它把作业或进程的静态特性和动态特性结合起来确定作
业或进程的优先级，随着作业或进程的执行过程，其优先级
不断变化。
§4.4
调
度
算
法(
续)
38
静态优先级
作业调度中的静态优先级大多按以下原则确定：
(1)
由用户自己根据作业的紧急程度输入一个适当的优先级。
为防止各用户都将自己的作业冠以高优先级，系统应对高
优先级用户收取较高的费用。
(2)
由系统或操作员根据作业类型指定优先级。作业类型一般
由用户约定或由操作员指定。例如：可将作业分为：
I
／O
繁忙的作业，
CPU
繁忙的作业，
I
／O
与CPU
均衡的作业， 一般作业，等等。
系统或操作员可以给每类作业指定不同的优先级。
(3)
系统根据作业要求资源情况确定优先级。例如根据估计所
需处理机时间、内存量大小、I
／O
设备类型及数量等，
确定作业的优先级。
§4.4
调
度
算
法(
续)
39
进程的静态优先级确定原则可以是：
(1)
按进程的类型给予不同的优先级。例如，在有些系统中，
进程被划分为系统进程和用户进程。系统进程享有比用户
进程高的优先级。对于用户进程来说，则可以分为：
I
／O
繁忙的进程，
CPU
繁忙的进程，
I
／O
与CPU
均衡的进程， 其他进程。
对系统进程，也可以根据其所要完成的功能划分为不同的
类型，例如，调度进程、I
／O
进程、中断处理进程、存储管
理进程等。这些进程还可进一步划分为不同类型和赋予不同
的优先级。例如，在操作系统中，对于键盘中断的处理优先
级和对于电源掉电中断的处理优先级是不相同的。
(2)
将作业的静态优先级作为它所属进程的优先级。
§4.4
调
度
算
法(
续)
40
动态优先级
基于静态优先级的调度算法实现简单，系统开销小，但由于静态优
先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较
低，调度性能不高。现在的操作系统中，如果使用优先级调度的话，则大
多采用动态优先级的调度策略。
进程的动态优先级一般根据以下原则确定：
(1)
根据进程占有CPU
时间的长短来决定。一个进程占有处理
机的时间愈长，则在被阻塞之后再次获得调度的优先级就
越低，反之，其获得调度的可能性就会越大。
(2)
根据就绪进程等待CPU
的时间长短来决定。一个就绪进程
在就绪队列中等待的时间越长，则它获得调度选中的优先
级就越高。
§4.4
调
度
算
法(
续)
41
由于动态优先级随时间的推移而变化，系统要经常计算
各进程的优先级，因此，系统要为此付出一定的开销。
例如：线性优先级调度策略（selfish round robin
）
使用轮转法调度进程时，新创建的进程也放入就绪队列末尾
享受平等的处理机时间片。这对于执行时间长的进程来说是
有点不公平的，因为它们需要多个时间片才能完成。因此，
线性优先级调度策略采用如下方式，即新创建的进程按FCFS
方式排成就绪队列，而其他已得到过时间片服务的进程也按
FCFS
方式排成另一个就绪队列或称享受服务队列(
图4.5
）。
§4.4
调
度
算
法(
续)
42
图4.5
线性优先级调度
对于这两个不同队列中的进程，设新创建进程就绪队列
中进程的优先级P
以
P=a
*
t (a>0)
的速率增加。另外，享
受服务队列中进程的优先级P
以
P=b
*
t (a>b>0)
的速率增
长。设某一进程在时刻t
1
时被创建，在时刻t
时，该进程的优
先级为
P(t)=a
*
(t-t
1
) (t
1
<t<t
1
′
)
§4.4
调
度
算
法(
续)
43
又设该进程在t
1
′
时刻转入享受服务队列，则在时刻t
，该
进程的优先级变为
P(t)=a
*
(t
1
′
-t
1
)+b
*
(t-t
1
′
) (t
1
′
<t<t
2
′
)
那么，一个新创建进程等待多长时间之后进入享受服务
队列较为合适呢？当新创建进程就绪队列中的头一个进
程的优先级P(t)=a
*
(t-t
1
)
与享受服务队列中最后一个就
绪进程的优先级P(t)=b
*
t
相等时，新创建进程队列中的
头一个进程可以转入享受服务进程队列。其优先级变化
曲线如图4.6
。(
见下页)
§4.4
调
度
算
法(
续)
44
图4.6
优先级变化曲线
§4.4
调
度
算
法(
续)
45
另外，当享受服务进程队列为空时，新创建进程队
列的头一个进程也将移入享受服务进程队列。
显然，在上述线性优先级调度法中，a>b>0
的条
件是必要的。否则，当b>a>0
时，两个不同队列中的
就绪态进程的优先级将永远不会相等，从而，在享受服
务进程队列中永远只有一个进程。因此，上述线性优先
级调度策略退回到FCFS
方式。另外，如果a>b=0
，则
线性优先级调度策略退回到轮转法调度方式。事实上，
线性优先级调度策略是一种介于轮转法和FCFS
方式之间
的调度策略。这几种方式的调度性能，将在下一节中更
进一步讨论。
§4.4
调
度
算
法(
续)
46
5.
最短作业优先法（shortest job first
）
最短作业优先法（SJF
）就是选择那些估计需要执行时间
最短的作业投入执行，为它们创建进程和分配资源。直观上
来说，采用最短作业优先的调度算法，可使得系统在同一时
间内处理的作业个数最多，从而吞吐量也就大于其他调度方
式。但是，对于一个不断有作业进入的批处理系统来说，最
短作业优先法有可能使得那些长作业永远得不到调度执行的
机会。
6.
最高响应比优先法（highest
responseratio
next
）
最高响应比优先法（HRN
）是对FCFS
方式和SJF
方式的
一种综合平衡。HRN
调度策略同时考虑每个作业的等待时间
长短和估计需要的执行时间长短，从中选出响应比最高的作
业投入执行。
§4.4
调
度
算
法(
续)
47
响应比R
定义如下： R=(W+T)/T=1+W/T
其中T
为该作业估计需要的执行时间，W
为作业在后备状
态队列中的等待时间。
每当要进行作业调度时，系统计算每个作业的响应
比，选择其中R
最大者投入执行。这样，即使是长作业，
随着它等待时间的增加，W/T
也就随着增加，也就有机
会获得调度执行。这种算法是介于FCFS
和SJF
之间的一
种折中算法。由于长作业也有机会投入运行，在同一时间
内处理的作业数显然要少于SJF
法，从而采用HRN
方式
时其吞吐量将小于采用SJF
法时的吞吐量。另外，由于每
次调度前要计算响应比，系统开销也要相应增加。
§4.4
调
度
算
法(
续)
48
本节主要利用解析技术从数学上分析几种主要调度方法的性能。
4.5.1 FCFS
方式的调度性能分析
设处理机或系统资源为服务器，一个进程或一个作业为
享受该服务器服务的顾客。当这些顾客按FCFS
方式排队享受
服务的系统模型如图4.7
。
图4.7 FCFS
方式的评价模型
这里，假定该系统模型中只有一个服务器Ｓ。
§4.5
算
法
评
价
49
设新顾客到达等待队列的时间与系统的当前状态、以前
的顾客到达时间都无关，也就是新顾客到达系统的时间是服
从泊松分布的。设λ为到达率，则在单位时间内x
个顾客到达
的概率为：
P(x
)=e
-
λλx
/x!
单位时间内顾客到达的期望值，即算术平均值为：
（y=x-1
）
由于
所以，E(x)
＝λ
也即单位时间内顾客到达的平均值等于其到达率。
å - å å
λ
x -
λ
x
x=0 x=1 y=0
E(x) = xP(x) =e
λ
/(x-1)!=
λ
e
λ
/y!
¥ ¥ ¥
å x
λ
x=0
λ
/x! = e
¥
4.5.1 FCFS
方式的调度性能分析(
续)
50
设服务器Ｓ为顾客提供服务的概率也服从泊松分布，且
μ为服务率，则单位时间内x
个顾客被服务的概率是
P(x)=e
-
μμx
/x!
同理，单位时间内被服务顾客个数的算术平均值等于其服务
率μ。将单位时间换成任意时间t
，可得到在已知时间t
内x
个顾客到达的概率为：
P(x(t))=e
λt
(
λt)
x
/x!
在t
时间内，一个顾客也不到达的概率为：
P(0)=e
-
λt
从而，t
时间内至少到达一个顾客的概率为：
P(x(t)>0)=1-e
-
λt
4.5.1 FCFS
方式的调度性能分析(
续)
51
如果把时间t
换成固定的时间间隔τ，则有，在任何时间间隔τ内至
少有一个到达发生的概率仍为1-e
-
λt
。这个概率和上一次顾客到达的时刻
无关。新顾客在下一个τ时间内到达的概率和以前顾客的到达无关，这
个特性称为无记忆特性或马尔可夫性质。利用该性质，可以简化顾客和
服务的排队模型。由于服务器的服务概率也服从泊松分布，也可推出它
在τ时间间隔内至少为一个顾客服务的概率为1-e
-
μt
，且与以前的服务过
程无关。因此，服务器的服务特性也是满足马尔可夫性质的。
由于
P(x(t)>0)=1-e
-
λt
其密度函数
P(x(t)>0)=
λe
-
λt
t
的期望值等于
E(t)
∫∞0t
λee-
λtdt=-tetdt=-
λt|
∞0+
∫∞0e-
λt=1/
λ
即两个连续到达的顾客之间的平均时间间隔为1
／λ。同理，可得服务器
服务时间的平均值为1
／μ。显然，只有当
1
／μ＜1
／λ
也就是
λ＜μ时系统才是稳定的。否则，等待服务队列将无限增长。
4.5.1 FCFS
方式的调度性能分析(
续)
52
设Ｓi
为系统的一个状态，表示等待服务的等待队列中有i-1
个顾客，
服务器中有1
个顾客存在。由概率密度函数可知，在dt
时间内1
个新顾客
到达的概率是：
P(dt
时间内1
个顾客到达)
＝λe
-
λdt
dt
将上式做多项式展开得：λe
-
λdt
dt
＝λdt
＋O(dt
2
)
同理可得，在dt
时间内服务器为1
个顾客提供服务的概率是：
P(dt
时间内1
个顾客离开)
＝μdt
＋O(dt
2
)
省略以上两式的二次方项，在dt
时间内1
个顾客到达或离开的概率为：
P(dt
时间内1
个顾客到达)=
λdt
P(dt
时间内1
个顾客离开)=
μdt
对于i
＝0
时，有：
P(dt
时间内1
个顾客离开)
＝0
在dt
时间内，顾客一个也不到达和顾客一个也不离开的概率为：
1-P(dt
时间内1
个顾客到达) -
P(dt
时间内1
个顾客离开)
-
P(dt
时间内2
个以上顾客到达)
-
P(dt
时间内2
个以上顾客离开)
。
4.5.1 FCFS
方式的调度性能分析(
续)
53
由于上式的后两项实际上是dt
的二次方以上的函数，从而上
式可合并为：
P(dt
时间内不发生变化)
＝1-(
λ＋μ) dt-O(dt
2
)(i
＞0)
或
P(dt
时间内不发生变化)
＝1-
λdt-O(dt
2
) (i
＝0)
忽略二次方项，可得状态变化图如图4.8
。
图4.8
状态转换图
4.5.1 FCFS
方式的调度性能分析(
续)
54
设系统在t+dt
时间内处于状态Ｓi
的概率为P
i
(t+dt
)
，则由状态转换图有：
P
i
(t
＋dt
)
＝［1-(
λ＋μ)
dt
］P
i
(t)
＋λdt
P
i-1
(t)
＋μdt
P
i+1
(t)
式中i
≥1
。对于i
＝0
时，有：
P
0
(t
＋dt
)
＝(1-
λdt)P
0
(t)
＋μdt
P
1
(t)
当系统到达稳定状态时，上述概率将会趋于一个常量，P
i
(t
＋dt
)
的导数为0
，
即：
P
i
′
(t
＋dt
)
＝-(
λ＋μ)P
i
(t)
＋λP
i-1
(t)
＋μP
i+1
(t)
＝0
P0
′
(t
＋dt
)
＝-
λP
0
(t)
＋μP
1
(t)
＝0
即：
P
1
＝(
λ／μ) P
0
(t)
(
λ＋μ) P
i
(t)
＝λP
i-1
(t)
＋μP
i+1
(t)
令λ／μ＝ρ，采用代入法可得：
P
i
(t)
＝ρi
P
0
(t)
4.5.1 FCFS
方式的调度性能分析(
续)
55
另外，系统运行中的任一时刻总是处于图4.8
所示状态图中的任一状
态中，从而有：
由此可得：
由于在ρ＜1
时有：
从而有：
P
0
(t)
＝1-
ρ
即，在稳态条件下，系统内不存在顾客的概率为1-
ρ＝(
μ-
λ)
／μ，而系统内存在顾客的概率为λ／μ。系统内顾客的
算术平均值是：
å 1 i
i = 0
P =
¥
å i
i=0
ρ
= 1/(1 -
ρ
)
¥
å i
0
i = 0
ρ
P (t) = 1
¥
å å i i
i
i=0 i=0
n = E(i) = iP (t) = (1-
ρ
)
ρ
=
ρ
(1-
ρ
)
¥ ¥
4.5.1 FCFS
方式的调度性能分析(
续)
56
把上述按FCFS
方式排列和调度，并只有一个服务器的系
统称为M/M/1
系统。第一个字母M
表示顾客到达时间间隔是
指数分布，具有马尔可夫性质，第二个字母M
表示从服务器离
开的顾客的时间间隔服从指数分布，具有马尔可夫性质，第
三个字母1
表示只有一个服务器。
设响应时间R
为从顾客到达等待队列后开始到离开服务器
的时间，则在系统进入稳定状态之后，系统中的顾客数n
和
平均响应时间之间存在一个非常简单的关系，即n=
λR
，λ
为顾客的平均到达率。该公式称为Little
结果（Little
’
s
result
），是一个在系统分析中广泛使用的公式。
利用Little
结果可求出M/M/1
系统的平均响应时间：
R
＝n
／λ＝ρ／λ(1
／(1-
ρ))
＝1
／(
μ(1-
ρ))
4.5.1 FCFS
方式的调度性能分析(
续)
57
平均响应时间和ρ的关系图如图4.9
。
图4.9
平均响应时间R
和ρ的关系
4.5.1 FCFS
方式的调度性能分析(
续)
58
由图4.9
可以看出，M/M/1
系统的服务性能是由ρ决定的。如果ρ趋
近1
，即λ趋近μ，则响应时间急剧增大，系统性能变差。而当ρ小于1/2
时，等待队列中为空的可能性较大，因为平均响应时间小于平均服务时间的
2
倍。
下面再来看看M/M/1
系统对短作业或短进程的影响。
设短作业的到达率和服务率分别为（λ1
，μ1
），长作业的到达率和服
务率为（λ2
，μ2
），且二者都服从泊松分布。二者的合成仍是泊松过程，
其到达率λ＝λ1
＋λ2
，平均服务时间为：
1
／μ＝λ1
／(
λ1
＋λ2
)
*
1
／μ1
＋λ2
／(
λ1
＋λ2
)
*
1
／μ2
＝1
／(
λ1
＋λ2
)
*
(
λ1
／μ1
＋λ2
／μ2
)
从而有：λ／μ＝λ1
／μ1
＋λ2
／μ2
＝ρ1
＋ρ2
一般来说，短作业的服务时间1
／μ1
远小于长作业的服务时间1
／μ2
。
FCFS
调度策略时有响应时间R
为：R
＝1
／λ*
ρ／(1-
ρ)
其中，λ＝λ1
＋λ2
，ρ＝ρ1
＋ρ2
由于λ和ρ中包含了λ1
，λ2
，μ1
和μ2
，所有作业的平均响应时间相
同，从而，短作业在系统中的驻留平均时间与长作业的驻留平均时间相同，
这对短作业是不利的。
4.5.1 FCFS
方式的调度性能分析(
续)
59
轮转法调度时的顾客到达率要大大高于FCFS
方式。
设时间片为q
，服务时间平均值为1
／μ，每个顾客平
均需要k
个时间片。从而有，1
／μ＝k
*
q
。如果某个
顾客刚好需要k
个时间片的服务时间，则这个顾客就会
到达等待队列k
次（k
＞1
）。
对于短作业，1
／μ1
＝k
1
*
q
，而对于长作业，
1
／μ2
＝k
2
*
q
。设新顾客的到达率等于λ＝λ1
＋λ
2
，服务时间：
1
／μ＝(
λ1
／μ) k
1
*
q
＋(
λ2
／μ) k
2
*
q
＝(1
／λ)(
λ1
／μ1
＋λ2
／μ2
)
从而有：
λ／μ＝ρ＝ρ1
＋ρ2
4.5.2
轮转法调度性能评价
60
这看上去好像在平均响应时间方面，轮转法和
FCFS
调度方式上变化不大。但事实上，在等待队列中
享受过k
次时间片服务的顾客的响应时间是：
R(k)
＝ρ／(
λ(1-
ρ))
＝1
／(
μ(1-
ρ))
＝k
*
q
／(1-
ρ)
也就是说，响应时间与服务时间成正比。从而，所
需服务时间短的顾客的响应时间将会小于所需服务时间
长的顾客的响应时间。因此，轮转法在响应时间上要优
于FCFS
调度方式。
4.5.2
轮转法调度性能评价(
续)
61
线性优先级调度策略（SRR
）是介于FCFS
方式和轮转法
之间的一种调度策略。SRR
方式把新到达的顾客首先送入等
待室休息一段时间后，再送到等待服务队列。（如图4.10
）
设顾客到达等待室的到达率为λ，到达等待队列的到达率为
λ′
。λ′
依赖于等待室的到达率λ和线性参数r
，其中r
＝1-b
／a
。由4.4
节可知，有a
＞b
，且a
和b
分别为等待室内顾客
和等待队列中顾客优先级的线性增加系数。
图4.10
线性优先级调度的评价模型
4.5.3
线性优先级法的调度性能
62
设t
1
和t
2
分别为两顾客接连到达等待室的时间，则有：1
／λ＝t
2
-t
1
设 t
１′
和t
２′
分别为两顾客从等待室接连到达等待队列的时间，则有：
1
／λ′
＝t
２′
-t
１′
由图4.6
可知，有：
(t
2
-t
1
)
／(t
2
′
-t
１′
)
＝r
即：
λ′
／λ＝r
，λ′
＝r
λ
由于r
＜1
，所以等待室以r
的比率滞留到达的顾客。
线性优先级调度系统的响应时间是Ｒs
*
r
。且Ｒs
*
r
由等待室的平均等
待时间Ｒd
和进入等待队列后得到服务的平均响应时间Ｒs
之和组成。
由对轮转法的分析，则有：
Ｒs
＝1
／(
μ-
λ)
r
*
Ｒs
＝1
／(
μ-
λ)
4.5.3
线性优先级法的调度性能(
续)
63
从而：
Ｒd
＝r
*
Ｒss-
Ｒs
＝1
／(
μ-
λ) -1
／(
μ-
λ)
＝(
λ-
λ)
／(
μ-
λ)(
μ-
λ)
另外，由轮转法可知：
Ｒs(k)
＝kq
／(1 -
ρ)
其中，ρ＝λ／μ。从而有：
Ｒsr(k
)
＝Ｒd
＋Ｒs(k)
＝(
λ-
λ)
／(
μ-
λ)(
μ-
λ)
＋kq
／(1-
ρ)
＝1
／(
μ-
λ) -(1 -
kq
μ)
／(
μ-
λ)
其中k
是一个顾客享受服务的时间片的次数，q
是时间片常数。
可以比较一下FCFS
方式、SRR
方式以及轮转法等三种调度方式
的平均响应时间。
FCFS
方式时，我们有：
Ｒfc(k
)
＝1
／(
μ-
λ)
轮转法时有：
Ｒrr(k
)
＝k q
μ／(
μ-
λ)
4.5.3
线性优先级法的调度性能(
续)
64
SRR
方式时，则响应时间为：
Ｒsr(k
)
＝1
／(
μ-
λ) -(1 -k q
μ)
／(
μ-
λ)
如果kq
＝1
／μ，即顾客的服务时间由其平均服务时间相等
的话，则Ｒsr(k
)
中第二项变为0
，上述Ｒfc(k
)
＝Ｒrr(k
)
＝
Ｒsr(k
)
。当然，对于需要服务时间短的顾客来说，有k
q
＜1
／μ，而对于需要服务时间长的顾客来说，则有kq
＞
1
／μ。从而，对于服务时间短的顾客其响应时间：
Ｒrr
＜Ｒsr
＜Ｒfc
而对于服务时间长的顾客来说，其响应时间则为：
Ｒfc
＜Ｒsr
＜Ｒrr
上面只是从响应时间的角度对几种常见的调度策略进行了评
价分析。除了响应时间之外，CPU
利用率也是评价调度性能
的另一个标准。
4.5.3
线性优先级法的调度性能(
续)
65
4.6.1
实时系统的特点
随着移动通信和网络计算技术的发展，实时系统正变
得越来越重要。操作系统是实时系统中最重要的部分之一。
它负责在用户要求的时限内进行事件处理和控制。
实时系统与其他系统的最大区别在于，其处理和控制
的正确性不仅仅取决于计算的逻辑结果，而且取决于计算
和处理结果产生的时间。因此，实时系统的调度与工业生
产中的生产过程调度有许多相同之处，即把给定的任务，
按所要求的时限调配到相应的设备上去处理完成。
4.6
实时系统调度方法
66
根据对处理外部事件的时限要求，实时系统中处理的外部事件可分为
硬实时任务和软实时任务。硬实时任务要求系统必须完全满足任务的时限
要求。软实时任务则允许系统对任务的时限要求有一定的延迟，其时限要
求只是一个相对条件。
实时系统的另一个特点是它所处理的外部任务可分为周期性的与非周
期性的两大类。对于非周期性任务来说，存在有一个完成或开始进行处理
时限，而周期性任务只要求在周期T
内完成或开始进行处理。
一般来说，实时操作系统具有以下特点：
(1)
有限等待时间（决定性）
(2)
有限响应时间
(3)
用户控制
(4)
可靠性高
(5)
系统出错处理能力强
4.6.1
实时系统的特点(
续)
67
u与分时系统的多个进程并发执行相比，分时系统中并发执行的
进程具有不确定性，其执行顺序与执行环境有关。实时系统则
不然，它要求所有的进程在处理事件时，都必须在有限时间内
开始处理。这一特性又被称为实时系统的决定性特性。
u实时系统的有限响应时间特性是指从系统响应外部事件开始，
必须在有限时间内处理完毕。
u另外，在分时系统的非实时系统中，用户不能参与对进程调度
的控制。在实时系统中，用户可以控制进程的优先级并选择相
应的调度算法，从而达到对进程执行先后顺序的控制。
u
实时系统要求很高的可靠性。实时系统主要是对外部事件进行
处理和控制，例如导弹系统的控制，这样的系统不允许出现控
制错误。
u实时系统要求系统在出错时，既能够处理所发生的错误，又不
影响当前正在执行的用户应用。
4.6.1
实时系统的特点(
续)
68
上述特性要求实时操作系统具有下述能力：
(1)
很快的进程或线程切换速度
进程或线程切换速度是实时系统设计的核心。调
度算法的设计原则是满足所有硬实时任务的处理时限
和尽可能多地满足软实时任务的处理时限。
(2)
快速的外部中断响应能力
(3)
基于优先级的随时抢先式调度策略
4.6.1
实时系统的特点(
续)
69
基于优先级的调度策略大致有以下4
种。即：
①
优先级+
时间片轮转调度策略；
②
基于优先级的非抢先式调度策略；
③
基于优先级的固定点抢先式调度策略；
④
基于优先级的随时抢先式调度策略。
对于调度策略①来说，因为调度必须在时间片到来时才能发生，实时
进程必须等待占有处理机的进程执行到时间片结束时才能获得处理机。因
此，这种方法不能用作实时调度。同理，基于优先级的非抢先式调度策略
也不能用作实时调度，因为高优先级的实时进程，只有在当前执行进程自
动让出处理机之后，才能获得处理机。
基于优先级的固定点抢先式调度方式与基于优先级的随时抢先式调度
策略是实时系统的主要调度策略。基于优先级的固定点抢先式调度方式与
优先级+
时间片轮转调度方式有相似之处，其主要区别在于允许抢先的固
定点间隔要比时间片小得多，并保证能满足所有硬实时的处理时限。
4.6.1
实时系统的特点(
续)
70
[17]
把实时调度算法分为4
类，并介绍了时限调度算法和频率
单调调度算法。4
类实时调度算法：
(1)
静态表格驱动类
静态表格驱动类的实时调度算法，对可能的调度条件和
参数进行静态分析，并将分析结果作为实际调度结果。这类
调度方法多用于调度处理周期性任务，其主要分析参数为周
期，执行时间、周期行结束时限和任务优先级等。最早时限
优先法是比较典型的静态表格驱动算法。这里，最早时限优
先法是优先调度时限最早的任务获得处理机的调度方法。
(2)
静态优先级驱动抢先式调度算法类
该类算法也进行静态分析，不过，它们的静态分析不直
接产生调度结果，而只用来指定任务的优先级。频率单调调
度算法就是一种静态优先级驱动的抢先式调度算法。
4.6.2
实时调度算法的分类
71
(3)
动态计划调度算法类
动态计划调度算法在调度任务执行之前排出
调度计划，并分析计划的调度结果是否使得任务
所要求的处理时限得到满足。如果能够满足，则
按调度计划执行，否则修改调度计划。
(4)
尽力而为调度算法类
这一类算法不进行可能性分析，只对到达的
事件和相关任务指定相应的优先级，并进行调度。
尽力而为调度方式开销较小，实现容易。但是，
该算法不一定满足用户要求的处理时限。
4.6.2
实时调度算法的分类(
续)
72
时限调度算法是一种以满足用户要求的时限为调度原则
的算法。在实时系统中的用户要求时限有两种，即处理开始
时限和处理结束时限。时限调度算法可以使用任一种时限。
时限调度算法可用于周期性调度与非周期性调度两种。
时限调度算法所需要的相关输入信息包括以下几种：
(1)
任务就绪时间或事件到达时间
指的是进程进入就绪状态，可以被调度执行的时间。对
于周期性任务来说，该时间是可以预知的，而且时间间隔是
周期性的。对于非周期性任务来说，这些时间可能是可预知
的，但大部分时候是不可预知的，需要事件发生来驱动。
4.6.3
时限调度算法与频率单调调度算法
73
(2)
开始时限
处理机必须开始对任务进行处理的时限。
(3)
完成时限
指的是任务必须完成的时间
(4)
处理时间
完成相关任务所需占用处理机的时间。
(5)
资源需求
除了处理机之处，另外还需要的其他硬软件资源。如果所处理的任
务有处理机之外的其他资源需求，则调度算法要相对复杂得多。
(6)
优先级
可由分析计算后获得，也可根据时限要求，由用户指定。
时限调度算法的基本思想是：按用户的时限要求顺序设
置优先级，优先级高者占据处理机，也就是说，时限要求最
近的任务优先占有处理机。时限调度是抢先式的。抢先式时
限调度算法必须把新到达任务的时限要求和当前正在执行任
务的时限要求进行比较，如果新到达任务的时限要求更近，
则应执行新到达的任务。
4.6.3
时限调度算法与频率单调调度算法(
续)
74
下面是用时限调度算法调度周期性实时任务的例子。
设实时系统从两个不同的数据源DA
和D
Ｂ周期性地
收集数据并进行处理，其中DA
的时限要求以30 ms
为周
期，DB
的时限要求以75 ms
为周期。设DA
所需处理时
限为15 ms
，DB
所需处理时限为38 ms
，则与DA
和DB
有关进程的事件发生时限（就绪时限），执行时限以及
结束时限如图4.11
所示。(
见下页)
4.6.3
时限调度算法与频率单调调度算法(
续)
图4.11 75
周期性任务的预计发生、执行与结束时限
4.6.3
时限调度算法与频率单调调度算法(
续)
76
如果使用时限调度算法，并按最近结束时限优先级最高
的方法进行排列，可以给出图4.11
所示各进程的调度顺序和
相对时间。（如图4.12
）
图4.12
时限调度算法给出的调度顺序
4.6.3
时限调度算法与频率单调调度算法(
续)
77
如图4.12
所示，在开始时，进程DA
（1
）和DB
（1
）
的结束时限比较结果，DA
（1
）的结束时限最近，从而调
度进程DA
（1
）执行。DA
（1
）的实际结束时间为15
，小
于30
的时限要求。紧接着，进程DB
（1
）被调度执行。在
执行到时间为30 ms
时，进程DA
（2
）进入就绪状态。由
于DA
（2
）的结束时限为60
，近于DB
（1
）的结束时限
75
，从而DB
（1
）被DA
（2
）抢先。DA
（2
）的实际结束
时间为45
，小于要求时限60
。
在DA
（2
）结束之后，DB
（1
）再次占有处理机继续
执行，当DB
（1
）执行到时间为60 ms
时，进程DA
（3
）
进入就绪状态。但是，由于DA
（3
）的结束时限为90
，远
于DB
（1
）的结束时限75
，从而DB
（1
）继续执行。
4.6.3
时限调度算法与频率单调调度算法(
续)
78
时限调度算法也可以用于非周期性任务调度。
频率单调调度算法是一种被广泛用于多周期性实
时处理的调度算法。
频率单调调度算法的基本原理是频率越低（周期
越长）的任务的优先级越低。
另外，设任务周期为T
，任务的执行时间为C
，则
使用频率单调调度算法的必要条件是C
≤ T
。
4.6.3
时限调度算法与频率单调调度算法(
续)
79
已经证明，对于n(n
≥1)
个周期的不同任务来说，设每个
周期为T
i
，其相应任务的执行时间为C
i
，则使用频率单调调度
算法的充分条件是
例如，对于由3
个周期组成的实时任务序列来说，其执行时间
与周期之比应是：
如果进程执行时间与周期比之和大于n(2
1/n
-1)
，则用户
所要求的时限无法保证。
1
1 2 i n
n
1 2 i n
C C C C
+ + + + + n (2 - 1)
T T T T
£
L L
1
3
1 2
3
1 2 3
C
C C
+ + 3 (2 - 1 ) = 0 .7 9 9
T T T
£
4.6.3
时限调度算法与频率单调调度算法(
续)
80
CPU
是计算机系统中一个十分重要的资源，本章主
要介绍处理机的调度目标、策略以及评价方法等。
因为处理机调度程序不可能选择全部驻留在内存的
进程，因此，在调度一个进程占有处理机之前，系统必
须按某种策略把外存中处于后备状态的作业选择出来，
并创建进程和分配内存，为进程执行准备必需的资源。
这一步称为作业调度或高级调度。作业调度的目标是尽
量做到公平合理，能执行尽可能多的作业、尽快地响应
时间以及高的设备利用率等。任一调度算法要同时满足
这些调度目标是不可能的。大多数操作系统都是根据用
户需要而采用兼顾某些目标的方法。
本
章
小
结
81
比较常用的作业调度算法有：FCFS
方法、SJF
（最短作
业优先）法、HRN
（最高响应比）法等。这几种方法各有特
点。其中FCFS
法系统开销小，且对每个作业来说按其到达顺
序被依次调度。FCFS
法不利于短作业。SJF
法可得到最大系
统吞吐率，即每天处理的作业个数最多。但是SJF
法有可能使
长作业永远没有机会执行。HRN
法是介于FCFS
法和SJF
法之
间的一种方法。
除了作业调度之外，还介绍了一种称为交换调度的中级
调度。在有的系统中，把那些处于等待状态或就绪状态的进
程换出内存，而把那些等待事件已经发生或已在外存交换区
中等待了较长时间的进程换入内存。
本
章
小
结(
续)
82
只有在进程被建立起来并且已获得足够的资源之后，系
统才使用进程调度策略把处理机分配给选出进程。因此，处
理机的调度涉及到三个层次的调度。进程调度的主要任务是
选择一个合适的进程占据处理机。根据系统的要求不一样，
进程调度方法变化较大。比较常用的有RR
（轮转）法、
FCFS
（先来先服务）法、优先级法和SRR
（线性优先级）
法等。其中轮转法主要用于分时系统，它具有较好的响应时
间，且对每个进程来说都具有较好的公平性。FCFS
法不利
于执行时间短的进程，而SRR
法则是介于FCFS
法和RR
法之
间的一种进程调度方法。