计算机操作系统课件第三章

1、第三章 处理机调度与死锁 主要内容n3.1 处理机调度的层次 n3.2 调度队列模型和调度准则n3.3 调度算法n3.4 实时调度n3.5 产生死锁的原因和必要条件 n3.6 预防死锁的方法 n3.7 死锁的检测与解除 3.1 处理机调度的层次n3.1.1 高级调度n3.1.2 低级调度n3.1.3 中级调度3.1.1 高级调度n作业调度、长程调度n功能n基本概念作业、作业步、作业流、作业控制块（JCB）n作业调度决定接纳多少个作业决定接纳哪些作业3.1.1 高级调度n思考：分时系统中是否需要高级调度？3.1.2 低级调度n进程调度、短程调度最基本的一种调度，三种类型的OS都必须配置n功能保存

2、处理机的现场信息按某种算法选取进程把处理器分配给进程3.1.2 低级调度n进程调度中的三个基本机制排队器分派器（分派程序）上下文切换机制3.1.2 低级调度n进程调度方式非抢占方式(Non-preemptive Model)抢占方式(Preemptive Model)3.1.2 低级调度n非抢占方式(Non-preemptive Model)正在执行的进程执行完毕， 或因发生某事件而不能再继续执行;执行中的进程因提出I/O请求而暂停执行；在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。优缺点优缺点3.1.2 低级调度n抢占方式(Preem

3、ptive Model)优先权原则短作业（进程）优先原则时间片原则3.1.3 中级调度n中程调度主要目的是为了提高内存利用率和系统吞吐量n基本思想主要内容n3.1 处理机调度的层次 n3.2 调度队列模型和调度准则n3.3 调度算法n3.4 实时调度n3.5 产生死锁的原因和必要条件 n3.6 预防死锁的方法 n3.7 死锁的检测与解除 3.2 调度队列模型和调度准则n3.2.1 调度队列模型n3.2.2 选择调度方式和调度算法的若干准则3.2.1 调度队列模型n仅有进程调度的调度队列模型n具有高级和低级调度的调度队列模型n同时具有三级调度的调度队列模型 3.2.1 调度队列模型n仅有进程调度

4、的调度队列模型就 绪队 列阻 塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完3.2.1 调度队列模型n具有高级和低级调度的调度队列模型就 绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现等待事件n事件n出现后备 队列1.就绪队列的形式2.设置多个阻塞队列3.2.1 调度队列模型n同时具有三级调度的调度队列模型就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.2.2 选择调度方式和调度算法的若干准则n面向用户的准则周转时间短响应时间快截止时间的保证优

5、先权准则n面向系统的准则系统吞吐量高处理机利用率高各类资源的平衡利用3.2.2 选择调度方式和调度算法的若干准则n周转时间短定义，组成部分平均周转时间作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，平均带权周转时间可表示为:iiiTnT11niSiiTTnW113.2.2 选择调度方式和调度算法的若干准则n响应时间快分时系统从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间n截止时间的保证：实时系统n优先权准则3.2.2 选择调度方式和调度算法的若干准则n面向系统的准则面向系统的准则系统吞吐量高。n单位

6、时间内系统所完成的作业数处理机利用率好。 各类资源的平衡利用。主要内容n3.1 处理机调度的层次 n3.2 调度队列模型和调度准则n3.3 调度算法n3.4 实时调度n3.5 产生死锁的原因和必要条件 n3.6 预防死锁的方法 n3.7 死锁的检测与解除 3.3 调度算法n3.3.1 先来先服务和短作业（进程）优先调度算法n3.3.2高优先权优先调度算法n3.3.3 基于时间片的轮转调度算法3.3.1 先来先服务和短作业（进程）优先调度算法n先来先服务调度算法进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D310001111101100 110110210

7、0 1001022021991.99有利于长作业，不利于短作业最短作业优先调度(Shortest-Job-First, SJR)n将每个进程与其下一个CPU区间段相关联。当CPU为可用时，它会赋给具有最短后续CPU区间的进程。如果两个进程具有同样长度的CPU区间，那么可以使用FCFS调度来处理。n两种方式非抢占式抢占式nSJF是最佳的：对于给定的一组进程，SJF算法的平均等待时间最小。非抢占式SJF的实例抢占式SJF的实例确定下一CPU区间的长度n只能估计CPU区间的长度，无法精确计算n下一CPU区间的长度通常可预测为以前CPU区间的测量长度的指数平均下一个CPU区间长度的预测指数平均计算的实

