第三章 处理机调度与死锁

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

1、处理机调度的层次

• 高级调度
  也叫长程调度或作业调度。选择外存中处于后备队列的哪个作业允许进入系统并创建进程。
• 低级调度
  也称短程调度、进程调度或CPU调度。选择就绪队列中哪个进程应获处理机。
  低级调度的功能：
  1）保存处理机的现场信息；
  2）按某种算法选取进程；
  3）把处理器分配给进程。
• 中级调度
  也称内存调度或中程调度。选择外村中哪些已具备运行条件的就绪进程再次调入内存，使其进入就绪状态。

2、进程调度中的三个基本机制
1）排队器；
2）分派器（分派程序）；
3）上下文切换机制

3、调度算法的目标

1）共同目标

• 资源利用率
• 公平性
• 平衡性
• 策略强制执行

2）批处理系统的目标

• 平均周转时间短
• 系统吞吐量高
• 处理机利用率高

3）分时系统目标

• 响应时间快
• 均衡性

4）实时系统目标

• 截止时间的保证
• 可预测性

3.2进程调度

1、CPU调度程序
调度程序从内存中就绪可执行的进程里选择一个，并为其中之一分配CPU。使用CPU调度程序的四种情况：
1）当一个进程从运行状态切换到等待状态
2）当一个进程从运行状态切换到就绪状态
3）当一个进程从等待状态切换到就绪状态
4）当一个 进程终止时
当调度只能发生在第一种和第四种两种情况时，称调度方法时非抢占的，否则调度方案就是可抢占的。
2、分派程序
分派程序是一个模块，用来将CPU的控制交给由短期调度程序所选择的进程。其功能包括：

• 切换上下文
• 切换到用户模式
• 跳转到用户程序的合适位置以重新启动这个程序

分派延迟：分派程序停止一个进程而启动另一个进程执行所要花费的时间
3、调度准则
1）面向用户的准则

• 周转时间短
• 响应时间快
• 截止时间的保证
• 优先权准则

2）面向系统的准则

• 系统吞吐量高
• 处理机利用率好
• 各类资源的平衡利用

4、调度算法
–First come first served (FCFS) （先来先服务调度）

CPU脉冲时间短的进程在CPU脉冲时间长的进程之后执行，FCFS调度算法是非抢占的;FCFS调度算法尤其不适合分时系统（原因：在分时系统中一个进程长时间占用处理机是不允许的）。由于所有其它进程都等待一个大进程释放CPU，就会产生护航效果。与可能允许较短进程先行相比，这种效果会导致CPU和设备的使用率变得更低

–Shortest job first (SJF) （短作业优先调度）

将每个进程与其下一个CPU脉冲相关联。当CPU为可用时，它会赋给具有最短后续CPU脉冲的进程，如果两个进程具有同样长度的CPU脉冲，那么可以使用FCFS调度来处理。SJF算法有两种方式：

• 非抢占式：一旦进程获得CPU就一直占据CPU，直到CPU脉冲完成为止
• 抢占式：如果一个新来的进程其CPU脉冲时间小于当前进程的CPU脉冲时间，则抢占之。这种调度方式成为最短剩余时间作业优先。

SJF是最佳的：对于给定的一组进程，SJF算法的平均等待时间最小。

–Priority scheduling （优先级调度）

常被用于批处理系统中，每个进程被赋予一个优先级数字（优先权），CPU分配给优先权高的进程（优先级数字越小，优先权越大），该算法存在的问题：饥饿，即低优先权的进程可能永远无法执行。解决方法：随着时间的推移，使进程的优先权逐渐提高。

–Round robin (RR) （时间片轮转调度）

轮转法是专门为分时系统而设计的。每个进程获得一小片CPU时间片，通常为10-100毫秒。时间片结束后，进程被抢占并放入到就绪队列的最后重新参加调度。如果就绪队列中有n个进程，时间片为q，则每个进程会得到1/n的CPU时间，每个长度不超过q时间单元。每个进程必须等待CPU的时间不会超过(n-1)q个时间单元，直到它的下一个时间片为止。

