华东石油大学计算机考研操作系统第三章.pptVIP

第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 进程调度算法 3.3 实时调度 3.4 多处理机系统中的调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法和死锁避免 3.7 死锁的检测和解除 3.1? 处理机调度的基本概念 高/中/低级调度 调度队列模型 调度方式和算法的选择准则 高/中/低级调度 高级调度（作业调度） 决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，准备执行。 低级调度（进程调度） 决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。 非抢占方式和抢占方式（非剥夺方式、剥夺方式） 中级调度 决定把又具备运行条件的挂起进程重新调入内存，挂到就绪队列上，准备执行。 调度队列模型 调度方式和算法的选择准则 面向用户的准则 周转时间短 响应时间快 截止时间保证 优先权准则 面向系统的准则 系统吞吐量高 处理机利用率好 各类资源的平衡利用 3.2? 调度算法 先来先服务 短作业（进程）优先 优先级 时间片轮转 多级反馈队列 1 、先来先服务（FCFS） 主要用于作业调度，也可用于进程调度。 用于作业调度： 每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。 有利于长作业，而不利于短作业。 用于进程调度： 每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。 直到运行完成进程才会让出处理机--非抢占式。 性能评价： 周转时间 Ti = 完成时间 – 到达时间 带权周转时间 Wi = 周转时间 / 服务（运行）时间 平均周转时间 T ------- 不同算法对同一作业流的调度性能 平均带权周转时间 W ------- 某算法对不同作业流的调度性能 2、短作业 / 进程优先（SJ/PF） 短作业优先（SJF） 从后备队列中选择估计运行时间最短的作业，调入内存运行。 短进程优先（SPF） 从就绪队列中选出估计运行时间最短的进程，将处理机分配给它，使它立即执行。 直到运行完成进程才会让出处理机--非抢占式。 缺点： 对长作业不利，有可能长期不被调度； 完全没考虑作业的紧迫程度（某些特殊的）； 用户做出的估计时间带有很大的主观性。 3、优先级（FPF） 既能用于作业调度，也可用于进程调度。 调度思想： 从队列中选择优先权最高的调度单元，装入内存或分配给处理机。 对进程调度而言，有非抢占式和抢占式两种。 优先权 静态优先权、动态优先权。 高响应比优先调度算法 动态优先权，与作业等待时间相关。 4、时间片轮转 特别适用于分时系统的可抢占方式的调度算法。 时间片： 大小：几ms ~ 几百ms 与系统性能的关系 实现方法： 由计时器发出时钟中断，引起一次轮转调度。 多级反馈队列 前面所述调度算法的局限性 多级反馈队列调度算法的思想 设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片； 新创建的进程挂到第一优先级的队列后，然后按 FCFS 原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，……； 仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推……；新进程可抢占低级进程的处理机。 多级反馈队列调度算法的性能 能较好地满足各种类型用户（进程）的需要。 终端（交互）型作业用户 短批处理作业用户 长批处理作业用户 3.3 实时调度 实现实时调度的基本条件 实时调度算法的分类 常见的几种实时调度算法 3.4??多处理机系统 中的调度 多处理器系统的类型 进程分配方式 进程（线程）调度方式 3.5.1 死锁的概念 1.死锁例子: 一个由于申请不同类型资源而产生死锁的例子 设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。 用信号量S1表示R1是否可用，用信号量S2表示R2是否可用， S1、 S2初值为1。 2.死锁概念 指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。 即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。  3.关于死锁的一些结论 参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。  4.永久性资源和临时性资源 永久性资源：可以被多个进程多次使用（可再用