第三章处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标
3.2 作业与作业调度
3.3 进程调度
3.4 实时调度
3.5 死锁概述
3.6 预防死锁
3.7 避免死锁
3.8 死锁的检测与解除

3.1 处理机调度的层次和调度算法的目标

在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理机调度算法是指根据处理机分配策略所规定的处理机分配算法。在多道批处理系统中，一个作业从提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度，下面先来了解处理机调度的层次。

处理机调度的层次

1. 高级调度(High Level Scheduling)

2. 低级调度(Low Level Scheduling)

3. 中级调度(Intermediate Scheduling)

处理机调度算法的目标

1. 处理机调度算法的共同目标

(1) 资源利用率。为提高系统的资源利用率，应使系统中的处理机和其它所有资源都尽可能地保持忙碌状态，其中最重要的处理机利用率可用以下方法计算：

CPU利用率  =  CPU有效工作时间    /     (CPU有效工作时间  +  CPU空闲时间)

(2) 公平性。公平性是指应使诸进程都获得合理的CPU 时间，不会发生进程饥饿现象。公平性是相对的，对相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度或重要性的不同，则应提供不同的服务。

(3) 平衡性。由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的平衡性。

(4) 策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。

2. 批处理系统的目标

(1) 平均周转时间短。

对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。应使作业周转时间和作业的平均周转时间尽可能短。否则，会使许多用户的等待时间过长，这将会引起用户特别是短作业用户的不满。可把平均周转时间描述为：

周转时间：从进程提交开始，到完成为止这段时间间隔（仅考虑进程在就绪队列上的等待时间和进程在CPU上的执行时间）；  

平均周转时间：所有进程的周转时间之和除以进程总数；

为了进一步反映调度的性能，更清晰地描述各进程在其周转时间中，等待和执行时间的具体分配状况，往往使用带权周转时间，即作业的周转时间T与系统为它提供服务的时间Ts之比，即W = T/Ts。而平均带权周转时间则可表示为：

带权周转时间：进程的周转时间除以系统为它服务的时间； 

平均带权周转时间：所有进程的带权周转时间之和除以进程总数。  

//第一个进程，开始时间 = 到达时间
//开始时间 = 上一个进程的完成时间
//完成时间 = 开始时间 + 服务时间
//周转时间 = 完成时间 - 到达时间
//带权周转时间 = 周转时间 / 服务时间

(2) 系统吞吐量高。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度有关。事实上，如果单纯是为了获得高的系统吞吐量，就应尽量多地选择短作业运行。

(3) 处理机利用率高。对于大、中型计算机，CPU价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法又对处理机的利用率起着十分重要的作用。如果单纯是为使处理机利用率高，应尽量多地选择计算量大的作业运行。由上所述可以看出，这些要求之间是存在着一定矛盾的。

3. 分时系统的目标

(1) 响应时间快。

(2) 均衡性。 

4. 实时系统的目标

(1) 截止时间的保证。

(2) 可预测性。 

3.2 作业与作业调度

在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作业通过相应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。再由作业调度程序将其从外存调入内存。

批处理系统中的作业

1. 作业和作业步

(1) 作业(Job)。

(2) 作业步(Job Step)。

2. 作业控制块(Job Control Block，JCB)

为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。通常在JCB中包含的内容有：作业标识、用户名称、用户账号、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使用情况等。

3. 作业运行的三个阶段和三种状态

作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有“后备状态”、“运行状态”和“完成状态”。

(1) 收容阶段。

(2) 运行阶段。

(3) 完成阶段。 

作业调度的主要任务 

作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。因此，也把作业调度称为接纳调度(Admission Scheduling)。在每次执行作业调度时，都需做出以下两个决定。

1. 接纳多少个作业

2. 接纳哪些作业

常用进程调度算法

先来先服务(FCFS)和短作业优先(SJF)调度算法  

1. 先来先服务(first-come first-served，FCFS)调度算法

FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。

2. 短作业优先(short job first，SJF)的调度算法

由于在实际情况中，短作业(进程)占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。

1) 短作业优先算法

SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。

2) 短作业优先算法的缺点

SJF调度算法较之FCFS算法有了明显的改进，但仍然存在不容忽视的缺点：

(1) 必须预知作业的运行时间。在采用这种算法时，要先知道每个作业的运行时间。即使是程序员也很难准确估计作业的运行时间，如果估计过低，系统就可能按估计的时间终止作业的运行，但此时作业并未完成，故一般都会偏长估计。

