处理机调度与死锁1.ppt

第三章 处理机调度与死锁,多进程并发运行多道程序并发执行CPU共享与分配 处理机调度 一、处理机调度类型和基本概念 高级调度：又称作业调度，或长程调度 中级调度：又称中程调度、激活操作（具有挂起状态系统） 低级调度：即进程调度，又称短程调度,1）作业调度和进程调度 * 作业、作业步 作业：用户要求计算机所做的工作集合（事务处理） 作业步：每一个工作（加工）步骤 * 作业说明书、作业控制块（JCB）,* 作业调度和进程调度的功能 作业调度：将后备状态的若干作业调入内存投入运行 进程调度：将就绪状态的一个进程分配CPU投入执行 2）处理机调度与OS类型的关系 多道批处理系统：存在作业调度、进程调度 分时系统：只有进程调度 实时系统：通常也不存在作业调度 共同点：三类系统均存在进程调度（分配CPU）,3）调度队列模型（P88-89）,4）调度性能评价 调度性能的好坏直接影响整个系统的工作效率 主要评价指标: *（面向用户） 作业周转时间：作业从提交到完成所需的总的时间（等待 加运行时间），有平均周转时间和平均带权周转时间。 响应时间、截止时间 *（面向系统） 吞吐量：单位时间内系统所处理和完成的作业数 处理机利用率、资源的均衡使用 ,二、进程调度方式CPU分配（调度）时机 非抢占方式 抢占方式 1）非抢占方式 进程一旦被调度执行，除非进程完成或发生某事件被阻塞，否则不允许其他进程抢夺其执行权。 * 优点：实现简单，调度频率低，系统开销小。 * 缺点：紧迫任务对应的进程得不到及时执行（处理）。,2）抢占方式 允许按某种策略（原则）剥夺执行进程的执行权。 优先权原则 短进程优先原则 时间片原则 其他原则 * 优、缺点：与非抢占方式相反（系统开销大）。 常采用有选择（条件）的抢占方式,三、调度算法 处理机调度时分配资源策略或方法 调度算法的好坏直接关系到调度性能的好坏。 常用的几种调度算法： 先来先服务调度算法 短作业（进程）优先调度算法 高优先权优先调度算法 时间片轮转调度算法 多级反馈队列调度算法 实时调度算法,1）先来先服务调度算法（FCFS） * 策略：先进入后备队列（就绪队列）的作业（进程） 先被调度。 * 优点：算法简单易实现 * 缺点：不分轻重缓急，对短作业（进程）不利 2）短作业（进程）优先调度算法（SJ（P）F） * 对短作业（进程）有利 * 长作业（进程）可能长期得不到服务（运行） 3）高响应比优先调度算法 响应比 =（等待时间+要求服务时间）/ 要求服务时间,4）高优先权优先调度算法 * 优先权概念 反映作业（进程）调度级别的权值（用优先数表示） 分为： 静态优先权（优先数） 动态优先权（优先数） 根据进程的类型，资源需求情况，用户要求等因素确定。* 策略 后备（就绪）队列根据优先数的大小来排队，级别高的 作业（进程）先被调度。 * 优点：可通过动态调整优先权以获得更好的调度性能。 * 缺点：算法复杂，尤其是采用动态优先数法。,5）时间片轮转调度算法（适合于分时系统） * 策略：各作业（进程）轮流运行（执行）一个时间片。 * 优、缺点：简单易实现，但不分轻重缓急。 6）多级反馈队列调度算法 即为时间片与优先级相结合的调度算法 * 策略：进程按其优先级（数）排到不同就绪队列， 先调度第一个队列的进程执行，若其在一个 时间片内未完成，则重新计算优先数，降到 下一队列。 * 优、缺点：通过合理设置时间片和优先级，从而提高 整个系统的调度性能系统开销加大（算法复杂）。,四、调度方式和调度算法的选择 * 按实现系统 批处理系统：非抢占方式； 先来先服务、短作业优先， 高优先权优先法等。 分时系统：两种调度方式均可采用； 时间片轮转法、多级反馈队列法。 实时系统：大多采用抢占方式； 高优先权法，其他实时调度算法等。,* 按设计目标 面向用户：周转时间要短，响应速度快。 面向系统：系统吞吐量大，CPU及设备利用率高， 资源能平衡利用，系统效率高。 * 其他特殊需求 专用计算机OS 多处理机系统 实时控制系统 网络系统 嵌入式系统,五、用于实时系统的调度算法 满足实时处理时间要求的调度策略 1）实时任务和截止时间 * 实时任务：必须在规定时间内完成的任务 硬实时任务 周期性实时任务 软实时任务 非周期性实时任务 * 截止时间：任务规定的时限 开始截止时间 完成截止时间,2）调度类型和调度方式 * 调度类型 静态调度：事先已决定好进程的执行顺序 动态调度：根据任务要求临时决定执行进程 * 调度方式 非抢占方式：轮转调度或优先权高者优先调度 抢占方式：立即抢占或待时钟中断时才抢占,3）几种常用的实时调度算法 * 最早截止时间优先算法 选择就绪队列中开始截止时间最早的实时任务对应的进程先执行（非抢占方式）,例：,t=0 只有P1进程，P1执行4个单位时间 t=4 P2 、P3 均到达，P3 截止时间早于P2 截止时间, P3 执行两个单位时间 t=6 P2 和P4 就绪，P4 截止时间早于P2 ，P4 执行 t=9 只剩P2 ，P2执行,* 最低松弛度优先算法 松弛度: 规定完成时间-所需执行时间-当前时间 选择松弛度最小的实时任务对应的就绪进程先执行（抢占方式），即当某进程松弛度为零时，必须立即抢占执行。,例：两个周期性实时任务A和B， A：每20ms执行一次，每次执行时间为10ms B：每50ms执行一次，每次执行时间为25ms,六、死锁 死锁：多个进程竞争系统资源，造成一种僵局，使得这些进程在无外力的作用下，均无法继续向前推进。 讨论问题： 造成死锁的原因和必要条件 (解决死锁问题的基本方法) 死锁的预防和避免 死锁的检测与解除,1）产生死锁的原因,交通死锁示意图,进程死锁示意图,原因：资源竞争且资源数目不足 进程推进顺序不当（进入死锁区D）,2）产生死锁的必要条件 互斥条件 请求和保持条件 不剥夺条件 环路等待条件 四个必要条件同时存在（满足）才会产生死锁,3）死锁的预防 破坏（摒弃）四个必要条件之一 * 摒弃“互斥条件”，受限于资源的性质 * 摒弃“请求和保持条件” 进程创建时，一次性将全部所需资源均分配给进程，其在运行过程中不会产生新的请求。,* 摒弃“不剥夺条件” 进程因请求新资源而得不到满足，造成阻塞时，暂时释放已占有的所有资源（剥夺）。 * 摒弃“环路等待条件” 进程对资源的请求顺序必须严格按照系统规定的次序进行，使之资源分配图不会形成环路。 预防措施给出了解决问题的思路及方法，实际 是不大可行的。,4）死锁的避免 通过对系统的安全性进行检测，避免死锁的发生 安全状态: 可分配资源 不安全状态: 暂不分配资源 安全状态： 能找到一个进程运行序列，使每个进程都能 分配到所需资源（即能满足每个进程对资源的最 大需求），从而都能顺利完成。 ( P108 安全状态例解： T0时刻安全序列为P2、P1、P3 ）,银行家算法：当某进程Pi发出资源请求后 判断请求的合法性（是否超出规定的请求数目）； 若合法，则判断现有资源数目是否足够分配； 若足够，则先预分配给Pi进程； 进行安全性检测， 安全：则正式分配资源 不安全：则不予分配（避免死锁的发生） 例、五个进程和三类资源（A，B，C）在某时刻的分配情况 如下表所示（T0时刻），资源总数为：10，5，7 。 此时P1请求资源（1，0，2），可找到一个安全序列 P1，P3，P4，P2，P0因此，此次分配是安全的。 （P110-P111 图表给出其判断过程需改错）,5）死锁的检测与解除 一旦发生死锁，如何发现它，并加以解除？ * 死锁的检测（发现） 三个基本概念: 系统死锁 死锁状态 资源分配图（或进程资源图，简称图） 资源分配图的简化： 在图中找一个既不孤立又未阻塞的进程结点Pi; 从图中删除与Pi相连接的所有边，从而得一个新图; 针对新图重复实施以上两步操作，直到找不到满足第一步的结点Pi。,简化结果： 简化后的图中的所有进程结点均为孤立结点，称该 图为可完全简化。反之，则称该图为不可完全简化。 死锁定理： S状态为死锁状态的充分条件是： 当S状态对应的进程资源图是不可完全简化的。 即：图不可完全简化，必定发生死锁； 图可完全简化，不一定不会发生死锁。,* 死锁的解除 解除方法（常用） 剥夺资源，供死锁进程使用 撤销进程，撤销部分或全