01先把问题说具体
长任务正在运行,新来的交互任务不想一直等到它结束,如何定期让出 CPU?
02一步步得到方法
一轮最多运行一个时间片
Round Robin 维护 FIFO 就绪队列。取队首任务运行 min(剩余时间,q),完成则退出,未完成则放回队尾。q 必须为正,否则时间无法前进。
新任务在到达后加入队尾。本课约定:在一个时间片结束时,先加入截至该时刻到达的新任务,再把未完成的当前任务放回队尾;同一时刻事件的先后会影响具体轨迹,应明确说明。
响应与周转可能向不同方向变化
每个任务较早拿到第一次运行机会,因此交互响应通常改善。但把任务切碎可能推迟某些任务的最终完成,使平均周转不一定最优。响应时间只计算首次调度,不是每次排队之和。
q 很大时,策略趋近 FCFS;q 很小时,任务切换更频繁。若每次切换耗时 s,运行满片的简化有效占比约为 q/(q+s),不能忽略切换代价无限缩小时间片。
用剩余时间维护不变量
代码把原始时长保留在输入,每次出队携带剩余时间。运行后减少剩余量,只有大于0才重新入队,避免已完成任务再次出现。
本模拟单 CPU、无 IO、切换成本为0,返回每段执行区间及完成时刻。由完成−到达−原始时长可以计算总等待;真实系统需要更多状态转换。
03把一个小例子完全算清楚
A、B 均在0到达,时长分别5、3,q=2。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 前两片 | A:0→2,B:2→4 | 剩余 A=3、B=1 |
| 第三、四片 | A:4→6,B:6→7 | B 完成,A 剩1 |
| 最后一片 | A:7→8 | A 完成 |
窄屏可左右滑动表格,阅读完整计算与理由。
A、B 完成时刻为8、7,等待分别3、4,首次响应分别0、2。
04为什么这个方法成立
- 队列中每个未运行且已到达任务保存正确剩余时间;运行中的任务暂时不在队列。
- 每段运行时间为剩余量和 q 的较小者,因此不会过度执行或出现负剩余。
- 每次运行都消耗正时间,有限正时长任务最终完成;重新入队顺序符合本课约定。
05把推导翻译成代码
Python · 可独立运行的教学实现
from collections import deque
def round_robin(jobs,quantum):
if quantum<=0 or any(a<0 or d<=0 for _,a,d in jobs):
raise ValueError("invalid schedule")
if len({name for name,_,_ in jobs})!=len(jobs):
raise ValueError("unique names required")
pending = sorted(jobs,key=lambda j:j[1])
ready,timeline,finished = deque(),[],{}
index,time = 0,0
while index<len(pending) or ready:
if not ready:
time = max(time,pending[index][1])
while index<len(pending) and pending[index][1]<=time:
name,arrival,duration = pending[index]
ready.append((name,duration))
index += 1
name,remaining = ready.popleft()
used = min(quantum,remaining)
timeline.append((name,time,time+used))
time += used
remaining -= used
while index<len(pending) and pending[index][1]<=time:
new_name,arrival,duration = pending[index]
ready.append((new_name,duration))
index += 1
if remaining>0:
ready.append((name,remaining))
else:
finished[name] = time
return timeline,finished
print(round_robin([("A",0,5),("B",0,3)],2))逐个理解关键决定
min(quantum,remaining)- 最后一次可能不足整片,完成就立即释放 CPU。
while index<len(pending)- 运行过程中到达的任务在片末按顺序加入,随后才重排当前任务。
finished[name] = time- 完成时刻只记录一次,用来计算周转和等待。
06时间、空间与实现范围
若每个任务时长为 dᵢ,产生 S=Σ⌈dᵢ/q⌉ 个运行片,总时间 O(n log n+S),含输入排序。
队列和完成表 O(n),保存完整时间线 O(S);真实切换时间尚未计入此模拟。
07改变条件,检查哪里会出错
把等待时间算成首次响应
抢占任务可以多次等待,总等待需要用周转减运行时长计算。
q 越小一定越好
切换开销会上升,缓存局部性也可能变差。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
本例 B 的等待为什么是4?
需要一点提示
完成7−到达0−运行3。
查看解析与答案
等于4,包含首次等待和中间被抢占后的等待。
q≥5 且同一输入时,结果接近什么?
需要一点提示
两个任务都能一次执行完。
查看解析与答案
FCFS:A先0→5,B再5→8。
任务恰在片末到达,排在当前任务前还是后?
需要一点提示
查看本课的事件约定。
查看解析与答案
先加入新到达任务,再重新入队当前任务,因此新任务在它前面。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Arpaci-Dusseau · Operating Systems: Three Easy Pieces