(2) 对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。

(3) 在采用FCFS算法时，人—机无法实现交互。

(4) 该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。

优先级调度算法和高响应比优先调度算法

1. 优先级调度算法(priority-scheduling algorithm，PSA)

我们可以这样来看作业的优先级，对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。对于短作业优先调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高，优先将它们调入内存运行。但上述两种优先级都不能反映作业的紧迫程度。 

2. 高响应比优先调度算法(Highest Response Ratio Next，HRRN) 

在批处理系统中，FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而SJF算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法则是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长作业的等待时间过长，从而改善了处理机调度的性能。

高响应比优先算法是如何实现的呢? 

如果我们能为每个作业引入一个动态优先级，即优先级是可以改变的，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可描述为：

优先权  =  （等待时间  + 要求服务时间）  /   要求服务时间

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比Rp。据此，优先又可表示为：

优先权Rp  = （等待时间 + 要求服务时间） /  要求服务时间  =  响应时间 /  要求服务时间 

3.3 进程调度

进程调度是OS中必不可少的一种调度。因此在三种类型的OS中，都无一例外地配置了进程调度。此外它也是对系统性能影响最大的一种处理机调度，相应的，有关进程调度的算法也较多。

进程调度的任务、机制和方式

1. 进程调度的任务

进程调度的任务主要有三：

(1) 保存处理机的现场信息。

2) 按某种算法选取进程。

(3) 把处理器分配给进程。 

2. 进程调度机制

为了实现进程调度，在进程调度机制中，应具有如下三个基本部分

(1) 排队器。

(2) 分派器。

(3) 上下文切换器。 

进程调度机制

3. 进程调度方式

1) 非抢占方式(Nonpreemptive Mode)

在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻塞时，才把处理机分配给其它进程。

2) 抢占方式(Preemptive Mode)

这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。在现代OS中广泛采用抢占方式，这是因为：

在批处理机系统，可以防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。
在分时系统中，只有采用抢占方式才有可能实现人—机交互。
在实时系统中，抢占方式能满足实时任务的需求。但抢占方式比较复杂，所需付出的系统开销也较大。

轮转调度算法

1. 轮转法的基本原理

在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间(如30 ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。

2. 进程切换时机

在RR调度算法中，应在何时进行进程的切换，可分为两种情况：

① 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。

② 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

3. 时间片大小的确定

在轮转算法中，时间片的大小对系统性能有很大的影响。 

图3-2示出了时间片大小对响应时间的影响，其中图(a)是时间片略大于典型交互的时间，而图(b)是时间片小于典型交互的时间。图3-3示出了时间片分别为q = 1和q = 4时对平均周转时间的影响。 

图3-2 时间片大小对响应时间的影响

图3-3 q = 1和q = 4时进程的周转时间

优先级调度算法

1. 优先级调度算法的类型

优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。这时，又可进一步把该算法分成如下两种。

(1) 非抢占式优先级调度算法。

(2) 抢占式优先级调度算法。 

2. 优先级的类型

1) 静态优先级

静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如0～255中的某一整数，又把该整数称为优先数。确定进程优先级大小的依据有如下三个：

(1) 进程类型。

(2) 进程对资源的需求。

(3) 用户要求。

2) 动态优先级

动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。 

多队列调度算法

如前所述的各种调度算法，尤其在应用于进程调度时，由于系统中仅设置一个进程的就绪队列，即低级调度算法是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求，在多处理机系统中，这种单一调度策略实现机制的缺点更显突出，由此，多级队列调度算法能够在一定程度上弥补这一缺点。

3.4 实时调度

在实时系统中，可能存在着两类不同性质的实时任务，即HRT任务和SRT任务，它们都联系着一个截止时间。为保证系统能正常工作，实时调度必须能满足实时任务对截止时间的要求。为此，实现实时调度应具备一定的条件。

3.5 死锁概述

资源问题

在系统中有许多不同类型的资源，其中可以引起死锁的主要是，需要采用互斥访问方法的、不可以被抢占的资源，即在前面介绍的临界资源。系统中这类资源有很多，如打印机、数据文件、队列、信号量等。

1. 可重用性资源和消耗性资源

1) 可重用性资源