性能与时间片大小的关系：

• 如果时间片非常大（无限），那么RR策略与FCFS策略一样
• 如果时间片很小，那么RR方法称为处理器共享。n个进程对于用户来说都有它自己的处理器，速度各为真正处理器速度的1/n。

–Multilevel queue algorithm （多级队列调度）

就绪队列分成几个相对独立的队列

• 前台（或交互式）
• 后台（或批处理）

每个队列都有自己的调度算法

• 前台：RR
• 后台：FCFS

队列之间必须有调度，通常采用固定优先权可抢占调度来实现，另一种可能是在队列直接按划分时间片。每个队列都有一定的CPU时间，这可用于调度队列内的不同进程。

–Multilevel feedback queue algorithm （多级反馈队列调度）

进程可以在不同队列间移动，通常，多级反馈队列调度程序可由下列参数来定义：

• 队列数目
• 每个队列的调度算法
• 用来决定当进程需要服务时进入哪个队列的方法
• 用来决定提升或者降低进程优先级的方法

3.3实时调度

实时调度是为了完成实时处理任务而分配计算机处理器的调度方法，实时处理任务要求计算机在用户允许的时限范围内给出计算机的响应信号。实时处理任务可分为硬实时任务和软实时任务。

1、实现实时调度的基本条件

为了实现对实时进程进行有效调度，系统必须满足下述条件：

• 提供必要的信息：如就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级
• 调度方式，广泛采用抢占调度方式，特别是在实时要求严格的实时系统
• 具有快速切换机制
• 系统处理能力强

2、实时调度算法的分类

按照调度方式分为抢占方式和非抢占方式调度

1）非抢占方式调度

​ a）非抢占式轮转调度算法（数秒—数十秒）

​ b）非抢占式优先调度算法（数百毫秒—数秒）

2）抢占式调度

​ c）基于时钟中断的抢占式优先权调度算法（几十—几毫秒）

​ d）立即抢占的优先权调度算法（几毫秒—100微秒）

3、常用的实时调度算法

1）最早截至时间优先即EDF算法

根据任务的开始截止时间来确定任务的优先级。截至时间愈早，其优先级越高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截至时间的早晚排序。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。该算法既可适用于抢占式调度，也可适用于非抢占式调度

2）最低松弛度优先即LLF算法

算法根据任务紧急（或松弛）的程度。来确定任务的优先级。任务的紧急程度越高（开始截至时间或完成截止时间越早），为该任务所赋予的优先级就越高，以使之执行。当某进程的松弛度降为0时，则立刻抢占CPU执行。一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms。进程在就绪队列中按松弛度排序，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。

3.4死锁概述

所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，他们都将无法在向前推进。

1、产生死锁的原因

• 竞争资源
  • 可剥夺和非可剥夺性资源
  • 竞争非剥夺性资源
  • 竞争临时性资源
• 进程间推进顺序非法

2、死锁的特点

• 互斥条件：至少有一个资源必须处于非共享模式；即一次只有一个进程使用。如果另一个进程申请该资源，那么申请进程必须延迟直到该资源释放为止。
• 请求与保持：一个进程必须占有至少一个资源，并等待另一资源，而该资源为其他进程所占有。
• 不可剥夺性：资源不能被抢占；即只有进程完成其任务后，才会释放其资源。
• 环路等待：有一组进程{P0, P1,…, Pn}，P0等待的资源为P1所占有，P1等待的资源为P2所占有，Pn-1等待的资源为Pn所占有，Pn等待的资源为P0所占有。

3、预防死锁

​ 出现死锁有四个必要条件，只要确保至少一个必要条件不成立，就能预防死锁发生。

互斥条件—通常不能通过否定互斥条件来预防死锁。有些资源本身是非共享的。

请求与保持—当一个进程申请一个资源时，它不能占有其他资源。

• 执行前申请并获得所有资源
• 申请其他资源之前，必须释放其现在已分配的并且是已用毕的所有资源
• 资源利用率可能比较低，可能发生饥饿

