计算机操作系统——调度与死锁

第三章 处理机调度与死锁

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

3.1.1 处理机调度层次

1. 高级调度(High Level Scheduling)
   又称为作业调度或长程调度，它的调度对象是作业。
   根据某种算法，将外存上处于后备队列中的哪几个作业调入内存。

2. 低级调度(Low Level Scheduling)

   又称为进程调度或短程调度，它的调度对象是进程(或内核级线程)。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的 OS 中，都必须配置这级调度。
   根据某种算法，决定就绪队列中的哪个进程获得处理机。

3. 中级调度(Intermediate Scheduling)

   又称为内存调度。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。实际上就是存储器管理中的对换功能。
   将暂时不能运行的进程调至外存等待，此时进程状态称为就绪驻外存状态(或挂起状态)。将外存上具备运行条件的就绪进程再调入内存，修改状态为就绪状态，挂在就绪队列上等待。

3.1.2 处理机调度算法目标

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

1. 资源利用率
2. 公平性
3. 平衡性
4. 策略强制执行

2、批处理系统的目标

1. 平均周转时间短

   周转时间：指从作业被提交给系统开始，到作业完成为止的这段时间间隔，称为作业周转时间。

   平均周转时间：N条作业从提交到结束的时间之和除以N。

   \[T=\frac{1}{n}[\sum_{i=1}^nT_i] \]

   带权周转时间：指作业的周转时间 T 与系统为它提供服务的时间 T_s 之比，即 W = T/T_s。

   平均带权周转时间：N条作业从提交到结束的时间与其对应每条作业运行时间之比除以N。

   \[W=\frac{1}{n}[\sum_{i=1}^n\frac{T_i}{T_s}] \]

2. 系统吞吐量高

   吞吐量：指在单位时间内系统所完成的作业数，它与批处理作业的平均长度有关。
   如果单纯为获得高的系统吞吐量，应尽量多地选择短作业运行。

3. 处理机利用率高

   如果单纯为使处理机利用率高，应尽量多地选择计算量大的作业运行。

3、分时系统的目标

1. 响应时间快

   响应时间：从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为止的一段时间间隔。

2. 均衡性

   均衡性：指系统响应时间的快慢应与用户请求服务的复杂性相适应。

4、实时系统目标

1. 截止时间保证

   截止时间：指某任务必须开始执行的最迟时间，或必须完成的最迟时间。

2. 可预测性

3.2 作业与作业调度

在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。

3.2.1 批处理系统中的作业

1、作业和作业步

• 作业(Job) ：不仅包含通常的程序和数据，还应配有一份作业说明书。
• 作业步(Job Step)

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

为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。

JCB包含内容：作业标识、用户名称、用户账号、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使用情况等。

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

• 三个阶段：收容阶段、运行阶段、完成阶段。

• 三种状态：后备状态、运行状态、完成状态。

3.2.3 先来先服务（FCFS）和短作业优先（SJF）调度算法

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

FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。

实现：

每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才将处理机分配给其他进程。

缺点：不利于短作业和 I/O 型作业的运行。

• 短作业优先（short job first，SJF)的调度算法

SJF以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。该算法可以分别用于作业调度和进程调度。

实现：

在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行。

缺点：

1. 必须预知作业的运行时间。
2. 对长作业非常不利。
3. 人-机无法实现交互。
4. 未考虑作业的紧迫程度，不能保证紧迫性作业能得到及时处理。

3.2.4 优先级调度算法(PSA)和高响应比优先调度算法(HRRN)

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

对于FCFS调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级越高。
对于SJF调度算法，作业的长短就是作业的优先级，作业所需运行的时间越短，其优先级越高。
但上述两种优先级都不能反映作业的紧迫程度。

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

实现：

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

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

特点：该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期
得不到服务。但在进行调度之前，须先做响应比的计算，这会增加系统开销。

3.3 进程调度

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

1、进程调度任务

1. 保存处理机的现场信息
2. 按某种算法选取进程
3. 把处理器分配给进程

