大学操作系统原理《处理机调度》课堂讲授课件

2026操作系统原理：处理机调度三级调度·调度时机·经典算法·性能比较课程导览01调度基础概念与三级调度层次02调度时机何时调度与切换机制03经典算法五种算法原理与例题04比较展望横向对比与现代实践01调度基础多道程序下，CPU是稀缺资源多道程序让CPU成为稀缺资源医院分诊：医生只有一位，候诊病人很多，分诊规则决定谁先就诊谁来运行、运行多久、下一个轮到谁——必须由一套规则决定，这就是处理机调度。单道时代资源独占，无竞争一个进程独占全部资源内存中只有一个进程，CPU、内存、外设全归它独占，不存在资源竞争。多道时代CPU成为稀缺资源多进程争用唯一CPU多个进程并发驻留内存，而CPU只有一个，同一时刻只能让一个进程运行。定位调度的地位多道程序设计的基础调度是多道程序设计的基础，也是操作系统设计的核心问题之一。三级调度构成完整调度体系高级调度作业调度作业调度，频率最低从外存后备队列选作业调入内存，分配资源、建立进程。每个作业通常只调入、调出各一次。作业调度中级调度内存调度内存调度，本质是对换把暂时无法运行的进程换出到外存挂起，腾出内存。条件具备再调回内存。内存调度低级调度进程调度进程调度，不可或缺从就绪队列按算法选进程分配CPU，频率极高。每几十毫秒一次。进程调度

后续算法均指低级调度三级调度各管一段状态迁移引入挂起后，五状态扩展为七状态模型：新增就绪挂起、阻塞挂起。状态模型：被换出外存的进程，其PCB仍驻留内存，由挂起队列统一管理，系统得以持续跟踪。调度层级决定状态流转，状态流转支撑并发执行。01高级调度作业从无→创建态→就绪态，获得竞争CPU资格，频率最低。02中级调度挂起态进程回到就绪态，完成内外存搬移，频率居中。03低级调度就绪态→运行态，真正占用CPU，频率最高。五个指标衡量调度优劣五项指标指向不同目标，往往相互牵制：追求高吞吐量可能牺牲响应时间，追求公平则付出更多上下文切换开销。理解这组指标，才能真正读懂每个算法的取舍。五项指标指向不同目标，往往相互牵制：追求高吞吐量可能牺牲响应时间，追求公平则付出更多上下文切换开销。理解这组指标，才能真正读懂每个算法的取舍。CPU使用率CPU工作时间的百分比，反映忙闲程度。吞吐量单位时间完成的进程数，即系统计算带宽。周转时间进程从提交到完成经历的全部时间。等待时间进程在就绪队列中排队等待的总时长。响应时间发出请求到首次获得响应的时间，对交互式系统尤为关键。02调度时机与机制何时换人，如何换人四类事件触发调度进程调度在四类时机被触发01进程结束→正常完成或异常终止，CPU被释放，系统从就绪队列另选进程；队列为空则运行闲逛进程。02进程阻塞→运行中的进程因

I/O请求、信号量操作等无法继续，CPU转交其他就绪进程。03时间片用完→分时系统中，进程耗尽分配的时间片，被强制换下。04更高优先级就绪→出现更高优先级进程就绪时，为保证其及时运行，当前进程被抢占。触发不等于立即切换，实际时机还受上下文限制。抢占与非抢占决定调度方式非抢占式进程一旦获得CPU，运行至完成或主动放弃，调度程序只能等待事件结束再决策。早期批处理系统多用非抢占式：实现简单，响应迟缓。抢占式中断响应后调度程序即可介入，当前进程可被更高优先级或时间片到期换出。现代通用操作系统普遍采用抢占式。调度器由三个部件协作三者各司其职，共同完成从选人到换人的全过程。排队器就绪队列管理就绪进程按策略插入一个或多个就绪队列，供调度程序挑选。按策略入队分派器CPU分配执行依据调度程序选定结果，把进程从就绪队列取出，将CPU真正分配给它。依选定结果分派上下文切换器现场保存与恢复先把当前进程上下文保存到其PCB，再装入分派程序上下文，随后把新进程CPU现场载入各寄存器。保存与装入现场上下文切换是有代价的必要环节理解这份开销，才能体会RR算法中时间片设计为何必须谨慎权衡。理解这份开销，才能体会

