[!info] related notes 操作系统 MOC

进程调度与 CPU 调度算法

速记结论（背就够用）

• 交互系统：RR、多级反馈队列
• 批处理系统：FCFS、SJF、HRRN
• 饥饿：SJF/优先级/（不公平的资源分配）常见
• 时间片：过大 -> FCFS；过小 -> 切换开销大

一个很实用的分类：

• 是否抢占：非抢占（FCFS/SJF/HRRN） vs 抢占（SRTF/抢占式优先级/RR/MLFQ）
• 是否需要“未来/先验信息”：SJF/SRTF 需要服务时间/剩余时间（题目通常直接给）

必背指标

• 周转时间 = 完成时间 - 到达时间
• 带权周转时间 = 周转时间 / 服务时间
• 等待时间、响应时间、吞吐量、CPU 利用率

常见题目默认：

• 到达时间不同：进程在到达前不在就绪队列
• 非抢占：一旦上 CPU，除非完成/阻塞，否则不会被换下
• 抢占：发生“更优进程到达/时间片用尽”等事件时切换

计算题模板（怎么做题）

拿到题干一般按这个顺序：

1. 画时间轴（Gantt chart）
2. 写出每个进程的开始/结束时刻
3. 算：完成时间、周转时间、带权周转时间、等待时间
4. 平均值 = 所有进程求和 / 进程数

如果要算等待时间，常用等价式：

• 等待时间 = 周转时间 - 服务时间

常见坑：

• 到达时间不同：就绪队列不是“从 0 开始全都有”
• 抢占式算法（SRTF 等）：时间轴会被切碎
• RR：注意每个时间片结束时是否有新进程到达，入队顺序要按题目规则

常见算法（记住特性 + 易错点）

• FCFS：简单；短作业吃亏（护航效应）
• SJF：平均等待时间小；长作业可能饥饿
• SRTF：SJF 抢占版
• HRRN：响应比 = (等待+服务)/服务；兼顾长短作业
• RR：时间片轮转；时间片太大退化 FCFS，太小切换开销大
• 优先级：可能饥饿
• 多级反馈队列：高频；新进程高优先级，耗完时间片降级

FCFS（先来先服务，非抢占）

• 规则：按到达顺序排队执行
• 特点：实现最简单；平均等待时间可能很差

SJF（最短作业优先，非抢占）

• 规则：就绪队列中选择服务时间最短的
• 特点：平均等待时间最小（理论上）；长作业易饥饿

SRTF（最短剩余时间优先，抢占）

• 规则：任何时刻选择剩余时间最短的执行；新进程到达可能抢占
• 易错点：切换点是“新进程到达”时刻，不是任意时刻

HRRN（高响应比优先，非抢占）

• 响应比：R = (等待时间 + 服务时间) / 服务时间
• 特点：兼顾长短作业；极端情况下仍可能饥饿（但比 SJF 好）

RR（时间片轮转，抢占）

• 规则：每个进程最多运行一个时间片 q，用尽则入队尾
• 易错点：时间片结束时，同时有新进程到达的入队顺序按题目规则（常见：先把新到的入队，再把用尽时间片的入队，或相反）

优先级调度（可抢占/非抢占）

• 特点：实现简单；容易饥饿
• 常见补救：aging（等待越久优先级越高）

多级反馈队列 MLFQ（抢占，面试/笔试高频）

• 核心：多个就绪队列，不同优先级对应不同时间片
• 经验规则：新进程进最高优先级；时间片用尽则降级；高优先级队列可抢占低优先级

高频陷阱

• FCFS 的“护航效应”：长作业在前，短作业全被拖慢
• SJF/SRTF 的“先验信息”问题：题目给的“服务时间/剩余时间”一般视为已知
• HRRN：响应比算式一定要背熟：(等待 + 服务) / 服务
• RR：题目没说明“入队顺序”，就按常见约定写清楚你采用的规则
• 抢占算法：到达时间是切换点；不要把时间轴画成“整段不切”

手算例题（FCFS）

题目：

进程	到达时间	服务时间
P1	0	3
P2	2	6
P3	4	4

FCFS 时间轴：

• P1: [0,3)
• P2: [3,9)
• P3: [9,13)

计算：

• 完成时间：P1=3, P2=9, P3=13
• 周转时间：P1=3-0=3, P2=9-2=7, P3=13-4=9
• 带权周转时间：P1=3/3=1, P2=7/6, P3=9/4

平均周转时间 = (3+7+9)/3。

手算例题（RR，给你一题能练到坑）

题目：时间片 q = 2。

进程	到达时间	服务时间
P1	0	5
P2	1	3
P3	2	2

做法：从 t=0 开始画时间轴；每次时间片用尽/进程完成/新进程到达，都要检查就绪队列。

建议你在纸上明确写出每次切换时刻的队列内容（例如：[P2, P3, P1]），避免“脑补排队”。