第三章：处理机调度和死锁

1、处理机调度概述

处理机调度：按照一定的算法，从就绪队列中选择一个进程将处理机分配给它运行，以实现进程并发地执行。

1.1、处理机调度的层次

一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历的三级调度：

1.2、高级调度

High Level Scheduling、又称作业调度、长程调度、接纳调度

分时系统、实时系统一般直接进入内存，无此环节。

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则，来决定将作业调入内存的顺序。

作用：按照一定的调度算法，从外存后备队列中选择作业调入内存，创建PCB等，插入就绪队列（内存资源的角度）
使用的系统：批处理系统
调度时要决定：
- 接纳作业数：取决于多道程序度。
- 接纳策略：取决于作业调度算法。
调度时机：有作业退出系统或者系统负荷不足时
执行频率：几分钟、几秒钟。

1.3、低级调度

Low Level Scheduling、又称进程调度、短程调度

作用：按某种规则，决定就绪队列中的某个进程获得处理机，由分派程序（Dispatcher）实施处理机分派。（CPU资源角度）
使用系统：各种系统均需要。
调度时要解决：
- What：按照什么原则分配CPU？进程调度算法
- When：什么时候引发进程调度、分配CPU？进程调度的时机
- How：如何分配CPU？进程调度过程
执行频率：几十毫秒一次。

1、抢占方式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将处理机重新分配给另一个进程。

优点：

防止一个长进程长时间占用处理机
为大多数进程提供更公平的服务
能满足对实时任务的需求

2、非抢占方式：一旦把处理机分配给某个进程后，一直让它运行下去，直至该进程完成，资源释放处理机，或被阻塞。

1.4、中级调度

Intermediate-Level Scheduling、中程调度

对象：外存中因暂时不能运行而被挂起（就绪挂起和阻塞挂起）的进程
动作：将外存挂起的进程激活，调入内存，进入就绪队列
目的：提高内存的利用率和系统吞吐量。

注意

三种调度运行频率：低级调度 > 中级调度 > 高级调度

进程调度（低级调度）在操作系统中必不可少。

2、选择调度算法的准则

2.1、面向用户的准则

	针对的系统
周转时间短（short turnaround time）	批处理系统
响应时间快（quick response time）	分时系统
截止时间的保证（guaranteed deadline）	实时系统
优先权原则（priority priciple）	各种OS

1、周转时间：从作业提交系统到完成为止

时间包括：

驻外存等待作业调度时间
驻内存等待进程调度时间（可能执行多次）
执行时间（可能执行多次）
阻塞时间（可能执行多次）

计算机系统要求的是：平均周转时间最短（mean turnaround time）

2、响应时间：从用户通过键盘提交一个请求开始，到系统首次产生响应（屏幕显示结果）为止的时间。是评价分时系统的一个重要指标。

输入传送到CPU的时间
处理的时间
结果回送到显示器的时间

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

评价实时系统性能的一个重要指标。

2.2、面向系统的准则

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

1、系统吞吐量：单位时间内系统所完成的作业数。

评价批处理系统性能的重要指标

处理的长作业多，则吞吐量低

3、先来先服务和短作业（进程）调度算法

先来先服务（FCFS, First Come First Serve）是最简单的调度算法，按先后顺序进行调度。

定义：

按照作业提交或进程变为就绪状态的先后次序，分派CPU；
当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。
在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。

举例：

只考虑等候时间，忽略了执行时间。

优缺点（适用场景）

有利于长作业（进程）而不利于短作业（进程）
有利于CPU繁忙型作业（进程）而不利于I/O繁忙型作业（进程）

短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPF(Shortest Process First)；这是对FCFS算法的改进，其目标是减少平均周转时间。

定义：

对预计执行时间短的作业（进程）优先分派处理机。
通常后来的短作业不抢先正在执行的作业。
但允许比当前进程剩余时间更短的进程来抢占

举例：

1、优点：

比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；

提高系统的吞吐量；

2、缺点：

对长作业非常不利，可能长时间得不到执行；
未能依据作业的紧迫程度来划分执行的优先级，不能保证紧迫性作业（进程）会被及时处理。
无法精确知道一个作业的运行时间，作业（进程）的长短只是根据用户所提供的估计运行时间而定的。