RR算法中时间片设计为何必须谨慎权衡。切换即搬移现场进程切换要把当前进程的寄存器、程序计数器等状态保存下来，再恢复新进程的状态，期间执行大量

load

和

store

指令，耗时可观。硬件优化：两组寄存器现代硬件常设两组寄存器——一组内核用、一组用户用，切换时只改指针指向当前寄存器组，省去逐项搬移。Linux的实现路径调度经

schedule()

函数触发，调用

context_switch

完成进程上下文切换，其中

switch_to

负责关键的寄存器级切换。03经典调度算法从排队到反馈，五种策略各有取舍FCFS：最简单的排队逻辑“按到达就绪队列的先后顺序执行，先到先得”——如同超市收银台排队，先来者先被服务。—最直观的调度规则非抢占式调度规则·性质·实现规则按到达就绪队列的先后顺序执行，先到先得。性质非抢占式——进程一旦获得CPU，就一直运行到完成或主动放弃（如等待I/O）。实现只需一个先入先出队列，无额外排序开销。评价优点·缺点·定位优点简单、绝对公平，所有任务一视同仁。缺点队首若为长任务，后续短任务被迫等待，拖长平均等待时间、降低吞吐量，对交互式系统不友好。定位常被用作评价其他算法优劣的基准。FCFS的护航效应护航效应：一个长进程抢先占住CPU，像大车带队，压住后面所有短进程。排队顺序决定体验，FCFS对短进程最不友好三个进程按P1→P2→P3顺序到达FCFS调度·先到先服务进程执行时间开始时刻等待时间P12400P232423P332721P1、P2、P3按顺序到达，P1=24、P2=3、P3=3。14.67平均等待时间24.67平均周转时间护航效应的代价视频转码

120秒在前，数据库查询

3秒只能干等120秒长任务卡住短任务，正是护航效应的由来SJF：优先照顾最短的任务核心思路CPU空闲时，从就绪队列中挑预估运行时间最短的进程先执行，快速消化短任务以压低整体等待。两种形态非抢占式短进程先跑完，不被打断抢占式（SRTF）运行中一旦出现剩余时间更短的新进程，立即抢下CPU优势平均等待时间理论最优有效提升吞吐量代价短作业持续到达时，长作业可能迟迟得不到执行，产生饥饿需预先知道每个进程的运行时长，实际系统难以精确获得，只能靠声明或历史统计估算SJF例题与饥饿风险沿用P1、P2、P3执行时间为

24、3、3，同一时刻到达。短任务受益，长任务可能永远等待先短后长SJF执行顺序P2（3）→P3（3）→P1（24）等待时间：P2=0，P3=3，P1=6平均等待时间约3vs14.67FCFS代价：饥饿公平性风险短作业持续涌入时，P1可能永远无法执行SJF追求效率，牺牲公平RR：时间片轮转保公平“时间片轮转：把CPU时间切成固定长度的时间片，就绪队列按FCFS顺序轮流”—公平调度核心机制时间片轮转把CPU时间切成固定长度的时间片就绪队列按FCFS顺序轮流占用一个时间片用完未结束则放回队尾重新排队解决什么问题公平性

长任务长期霸占处理机，其他任务完全无响应

每个进程周期性获得CPU，公平性显著提升，无饥饿问题实现与效果抢占式调度通常是抢占式，依赖时钟中断标记时间片到期时间片合理→交互响应流畅；设置不当→性能迅速劣化时间片轮转以公平换响应，设置不当则性能劣化时间片长度是关键权衡时间片通常取10–100毫秒，取值直接决定算法表现。理想取值目标：切换开销占比低，且多数交互请求能在几个时间片内得到响应。RR平均等待时间一般、吞吐量不如SJF，但公平与响应性出色，在桌面系统中不可替代。时间片取值：10–100毫秒过短进程频繁切换，上下文切换开销占比过高，CPU大量时间浪费在换人而非干活。过长轮转退化为FCFS，交互响应变差，失去分时意义。优先级调度：按重要性分派核心规则：CPU始终选择就绪队列中优先级最高的进程执行。动态调整能根据运行状态优化调度，但需专门逻辑维护优先级变化，带来额外计算开销。与前两种算法的差异FCFS