8、例3.3.2 高优先权优先调度算法n优先权调度算法的类型非抢占式优先权算法抢占式优先权调度算法n优先权类型静态优先权n进程类型n进程对资源的需求n用户要求n缺点及解决办法饥饿与老化动态优先权n高响应比优先调度算法要求服务时间等待时间要求服务时间要求服务时间等待时间优先权1要求服务时间响应时间要求服务时间要求服务时间等待时间优先权等待时间相同时？要求服务时间相同时？等待时间变长时？3.3.3 基于时间片的轮转调度算法n基本原理n时间片大小的确定n图3-5、3-6Example of RR with Time Q = 20Process Burst TimeP153 P2 17 P368 P4 2

9、4nThe Gantt chart is: P1P2P3P4P1P3P4P1P3P302037577797117121 134154 162n多级反馈队列调度算法性能：终端型作业用户。 短批处理作业用户。 长批处理作业用户。作业nP114:167n对于下面一组进程，假设在0时刻以ABCDE的顺序到达进程服务时间优先级A103B11C23D14E521、画图演示进程使用FCFS、SJF、非抢占优先级、时间片轮转法(RR=1)算法调度时进程的执行过程2、每个进程在每种调度算法下的周转时间和平均周转时间？3、每个进程在每种调度算法下的等待时间？主要内容n3.1 处理机调度的层次 n3.2 调度队列模

10、型和调度准则n3.3 调度算法n3.4 实时调度n3.5 产生死锁的原因和必要条件 n3.6 预防死锁的方法 n3.7 死锁的检测与解除 3.4 实时调度n3.4.1 实现实时调度的基本条件n3.4.2 实时调度算法的分类n3.4.3 常用的几种实时调度算法3.4.1 实现实时调度的基本条件n提供必要的信息n系统处理能力强n采用抢占式调度机制n具有快速切换机制n必要的信息就绪时间开始截止时间和完成截止时间处理时间资源要求优先级n系统处理能力强若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不能得到及时处理， 从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务，它们

11、的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：miiiPC113.4.2 实时调度算法的分类n非抢占式调度算法一些小实时系统或要求不太严格的实时系统非抢占式轮转调度算法非抢占式优先调度算法n抢占式调度算法基于时钟终端的抢占式优先权调度算法立即抢占的优先权调度算法(a) 非抢占轮转调度当前进程实时进程实时进程请求调度实时进程枪占当前进程，并立即执行(d) 立即抢占的优先权调度调度时间进程 1进程 2实时进程要求调度进程 n实时进程调度实时进程运行(b) 非抢占优先权调度当前进程实时进程实时进程请求调度当前进程运行完成调度时间当前进程实时进程请求调度时钟中

12、断到来时调度时间(c) 基于时钟中断抢占的优先权抢占调度调度时间实时进程图 3-6 实时进程调度 3.4.3 常用的几种实时调度算法n最早截止时间优先算法EDF (Earliest Deadline First)非抢占式调度方式用于非周期实时任务抢占式调度方式用于周期实时任务n最低松弛度优先算法LLF (Least Laxity First)问题描述n有两个周期性任务，任务A的周期时间为20ms，每个周期处理时间为10ms；任务B的周期时间为50ms，每个周期处理时间为25ms。两个任务的到达时间，最后期限和执行时间如下图：B2最后期限A1A3A5A4A2B1B2A1最后期限A2最后期限A3最

13、后期限A4最后期限A5最后期限B1最后期限0 10 20 30 40 50 60 70 80 90 100 时间t/ms1. 非抢占式调度方式用于非周期实时任务图 3-7 EDF算法用于非抢占调度方式 1342开始截止时间任务执行任务到达12341342t抢占式调度方式用于周期实时任务2. 最低松弛度优先即最低松弛度优先即LLF(Least Laxity First)算法算法 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0松弛度松弛度=必须完成时间必须完成时间-其本身的运行时间其本身的运行时间-当前时间当前时间过桥的实例主要内容n3.1 处理机调度的层