2、进程调度机制

1. 排队器
2. 分派器
3. 上下文切换器

3、进程调度方式

1. 非抢占方式

特点：实现简单，系统开销小，适用于大多数批处理系统，但不能用于实时系统和大多数分时系统。

2. 抢占方式

在现代OS中广泛采用，原因：

1. 批处理系统：可以防止一个长进程长时间占用处理机
2. 分时系统：只有采用抢占方式才有可能实现人-机交互
3. 实时系统：能满足实时任务的需求

特点：抢占方式比较复杂，所需系统开销较大。

抢占原则

1. 优先权原则
2. 短进程优先原则
3. 时间片原则

3.3.2 轮转调度算法(RR)

在分时系统中，最简单也较常用的是基于时间片的轮转(round robin，RR)调度算法。

基本原理

让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有n个进程，则每个进程每次大约都可获得 1/n 的处理机时间。

进程切换时机

1. 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
2. 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

时间片大小的确定

时间片的大小对系统性能有很大影响：

• 时间片很小，将有利于短作业；但会频繁地执行进程调度和进程上下文的切换，增加系统开销。
• 时间片太长，为使每个进程在一个时间片内完成，RR算法会退化为FCFS算法，无法满足短作业和交互式用户需求。
• 一个较为可取的时间片大小是略大于一次典型的交互所需时间，使大多数进程能在一个时间片内完成。

3.3.3 优先级调度算法*

优先级调度算法，是把处理机分配给就绪队列中优先级最高的进程。

分类

1. 非抢占式优先级调度算法
2. 抢占式优先级调度算法

优先级类型

1. 静态优先级
2. 动态优先级

3.3.4 多队列调度算法*

将系统进程的就绪队列拆分为若干个，不同就绪队列可采用不同的调度算法，一个就绪队列中的进程可设置不同优先级，不同就绪队列本身也可设置不同优先级。

3.3.5 多级反馈队列(multileved feedback queue)调度算法

不必事先知道进程所需执行时间，还可以较好满足各种类型进程需要，是目前公认的一种较好的进程调度算法。

调度机制

1. 设置多个就绪队列。第一个队列优先级最高，第二个次之，其余队列的优先权逐个降低。优先级愈高，时间片愈小。
2. 每个队列都采用FCFS算法。最后第n队列采取RR方式运行。
3. 按队列优先级调度。如果处理机正在第 i 队列中为某进程服务时，又有新进程进入优先级较高的队列，此时须立即把正在运行的进程放回第i队列末尾，转而运行优先级高的队列。

3.3.6 基于公平原则的调度算法*

1. 保证调度算法
2. 公平分享调度算法

3.4 实时调度

3.4.1 实现实时调度基本条件

1. 提供必要的信息

2. 系统处理能力强

   假定系统中有m个周期性的硬实时任务HRT，它们的处理时间可表示为\(C_i\)，周期时间表示为\(P_i\)，则在单处理机情况下，必须满足下面的限制条件时系统才是可调度的：

   \[\sum_{i=1}^m\frac{C_i}{P_i}\leq1 \]

3. 采用抢占式调度机制

4. 具有快速切换机制

3.4.2 实时调度算法分类

1. 按实时任务性质：
   硬实时调度算法、软实时调度算法
2. 按调度方式：
   非抢占调度算法、抢占调度算法
3. 按非抢占式调度：
   非抢占式轮转调度算法、非抢占式优先调度算法
4. 按抢占式调度：
   基于时钟中断的抢占式优先级调度算法、立即抢占的优先级调度算法

3.4.3 最早截止时间优先EDF(Earliest Deadline First)算法

该算法是根据任务的截止时间确定任务的优先级。任务的截止时间愈早，其优先级愈高，具有最早截止时间的任务排在队列的队首。

最早截止时间优先算法既可用于抢占式调度，也可用于非抢占式调度方式中。

1. 非抢占式调度方式用于非周期实时任务
   

2. 抢占式调度方式用于周期实时任务
   最早截止时间优先算法用于抢占调度方式之例：

   

