操作系统·处理机调度死锁

3.1 处理机调度概述

3.1.1 处理机调度概述

高级调度 (High level Scheduling)决定把外存上哪些作业调入内存、创建进程、分配资源。高级调度又称作业调度、长程调度或宏观调度。只在批处理系统中有高级调度。

中级调度 (Middle level Scheduling)完成进程的部分或全部在内、外存间的交换。中级调度又称中程调度。

低级调度 (Low level Scheduling)决定就绪队列中哪个进程应获得处理机。低级调度又称进程调度、短程调度或微观调度。

3.1.2 作业调度及算法

作业基本概念：
作业：是用户提交给系统的一项相对独立的工作。比程序更为广泛，批处理系统中，以作业为单位从外存调入内存。
作业步：作业进行的步骤。
作业控制块：JCB，作业在系统中存在的唯一标识。
作业运行的三个阶段：收容、运行、完成。
作业的三种状态：后备、运行、完成。

作业调度的主要决策：
接纳多少个作业？ 取决于系统多道程序度
多道程序度的确定根据计算机的系统规模、运行速度、作业大小以及能否获得较好的系统性能等

接纳哪些作业？ 取决于系统的调度算法
先来先服务调度算法
短作业优先调度算法
优先级调度算法

3.1.3 进程调度及算法

进程调度的任务：
保存处理机的现场信息
按某种调度算法选取进程
把处理器分配给进程：由分派程序把处理器分配给该进程，设置选中进程的处理机现场信息，交处理机控制权给进程运行

进程调度的机制：

进程调度方式：
非抢占式(Non-preemptive Mode)：不允许某进程抢占已经分配出去的处理机。
抢占方式(Preemptive Mode)：允许调度程序根据某种原则，暂停正在执行进程，将处理机重新分配给另一进程。（优先权原则、短进程优先原则、时间片原则）

3.1.4 处理机调度算法的目标

共同的目标：
资源利用率（ Utilization ）高

公平性(Fairness)
资源的平衡利用(Balance)
策略的强制执行

批处理系统的目标：
周转时间(Turnaround time)短：每个用户都希望自己的周转时间短，系统希望 平均周转时间短
假定某一作业提交系统的时间为Si，它被选中执行，运行结束时的时间为Ei 。
周转时间为Ti ＝Ei – Si
则作业平均周转时间为：

平均带权周转时间为：

CPU利用率（ CPU Utilization ）高：尽量选择计算量大的作业
系统吞吐量（Throughput）高：吞吐量指在单位时间内系统所完成的作业数。

分时系统的目标：
响应时间(Response time)快 
响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。
均衡性：系统响应时间的快慢应与用户请求服务的复杂性相适应

实时系统的目标：
截止时间(Deadline)的保证
可预测性(Predictability)准则

3.2 调度算法

3.2.1 先来先服务调度算法（FCFS: First Come First Served）

调度思想：完成选择一个或多个最先进入后备队列的作业，将它们调入内存，为它们分配资源、创建进程，并放入就绪队列。

FCFS的特点：
有利于长作业，不利于短作业。
有利于CPU密集/繁忙型的作业，不利于I/O密集/繁忙型的作业。
CPU密集型作业(CPU-bound process)：作业大部分时间用于计算
I/O密集型作业 (I/O bound process )：作业大部分时间用于等待I/O
随着计算机运行速度加快，作业越来越趋向于I/O密集型进程

3.2.2 短作业优先调度算法（SJF: Shortest Job First）

调度思想：完成在后备队列选择一个或多个估计运行时间最短的作业，将它们调入内存，为它们分配资源、创建进程，并放入就绪队列。

SJF的特点：
优点：能有效地降低作业的平均等待时间，提高系统吞吐量。
缺点：对长作业不利，未考虑作业紧迫程度，作业的估计运行时间不准确。

3.2.3 优先级调度算法（PSA: Priority-scheduling algorithm）

