专题进阶 · 操作系统算法推荐总顺序 · 第 143 / 148 课

通过时间片与就绪队列手算抢占过程,分析响应时间和切换成本的取舍。

先学会这些,再进入本课 先来先服务
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 操作系统算法

时间片轮转Round Robin

每个可运行任务轮流获得一个时间片,片长影响响应延迟与切换开销。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

通过时间片与就绪队列手算抢占过程,分析响应时间和切换成本的取舍。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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→7B 完成,A 剩1
最后一片A:7→8A 完成

窄屏可左右滑动表格,阅读完整计算与理由。

A、B 完成时刻为8、7,等待分别3、4,首次响应分别0、2。

04为什么这个方法成立

  1. 队列中每个未运行且已到达任务保存正确剩余时间;运行中的任务暂时不在队列。
  2. 每段运行时间为剩余量和 q 的较小者,因此不会过度执行或出现负剩余。
  3. 每次运行都消耗正时间,有限正时长任务最终完成;重新入队顺序符合本课约定。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

本例 B 的等待为什么是4?

需要一点提示

完成7−到达0−运行3。

查看解析与答案

等于4,包含首次等待和中间被抢占后的等待。

练习 2 · 边界与辨析

q≥5 且同一输入时,结果接近什么?

需要一点提示

两个任务都能一次执行完。

查看解析与答案

FCFS:A先0→5,B再5→8。

练习 3 · 变式与迁移

任务恰在片末到达,排在当前任务前还是后?

需要一点提示

查看本课的事件约定。

查看解析与答案

先加入新到达任务,再重新入队当前任务,因此新任务在它前面。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Arpaci-Dusseau · Operating Systems: Three Easy Pieces

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。