01先把问题说具体
三个任务先后进入单核 CPU,若谁先到谁先执行,会得到怎样的等待体验?
02一步步得到方法
先明确调度模型
本课假定单 CPU、每个任务只有一个 CPU burst、不发生 IO、上下文切换成本为 0。FCFS 采用非抢占策略:一旦开始运行,就一直执行到本次任务结束,后到任务只能排队。
任务按到达时间进入 FIFO 队列,到达时间相同则保持输入顺序。若 CPU 空闲,要把当前时间推进到下一个任务到达,而不是让尚未到达的任务提前执行。
三种时间指标不要混用
响应时间=首次运行时刻−到达时刻;周转时间=完成时刻−到达时刻;等待时间=周转时间−CPU 运行时长。在本课无 IO、单次非抢占模型中,响应时间恰等于等待时间。
对抢占或多次 IO 的系统,这两者通常不同。解释一个调度结果时,要先写清任务模型,再比较同一组指标。
队头长任务造成车队效应
短任务若排在长任务后面,会长时间等待。FCFS 实现简单、顺序可预期,但不根据任务长度改善平均等待。后续 SJF 会尝试先处理短任务,Round Robin 则用时间片改善首次响应。
不同策略服务不同目标;吞吐、平均等待、交互响应和公平性不能只用一个数字概括。真实系统还面对多核、优先级和 IO 行为。
03把一个小例子完全算清楚
任务 A=(到达0,时长5),B=(1,1),C=(2,2)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 执行 A | 0→5,等待0 | B、C 到达后排队 |
| 执行 B | 5→6,等待4 | 5−1=4 |
| 执行 C | 6→8,等待4 | 6−2=4 |
窄屏可左右滑动表格,阅读完整计算与理由。
平均等待为 (0+4+4)/3=8/3;周转分别为 5、5、6。
04为什么这个方法成立
- 队列按到达时间稳定排序,执行时不会跳过更早到达的任务,符合 FCFS 定义。
- start=max(当前时间,到达时间) 保证无重叠运行且不会提前执行。
- finish=start+duration,代入指标定义即可逐项核对结果。
05把推导翻译成代码
Python · 可独立运行的教学实现
def fcfs(jobs):
if any(arrival<0 or duration<=0 for name,arrival,duration in jobs):
raise ValueError("invalid job")
time = 0
result = []
for name,arrival,duration in sorted(jobs,key=lambda job:job[1]):
start = max(time,arrival)
time = start+duration
result.append({"name":name,"start":start,"finish":time,
"waiting":start-arrival,"turnaround":time-arrival})
return result
print(fcfs([("A",0,5),("B",1,1),("C",2,2)]))逐个理解关键决定
sorted(jobs,key=lambda job:job[1])- Python 稳定排序保留同时到达任务的输入顺序。
max(time,arrival)- 正确处理没有任务可运行的空闲区间。
turnaround- 包含等待和运行时长,不等于单纯 CPU 时间。
06时间、空间与实现范围
离线输入排序 O(n log n),扫描调度 O(n),结果空间 O(n)。
若任务已经按到达顺序在线入队,FIFO 操作可做到每次 O(1)。
07改变条件,检查哪里会出错
直接把 start 设为当前 time
若任务尚未到达,会产生不可能的提前运行。
长任务先执行也一定公平
它遵守到达次序,但短交互任务可能经历很差的响应时间。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
若第一个任务到达 5,CPU 从几时开始它?
需要一点提示
此前无就绪任务。
查看解析与答案
时刻 5,0 到 5 是空闲时间。
B 的周转为何是 5 而不是 1?
需要一点提示
完成时刻 6,到达时刻 1。
查看解析与答案
周转包含等待4和运行1,总计5。
把 A 改成时长100,B、C 的等待怎样变化?
需要一点提示
后续任务被队头阻塞。
查看解析与答案
B 等待99,C 等待99,体现车队效应。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Arpaci-Dusseau · Operating Systems: Three Easy Pieces