等待事件1 等待事件2
三、具有三级调度
作业调度
时间片完
后备队列 交互型作业
就绪队列
中级调度 就绪、挂起队列
事件出现 阻塞、挂起队列
阻塞队列
进程调度 CPU
进程 完成
事件出现 挂起
等待事件
3.1.3选择调度方式和算法的若干准则
❖ 一、面向用户的准则 ‫ ٭‬1．周转时间短（常用于批处理系统） ▪ 概念：作业从提交――> 完成的时间.分为： ▪ （1）驻外等待调度时间 ▪ （2）驻内等待调度时间 ▪ （3）执行时间 ▪ （4）阻塞时间
❖ 2.优先权类型： ‫ ٭‬1．静态优先权： ▪ 进程优先权在整个运行期不变。 ▪ 确定优先权依据 – （1）进程类型 – （2）进程对资源的需求； – （3）根据用户需求。 ▪ 特点：简单，但低优先权作业可能长期不被 调度。
3.2.2高优先权优先调度算法(2)
❖ 2．动态优先权： ‫ ٭‬如：优先权随执行时间而下降，随等待时间而升高。 ‫ ٭‬响应比Rp=（等待时间＋服务时间）/服务时间 作为优 先权 ‫ ٭‬优点：长短兼顾 缺点：需计算Rp
❖ 2、低级调度（进程调度，短程调度） ❖ 主要是由分派程序（Dispatcher）分派处理机。
‫ ٭‬1.非抢占方式： 简单，实时性差 (如win31)
‫ ٭‬2.抢占方式 （1）时间片原则 （2）优先权原则 （3）短作业优先原则。
❖3、中级调度（中程） ❖为提高系统吞吐量和内存利用率而引入的一内------外存对 换功能（换出时，进程为挂起或就绪驻外状态）
图3－5多级队列反馈调度算法
就绪队列1 就绪队列2 就绪队列3 就绪队列n
S1
至CPU
S2
至CPU
S3
至CPU
Sn
至CPU
时间片：S1<S2<S3
3.3实时调度
❖ 3.3.1实现实时调度的基本条件 ‫ ٭‬1．提供必要的调度信息 ▪ （1）就绪时间； ▪ （2）开始/完成截止时间； ▪ （3）处理时间； ▪ （4）资源要求； ▪ （5）优先级；
3.1.3选择调度方式和算法的若干准则
❖ 一、面向用户的准则
‫ ٭‬平均周转时间
1n
T n [ i1 Ti ]
‫ ٭‬平均带权
1 n
W [
Ti ]
n T i1 s
‫ ٭‬可见带权w越小越好,Ts为实际服务时间。
3.1.3选择调度方式和算法的若干准则
❖ 一、面向用户的准则 ‫ ٭‬2．响应时间快：（对交互性作业） ▪ 概念：键盘提交请求到首次响应时间 ▪ （1）输入传送时间 ▪ （2）处理时间 ▪ （3）响应传送时间 ‫ ٭‬3．截止时间的保证（特别于实时系统） ‫ ٭‬4．优先权准则：（即需要抢占调度）
例
进程名 到达时 服务时 开始执 完成时 周转时 带权周
间
间
行时间 间
间
转时间
A
0
1
0
1
1
1
B
1
100 1
101 100 1
C
2
1
101 102 100 100
D
3
100 102 202 199 1.99
FCFS SJF
图3.4FCFS和SJF比较
进程名 到达时间 服务时间 完成时间 周转时间 带权周转时间 完成时间 周转时间 带权周转时间
第三章 处理机的调度和死锁
整体概况
+ 概况1
您的内容打在这里，或者通过复制您的文本后。
概况2
+ 您的内容打在这里，或者通过复制您的文本后。
概况3
+ 您的内容打在这里，或者通过复制您的文本后。
处理机调度与死锁
3.1 处理机调度的基本概念
❖ 3.1高、中、低三级调度 ❖ 1、高级调度（作业调度、长程调度、接纳调度）
▪ 太大：退化为FCFS； ▪ 太小：系统开销过大
‫ ٭‬系统对响应时间的要求；T=nq ‫ ٭‬就绪队列中进程的数目； ‫ ٭‬系统的处理能力：（应保证一个时间片处理完常用命令）
3.2.3基于时间片的轮转调度算法
❖ 2.多级反馈队列调度 ‫ ٭‬特点：长、短作业兼顾，有较好的响应时间 ▪ （1）短作业一次完成； ▪ （2）中型作业周转时间不长； ▪ （3）大型作业不会长期不处理。
ABCDE 0 1 2 34 4 3 5 24 4 7 12 14 18 4 6 10 11 14 1 2 2 5.5 3.5 4 9 18 6 13 4 8 16 3 9 1 2.67 3.1 1.5 2.25
平均
9 2.8 8 2.1
3.2.2高优先权优先调度算法
❖ 1.优先权调度算法类型 ‫ ٭‬非抢占式优先权算法 ‫ ٭‬抢占式优先权算法，实时性更好。
▪ 将外存作业调入内存，创建PCB等，插入就绪 队列。
▪ 一般用于批处理系统，分/实时系统一般直接 入内存，无此环节。
‫ ٭‬调度特性 ▪ 1.接纳作业数（内存驻留数） 太多―――> 周转时间T长 太少―――> 系统效率低 ▪ 2.接纳策略：即采用何种调度算法：FCFS、短 作业优先等
处理机调度的基本概念（2）
❖运行频率：低>中>高。
3.1.2调度的队列模型
❖ 一、仅有进程调度的队列模型
时间片完
交互用户
就绪队列
事件出现 阻塞队列
进程完成 进程调度 CPU 等待事件
3.1.2调度的队列模型
❖ 二、具有高/低级模型
作业调度
时间片完
后备队列
就绪队列
进程调度
C件2出现
阻塞队列 阻塞队列
❖ 3.高响应比优先算法： ‫ ٭‬特点： ‫ ٭‬响应比Rp=（tw+ts）/ts ‫（ ٭‬1）短作业 RP大。 ‫（ ٭‬2）ts（要求服务时间）相同的进程间相当于FCFS。 ‫（ ٭‬3）长作业等待一段时间仍能得到服务。
3.2.3基于时间片的轮转调度算法
❖ 1.时间片轮转 ‫ ٭‬时间片大小的确定
3.1.3选择调度方式和算法的若干准则
❖ 二、面向系统的准则 ‫ ٭‬1．吞吐量高（特别于批处理）：单位时间完成作 业数 ‫ ٭‬2．处理机利用率好：（因CPU贵，特别于大中型 多用户系统） ‫ ٭‬3．各类资源的平衡利用。（？折算标准）
3.2调度算法——是一个资源分配问题
❖ 3.2.1先来先服务和短作业（进程）优先调度算法 ‫ ٭‬1.FCFS ▪ 特点：简单，有利于长作业 即CPU繁忙性作业 ‫ ٭‬2.短作业进程优先调度算法：SJ(P)F ▪ 提高了平均周转时间和平均带权周转时间（从而提 高了系统吞吐量） ▪ 特点：对长作业不利，有可能得不到服务（饥饿） ▪ 估计时间不易确定