第三章处理机调度与死锁New80130.ppt

教学目的与要求 理解处理机调度的概念和调度的层次 掌握各种作业、进程调度算法和实时调度算法 理解死锁的基本概念 掌握死锁的处理方法 3.1 处理机调度的层次 3.1.1高级调度 （作业调度、长程调度、接纳调度） 1、作业和作业步 作业：包含程序、数据和作业说明书。 作业步：作业执行过程中的每一个加工步骤 作业流：作业进入系统，依次存于外存形成作业流 2、作业控制块（JCB） 它是作业在系统中存在的标志，其中保存了系统 对作业进行管理和调度所需的全部信息。 内容： 作业标识，用户名，作业类型，作业状态，调度信息等 进入系统－建立JCB-插入相应后备队列-作业调度-作业控制－作业结束－回收资源 3、作业调度 将外存作业调入内存，创建PCB等，插入就绪队列。 一般用于批处理系统，分/实时系统一般直接入内存，无此环节。 调度特性 接纳作业数（内存驻留数，多道程序度） 太多――― 周转时间T长 太少――― 系统效率低 接纳策略：即采用何种调度算法：FCFS、短作业优先等 3.1.2 低级调度（进程调度，短程调度） 主要是决定就绪队列中的哪个进程应获得处理机， 然后由分派程序（Dispatcher）分派处理机。 1.低级调度的功能： 保存处理机现场信息 按某种算法选取进程 把处理机分配给进程 2.进程调度的三个进步机制 排队器 分派器 上下文切换机制：两对切换 3.进程调度方式： 1)非抢占方式： 简单、系统开销小，实时性差 (如win31) 2)抢占方式 （1）优先权原则 （2）短进程优先原则 （3）时间片原则 引起进程调度的因素有哪些？ 进程正常终止或异常终止 进程因某种原因阻塞：I/O请求；wait操作等 时间片用完 抢占方式下，就绪队列中某进程的优先权比当前执行的进程高 3. 2调度的队列模型和调度准则 1.仅有进程调度的队列模型 3.2.1调度的队列模型 2.具有高、低级调度的队列模型 3.具有三级调度的队列模型 3.2.2 选择调度方式和调度算法的若干准则 1、面向用户的准则 （1）周转时间短（常用于批处理系统） 概念：作业从提交―― 完成的时间.分为： 驻外存等待调度时间 驻内存等待调度时间 执行时间 阻塞时间 3.1.3选择调度方式和算法的若干准则 1、面向用户的准则 平均周转时间 平均带权 可见带权w越小越好,Ts为实际服务时间。 3.1.3选择调度方式和算法的若干准则 1、面向用户的准则 （2）响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间 输入传送时间 处理时间 响应传送时间 （3）截止时间的保证（特别是实时系统） （4）优先权准则：（即需要抢占调度） 3.1.3选择调度方式和算法的若干准则 2、面向系统的准则 （1）吞吐量高（特别是批处理）：单位时间完成作业数 （2）处理机利用率好：（因CPU贵，特别是大中型多用户系统） （3）各类资源的平衡利用。 3.3调度算法——是一个资源分配问题 3.3.1先来先服务和短作业（进程）优先调度算法 1.先来先服务调度算法（FCFS） 特点：简单，有利于长作业（进程） 即CPU繁忙性作业,不利于短作业（进程） 2.短作业（进程）优先调度算法：SJ(P)F 提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 特点：对长作业不利，有可能得不到服务 估计时间不易确定 先来先服务算法实例 图3-4 FCFS和SJ(P)F比较 3.3.2高优先权优先调度算法 1.优先权调度算法类型 非抢占式优先权算法 抢占式优先权算法，实时性更好。 2.优先权类型： 1）静态优先权： 进程优先权在整个运行期不变。 确定优先权依据 进程类型 进程对资源的需求； 根据用户需求。 特点：简单，但低优先权作业可能长期不被调度（饥饿）。 （例子MIT IBM7049 ） 3.3.2高优先权优先调度算法(2) 2）动态优先权： 如：优先权随执行时间而下降，随等待时间而升高。 优点：长短兼顾 缺点：需经常计算各进程优先级 3.高响应比优先调度算法： 响应比Rp=（Tw+Ts）/Ts 特点： （1）短作业RP大。 （2）Ts（要求服务时间）相同的进程间相当于FCFS。 （3）长作业等待一段时间仍能得到服务。 常见的批处理作业调度算法 先来先服务算法（FCFS：First Come First Serve） 最短作业优先算法（SJF：Shortest Job First） 最短剩余时间优先（SRTF: Shortest Remaining Time First） 最高响应比优先算法（HRRF：Highest Response Ratio First） 响应比 R = 响应时间/要求服务时间 =（等待时间+要求服务时间