调度思想：完成在后备队列选择一个或多个优先级最高的作业，将它们调入内存，为它们分配资源、创建进程，并放入就绪队列。
静态优先级
动态优先级：随着时间延长而增加

3.2.4 高响应比优先调度算法（HRRN: Highest Response Ratio Next） 

如作业等待时间相同，则处理时间越短，响应比越高，有利于短作业。
对于长作业，随等待时间增加，响应比增高，最后同样可获得处理机。
如处理时间相同，等待时间越长，响应比越高，实现的是先来先服务。

3.2.5 基于时间片的轮转调度算法（RR—Round Robin）

RR的基本原理
把CPU划分成若干时间片
按顺序赋给FCFS就绪队列中的每一个进程
时间片用完时（时钟中断请求），即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾，同时系统选择队首进程运行

RR的进程切换时机
时间片内进程已运行完成，立即激活进程调度程序
时间片用完，计时器中断处理程序被激活，送当前进程到就绪队列末尾

时间片大小的确定
时间片大小对系统性能影响很大
时间片很小，有利于短进程，但进程调度和切换频繁，增加系统开销
时间片过大，退化为FCFS，无法满足短作业和交互式进程的需求
时间片可选取略大于一次典型交互的所需时间，使大多数交互式进程能在一个时间片内完成，从而获得很小的响应时间

3.2.6 多级反馈队列调度算法（multileveled feedback queue）

将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间片越短，级别越低，时间片越长。

进程第一次就绪时，进入第一级队列队尾，按FCFS 原则等待调度。

系统从第一级队列调度，当第一级为空时，系统转向第二级队列，.....

当前进程用完一个时间片，如运行完成，则退出系统，否则必须放弃CPU，并插入下一级队列队尾；如果CPU正在处理第i级队列时，有新进程加入第一级队列，或者有新唤醒的进程比当前进程的队列级别高，则新进程抢占当前进程的CPU，而原来的当前进程插入第i级队列队尾。

特点：
终端型作业用户：交互型作业，第一级队列的时间片可完成
短批处理作业用户：最多轮两次就可完成，周转时间较短
长批处理作业用户：不必担心长期得不到调度，比简单轮转性能好

3.3 实时调度

实时系统例子：实验控制、过程控制设备、机器人、空中交通管制、远程通信、军事指挥与控制系统，下一代系统还包括自动驾驶汽车、具有弹性关节的机器人控制器、智能化生产中的系统查找、空间站和海底勘探。

每种实时系统都有若干个实时进程，来反应或控制某个外部事件，它们往往带有某种程度的紧迫性，需要实时系统的调度有特殊处理，所以引入实时调度。

3.3.1 实现实时调度的基本条件

提供必要的信息：开始/完成截止时间、就绪时间、处理时间、资源要求、优先级
系统处理能力强
采用抢占式调度机制（硬实时系统）
具有快速切换机制：对外部中断的快速响应能力——要求快速硬件中断机构、允许中断的间隔短；快速的任务分派能力——系统中的每个运行功能单位适当的小

3.3.2 实时调度算法的分类

根据实时任务性质不同可分为硬实时调度和软实时调度；
根据调度方式不同可分非抢占调度和抢占调度算法；
根据调度时间的不同分成静态和动态调度算法；
在多处理机情况下可分为集中式和分布式调度算法。

非抢占式调度算法：轮转调度算法、优先调度算法
响应时间在几秒到数十秒之间。
应用于不太严格的实时控制系统，比如工业生产的群控系统。

抢占式调度算法：基于时钟中断的抢占式优先权调度算法、立即抢占的优先权调度算法。
当实时任务到达，放在就绪队列队首，等待当前任务的自我终止或运行完成。
响应时间为数百毫秒，适用于较为严格的实时控制系统。

基于时钟中断的抢占式优先权调度算法：
当优先级高于当前任务的实时任务到达，则等到下一个时钟中断，抢占当前任务的处理机。
响应时间为几到数十毫秒之间，应用于较严格的实时系统。