4、高优先权优先和高响应比优先调度算法

优先级算法（Priority Scheduling）是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。

静态优先权：

在创建进程时确定的，且在进程的整个运行期间保持不变。

动态优先权：

在创建进程时所赋予的优先权。
可以随进程的推进或随其等待时间的增加而改变的。

同时适用于作业调度和进程调度

优先权调度算法的类型：

1、非抢占式优先权算法：

用于批处理系统中；
也可用于某些对实时性要求不严的实时系统中；

2、抢占式优先权算法：

常用于 要求比较严的实时系统 中
对性能要求较高的批处理和分时系统中

最高响应比优先法(HRRF，Highest Response_ratio First)是对FCFS方式和SJF方式的一种综合平衡

FCFS只考虑作业的等待时间，而忽视了作业的计算时间
SJF或SPF只考虑用户估计的作业的计算时间，而忽视了作业的等待时间

最高响应比优先算法（HRRF）是介于FCFS和SJF这两者之间的折中算法。

既考虑了作业等待时间，又考虑了作业的运行时间。
既照顾了短作业，又不使长作业的等待时间过长。
改进了调度性能。

引入动态优先权，使作业的优先级随着等待时间的增加而以速率 a 提高

响应比R定义如下： R =(W+T)/T = 1+W/T

其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。

几点说明：

等待时间相同，则要求服务时间愈短，优先权愈高 -- SJF
服务时间相同，优先权决定于等待时间 -- FCFS
长作业，等待一定时间后，则响应比增加，利于调度。

由于每次调度前要计算响应比，系统开销也要相应增加。

5、死锁概述

死锁：死锁是指两个或两个以上的线程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象。

若无外力作用，它们都将无法推进下去。

此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

5.1、产生死锁的原因：

资源不足导致的资源竞争：多个进程所共享的资源不足，引起它们对资源的竞争而产生死锁。
并发执行的顺序不当。进程运行过程中，请求和释放资源的顺序不当，而导致进程死锁。如在消费者-生产者问题中的P，V操作的顺序不当。

死锁可能涉及同一种类型的资源、或者是不同类型的资源。

5.2、竞争资源引起死锁（不可避免）

5.3、进程推进顺序不当引起死锁（进程并发的异步性）

关于死锁的几个有用结论

参与死锁的进程数至少为二；
参与死锁的所有进程均在等待资源；
参与死锁的进程至少有两个占有资源；
参与死锁的进程时系统中当前正在运行进程集合的一个子集；

5.4、死锁产生的四个必要条件

虽然进程在运行过程中，可能发生死锁，但死锁的发生也必须具备一定的条件，死锁的发生必须同时具备以下四个必要条件：

1、互斥条件

系统中存在临界资源，进程应互斥使用这些资源

2、请求和保持条件

进程在请求资源得不到满足而等待时，不释放已占有的资源。

3、不剥夺条件

已占有的资源只能由属主释放，不允许被其他进程剥夺。

4、环路等待条件

在发生死锁时，必然存在一个由 两个或两个以上进程 形成的进程—资源 环形链。环路中的进程形成等待链。

6、死锁的预防和避免

6.1、处理死锁的方法

1、预防死锁：通过预先设置条件，破坏产生死锁的一个或几个必要条件（静态策略）

2、避免死锁（不让死锁发生）：不事先采取措施，在资源的动态分配过程中，防止出现死锁（动态策略）

3、检测和接触死锁（允许死锁发生）：允许死锁发生，但通过检测机构能及时检测出，采用解除机制，清除死锁。

4、忽略死锁（鸵鸟算法）：假装死锁永不发生，对死锁不采取任何措施，会造成系统奔溃。

6.2、预防死锁

预防死锁的本质实际上是，破坏产生死锁的四个必要条件中的一个或者多个，来保证不会发生死锁现象。

保证互斥条件

由于设备（非共享资源）的固有特性所决定，因此我们无法剥夺互斥条件，只能加以保护互斥条件。

摒弃请求和保持条件

要求所有的进程要一次性的申请在整个运行过程中所需的所有资源；