可重用性资源是一种可供用户重复使用多次的资源，它具有如下性质：

(1) 每一个可重用性资源中的单元只能分配给一个进程使用，不允许多个进程共享。

(2) 进程在使用可重用性资源时，须按照这样的顺序：

① 请求资源。如果请求资源失败，请求进程将会被阻塞或循环等待。

② 使用资源。进程对资源进行操作，如用打印机进行打印；

③ 释放资源。当进程使用完后自己释放资源。

(3) 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它。

2) 可消耗性资源

可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态地创建和消耗的，它具有如下性质：

① 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有许多，有时可能为0；

② 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目。

③ 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中。 

2. 可抢占性资源和不可抢占性资源

1) 可抢占性资源

可把系统中的资源分成两类，一类是可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占。

2) 不可抢占性资源

另一类资源是不可抢占性资源，即一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。 

计算机系统中的死锁

1. 竞争不可抢占性资源引起死锁

通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。 

图3-12　共享文件时的死锁情况 

2. 竞争可消耗资源引起死锁

现在进一步介绍竞争可消耗资源所引起的死锁。图3-13示出了在三个进程之间，在利用消息通信机制进行通信时所形成的死锁情况。 

图3-13 进程之间通信时的死锁

3. 进程推进顺序不当引起死锁

除了系统中多个进程对资源的竞争会引发死锁外，进程在运行过程中，对资源进行申请和释放的顺序是否合法，也是在系统中是否会产生死锁的一个重要因素。 

死锁的定义、必要条件和处理方法

1. 死锁的定义

在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占有的资源。

2. 产生死锁的必要条件

虽然进程在运行过程中可能会发生死锁，但产生进程死锁是必须具备一定条件的。综上所述不难看出，产生死锁必须同时具备下面四个必要条件，只要其中任一个条件不成立，死锁就不会发生：

(1) 互斥条件。

(2) 请求和保持条件。

(3) 不可抢占条件。

(4) 循环等待条件。

3. 处理死锁的方法

目前处理死锁的方法可归结为四种：

(1) 预防死锁。

(2) 避免死锁。

(3) 检测死锁。

(4) 解除死锁。

3.6 预防死锁

预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁。由于互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要是破坏产生死锁的后三个条件。

3.7 避免死锁

避免死锁同样是属于事先预防的策略，但并不是事先采取某种限制措施，破坏产生死锁的必要条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加的限制条件较弱，可能获得较好的系统性能，目前常用此方法来避免发生死锁。

系统安全状态 

在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。

1. 安全状态

在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。 

2. 安全状态之例

假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：

3. 由安全状态向不安全状态的转换

如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。 

利用银行家算法避免死锁

最有代表性的避免死锁的算法是Dijkstra的银行家算法。起这样的名字是由于该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS中也可用它来实现避免死锁。

银行家算法之例

假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。

(1)  T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(如图3-16所示)可知，在T0时刻存在着一个安全序列{P1, P3, P4, P2, P0}，故系统是安全的。

(2)  P1请求资源：P1发出请求向量Request1(1, 0, 2)，系统按银行家算法进行检查：

① Request1(1, 0, 2)≤Need1(1, 2, 2)；

② Request1(1, 0, 2)≤Available1(3, 3, 2)；

③ 系统先假定可为P1分配资源，并修改Available，Allocation1和Need1向量，由此形成的资源变化情况如图3-15中的圆括号所示；

④ 再利用安全性算法检查此时系统是否安全，如图3-17所示。

图3-17 P1申请资源时的安全性检查

(3)  P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：

① Request4(3，3，0)≤Need4(4，3，1)；

② Request4(3，3，0)＞Available(2，3，0)，让P4等待。

(4)  P0请求资源：P0发出请求向量Request0(0，2，0)，系统按银行家算法进行检查：

① Request0(0，2，0)≤Need0(7，4，3)；

② Request0(0，2，0)≤Available(2，3，0)；

③ 系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。

图3-18 为P0分配资源后的有关资源数据

(5) 进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

3.8 死锁的检测与解除 

如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁。在这种情况下，系统应当提供两个算法：

① 死锁检测算法。该方法用于检测系统状态，以确定系统中是否发生了死锁。

② 死锁解除算法。当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

死锁的检测 

为了能对系统中是否已发生了死锁进行检测，在系统中必须：

① 保存有关资源的请求和分配信息；

② 提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。