立即抢占的优先权调度算法：
一旦出现请求中断的紧急任务，只要当前任务未在临界区，立即抢占它的CPU
响应时间为100微秒到几毫秒之间
系统必须具有快速响应外部中断能力

3.3.3 最早截止时间优先算法EDF

根据任务的开始截止时间来确定任务的优先级；可用于抢占式调度和非抢占式调度。

3.3.4 最低松弛度优先算法 LLF

根据任务的紧急（或松弛）程度确定任务的优先级（松弛度＝必须完成的时间-还需运行的时间-当前时间），松弛度是动态变化的，主要用于可抢占式调度方式。

3.4   死锁的概念

一组进程中每个进程都无限等待被该组进程中另一进程所占有的资源，而处于的一种僵持局面，若无外力作用，它们都无法向前推进，这种现象称为进程死锁(Deadlock)，这组进程就称为死锁进程。

3.4.1 死锁产生的原因

竞争资源引起进程死锁
（1）可剥夺和非可剥夺资源
可剥夺资源：进程在获得这个资源后可以在被其它进程或系统剥夺
非可剥夺资源：资源被系统分配给某个进程后就不能强行收回，只能进程自己释放
（2）竞争不可抢占资源引起死锁
（3）竞争临时性资源（可消耗资源）引起死锁

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

3.4.2 死锁产生的必要条件

一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。
互斥条件（Mutual exclusion）：涉及的资源是非共享的
不剥夺条件（no preemption）：不能剥夺进程拥有资源
请求保持条件（hold and wait）：进程在等待一新资源时继续占有已分配的资源
环路条件（circular wait）：存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。

3.4.3 预防死锁（deadlock prevention）

通过设置某些限制条件，去破坏死锁四个必要条件中的
一个或多个，来防止死锁。
较易实现，广泛使用。
由于所施加的限制往往太严格，可能导致系统资源利用率和系统吞吐量的降低。

3.4.4 避免死锁（deadlock avoidance）

不事先采取限制去破坏产生死锁的条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。
事先只需要较弱的限制条件，可获得较高的资源利用率和系统吞吐量。

3.4.5 检测死锁（deadlock detection）

事先并不采取任何限制，也不检查系统是否进入不安全区，允许死锁发生；但可通过检测机构及时检测出死锁的发生，并精确确定与死锁有关的进程和资源，然后采取适当措施，将系统中已发生的死锁清除掉。

3.4.6 解除死锁（deadlock recovery）

与检测死锁相配套，用于将进程从死锁状态解脱出来。
常用的方法是撤消或挂起一些进程以回收一些资源，再将它们分配给处于阻塞状态的进程，使
之转为就绪状态。
实现难度大，但可获得较好的资源利用率和系统吞吐量。

3.4.7 资源分配图法

二元组G=<N,E>
N：结点集，分为P，R两部分
P={p1,p2,…,pn}进程结点
R={r1,r2,…,rm}资源结点
E：边的集合，其元素为有序二元组<pi,rj> 或<rj,pi>

系统由若干类资源构成，一类资源称为一个资源类，每个资源类包含若干个同种资源，称为资源实例。

结点的表示法：
资源类（资源的不同类型）：用方框表示Pi
资源实例（存在于每个资源类中）：用方框中的黑圆点（圈）表示

进程：用圆圈中加进程名表示边集中各边的含义：
  分配边：资源实例→进程 的一条有向边 <rj,pi>
  申请边：进程→资源类 的一条有向边 <pi,rj>

3.5 死锁的预防

破坏产生死锁的四个必要条件之一.
原理：设计不同的资源分配算法，来保证不发生死锁。

3.5.1 破坏互斥条件

如果资源不需要互斥访问，就可以破坏互斥条件。
对于某些硬件资源，可以采用特殊技术实现允许同时访问；
对于软件资源，无法实现。

3.5.2 破坏请求和保持条件

