《08处理机调度2概要》由会员分享，可在线阅读，更多相关《08处理机调度2概要（76页珍藏版）》请在金锄头文库上搜索。
1、,Page 1,2019/10/28,第三章 处理机调度与死锁,山东交通学院 信电学院,Page 2,2019/10/28,死锁 1. 死锁的概念 2. 死锁处理策略 3. 死锁预防 4. 死锁避免 系统安全状态：银行家算法。 5. 死锁检测和解除,Page 3,2019/10/28,第三章 处理机调度与死锁,知识点 产生死锁的原因和必要条件 预防死锁的方法，死锁的检测与解除 银行家算法,Page 4,2019/10/28,调度队列模型,仅有进程调度的调度队列模型,进程调度,进程完成,等待事件,交互用户,时间片完,Page 5,2019/10/28,调度队列模型,进程调度,进程完成,时间片完,
2、与上一模型的主要区别：就绪队列的形式； 设置多个阻塞队列,Page 6,2019/10/28,调度队列模型,同时具有三级调度的调度队列模型,进程调度,中级调度,等待事件,进程完成,时间片完,作业调度,交互型作业,批量作业,挂起,挂起,事件出现,Page 7,2019/10/28,3.1.3 选择调度方式和调度算法的若干准则,1. 面向用户的准则,(1) 周转时间短。,(2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。,Page 8,2019/10/28,选择调度方式和调度算法的若干准则,面向用户的准则 周转时间短 平均周转时间,带权周转时间：进程（或作业）的周转时间T与系统为
3、它提供服务的时间TS之比，即W=T/TS 。而平均带权周转时间则可表示为:,Page 9,2019/10/28,选择调度方式和调度算法的若干准则,面向用户的准则 响应时间快 响应时间是指从用户通过键盘提交一个请求开始，直至系统中首次产生响应为止的时间 交互式系统用周转时间衡量不是最佳 截止时间保证 截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间 截止时间是实时系统中的重要指标,Page 10,2019/10/28,选择调度方式和调度算法的若干准则,面向用户的准则 等待时间短 等待时间是在就绪队列中等待所花的时间 调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中
4、等待所花费的时间 优先权准则 在批处理、实时和分时系统中都可以选择优先权准则，以便让紧急任务先处理 有时还选择抢占式调度方式,Page 11,2019/10/28,选择调度方式和调度算法的若干准则,面向系统的准则 系统吞吐量高 吞吐量指单位时间内系统所完成的作业数 作业调度的方式和算法对吞吐量的大小有较大影响 处理机利用率高 各类资源的平衡利用 使内存、外存和I/O设备的利用率高,基于这样的准则，你设计操作系统的调度策略应如何？,Page 12,2019/10/28,调度算法,先来先服务和短作业优先算法 高优先权优先调度算法 基于时间片的轮转调度算法,Page 13,2019/10/28,先来
5、先服务和短作业优先算法,先来先服务（先进先出）优缺点,比较有利于长作业（进程），而不利于短作业（进程） 有利于CPU繁忙型作业（进程） ，而不利于I/O繁忙型作业（进程） 用于批处理系统，不适于分时系统,Page 14,2019/10/28,先来先服务和短作业优先算法,SJ(P)F调度算法也存在不容忽视的缺点 对长作业不利。严重的是，若一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度饥饿 完全未考虑作业(进程)的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理 由于作业(进程)的长短只是根据用户所
6、提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。,Page 15,2019/10/28,高优先权优先（HPF，Highest Priority First）调度算法,优先权调度算法的类型 非抢占式优先权调度算法 抢占式优先权调度算法,Page 16,2019/10/28,高优先权优先调度算法,优先权的类型 静态优先权 动态优先权,Page 17,2019/10/28,高优先权优先调度算法,高响应比优先调度算法（HRF） 是FCFS和SJF的结合，克服了两种算法的缺点 调度策略：响应比最高的作业优先启动 因等待时间+服务时间
7、=该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为,Page 18,2019/10/28,高优先权优先调度算法,对HRF的小结 等待时间相同的作业，则要求服务的时间愈短，其优先权愈高， 要求服务的时间相同的作业，则等待时间愈长，其优先权愈高， 长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高， 从而也可获得处理机 是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。,缺点：要进行响应比计算，增加了系统开销,对短作业有利,是先来先服务,对长作业有利,Page 19,2019/10/28,调度算法,先来先服务和短作业优
8、先算法 高优先权优先调度算法 基于时间片的轮转调度算法,Page 20,2019/10/28,多级反馈队列调度算法 设置多个就绪队列，并为各个队列赋予不同的优先级 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低 该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍,Page 21,2019/10/28,就绪队列1,基于时间片的轮转调度算法,就绪队列2,就绪队列3,就绪队列n,调度方式,按FIFO原则排队等待调度,尚
9、未完成转入第二队列的末尾，按FIFO原则等待调度,采取按时间片轮转的方式运行,因等待而放弃CPU后，进入阻塞队列，一旦等待的事件发生，则回到原来的就绪队列,Page 22,2019/10/28,第三章 处理机调度与死锁,处理机调度的基本概念 作业和作业调度算法 进程调度 实时调度 死锁概述 预防死锁 避免死锁 死锁的检测与解除,Page 23,2019/10/28,3.5死锁概述,死锁的基本概念 产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法,Page 24,2019/10/28,死锁的基本概念,死锁的概念 指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再
10、向前推进。 即：如果一组进程中，每个进程都在等待仅有该组进程中其他进程才能引发的事件，那么该组进程就称为死锁进程。,Page 25,2019/10/28,死锁的基本概念,关于死锁的一些结论 参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。,Page 26,2019/10/28,产生死锁的原因和必要条件,死锁的基本概念 产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法,Page 27,2019/10/28,产生死锁的原因,竞争资源。 当系统中供多
11、个进程所共享的资源，不足以同时满足 它们的需要时，引起它们对资源的竞争而产生死锁。 (2) 进程间推进顺序非法。 进程在运行过程中，请求和释放资源的顺序不当， 导致了进程死锁。,所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种 僵局，若无外力作用，这些进程都将永远不能再向前推进。,Page 28,2019/10/28,产生死锁的原因,竞争资源引起进程死锁 可剥夺和非剥夺性资源 可剥夺性资源是指进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，如处理机、内存等 非剥夺性资源是指当系统把这类资源分配给某个进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等 竞
12、争非剥夺性资源 系统中的非剥夺性资源由于数量有限而不能满足进程运行的需要，进程在运行过程中因争夺这些资源而限入僵局 竞争临时性资源,Page 29,2019/10/28,产生死锁的原因,I/O设备共享时的死锁情况,若系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。,Page 30,2019/10/28,产生死锁的原因,进程之间通信时的死锁,Page 31,2019/10/28,产生死锁的原因,进程推进顺序不当引起死锁,不安全区,Page 32,2019/10/28,产生死锁的原因和必要条件,死锁的基本概念 产生死锁的原因 产生死锁的必要条件 处理死
13、锁的基本方法,Page 33,2019/10/28,产生死锁的必要条件,互斥条件 进程对所分配到的资源进行排它性的使用 请求和保持条件 进程已经至少保持了一个资源，但又提出了新的资源请求，而该资源又已被其他进程占有 不剥夺条件 进程已获得的资源在未使用完之前不能被剥夺 环路等待条件 在发生死锁时，必然存在一个进程-资源循环等待的环形链,Page 34,2019/10/28,产生死锁的原因和必要条件,死锁的基本概念 产生死锁的原因 产生死锁的必要条件 处理死锁的基本方法,Page 35,2019/10/28,处理死锁的基本方法,预防死锁 避免死锁 检测死锁 解除死锁,Page 36,2019/1
14、0/28,第三章 处理机调度与死锁,处理机调度的基本概念 作业与作业调度算法 进程调度 实时调度 死锁概述 预防死锁 避免死锁 死锁的检测与解除,Page 37,2019/10/28,3.6预防死锁,摒弃“请求和保持”条件 所有进程在开始运行之前必须一次性的申请整个运行过程所需的全部资源 简单、易于实现、安全 资源浪费严重 进程延迟运行,Page 38,2019/10/28,预防死锁,摒弃“不剥夺”条件 进程逐个地申请所需资源 当一个已经保持了某些资源的进程申请新资源而不能得到满足时，必须放弃所有已保持的资源 实现复杂、代价高昂 延长了进程的周转时间，还增加了系统开销，降低了系统的吞吐量,Pa
15、ge 39,2019/10/28,预防死锁,摒弃“环路等待”条件 系统将所有资源按类型分配序号并排队 所有进程申请资源必须按序号递增的顺序 资源利用率和系统吞吐量较高 但在资源管理和资源申请方面仍有问题,Page 40,2019/10/28,3.7避免死锁,系统安全状态 利用银行家算法避免死锁,Page 41,2019/10/28,产生死锁的原因,进程推进顺序不当引起死锁,Page 42,2019/10/28,系统安全状态,安全状态 在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否
16、则，令进程等待 所谓安全状态，是指系统能按某种进程顺序(P1, P2, ，Pn)(称P1, P2, , Pn序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态,安全状态与不安全状态,不安全状态:不存在一个安全序列。,安全状态之例 假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：,此时系统是安全的。安全序列为（P2,P1,P3）.按照此顺序分配资源，每个进程都可顺利完成。,安全状态向不安全状态的转化,如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。 例如，在T
