[工学]OS-Ch03-处理机的调度和死锁.ppt

3.1 处理机调度的基本概念 3.1高、中、低三级调度 1、高级调度（作业调度、长程调度、接纳调度） 将外存作业调入内存，创建PCB等，插入就绪队列。 一般用于批处理系统，分/实时系统一般直接入内存，无此环节。 调度特性 1.接纳作业数（内存驻留数） 太多――― 周转时间T长 太少――― 系统效率低 2.接纳策略：即采用何种调度算法：FCFS、短作业优先等 处理机调度的基本概念（2） 2、低级调度（进程调度，短程调度） 主要是由分派程序（Dispatcher）分派处理机。 1.非抢占方式： 简单，实时性差 (如win31) 2.抢占方式 （1）时间片原则 （2）优先权原则 （3）短作业优先原则。 问？ 三种调度被引发的事件？ 事件的表现方式？ 3.1.2调度的队列模型 一、仅有进程调度的队列模型 3.1.2调度的队列模型 二、具有高/低级模型 三、具有三级调度 3.1.3选择调度方式和算法的若干准则 一、面向用户的准则 1．周转时间短（常用于批处理系统） 概念：作业从提交―― 完成的时间.分为： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间 3.1.3选择调度方式和算法的若干准则 一、面向用户的准则 平均周转时间 平均带权 可见带权w越小越好,Ts为实际服务时间。 3.1.3选择调度方式和算法的若干准则 一、面向用户的准则 2．响应时间快：（对交互性作业） 概念：键盘提交请求到首次响应时间 （1）输入传送时间 （2）处理时间 （3）响应传送时间 3．截止时间的保证（特别于实时系统） 4．优先权准则：（即需要抢占调度） 3.1.3选择调度方式和算法的若干准则 二、面向系统的准则 1．吞吐量高（特别于批处理）：单位时间完成作业数 2．处理机利用率好：（因CPU贵，特别于大中型多用户系统） 3．各类资源的平衡利用。（？折算标准） 3.2调度算法——是一个资源分配问题 3.2.1先来先服务和短作业（进程）优先调度算法 1.FCFS 特点：简单，有利于长作业 即CPU繁忙性作业 2.短作业进程优先调度算法：SJ(P)F 提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 特点：对长作业不利，有可能得不到服务（饥饿） 估计时间不易确定 示例 图3.4FCFS和SJF比较 3.2.2高优先权优先调度算法 1.优先权调度算法类型 非抢占式优先权算法 抢占式优先权算法，实时性更好。 2.优先权类型： 1．静态优先权： 进程优先权在整个运行期不变。 确定优先权依据 （1）进程类型 （2）进程对资源的需求； （3）根据用户需求。 特点：简单，但低优先权作业可能长期不被调度。 3.2.2高优先权优先调度算法(2) 2．动态优先权： 如：优先权随执行时间而下降，随等待时间而升高。 响应比Rp=（等待时间＋服务时间）/服务时间 作为优先权 优点：长短兼顾 缺点：需计算Rp 3.高响应比优先算法： 特点： 响应比Rp=（tw+ts）/ts （1）短作业RP大。 （2）ts（要求服务时间）相同的进程间相当于FCFS。 （3）长作业等待一段时间仍能得到服务。 3.2.3基于时间片的轮转调度算法 1.时间片轮转 时间片大小的确定 太大：退化为FCFS； 太小：系统开销过大 系统对响应时间的要求；T=nq 就绪队列中进程的数目； 系统的处理能力：（应保证一个时间片处理完常用命令） 3.2.3基于时间片的轮转调度算法 2.多级反馈队列调度 特点：长、短作业兼顾，有较好的响应时间 （1）短作业一次完成； （2）中型作业周转时间不长； （3）大型作业不会长期不处理。 3.3实时调度 3.3.1实现实时调度的基本条件 1．提供必要的调度信息 （1）就绪时间； （2）开始/完成截止时间； （3）处理时间； （4）资源要求； （5）优先级； 2．系统处理能力强 3.3实时调度 3.3.1实现实时调度的基本条件 3.采用抢占调度方式 剥夺方式：一般都采用此 非剥夺方式（实现简单）：一般应使实时任务较小，以及时放弃CPU。 4.具有快速切换机制 具有快速响应外部中断能力。 快速任务分派 3.3.2实时调度算法的分类 1非抢占式调度算法 时间片轮转 秒级 非抢占优先权（协同） 秒~毫秒级 2抢占式调度算法 时钟中断抢占优先权 毫秒级 基于抢占点抢占 立即抢占immediate preemption 毫秒-微秒级 只要不在临界区即抢占（中断引发） 3.3.3常用的几种实时调度算法 1.最早截止时间优先EDF（earliest deadline first)算法 根据任务的截止时间来确定任务的优先级 截止时间越早，优先级越高 可以是抢占式或非抢占式