OS-03 处理机调度
OS-03 处理机调度
一、调度算法概述
CPU调度是操作系统最核心的功能之一。当多个进程同时处于就绪态时，调度器需要决定"谁先用CPU"。不同的调度算法对系统性能的影响是巨大的。我们先来理解几个衡量调度算法性能的关键指标。
二、关键性能指标
周转时间（Turnaround Time）：从进程到达系统到它完成任务所经过的时间。即：完成时间 − 到达时间。这个指标反映了一个进程从提交到完成的总耗时。
等待时间（Waiting Time）：进程在就绪队列中等待CPU的总时间。注意：等待时间不包括正在执行的时间。即：周转时间 − 执行时间。
响应时间（Response Time）：从进程提交到首次获得CPU的时间。在交互式系统中，响应时间比周转时间更重要。
带权周转时间：周转时间 / 执行时间。这个值反映了执行的"效率"，最小为1（没有任何等待，一到就执行）。
三、常见调度算法详解
3.1 先来先服务（FCFS）
FCFS是最简单的调度算法——按照进程到达就绪队列的顺序依次调度。就像顾客在银行柜台排队一样，先到的人先办理业务。
优点：实现简单，公平。每个进程迟早都能被执行。
缺点：短作业可能需要等待很长的时间（排在长作业后面时）。假设一个需要执行1秒的作业到达时，正好在前面有一个需要执行100秒的作业，那么短作业的等待时间就是100秒。
3.2 短作业优先（SJF）
SJF选择执行时间最短的就绪进程来执行。这是一种"贪心"策略，目标是最小化平均等待时间。
优点：理论上可以证明SJF能给出最小的平均等待时间。对于批处理系统来说，这是最优的调度策略。
缺点：需要预知进程的执行时间，这在实践中几乎不可能实现。长作业可能永远得不到执行（饥饿现象），因为系统中只要有短作业到来，长作业就轮不到。
3.3 响应比高者优先（HRRN）
HRRN是对SJF的改进，它引入了"响应比"的概念：响应比 = (等待时间 + 执行时间) / 执行时间。
这个公式的含义是：执行时间短的作业有更高的响应比（效率优先），而等待时间长的作业的响应比会随着等待时间的增加而增加（避免饥饿）。这样既兼顾了效率又保证了公平。
3.4 时间片轮转（RR）
RR是分时系统的核心算法。每个进程被分配一个固定的时间片（例如100ms），用一个接一个地轮流执行。如果一个进程在时间片内没有完成，它被放回就绪队列的尾部，调度器选择下一个进程执行。
时间片的选择至关重要：
- 时间片太大 → 退化为FCFS，响应时间变长
- 时间片太小 → 频繁的上下文切换，CPU的有效利用率下降（大量时间花在切换而非计算上）
3.5 多级反馈队列
这是现代操作系统中最常用的调度算法。它设置了多个不同优先级的队列，每个队列有不同的时间片大小。新到达的进程先进入最高优先级队列（时间片最小）。如果进程在时间片内没有完成，被降级到下一个优先级队列（时间片更大）。这种设计兼顾了I/O密集型和CPU密集型进程的不同需求。
四、典型例题精讲
设有四个进程：
| 进程 | 到达时间 | 执行时间 |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
下面的甘特图直观地展示了三种调度算法的执行时序差异：
4.1 先来先服务（FCFS）
执行顺序：P1(0-8) → P2(8-12) → P3(12-21) → P4(21-26)
计算结果：
P1: 完成时间=8, 周转时间=8, 带权=1.0, 等待时间=0
P2: 完成时间=12, 周转时间=11, 带权=2.75, 等待时间=7
P3: 完成时间=21, 周转时间=19, 带权=2.11, 等待时间=10
P4: 完成时间=26, 周转时间=23, 带权=4.6, 等待时间=18
平均周转时间 = (8+11+19+23)/4 = 15.25
平均带权周转时间 = (1+2.75+2.11+4.6)/4 = 2.615
FCFS的缺点是显而易见的：P4虽然只执行5秒，但要等到P3执行完才能运行，等待了18秒。
4.2 非抢占式短作业优先（SJF）
执行顺序：P1(0-8) → P2(8-12) → P4(12-17) → P3(17-26)
在t=8时，P2(4)、P3(9)、P4(5)都已到达，选最短的P2执行
在t=12时，P4(5) < P3(9)，选P4
最后执行P3
平均周转时间 = (8+11+14+24)/4 = 14.25
相比FCFS，SJF的平均周转时间更短。
4.3 时间片轮转法（RR, q=2）
执行序列（按时间点展开）：
t=0: P1开始 → t=2: P1时间片完，P2开始
t=4: P2时间片完，P3开始
t=6: P3时间片完，P4开始
t=8: P4时间片完，P1继续 → t=10: P1时间片完，P2继续
t=11: P2执行完毕，P3继续 → t=13: P3时间片完，P4继续
t=15: P4时间片完，P1继续 → t=17: P1时间片完，P3继续
t=19: P3时间片完，P4继续 → t=20: P4执行完毕
t=22: P1继续 → t=24: P1执行完毕，P3继续
t=26: P3执行完毕
平均周转时间 = (24+10+24+19)/4 = 19.25
RR的周转时间比FCFS和SJF都长，但响应时间最短（所有进程都在2个单位时间内获得首次响应）。