第四章 进程的调度第二篇 操作系统进程调度的模型进程调度的算法死锁及解决进程调度引言
引言
处理机调度的主要目的：分配处理机
调度影响的因素：
响应的及时性
进程是否能在限定时间内获得处理机，对用户进行响应
周转时间（等待时间 +使用 CPU时间）
进程是否等待时间太长
系统吞吐量（进程时间 +系统开销）
CPU是否总是用在刀刃上进程调度
4.1 进程调度模型
对象：
就绪队列中的进程
动作：
决定由哪个进程获得 CPU
低级调度进程并发执行其它作业成批进入输入井 输出井内存 CPU
高级调度进程调度过程
进程调度对象：就绪队列中的进程
进程调度功能及过程
纪录当前进程的状态、保存 CPU现场
选取适当的就绪进程
进程调度算法
分配处理机：恢复选取进程的 现场
CPU
就绪队列交互用户 123
进程调度进程调度方式
4.1.2 进程调度的方式
非抢占式（非剥夺式）
现运行进程的 CPU使用权不能被中途强行剥夺
除非进程主动放弃
抢占式（剥夺式）
系统按照某种原则剥夺现行进程的 CPU使用权
将 CPU使用权分配给其他进程
抢占原则
优先权原则
时间片原则
短进程优先原则进程调度原因
4.1.3进程调度原因（调度时刻）
阻塞队列交互用户阻塞进程调度就绪队列结束时间片完唤醒现进程运行完毕现进程阻塞优先权高的进程进入就绪队列现进程“超时”
/被中断
CPU
进程调度算法类型
4.2算法类型简单的调度算法 先来先服务算法短进程优先轮转法 等时间片轮转不等时间片轮转优先权法抢占式优先权非抢占式优先权静态优先权动态优先权多级反馈队列算法
FCFS
1）先来先服务算法 FCFS
按照就绪进程进入就绪队列的先后次序进行调度
简单易实现
利于长进程,CPU繁忙型作业
不利于短进程
排队时间相对过长
CPU
就绪队列
123
SCBF
2）短进程优先算法
对系统服务时间需求短的进程优先被调度
短进程估算：
依赖于前一周期的实际 CPU时间和估计时间
系统性能改善，平均带权周转时间优于 FCFS
不利于长作业，当不断有短进程到达时，不保证长进程响应的及时性，甚至可能得不到调度其中? n为估计的第 n个 CPU 周期。 tn 为实际值。
为控制值,0≤ ≤1,常取 0.5
n+1 n nt? ＝ ＋ （ 1 － ）?
RR等时间片
3）等时间片轮转
保证人机交互的及时性
（ 1）按照 FCFS顺序从就绪队列选取进程
（ 2）每个进程分配给相同的 CPU时间片
（ 3）时间片到后将进程排到就绪队列尾
公平性的保证
响应及时性的保证
RR不等时间片
4）不等时间片轮转法
短时间片满足快速响应的需要
长时间片使周转时间降低
在保证及时响应的基础上，为不同的需求分配大小不等的时间片－－ 降低周转时间长进程短进程
I/O频繁型
CPU密集型长时间片短时间片引入“前台”、“后台” 提高系统资源利用率课堂练习
HPF
5）最高优先权调度算法（ HPF）
保证实时性。（事件响应的及时性）
（ 1）为每个进程设臵优先级
（ 2）调度时选取优先级最高的进程，相同优先级的进程按照 FCFS选取
抢占式调度：
高优先权的进程进入就绪队列时引起调度
非抢占式调度：
高优先权的进程进入就绪队列仅引起队列重排
HPF静态优先权
静态优先权
进程的优先权在进程创建时设定，以后 不会改变
优先权设定的一般依据：
（ 1）进程类型
（ 2）进程对资源的需求
（ 3）根据用户的需求优先级设定后可能造成低优先权的进程得不到运行的机会当不断有高优先进程进入就绪队列时
HPF动态优先权
动态优先权
进程的优先权在系统周转过程中动态改变就绪等待进程优先级随等待时间以?速率升高执行进程的优先级以?速率下降优先权 = 等待时间 + 要求服务时间要求服务时间等待时间一定：优先权与要求服务时间成反比要求服务时间一定：优先权与等待时间成正比短进程优先优先权低的进程也能有运行的机会多级反馈队列
6）多级反馈队列调度
综合各种算法长处
设计思想
设臵多个就绪队列
各队列优先级不一样，
分配的时间片也不一样，高优先权队列进程的时间片较小
调度算法 （见后）
多级反馈队列算法短时间片长时间片
（ 1）在选取进程时，
选取高优先权队列里的进程。 ——
分配给相应的时间片。
同一队列按照 FCFS—
—
（ 2）进程使用完时间片后，回到就绪态是则进入低一级优先权队列 ——
（ 3）当高优先权队列里没有进程时，才调度低优先权队列进程
（ 4）进程创建后进入最高优先权队列优先级调度时间片轮转动态优先权、不等时间片多级反馈队列性能
多级反馈队列的性能
（ 1）短进程
在第一级队列的时间片中完成，
满足及时响应和短进程的周转要求
（ 2）动态变化的优先权
使优先权低的进程也得到执行的机会
（ 3）动态变化的时间片
长进程在长时间等待后获得长时间片，可减少周转时间和系统开销死锁
4.3死锁问题（ dead lock）
例：
P( s1 )
P( s2 )
临界区
V( s2 )
V( s1 )
P( s2 )
P( s1 )
临界区
V( s1 )
V( s2 )
......
......,.....
......
进程 1 进程 2
就绪 就绪 执行执行 阻塞
s1
s2
阻塞状态,状态：
死锁死锁
死锁
当两个或两个以上进程因竞争资源而无休止地处于相互等待状态
死锁将使进程已占用的资源的不到利用
严重情况下，死锁“蔓延”开，会导致“死机”
Proc1
s2
Proc2
s1
死锁产生的必要条件
4.3.1 死锁产生的必要条件
死锁和“资源”密切相关
1） 资源 访问的互斥条件
2）请求和保持条件
进程在需要时才申请 资源 —— 进程对 资源 的申请是分步的
进程在申请新 资源 时，对旧 资源 仍然保持占用
3）不剥夺条件
资源 一旦获得后在 V(s)之前不放弃
4）环路等待条件死锁产生的必要条件
4）环路等待条件
存在进程 —— 资源环形链
Proc1
s2
Proc2
s1
Proc1
Proc3
Proc2
s2
s3
s1
从进程出发的箭头表示进程正在申请资源从资源出发的箭头表示已分配该资源预防死锁
4.3.2 解决死锁的方法之一 —— 预防
破坏死锁产生的四个条件的一个或几个
1）破坏互斥条件
互斥访问是大部分资源的固有属性
2）破坏请求和保持条件
资源预分配,资源利用率低
3）破坏不剥夺条件
阻塞进程释放所有的资源,进程先前工作白费
4）破坏环路等待条件
资源按序分配,资源利用率低，进程受限死锁的检测
4.3.3 死锁的检测
资源分配图
结点：
进程结点
资源结点（同类资源形成一个结点）
有向线段：
进程正申请一个资源
进程已获得一个资源
P1
P1
P1
资源分配图的化简
死锁检测法 —— 资源图的化简
P1
P2
r1 r2
1）在图中找出一个不阻塞，又不孤立的结点
2）削去该结点的所有边，
使结点成为孤立结点
3）继续步骤 1直到所有的结点都成为孤立结点，
或找不到可简化的结点若资源分配图能被完全简化，则当前状态不存在死锁。
反之，存在死锁进程，即那些非孤立结点。
资源分配图的化简
课堂练习：请化简下图
P1
P2
r1 r2
P4
P6
P5
P3
P7
作业
进程调度有哪些算法？批处理系统、分时系统和实时系统分别采用哪种调度算法
死锁产生的必要条件是哪些？
请简要描述解决死锁的几种方法。如果你是系统设计人员，你会选取哪种方式，为什么？
引言
处理机调度的主要目的：分配处理机
调度影响的因素：
响应的及时性
进程是否能在限定时间内获得处理机，对用户进行响应
周转时间（等待时间 +使用 CPU时间）
进程是否等待时间太长
系统吞吐量（进程时间 +系统开销）
CPU是否总是用在刀刃上进程调度
4.1 进程调度模型
对象：
就绪队列中的进程
动作：
决定由哪个进程获得 CPU
低级调度进程并发执行其它作业成批进入输入井 输出井内存 CPU
高级调度进程调度过程
进程调度对象：就绪队列中的进程
进程调度功能及过程
纪录当前进程的状态、保存 CPU现场
选取适当的就绪进程
进程调度算法
分配处理机：恢复选取进程的 现场
CPU
就绪队列交互用户 123
进程调度进程调度方式
4.1.2 进程调度的方式
非抢占式（非剥夺式）
现运行进程的 CPU使用权不能被中途强行剥夺
除非进程主动放弃
抢占式（剥夺式）
系统按照某种原则剥夺现行进程的 CPU使用权
将 CPU使用权分配给其他进程
抢占原则
优先权原则
时间片原则
短进程优先原则进程调度原因
4.1.3进程调度原因（调度时刻）
阻塞队列交互用户阻塞进程调度就绪队列结束时间片完唤醒现进程运行完毕现进程阻塞优先权高的进程进入就绪队列现进程“超时”
/被中断
CPU
进程调度算法类型
4.2算法类型简单的调度算法 先来先服务算法短进程优先轮转法 等时间片轮转不等时间片轮转优先权法抢占式优先权非抢占式优先权静态优先权动态优先权多级反馈队列算法
FCFS
1）先来先服务算法 FCFS
按照就绪进程进入就绪队列的先后次序进行调度
简单易实现
利于长进程,CPU繁忙型作业
不利于短进程
排队时间相对过长
CPU
就绪队列
123
SCBF
2）短进程优先算法
对系统服务时间需求短的进程优先被调度
短进程估算：
依赖于前一周期的实际 CPU时间和估计时间
系统性能改善，平均带权周转时间优于 FCFS
不利于长作业，当不断有短进程到达时，不保证长进程响应的及时性，甚至可能得不到调度其中? n为估计的第 n个 CPU 周期。 tn 为实际值。
为控制值,0≤ ≤1,常取 0.5
n+1 n nt? ＝ ＋ （ 1 － ）?
RR等时间片
3）等时间片轮转
保证人机交互的及时性
（ 1）按照 FCFS顺序从就绪队列选取进程
（ 2）每个进程分配给相同的 CPU时间片
（ 3）时间片到后将进程排到就绪队列尾
公平性的保证
响应及时性的保证
RR不等时间片
4）不等时间片轮转法
短时间片满足快速响应的需要
长时间片使周转时间降低
在保证及时响应的基础上，为不同的需求分配大小不等的时间片－－ 降低周转时间长进程短进程
I/O频繁型
CPU密集型长时间片短时间片引入“前台”、“后台” 提高系统资源利用率课堂练习
HPF
5）最高优先权调度算法（ HPF）
保证实时性。（事件响应的及时性）
（ 1）为每个进程设臵优先级
（ 2）调度时选取优先级最高的进程，相同优先级的进程按照 FCFS选取
抢占式调度：
高优先权的进程进入就绪队列时引起调度
非抢占式调度：
高优先权的进程进入就绪队列仅引起队列重排
HPF静态优先权
静态优先权
进程的优先权在进程创建时设定，以后 不会改变
优先权设定的一般依据：
（ 1）进程类型
（ 2）进程对资源的需求
（ 3）根据用户的需求优先级设定后可能造成低优先权的进程得不到运行的机会当不断有高优先进程进入就绪队列时
HPF动态优先权
动态优先权
进程的优先权在系统周转过程中动态改变就绪等待进程优先级随等待时间以?速率升高执行进程的优先级以?速率下降优先权 = 等待时间 + 要求服务时间要求服务时间等待时间一定：优先权与要求服务时间成反比要求服务时间一定：优先权与等待时间成正比短进程优先优先权低的进程也能有运行的机会多级反馈队列
6）多级反馈队列调度
综合各种算法长处
设计思想
设臵多个就绪队列
各队列优先级不一样，
分配的时间片也不一样，高优先权队列进程的时间片较小
调度算法 （见后）
多级反馈队列算法短时间片长时间片
（ 1）在选取进程时，
选取高优先权队列里的进程。 ——
分配给相应的时间片。
同一队列按照 FCFS—
—
（ 2）进程使用完时间片后，回到就绪态是则进入低一级优先权队列 ——
（ 3）当高优先权队列里没有进程时，才调度低优先权队列进程
（ 4）进程创建后进入最高优先权队列优先级调度时间片轮转动态优先权、不等时间片多级反馈队列性能
多级反馈队列的性能
（ 1）短进程
在第一级队列的时间片中完成，
满足及时响应和短进程的周转要求
（ 2）动态变化的优先权
使优先权低的进程也得到执行的机会
（ 3）动态变化的时间片
长进程在长时间等待后获得长时间片，可减少周转时间和系统开销死锁
4.3死锁问题（ dead lock）
例：
P( s1 )
P( s2 )
临界区
V( s2 )
V( s1 )
P( s2 )
P( s1 )
临界区
V( s1 )
V( s2 )
......
......,.....
......
进程 1 进程 2
就绪 就绪 执行执行 阻塞
s1
s2
阻塞状态,状态：
死锁死锁
死锁
当两个或两个以上进程因竞争资源而无休止地处于相互等待状态
死锁将使进程已占用的资源的不到利用
严重情况下，死锁“蔓延”开，会导致“死机”
Proc1
s2
Proc2
s1
死锁产生的必要条件
4.3.1 死锁产生的必要条件
死锁和“资源”密切相关
1） 资源 访问的互斥条件
2）请求和保持条件
进程在需要时才申请 资源 —— 进程对 资源 的申请是分步的
进程在申请新 资源 时，对旧 资源 仍然保持占用
3）不剥夺条件
资源 一旦获得后在 V(s)之前不放弃
4）环路等待条件死锁产生的必要条件
4）环路等待条件
存在进程 —— 资源环形链
Proc1
s2
Proc2
s1
Proc1
Proc3
Proc2
s2
s3
s1
从进程出发的箭头表示进程正在申请资源从资源出发的箭头表示已分配该资源预防死锁
4.3.2 解决死锁的方法之一 —— 预防
破坏死锁产生的四个条件的一个或几个
1）破坏互斥条件
互斥访问是大部分资源的固有属性
2）破坏请求和保持条件
资源预分配,资源利用率低
3）破坏不剥夺条件
阻塞进程释放所有的资源,进程先前工作白费
4）破坏环路等待条件
资源按序分配,资源利用率低，进程受限死锁的检测
4.3.3 死锁的检测
资源分配图
结点：
进程结点
资源结点（同类资源形成一个结点）
有向线段：
进程正申请一个资源
进程已获得一个资源
P1
P1
P1
资源分配图的化简
死锁检测法 —— 资源图的化简
P1
P2
r1 r2
1）在图中找出一个不阻塞，又不孤立的结点
2）削去该结点的所有边，
使结点成为孤立结点
3）继续步骤 1直到所有的结点都成为孤立结点，
或找不到可简化的结点若资源分配图能被完全简化，则当前状态不存在死锁。
反之，存在死锁进程，即那些非孤立结点。
资源分配图的化简
课堂练习：请化简下图
P1
P2
r1 r2
P4
P6
P5
P3
P7
作业
进程调度有哪些算法？批处理系统、分时系统和实时系统分别采用哪种调度算法
死锁产生的必要条件是哪些？
请简要描述解决死锁的几种方法。如果你是系统设计人员，你会选取哪种方式，为什么？
