处理机调度与死锁

第三章第三章 处理机调度与死锁处理机调度与死锁 3.1 处理机调度的层次3.2 调度队列模型和调度准则3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 1教学目的与要求教学目的与要求 理解处理机调度的概念和调度的层次 掌握各种作业、进程调度算法和实时调 度算法 理解死锁的基本概念 掌握死锁的处理方法 教学重点：各种作业、进程调度算法和死锁 的处理方法等。教学难点：作业、进程调度算法, 死锁23.1 3.1 处理机调度的层次处理机调度的层次CPU是计算机系统中的一个十分重要的资源，对 它进行高效的调度是操作系统设计的中心问 题之一。一个作业从提交开始，往往要经历三级调度： 高级调度、低级调度、中级调度。33.1 3.1 处理机调度的层次处理机调度的层次3.1.13.1.1高级调度高级调度 （作业调度、长程调度）1、作业和作业步 作业：包含程序、数据和作业说明书。 作业步：作业执行过程中的每一个加工步骤 作业流：作业进入系统，依次存于外存形成作业流 2、作业控制块（JCB） 它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。 内容： 作业标识，用户名，作业类型，作业状态，调度信 息等 进入系统>建立JCB->插入相应后备队列->作业 调度->作业控制>作业结束>回收资源43、作业调度 将外存作业调入内存，创建PCB等，插入就 绪队列。 一般用于批处理系统，分/实时系统一般直 接入内存，无此环节。 调度特性 接纳作业数（内存驻留数，多道程序度） 太多>周转时间T长 太少>系统效率低 接纳策略：即采用何种调度算法：FCFS、短 作业优先等53.1.2 3.1.2 低级调度低级调度（进程调度，短程调度）主要是决定就绪队列中的哪个进程应获得处理机 ， 然后由分派程序（Dispatcher）分派处理机。 1.低级调度的功能： 保存处理机现场信息 按某种算法选取进程 把处理机分配给进程 2.进程调度的三个进步机制 排队器 分派器 上下文切换机制：两对切换6CPU Switch From Process to Process73.进程调度方式：1)非抢占方式：n 一旦把处理机分配给某进程后，便让该进程一直执行，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。n简单、系统开销小，实时性差 (如win31)82)抢占方式允许调度程序根据某种原则（时间片、优先权、短 进程优先），停止正在执行的进程，而将处理机重 新分配给另一进程。 （1）优先权原则 （2）短进程优先原则 （3）时间片原则有利于处理紧急任 务，故实时与分时 系统中常采用。开 销大。9 引起进程调度的因素有哪些？ 进程正常终止或异常终止 进程因某种原因阻塞：I/O请求；wait操作 等 时间片用完 抢占方式下，就绪队列中某进程的优先权 比当前执行的进程高10为提高系统吞吐量和内存利用率而引入的为提高系统吞吐量和内存利用率而引入的: :内内-外存对换功能（换出时，进程为挂起或就绪驻外外存对换功能（换出时，进程为挂起或就绪驻外 存状态）存状态）三级调度的三级调度的运行频率n低>中>高。3.1.3 3.1.3 中级调度（中程）中级调度（中程）11 在OS中的任何一种调度中，都将涉及到进 程队列，由此形成了三种类型的调度队列模 型。3.23.2调度的队列模型和调度准则调度的队列模型和调度准则121.仅有进程调度的队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度进程完成等待事件事件出现133.2.13.2.1调度的队列模型调度的队列模型2.具有高、低级调度的队列模型就绪队列CPU阻塞队列时间片完进程调度进程 完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度143.3.具有三级调度的队列模型具有三级调度的队列模型就绪队列CPU就绪、挂起队列时间片完进程调度进程 完成后备队列阻塞、挂起队列事件出现作业调度阻塞队列 等待事件挂起事件出现中级调度交互型作业153.2.2 3.2.2 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则1、面向用户的准则 （1）周转时间短（常用于批处理 系统） 概念：作业从提交> 完成的时间.分为： 驻外存等待调度时间 驻内存等待调度时间 执行时间 阻塞时间161、面向用户的准则 平均周转时间 平均带权 可见带权w越小越好,Ts为实际服务时间。3.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则 171、面向用户的准则 （2）响应时间快：（对交互性作 业） 概念：键盘提交请求到首次响 应时间 输入传送时间 处理时间 响应传送时间3.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则 181、面向用户的准则 （3）截止时间的保证（特别是实 时系统） 某任务必须开始执行的最迟时间， 或必须完成的最迟时间。（4）优先权准则：（即需要抢占 调度）3.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则 192、面向系统的准则 （1）吞吐量高（特别是批处理）： 单位时间完成作业数 （2）处理机利用率好：（因CPU贵 ，特别是大中型多用户系统） （3）各类资源的平衡利用。3.1.33.1.3选择调度方式和算法的若干准则选择调度方式和算法的若干准则 203.33.3调度算法调度算法是一个资源分配问题是一个资源分配问题 3.3.13.3.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法1.先来先服务调度算法（FCFS） 按照进程进入就绪队列的先后次序来分配处理 机。一般采用非剥夺的调度方式 特点： FCFSFCFS调度算法有利于调度算法有利于CPUCPU繁忙型的作业，而不利繁忙型的作业，而不利 于于I/OI/O繁忙型的作业繁忙型的作业( (进程进程) )。 FCFSFCFS算法比较有利于长作业算法比较有利于长作业( (进程进程) )，而不利于，而不利于 短作业短作业( (进程进程) )。21先来先服务算法实例223.33.3调度算法调度算法是一个资源分配问题是一个资源分配问题 3.3.13.3.1先来先服务和短作业（进程）优先调度算法先来先服务和短作业（进程）优先调度算法 2.短作业（进程）优先调度算法：SJ(P)F 短作业优先调度算法（SJF）用于作业调度主要任务是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短进程优先调度算法（SPF）用于进程调度主要任务是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它。可采用抢占（剥夺）或者非抢占（非剥夺）调度方式23图3-4 FCFS和SJ(P)F比较243.33.3调度算法调度算法是一个资源分配问题是一个资源分配问题2.短作业（进程）优先调度算法：SJ(P)F 优点：优点：1 1）提高吞吐量；）提高吞吐量；2 2）能有效缩短进程的周转时间；）能有效缩短进程的周转时间； 缺点：缺点：1 1）对长作业不利；）对长作业不利；2 2）不考虑）不考虑作业的紧迫程度；作业的紧迫程度；3 3）作业执行时间、剩余时间仅为）作业执行时间、剩余时间仅为估计估计* *；故故SJ(P)FSJ(P)F算法虽然是优化的，但在算法虽然是优化的，但在CPUCPU调度中很难实现。调度中很难实现。253.3.23.3.2高优先权优先调度算法高优先权优先调度算法1.优先权调度算法类型 非抢占式优先权算法 系统一旦把处理机分配给就绪队列中优先权系统一旦把处理机分配给就绪队列中优先权 最高的进程后，该进程便一直执行下去，直最高的进程后，该进程便一直执行下去，直 至完成；至完成； 或因发生某事件使该进程放弃处理机时，系或因发生某事件使该进程放弃处理机时，系 统方可再将处理机重新分配给另一优先权最统方可再将处理机重新分配给另一优先权最 高的进程。高的进程。 主要用于批处理系统中；也可用于某些对实主要用于批处理系统中；也可用于某些对实 时性要求不严的实时系统中。时性要求不严的实时系统中。261.优先权调度算法类型 抢占式优先权算法，实时性更好。 把处理机分配给优先权最高的进程，使之把处理机分配给优先权最高的进程，使之 执行。执行。 但在其执行期间，只要又出现了另一个其但在其执行期间，只要又出现了另一个其 优先权优先权更高更高的进程，进程调度程序就立即停止的进程，进程调度程序就立即停止 当前进程当前进程( (原优先权最高的进程原优先权最高的进程) )的执行，重新的执行，重新 将处理机分配给新到的优先权最高的进程。将处理机分配给新到的优先权最高的进程。273.3.23.3.2高优先权优先调度算法高优先权优先调度算法2.优先权类型： 1）静态优先权： 进程优先权在整个运行期不变。 确定优先权依据 进程类型 进程对资源的需求； 根据用户需求。 特点：简单，但低优先权作业可能长期不 被调度（饥饿）。 2）动态优先权： 如：优先权随执行时间而下降，随等待时间而 升高。 优点：长短兼顾 缺点：需经常计算各进程优 先级283.3.23.3.2高优先权优先调度算法高优先权优先调度算法(2)(2)3.高响应比优先调度算法： 响应比Rp=（Tw+Ts）/Ts1)如等待时间相同,则要求服务时间愈短,其优先权愈高-SPF.2)如要求服务时间相同,优先权决定于等待时间-FCFS。3)对长作业,若等待时间足够长，优先权也高，也能获得CPU。29常见的批处理作业调度算法常见的批处理作业调度算法l 先来先服务算法（FCFS：First Come First Serve ） l 最短作业优先算法（SJF：Shortest Job First） l 最高响应比优先算法（HRRF：Highest Response Ratio First）响应比响应比 R R = = 响应时间响应时间/ /要求服务时间要求服务时间= =（等待时间（等待时间+ +要求服务时间）要求服务时间）/ /要求服务时间要求服务时间= 1 += 1 +（等待时间（等待时间/ /要求服务时间）要求服务时间） l 基于优先级调度算法（HPF：Highest Priority First）30313233343536373839403.2.33.2.3基于时间片的轮转调度算法基于时间片的轮转调度算法1.时间片轮转 系统将所有原就绪进程按FCFS的原则，排 成一个队列，依次调度，把CPU分配给队首 进程，并令其执行一个时间片/CPU时间， 通常为10-100ms。时间片用完后，该进程 将被抢占并插入就绪队列末尾。411.时间片轮转（1 1）保证了就绪队列中的所有进程在给定的时间内）保证了就绪队列中的所有进程在给定的时间内 ，均能获得一时间片来执行，即系统在给定的时间，均能获得一时间片来执行，即系统在给定的时间 内，响应所有用户的请求。内，响应所有用户的请求。 （2 2）若进程的执行时间少于时间片，则自愿释放）若进程的执行时间少于时间片，则自愿释放 CPUCPU。 （3 3）时间片将影响：）时间片将影响：qq调度算法（太长调度算法（太长-FCFS-FCFS）；）；qq上下文切换（上下文切换（太短太短-上下文切换频上下文切换频 繁繁）；）；qq平均周转时间平均周转时间。42 4）时间片大小的确定 一个较为可取的大小是，时间片略大 于一次典型的交互所需要的时间。这样可使 大多数进程在一个时间片内完成。 43图3-6 q=1和q=4时进程的周转时间 443.2