3.4.4 最低松弛度优先LLF(Least Laxity First)算法

该算法在确定任务的优先级时，根据的是任务的紧急(或松弛)程度。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行。

例如：一个任务在200ms时必须完成，而它本身所需的运行时间是100ms，因此调度程序必须在100ms之前调度执行，该任务的紧急程度(松弛程度)为100ms。

最低松弛度优先算法主要用于可抢占调度方式中。

实现方法：

假如在一个实时系统中有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms，任务B要求每 50 ms执行一次，执行时间为 25 ms.由此可知，任务A和B每次必须完成的时间分别为：A1、A2、A3、…和B1、B2、B3、…，见下图。

t1 = 0 ms:：A1松弛度为10 ms，B1松弛度为25 ms
t2 = 10 ms：A2松弛度为20 ms，B1松弛度为15 ms
t3 = 30 ms：A2松弛度为 0 ms，B1松弛度为15 ms
t4 = 40 ms：A3松弛度为10 ms，B1松弛度为 5 ms
t5 = 45 ms：A3松弛度为 5 ms，B2松弛度为30 ms
t6 = 55 ms：任务A尚未进入第4周期，调度B2执行
t7 = 70 ms：A4松弛度为0 ms，B2松弛度为20 ms

3.4.5 优先级倒置*

略

3.5 死锁概述

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

3.5.1 资源问题

1. 可重用性资源和消耗性资源
   • 可重用性资源是一种可供用户重复使用多次的资源。
   • 消耗性资源又称为临时性资源，是在进程运行期间由进程动态地创建和消耗的资源。
2. 可抢占资源和不可抢占资源
   • 可抢占资源是指某进程在获取这类资源后，该资源可以再被其他进程或系统抢占。
   • 不可抢占资源是指一旦系统把某资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。

3.5.2 死锁原因

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

   • 资源分配图：
     方块代表资源，圆圈代表进程，从进程指向资源的箭头表示请求资源，从资源指向进程的箭头表示已分配资源。

   

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

   

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

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

定义

如果一组进程中每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的(Deadlock)。

必要条件

1. 互斥条件
2. 请求和保持条件
3. 不可抢占条件
4. 循环等待条件

处理方法

1. 预防死锁
2. 避免死锁
3. 检测死锁
4. 解除死锁

4种方法对死锁的防范程度逐渐削弱，但对应的是资源利用率的提高，以及进程因资源因素而阻塞的频度下降(即并发程度提高)。

3.6 预防死锁

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

3.6.1 破坏”请求和保持”条件

方法：为了能破坏“请求和保持”条件，系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源。

1. 第一种协议

   规定：所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。

   优点：简单、易行和安全。

   缺点：1. 资源被严重浪费，严重恶化了资源的利用率。2. 使进程经常会发生饥饿现象。

2. 第二种协议

   是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后便开始运行。运行过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。

3.6.2 破坏“不可抢占”条件

方法：为了能破坏“不可抢占”条件，协议中规定：当一个已经保持了某些不可被抢占资源的进程提出新的资源请求而不能得到满足时，必须释放已经保持的所有资源，待以后需要时再重新申请。

特点：该方法实现起来比较复杂，且需付出很大的代价。还可能因为反复申请和释放资源致使进程的执行被无限推迟，延长了进程的周转时间、增加了系统开销、降低了系统吞吐量。

3.6.3 破坏“循环等待”条件

方法：一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。

优点：资源利用率和系统吞吐量都有较明显的改善。

缺点：

1. 因系统规定的序号须稳定，限制了新类型设备的增加。
2. 可能因作业使用各类资源的顺序与系统规定顺序不同而造成资源浪费。
3. 会限制用户简单、自主地编程。

3.7 避免死锁

避免死锁属于事先预防策略，是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。该方法施加的限制条件较弱，可能获得较好的系统性能，目前常用此方法来避免死锁。

3.7.1 系统安全状态

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

避免死锁的实质：系统在进行资源分配时，应使系统不进入不安全状态。