第一种协议：在执行时不再提出资源请求系统要求所有进程要一次性地申请在整个运行过程中所需
的全部资源。若系统有足够资源则完全分配。
缺点：
用户作业必须等待，直到所有资源满足才能运行。
一个作业运行期间，对某些设备的使用时间很短，甚至不会用到。如：当用户作业出错时才需要打印机输出错误信息，但采用静态分配法必须把打印机分配给该作业，并长期占用。采用该方法对系统来说是非常浪费的。

第二种协议：请求，不保持所有资源
获得初期所需资源以后就开始运行，在运行过程中逐步释放分配给自己的并且已经用毕的全部资源，然后再请求新的所需资源。

3.5.3 破坏不可抢占条件

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

实现复杂且要付出很大的代价（以前工作的失效，执行的推迟）。

3.5.4 破坏环路条件

系统将所有资源按类型进行线性排序，并赋予不同的序号，所有进程对资源的请求必须严格按照资源序号递增的次序提出。

例如：系统中有下列设备：输入机（1），打印机（2），穿孔机（3），磁带机（4），磁盘（5）。有一进程要先后使用输入机、磁盘、打印机，则它申请设备时要按输入机、打印机、磁盘的顺序申请。

优点：同前两法相比，其资源利用率和系统吞吐量有较明显的改善。 
缺点：进程实际需要资源的顺序不一定与资源的编号一致，因此仍会造成资源浪费；资源的序号必须相对稳定，从而限制了新设备的增加。

3.6 避免死锁

3.6.1 系统的安全状态

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

如果系统能按某种顺序为每个进程依次分配其所需的资源，直至所有进程都能运行完成，称此时
系统处于安全状态。
这种进程的顺序，如P4,P1,…,Pn, 称为安全序列。
若不存在这样一个安全序列称此时系统处于不安全状态。

注意：不安全状态≠死锁
处于不安全状态的系统不一定会发生死锁；处于安全状态的系统一定不会发生死锁。
系统处于安全与不安全状态都是静态进行的评价。

安全状态举例：

由安全状态向不安全状态的转换： 

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

银行家算法中的数据结构：

可利用资源向量（Available）是一个含有m个元素的数组，其中每个元素代表一类资源的可利用的数目。

最大需求矩阵（Max）n×m矩阵，n为当前系统进程的数目，m为系统资源种类数。Max[i,j]为第i个进程对j类资源的最大需求。

分配矩阵（Allocation ）n×m矩阵，表示每个进程已分配的每类资源数。

需求矩阵（Need）n×m矩阵，表示每个进程还需要各类资源数。

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

银行家算法：
当Pi发出资源请求，分配一个Request向量。（Request_i：是进程Pi的请求向量。如Request_i[j]=K，表示进程i需要K个R_j类型的资源。）然后系统按下述流程进行执行。

安全性算法：
增加两个向量：Work和Finish
Work表示系统可提供给进程继续运行所需的各类资源数目（即在试着分配过程中，系统的可用资源数）。初始值 Work∶=Available（可用资源向量）;
Finish表示系统是否有足够的资源分配给进程i，使之运行完成。初始值 Finish[i]:=false（布尔型）；当有足够资源分配给进程时 Finish[i]:=true。

3.8 死锁的检测和解除

3.8.1 死锁检测

允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生 
一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行

检测时机：
定时检测
当进程阻塞时检测死锁（其缺点是系统的开销大）
系统资源利用率下降时检测死锁

检测方法：资源分配图法

死锁定理：如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。

资源分配图化简：
1.找一个非阻塞非独立的进程结点，去掉分配和请求边，将其变为孤立结点；
2.再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边；
3.重复以上步骤，若所有进程都可成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简化的。

死锁状态的充分条件是：资源分配图是不可完全简化的。

3.8.2 死锁的解除

抢占资源
终止或者撤销进程（终止所有进程、逐个终止进程）

重要的是以最小的代价解除死锁，恢复系统运行。方法如下：
撤消所有的死锁进程
连续撤消死锁进程直至不再存在死锁
连续剥夺资源直到不再存在死锁
把每个死锁进程备份到前面定义的某个检查点，并重新启动所有进程