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