安全状态 & 安全序列

安全状态是指系统能按某种进程推进顺序(P1，P2，…，Pn)为每个进程 Pi分配其所需资源，直至满足每个进程对资源的最大需求， 使每个进程都可顺利地完成。此时称〈P1，P2，…，Pn〉为安全序列。

3.7.2 利用银行家算法避免死锁

数据结构

i —>进程 ，j —>资源

1. 可利用资源向量 Available

   一个含有 m 个元素的数组，每个元素代表一类可利用的资源数目。初始值是系统中所配置的该类全部可用资源的数目，数值随该类资源的分配和回收而动态改变。

   Available[j]=K，表示系统中现有 Rj 类资源 K 个。

2. 最大需求矩阵 Max

   一个 n×m 的矩阵，定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。
   Max[i,j]=K，表示进程 i 需要 Rj 类资源的最大数目 K。

3. 分配矩阵 Allocation

   一个 n×m 的矩阵，定义了系统中每类资源当前已分配给每一进程的资源数。
   Allocation[i,j]=K，表示进程 i 当前已分得 Rj 类资源的数目 K。

4. 需求矩阵 Need

   一个 n×m 的矩阵，表示每一个进程尚需的各类资源数。
   Need[i,j]=K，表示进程 i 还需要 Rj 类资源 K 个。

   三个矩阵的关系：

   \[Need[i,j]=Max[i,j]-Allocation[i,j] \]

银行家算法

Request_i 是进程 Pi 的请求向量。Request_i[j] = K，表示进程 Pi 需要 K 个 Rj 类型的资源。

Pi 发出资源请求后，检查步骤如下：

1. 如果 Request_i[j]≤Need[i,j]，便转向步骤2；否则认为出错

2. 如果 Request_i[j]≤Available[j]，便转向步骤3；否则 Pi 等待

3. 系统试探着把资源分配给进程 Pi，并修改数值：

   Available[j] = Available[j] – Request_i[j];
   Allocation[i,j] = Allocation[i,j] + Request_i[j];
   Need[i,j] = Need[i,j] – Request_i[j];

4. 系统执行安全性算法。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则，本次试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。

3.8 死锁的检测与解除

3.8.1 死锁的检测

资源分配图(Resource Allocation Graph)

系统死锁可利用资源分配图来描述。该图是由一组结点 N 和一组边 E 所组成的一个对偶 G=(N, E)，其定义和限制如下：

1. N 分为两个互斥的子集，即一组进程结点 P={p1，p2，…，pn}和一组资源结点 R={r1，r2，…，rn}，N=P∪R。
2. 凡属于 E 中的一个边 e∈E，都连接着 P 中的一个结点和 R 中的一个结点。
   e={Pi, Rj} 是资源请求边，由进程 Pi 指向资源 Rj，表示进程 Pi 请求一个单位的 Rj 资源。
   e={Rj, Pi}是资源分配边，由资源 Rj 指向进程 Pi，表示把一个单位的资源 Rj 分配给进程 Pi。
3. 用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。

死锁定理

利用把资源分配图加以简化的方法来检测死锁。

简化方法：

1. 在资源分配图中，找出一个既不阻塞又非独立的进程结点 Pi。消去 Pi 的请求边和分配边，使之成为孤立的结点。
2. 进行一系列简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。
   

S 为死锁状态的充分条件是：当且仅当 S 状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。

3.8.2 死锁的解除

措施

1. 人工方式解除死锁
   最简单措施是立即通知操作员，请操作员来以人工方法处理。
2. 利用死锁解除算法解除死锁
   1. 抢占资源
   2. 终止(或撤消)进程

终止进程方法

1. 终止所有死锁进程
2. 逐个终止进程

考虑因素

1. 进程优先级大小
2. 进程已执行时间、仍需时间
3. 进程已使用资源量、仍需资源量
4. 进程性质（交互式 / 批处理式）

原文地址：http://www.cnblogs.com/0dot7/p/16879205.html