14、次 n3.2 调度队列模型和调度准则n3.3 调度算法n3.4 实时调度n3.5 产生死锁的原因和必要条件 n3.6 预防死锁的方法 n3.7 死锁的检测与解除 n死锁死锁指多个进程在运行过程中因争夺资源而造成的指多个进程在运行过程中因争夺资源而造成的一种僵局。一种僵局。是是OS的一种随机故障，是指两个或两个以上的一种随机故障，是指两个或两个以上的进程都无限制的地等待永远不会出现的事件的进程都无限制的地等待永远不会出现的事件而发生的状态。而发生的状态。3.5.1 产生死锁的原因产生死锁的原因 (1) 竞争资源。竞争资源。 (2) 进程间推进顺序非法。进程间推进顺序非法。 1. 竞争资源引起进程

15、死锁竞争资源引起进程死锁 1) 可剥夺和非剥夺性资源：内存VS打印机 2) 竞争非剥夺性资源 ：3) 竞争临时性资源 ：消息、缓冲区等图 3-12 I/O设备共享时的死锁情况 R1R2P1P2图 3-13 进程之间通信时的死锁 S2P1S3P3S1P22. 进程推进顺序不当引起死锁进程推进顺序不当引起死锁 1) 进程推进顺序合法 图 3-14 进程推进顺序对死锁的影响 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)D3.5.2 产生死锁的必要条件产生死锁的必要条件 (1) 互斥条件 (2) 请求和

16、保持条件 (3) 不剥夺条件 (4) 环路等待条件 3.5.3 处理死锁的基本方法处理死锁的基本方法(1) 预防死锁。 (2) 避免死锁。 (3) 检测死锁。 (4) 解除死锁。 主要内容n3.1 处理机调度的层次 n3.2 调度队列模型和调度准则n3.3 调度算法n3.4 实时调度n3.5 产生死锁的原因和必要条件 n3.6 预防死锁的方法 n3.7 死锁的检测与解除 3.6 预防死锁的方法n3.6.1 预防死锁n3.6.2 系统安全状态n3.6.3 银行家算法3.6.1 预防死锁n产生死锁的必要条件？n预防死锁摒弃“请求和保持”条件 摒弃“不剥夺”条件 摒弃“环路等待”条件3.6.2 系统

17、安全状态n安全状态系统能按某种进程顺序(P1, P2, ，Pn)来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成，并且称P1, P2, , Pn序列为安全序列如果系统无法找到这样一个安全序列，则称系统处于不安全状态。安全、不安全、死锁状态空间避免死锁的实质在于：系统在资源分配时，如何使系统不进入安全状态安全状态之例安全状态之例n系统当前是否为安全状态？n若P3又请求1台磁带机，并且分配给它，系统是否仍然处于安全状态？进 程 最 大 需 求 已 分 配 可 用 P1P2P310495223系统可能会由安全状态系统可能会由安全状态进入不安全状态进入不安全状

18、态3.6.3 银行家算法避免避免死锁n由于该算法能用于银行系统现金贷款的发放而得名操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 n当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; n顾客可以分期贷款,但贷款的总数不能超过最大需求量; n当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; n当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金. 数据结构n可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类

19、可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。n最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。n分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。n需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。

20、如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务Needi,j=Maxi,j-Allocationi,j 银行家算法银行家算法n设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 系统试探着把资源分配给进程Pi，并修改下面数据结构：n Availablej =Availablej-Requestij;n All

21、ocationi,j =Allocationi,j+Requestij;n Needi,j =Needi,j-Requestij;系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 安全性算法安全性算法 (1) 设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work =Available; Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi =

22、false; 当有足够资源分配给进程时， 再令Finishi =true。 (2) 从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。 (3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj =Worki+Allocationi,j; Finishi =true; go to step 2; (4) 如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 实例实例nT0时刻的安全性？nP1发出请求向量Req

23、uest1(1，0，2)，是否可以满足？nP4发出请求向量Request4(3，3，0) ，是否可以满足？nP0发出请求向量Requst0(0，2，0) ，是否可以满足？作业n18、19、22主要内容n3.1 处理机调度的层次 n3.2 调度队列模型和调度准则n3.3 调度算法n3.4 实时调度n3.5 产生死锁的原因和必要条件 n3.6 预防死锁的方法 n3.7 死锁的检测与解除 3.7 死锁的检测与解除死锁的检测与解除n3.7.1 死锁的检测死锁的检测n3.7.2 死锁的解除死锁的解除3.7.1 死锁的检测死锁的检测n1.资源分配图资源分配图(Resource Allocation Graph