允许进程在没有资源的情况下，可以申请资源。

优点：

简单、易于实现、安全。

缺点：

一个进程可能被阻塞很长时间，等待资源，发生饥饿。
资源严重浪费，进程延迟运行。

摒弃不剥夺条件

可以剥夺一个进程占有的资源，分配给其他进程

一个已经保持了某些资源的进程，当它再提出新的资源请求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请；

适用条件：资源的状态可以很容易地保存和恢复，如CPU寄存器、内存空间，不能适用于打印机、磁带机

缺点：实现复杂、代价大，反复申请 / 释放资源，系统开销大，降低系统吞吐量。

摒弃环路等待条件

此方法要求资源类型序号相对稳定，进程对资源的请求 必须按照资源序号递增 的次序提出。

缺点：

易造成资源浪费
限制进程对资源的请求

总之，预防死锁是一种较易实现的方法，但由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量降低。

6.3、避免死锁

定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。

也就是：

如果一个新进程的资源请求会导致死锁，则拒绝启动这个进程；
如果满足一个进程新提出的一项资源请求会导致死锁，则拒绝分配资源给这个进程；

如果系统处于安全状态（safe），没有死锁；
如果系统处于不安全状态（unsafe），有可能死锁；
死锁的避免本质上是：确保系统永远不会进入不安全状态；

7、银行家算法

重点是掌握算法的执行过程（原理）！

7.1、银行家算法

背景：银行家算法（Banker's Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

对借贷的客户，好比是向操作系统申请资源的进程，需要满足一下约束条件：

每位客户必须预先说明自己所要求的的 最大资金量；
每位客户每次提出 部分资金量 申请和获得分配；
如果银行满足了客户对资金的最大需求量，则客户在资金运作后，能在有限时间内 全部归还；

银行家算法的设计思想：

当用户申请一组资源时，系统必须做出判断：如果把这些资源分出去，系统是否还处于安全状态，若是，就可以分配这些资源；否则，暂时不分配。

为实现银行家算法，系统必须实现某些数据结构：

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是进程P_i的请求向量，如果Request_i[ j ] = K，表示进程 P_i需要K个R_j类型的资源。当P_i发出资源请求后，系统按下述步骤进行检查：

1）如果Request_i[ j ] <= Need[i, j]，便转向步骤 2）；

否则认为出错，因为它所需要的资源数已超过它所宣布的最大值；

2）如果Request_i[ j ] <= Available[i, j]，便转向步骤 3）；

否则表示当前尚无足够的资源，P_i需要等待；

3）系统试探着把资源分配给进程 P_i，并修改下面的数据结果中的数值

Available[j] = Available[j] - Request[j];
Allocation[i, j] = Allocation[i, j] - Request[j];
Need[i, j] = Need[i, j] - Request[j];

4）系统执行安全性检查算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程 P_i，已完成本次分配；

否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 P_i等待。

7.2、安全性检查算法

1、设置两个向量

工作向量 Work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有 m 个元素，在执行安全性检查算法开始时， Work := Available
Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finish[ i ] := false; 当有足够资源分配给进程时，再令 Finish[ i ] := true;

2、从进程集合中找到一个能满足下述条件的进程

Finish[i] = false;
Need[i,j] <= Work[j]; 
// 若找到，执行步骤 3，否则，执行步骤 4

8、例题

1、

1）FCFS：

作业号	提交时刻	执行时间	完成时间	周转时间	带权周转时间
1	10:00	2	12:00	2	1
2	10:20	1	13:00	2.67	2.67
3	10:40	0.5	13:30	2.83	5.66
4	10:50	0.3	13:48	2.97	9.89

平均周转时间：2.617 小时

平均带权周转时间：4.805 小时

调度顺序：1 --> 2 --> 3 --> 4

2）SJF：

作业号	提交时刻	执行时间	完成时间	周转时间	带权周转时间
1	10:00	2	12:00	2	1
2	10:20	1	13:48	3.47	3.47
3	10:40	0.5	12:48	2.13	4.26
4	10:50	0.3	12:18	1.47	4.9

平均周转时间：2.268 小时

平均带权周转时间：3.408 小时

调度顺序：1 --> 4 --> 3 --> 2