不可剥夺性

• 如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都被抢占。
• 通常应用于其状态可以保存和恢复的资源，如CPU寄存器和内存空间，不能适用于其他资源如打印机和磁带驱动器。

环路等待

• 对所有资源进行完全排序，且要求每个进程按递增顺序来申请资源

3.5避免死锁

1、安全状态

当一个进程申请一个可用资源的时候，系统必须决定这次分配是否会使系统处在一种安全状态。

如果存在所有进程的一种安全序列，则系统是安全的。进程序列<P1, P2, …, P**n>，如果对于每个Pi，Pi申请的资源小于等于当前可用资源加上所有进程Pj（其中j < i）所占有的资源，那么这一序列为安全序列。如果没有这样的序列存在，则系统状态就处于不安全。

如果系统中的所有进程存在一个安全序列，则该系统处于安全状态。

• 如果进程Pi所需要的资源不能立刻使用，那么Pi可以等待直到所有Pj完成释放其资源。
• 当Pj完成时，Pi可得到它所需要的所有资源，并执行，完成其给定任务，返回其所分配的资源并终止。
• 当Pi完成时，Pi+1可得到它所需要的所有资源，如此进行。

2、避免死锁

如果系统是安全的，则不会死锁

如果系统不安全，可能会发生死锁

• May be YES
• May be NO

死锁避免：确保系统永远不会进入不安全状态

两种算法

• 资源分配图算法（每个资源类型拥有一个资源实例）
• 银行家算法（每个资源类型拥有多个资源实例）

3、银行家算法

3.6死锁的检测与解除

1、死锁检测

如果系统既不采取死锁预防算法，也不采用死锁避免算法，那么可能会出现死锁

• 检测算法：一个用来检查系统状态从而确定是否出现了死锁的算法
• 恢复算法：一个用来从死锁状态中恢复的算法

1）两种检测算法

• 等待图

a)从资源分配图中，删除所有资源类型节点，合并适当边，就可以得到等待图。

i)节点表示进程

ii)Pi->Pj表示Pi等待Pj释放一个Pi所需的资源

b)周期性地调用在图中进行搜索的算法

c)从图中检测环的算法需要n^2级别操作，其中n为图中的节点数。

d)数据结构

i)Available：长度为m的向量，表示各种资源的可用实例

ii)Allocation：n×m矩阵，表示当前各进程的资源分配情况

iii)Request：n×m矩阵，表示当前各进程的资源请求情况。如果Request[i, j] = k, 那么Pi现在需要k个资源Rj

• 检测算法

2）应何时调用检测算法，取决于两个因素：

• 死锁可能发生的频率是多少？
• 当死锁发生时，有多少进程会受影响？

3）当某个进程提出请求且得不到满足时，才会出现死锁，这时可以调用死锁检测算法。

• 但死锁后的每一个请求都会造成死锁。因此，可能需要对于之后的每个请求都调用死锁检测算法，但会引起相当的计算开销。

4）只是在一个不频繁的时间间隔里调用检测算法，如每小时一次或当CPU使用率低于40%时。

• 在不定的时间点调用检测算法，通常不能确定死锁进程中是哪些引起了死锁。

2、死锁恢复

死锁恢复的两种方式：进程终止、资源抢占。

1）进程终止

a)有两种方法通过终止进程以取消死锁

• 终止所有进程
• 一次只终止一个进程直到取消死锁循环为止

b)确定终止哪个进程或哪些进程可以打破死锁需要考虑的因素

• 进程的优先级是什么？
• 进程已计算了多久，进程在完成其指定任务之前还需要多久？
• 进程使用了多少什么类型的资源（是否容易抢占？）
• 进程需要多少资源以完成？
• 多少进程需要被终止？
• 进程是交互的还是批处理的？

2）资源抢占

• 选择一个牺牲品
• 回滚——必须将被抢占进程的状态恢复到某个安全状态
• 饥饿——如何保证资源不会总是从同一个进程被抢占