第二篇操作系統 第四章冼程的调度 选程调度的模型 选程调度的犷法 死锁及解决
第四章 进程的调度 第二篇 操作系统 进程调度的模型 进程调度的算法 死锁及解决
选程调度引言 引言 ◆处理机调度的主要目的:分配处理机 ◆调度影响的因素 c响应的及时性 ÷进程是否能在限定时间内获得处理机,对用 户进行响应 o周转时间(等待时间+使用CPU时间) 进程是否等待时间太长 系统吞吐量(进程时间+系统开销) CPU是否总是用在刀刃上
进程调度引言 ◼ 引言 ◆处理机调度的主要目的：分配处理机 ◆调度影响的因素： 响应的及时性 ❖进程是否能在限定时间内获得处理机，对用 户进行响应 周转时间（等待时间+使用CPU时间） ❖进程是否等待时间太长 系统吞吐量（进程时间+系统开销） ❖CPU是否总是用在刀刃上
进程调度 4.1进程调度模型 ◆对象: c就绪队列中的进程 动作: c决定由哪个进程获得cPU 低级调度 进程并发执行 作业成批进入 内存□cPU 输入井 输出井其它 高级调度
进程调度 ◼ 4.1 进程调度模型 ◆对象： 就绪队列中的进程 ◆动作： 决定由哪个进程获得CPU 低级调度 进程并发执行 其它 作业成批进入 输入井 输出井 内存 CPU 高级调度
选程调度过程 交互用户 3 1+CPU 就绪队列 进程调度 ■进程调度对象:就绪队列中的进程 ■进程调度功能及过程 ◆纪录当前进程的状态、保存CPU现场 ◆选取适当的就绪进程 c进程调度算法 ◆分配处理机:恢复选取进程的现场
进程调度过程 ◼ 进程调度对象：就绪队列中的进程 ◼ 进程调度功能及过程 ◆纪录当前进程的状态、保存CPU现场 ◆选取适当的就绪进程 进程调度算法 ◆分配处理机：恢复选取进程的现场 CPU 就绪队列 交互用户 3 2 1 进程调度
选程调度方式 4.12进程调度的方式 ◆非抢占式(非剥夺式) 现运行进程的cPU使用权不能被中途强行剥夺 c除非进程主动放弃 ◆抢占式(剥夺式) c系统按照某种原则剥夺现行进程的cPU使用权 c将CPU使用权分配给其他进程 c抢占原则 优先权原则 时间片原则 短进程优先原则
进程调度方式 ◼ 4.1.2 进程调度的方式 ◆非抢占式（非剥夺式） 现运行进程的CPU使用权不能被中途强行剥夺 除非进程主动放弃 ◆抢占式（剥夺式） 系统按照某种原则剥夺现行进程的CPU使用权 将CPU使用权分配给其他进程 抢占原则 ❖优先权原则 ❖时间片原则 ❖短进程优先原则
选程调度原因 41.3进程调度原因(调度时刻) 时间廾完被中断 交互用 结束 ↓就缁■→→c@→ 现进程运行完毕 进程调度 唤醒魏进程阻塞 阻塞 现进程“超时” 优先权高的进程进入就绪队列 独塞队列
进程调度原因 ◼ 4.1.3进程调度原因（调度时刻） 阻塞队列 交互用户 阻塞 进程调度 就绪队列 结束 时间片完 唤醒 现进程运行完毕 现进程阻塞 优先权高的进程进入就绪队列 现进程“超时” /被中断 CPU
选程调度犷法类烈 42算法类型 先来先服务算法 简单的调度算法1短进程优先 等时间片轮转 轮转法 不等时间片轮转 抢占式优先权 优先权法非抢占式优先权 静态优先权 动态优先权 多级反馈队列算法
进程调度算法类型 ◼ 4.2算法类型 简单的调度算法 先来先服务算法 短进程优先 轮转法 等时间片轮转 不等时间片轮转 优先权法 抢占式优先权 非抢占式优先权 静态优先权 动态优先权 多级反馈队列算法
FCFS 1)先来先服务算法FcFs ◆按照就绪进程进入就绪队列的先后次序进行调度 c简单易实现 c利于长进程,CPU繁忙型作业 不利于短进程 ÷排队时间相对过长 321 CPU 就绪队列
FCFS ◼ 1）先来先服务算法FCFS ◆按照就绪进程进入就绪队列的先后次序进行调度 简单易实现 利于长进程，CPU繁忙型作业 不利于短进程 ❖排队时间相对过长 CPU 就绪队列 3 2 1
SCBF 2)短进程优先算法 ◆对系统服务时间需求短的进程优先被调度 ◆短进程估算 c依赖于前一周期的实际cPU时间和估计时间 T n+1 +(1-), 其中[n为估计的第n个CPU周期。tn为实际值。 为控制值,0≤≤1,常取05 吣系统性能改善,平均带权周转时间优于FCFS c不利于长作业,当不断有短进程到达时,不保 证长进程响应的及时性,甚至可能得不到调度
SCBF ◼ 2）短进程优先算法 ◆对系统服务时间需求短的进程优先被调度 ◆短进程估算： 依赖于前一周期的实际CPU时间和估计时间 系统性能改善，平均带权周转时间优于FCFS 不利于长作业，当不断有短进程到达时，不保 证长进程响应的及时性，甚至可能得不到调度 其中Ʈ n为估计的第n个CPU 周期。tn 为实际值。 为控制值，0≤ ≤1，常取 0.5 n+1 n n Ʈ ＝ t ＋ （1 － ）Ʈ
RR等时间片 3)等时间片轮转 ◆保证人机交互的及时性 c(1)按照CFS顺序从就绪队列选取进程 o(2)每个进程分配给相同的CPU时间片 o(3)时间片到后将进程排到就绪队列尾 ◆公平性的保证 ◆响应及时性的保证
RR等时间片 ◼ 3）等时间片轮转 ◆保证人机交互的及时性 （1）按照FCFS顺序从就绪队列选取进程 （2）每个进程分配给相同的CPU时间片 （3）时间片到后将进程排到就绪队列尾 ◆公平性的保证 ◆响应及时性的保证