第四章 调度与死锁
4．1 调度的类型和模型
4．2 调度算法
4．3 实时系统中的调度
4．4 多处理机调度
4．6 死锁的基本概念
4．7 死锁的预防和避免
4．8 死锁的检测和解除
4．1 调度的类型和模型
4．1．1 调度类型
一、高级调度
1．接纳多少个作业
2．接纳哪些作业
二、低级调度
1．非抢占方式
2．抢占方式
三、中级调度
4．1．2 调度队列模型
一、 仅有进程调度的调度队列模型
二、 具有高级和低级调度的调度队列模型
三、 同时具有三级调度的调度队列模型
4．1．3 选择调度方式和算法的若干准则
一、 面向用户的准则
1．周转时间短
2．响应时间快
3．截止时间的保证
4．优先权准则
二、 面向系统的准则
1．系统吞吐量高
2．处理机利用率好
3．各类资源的平衡利用
4．2调度算法
概念：根据系统的资源分配策略所规定的资源分配算法。
4．2．1 先来先服务调度算法（FCFS）
一、调度算法
二、 FCFS实例
4．2．2 短作业（进程）优先调度算法
4．2．3 时间片轮转调度算法
一、调度算法
二、时间片大小的确定
1．系统对响应时间的要求
2．就绪队列中进程的数目
3．系统的处理能力
4．2．4 优先权调度算法
一、优先权调度算法的类型
1．非抢占式优先权算法
主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
2．抢占式优先权调度算法
这种方式的优先权调度算法．能更好地满足紧迫作业的要求，常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。
二、优先权的类型
1．静态优先权
在创建进程时确定，且优先权在整个进程的生命周期内不会发生变化。
确定优先权的依据有：
（1）进程类型。（2）进程对资源的需求。（3）根据用户要求。
2．动态优先权
在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能。
4．2．5 高响应比优先调度算法
4．2．6 多级队列调度
4．2．7 多级反馈队列调度算法
一、调度算法
二、多绍反馈队列调度算法的牲能
4．3 实时系统中的调度
4．3．1 对实时系统的要求
1．提供必要的调度信息
（1）就绪时间。（2）开始截止时间和完成截止时间。（3）处理时间。（4）资源要求。（5）优先级。
2．调度方式
在实时控制系统中，广泛采用抢占调度方式。
3．具有快速响应外部中断的能力
4．快速任务分派
4．3．2 实时调度算法
1．时间片轮转调度算法
2．非抢占优先权调度算法
3．基于时钟中断抢占的优先权调度算法
4．立即抢占的优先权调度
4．3．3 实时调度实例
一、具有开始截止时间的非周期实时任务的调度
在事前能知道各实时任务的开始截止时间，且对调度时延要求不太严格的情况下，系统采用最早截止时间优先的非剥夺调度策略。
任务1、2、3、4的调度
二、具有完成截止时间的周期性实时任务的调度
A：每20ms执行一次，执行时间为10ms。
B：每50ms执行一次，执行时间为25ms
4．4 多处理机调度
4．4．1 进程调度
一、同构型多处理机系统中的进程调度
1．静态分配（Static Assignment）
2．动态分配（Dynamic Assignment）
3．自调度（Self-Scheduling）
二、异构型多处理机系统中的进程调度
4．4．2 自调度
（1）自调度方式。系统中有一个公共的线程或进程的就绪队列，所有的处理机在空闲时，都可自己从该队列中取出一个进程或线程运行。
（2）成组调度。这时由系统将一组相关的进程或线程，同时分配到—组处理机上运行，进程或线程与处理机一—对应。
（3）专用处理机分配方式。它是将同属于一个应用程序的一组线程，分配到一组处理机上，在应用程序末结束前，处理机专用于处理这组线程。
4．4．3 成组调度
1．面向所有的应用程序平均分配处理机时间
2．面向所有的线程平均分配处理机时间
4．4．4 专用处理机分配
把这种调度方式用于并发程度相当高的多处理机环境，是根据下述一些理由：
（1）在具有数十个乃至数百个处理机的高度并行的系统中，单个处理机的利用率已远不像在单机系统中那么重要。
（2）可以避免了进程或线程的切换，从而可大大地加速程序的完成。
根据实践证明：在同时加工的应用程序中，其线程数的总和不应超过系统中处理机的数目。
4．6 死锁的基本概念
所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。
4．6．1 产生死锁的原因
产生死锁的原因可归结为两点：
（1） 竞争资源。
（2） 进程推进顺序非法。
一、竞争资源引起死锁
1．可剥夺和非剥夺性资源
2．竞争非剥夺促资源
3．竞争临时性资源
二、进程推进顺序不当引起死锁
1．进程推进顺序合法
2．进程推进顺序非法
4．6．2 产生死锁的必要条件
1．互斥条件
2．请求和保持条件
3．不剥夺条件
4．环路等待条件
4．6．3 处理死锁的基本方法
1．预防死锁
2．避免死锁
3．检测死锁
4．解除死钡
死锁的检测和解除措施，有可能使系统获得较好的资源利用宰相系统吞吐量，但在实现上难度也最大。
4．7 死锁的预防和避免
4．7．1 死锁的预防
一、摒弃“请求和保持”条件
二、据弃”不剥夺”条件
三、摒弃“环路等待”条件
4．7．2 系统的安全状态
一、安全状态
所谓安全状态，是指系统能按某种顺序如<P1，P2，…，Pn>（称<P1，P2，…，Pn>序列为安全序列），来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个安全序列，则称系统处于不安全状态。
虽然并非所有不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于：如何使系统不进入不安全状态。
二、安全状态之例
我们通过一个例子来说明安全性。假定系统有三个进程P1、P2和P3，共有12台磁带
机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。设在T0时刻，进程Pl、
P2和P3已分别获得5台、2台和2台，尚有3台空闲未分，如下表所示：
进程 最大需求 已分配 可用
P1 10 5 3
P2 4 2
P3 9 2
三、由安全状态向不安全状态的转换
如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。
4．7．3 利用银行家算法避免死锁
一、银行家算法中的数据结构
1．可利用资源向量Available
它是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。
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的矩阵，用以表示每一个进程尚需的各类资源数，如果 ，表示进程i还需要Rj类资源k个，方能完成其任务。
上述三个矩阵间存在下述关系：
二、银行家算法
设Requesti是进程Pi的请求向量。如果Requesti[j]＝k，表示进程只需要k个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：
（1）如果 ，则转向步骤2；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。
（2）如果 ，则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待。
（3）系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：
（4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
三、安全性算法
系统所执行的安全性算法可描述如下：
（1）设置两个向量
①、工作向量Work。它表示系统可提供给进程继续运行所需要的各类资源数目，它含有m个元素，执行安全算法开始时，Work = Available。
②、Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做 ；当有足够资源分配给进程时，令 。
（2）从进程集合中找到一个能满足下述条件的进程：
如找到，执行步骤（3）；否则，执行步骤（4）。
（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
go to step 2；
（4）如果所有进程的 ，则表示系统处于安全状态；否则，系统处于不安全状态。
四、银行家算法之例
假定系统中有五个进程：{P0，P1，P2，P3，P4}和三种类型的资源{A，B，C}，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图4—17所示。
4．8 死锁的检测和解除
4．8．1 死锁的检测
当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段。为此，系统必须：
（1）保存有关资源的请求和分配信息；
（2）提供—种算法，以利用这些信息来检测系统是否已进入死锁状态。
一、资源分配图(Resource Allocation Graph)
二、死锁定理
我们可以利用把资源分配图加以简化的方法，来检测系统处于S状态时，是否为死锁状态。简化方法如下：
（1）在资源分配图中，找出—个既不阻塞又非独立的进程结点pi。在顺利情况下，pi可获得所需资源而继续执行，直至运行完毕，再释放其所占有的全部资源。这相当于消去pi所有的请求边和分配边，使之成为孤立的结点。
（2）pi释放资源后．便可使p2获得资源而继续运行，直到p2完成后又释放出它所占有的全部资源。
（3）在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。
对于较复杂的资源分配图，可能有多个既末阻塞、又非孤立的进程结点，有关文献已经证明不同的简化顺序，将得到相同的不可简化图，同样可以证明：S为死锁状态的充分条件是，当且仅省S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理。
三、死锁检测中的数据结构
死锁检测中的数据结构，类似于银行家算法中的数据结构：
（1）可利用资源向量Available。它表示了m类资源中每一类资源的可用数目。
（2）把不占用资源的进程向量Allocation＝0记人表L中，即 。
（3）从进程集合中找到一个 的进程，做如下处理：
①、将其资源分配图简化，释放出资源，增加工作向量。
②、将它记入L表中。
（4）若不能把所有进程都记人L表中，则表明系统状态S的资源分配图是不可完全简化的。因此。该系统状态将发生死锁。
4．8．2 死锁的解除
当发现有进程死锁时，使当立即把它们从死锁状态中解脱出来，常采用的两种方法是：
（1）剥夺资源。
（2）撤消进程。
一个付出最小代价的方法为树的宽度优先搜索算法。这种算法不太实际。
一个比较有效地方法为最短路径的优先策略搜索算法。