只看先后，SJF

只看长短优先级调度把“谁更重要”纳入决策，灵活性更强，适合实时系统等需区分紧急程度的场景两种优先级类型静态优先级：进程创建时确定，此后不再改变动态优先级：随等待时间、CPU使用情况等因素调整饥饿问题与老化机制饥饿成因：高优先级任务持续到达时，低优先级进程长期就绪却得不到CPU老化机制让低优先级进程最终也能获得执行。饥饿成因高优先级任务持续到达时，低优先级进程长期就绪却得不到CPU，形成饿死。老化机制优先级随等待时间逐步提升，等待越久优先级越高，最终低优先级进程也能排到前面获得执行。代价与价值老化增加了动态调整开销，但有效缓解饥饿，是有实用价值的折中设计。多级反馈队列：综合各家之长FCFS简单但低效SJF理论最优却需预知运行时间RR公平但平均等待一般优先级调度灵活却可能饿死低优先级进程MFQ的解法多级反馈队列设置多个就绪队列，高优先级队列时间片小、响应快，低优先级队列时间片大、适合长任务。关键特征是进程可在队列间移动——这就是"反馈"。动态降级新进程先进入最高优先级队列；一个时间片内没完成就降到下一级，逐级下沉直至完成。无需预知运行时间多级反馈队列的调度规则01规则一：新进程入最高级新进程进入最高优先级队列，获得快速响应机会。02规则二：时间片用完降级时间片耗尽仍未完成，降至下一级队列，时间片同步增大。03规则三：I/O阻塞后回升因I/O阻塞的进程完成后回到较高优先级队列，交互式任务持续受优待。04规则四：高优先级优先服务仅当高优先级队列全空时，才服务低优先级队列；低优先级内部采用时间片轮转或FCFS。8单位16单位32单位64单位时间片随优先级下降而递增——短任务在高优先级快速完成，长任务在低优先级用大时间片慢慢跑。多级反馈队列例题队列参数多级反馈队列·时间片设置队列0时间片4单位队列1时间片8单位P1、P2、P3运行时间10、3、6

单位执行过程4个阶段P2先到队列0用

3

个单位，直接完成P1入队0跑满

4

个单位，时间片耗尽，降入队列1P3入队0跑满

4

个单位，同样降入队列1低优先级阶段P1在队列1续跑

6

个单位完成；P3再跑剩余

2

个单位完成结论短任务

P2

在高优先级队列即刻完成；长任务自动下沉，却始终不会被饿死——直观体现MFQ“短快长稳、公平不饿死”。多级反馈队列的价值与落地公平、响应与吞吐，在一个框架里动态平衡真实系统已落地：UNIX

采用此算法；LinuxCFS

以红黑树管理进程、追踪虚拟运行时间，被视为多级反馈思想的变体。短任务响应快第一级小时间片队列即可完成，兼具

SJF

与

RR

优点。长任务不饿死降级后低优先级队列最终被服务，配合

老化机制

兜底。交互进程延迟小频繁

I/O

的进程每次I/O后回到高优先级，用户感知顺畅。全程自适应无需预知运行时长，系统

动态调整。真实系统已落地UNIX

采用此算法；LinuxCFS

以红黑树管理进程、追踪虚拟运行时间，被视为多级反馈思想的变体。04算法比较与展望没有完美算法，只有合适场景五项指标横向对比评价算法，本质是看它在五项指标间的取舍。FCFS实现最简单、无排序开销，但平均等待时间长、吞吐量低，护航效应明显。SJF平均等待时间最优、吞吐量高，却依赖预估运行时间，且有饥饿风险。RR响应性好、公平无饥饿，是分时系统标准选择，但平均等待与吞吐表现一般。优先级调度灵活、能体现任务重要性，代价是低优先级饥饿与动态开销。MFQ队列迁移与老化机制兼顾短任务快响应、长任务不饿死、I/O任务受优待，公平与效率兼得。没有完美算法，只有匹配场