2.2.5_2 调度算法：时间片轮转、优先级、多级反馈队列

专题讲解：处理机调度

时间片轮转：公平的代价是切换

上一课得到 ready 队列。今天三个进程同时在0时刻到达，CPU 运行时间 P1=5、P2=3、P3=1，时间片 q=2。请画甘特图，并计算完成时间与平均周转时间。

from collections import deque

def round_robin(bursts,quantum):
    remain=dict(bursts); q=deque(name for name,_ in bursts)
    time=0; gantt=[]; completion={}
    while q:
        p=q.popleft(); run=min(quantum,remain[p])
        gantt.append((time,time+run,p)); time+=run; remain[p]-=run
        if remain[p]: q.append(p)
        else: completion[p]=time
    return gantt,completion

g,c=round_robin([("P1",5),("P2",3),("P3",1)],2)
assert g==[(0,2,"P1"),(2,4,"P2"),(4,5,"P3"),(5,7,"P1"),(7,8,"P2"),(8,9,"P1")]
assert c=={"P3":5,"P2":8,"P1":9}
assert sum(c.values())/3 == 22/3

甘特图按队首运行：P1 0–2、P2 2–4、P3 4–5、P1 5–7、P2 7–8、P1 8–9。到达均为0，所以周转时间等于完成时间，平均为 (9+8+5)/3=22/3。等待时间是周转减实际运行，分别4、5、4。

为何模拟正确：每次只运行 min(q,剩余时间)；未完成进程重新入队尾，完成进程离开。队列顺序精确实现轮转公平。

总运行步数与时间片切分数有关，模拟时间 O(总时间片数)，队列空间 O(n)。典型错误：把响应时间写成完成时间；忽略到达时间会错误地把尚未到达进程入队；时间片过小会增加上下文切换开销，过大则退化近似 FCFS。

迁移答案：若每次切换耗时0.1，本例进程片段之间有5次切换，应在墙钟完成时间中额外加入0.5；CPU 有效执行仍为9。

下一课多个进程不只争 CPU，还会并发修改共享缓冲区；PV 操作必须同时守住互斥与资源计数。

专题讲解：时间片轮转甘特图

到达发生在时间片内，先入队还是运行者先回队尾

主章只处理同时到达。强化题给 P1 (到达0,运行5)、P2 (1,3)、P3 (2,4)，时间片 q=2，忽略切换开销。要求画甘特图并算完成、周转、等待、响应时间。约定运行片结束时，先接纳截至该时刻的新到达进程，再把未完成运行者放回队尾。

from collections import deque

def rr(processes,quantum):
    jobs=sorted(processes,key=lambda x:x[1]); remain={p:b for p,a,b in jobs}
    arrival={p:a for p,a,b in jobs}; first={}; completion={}; gantt=[]
    q=deque(); i=0; time=0
    while i<len(jobs) or q:
        if not q and time<jobs[i][1]: time=jobs[i][1]
        while i<len(jobs) and jobs[i][1]<=time:
            q.append(jobs[i][0]); i+=1
        p=q.popleft(); first.setdefault(p,time)
        run=min(quantum,remain[p]); start=time; time+=run; remain[p]-=run
        gantt.append((start,time,p))
        while i<len(jobs) and jobs[i][1]<=time:
            q.append(jobs[i][0]); i+=1
        if remain[p]: q.append(p)
        else: completion[p]=time
    metrics={p:(completion[p]-arrival[p],completion[p]-arrival[p]-b,first[p]-arrival[p]) for p,a,b in jobs}
    return gantt,completion,metrics

g,c,m=rr([("P1",0,5),("P2",1,3),("P3",2,4)],2)
assert g==[(0,2,"P1"),(2,4,"P2"),(4,6,"P3"),(6,8,"P1"),(8,9,"P2"),(9,11,"P3"),(11,12,"P1")]
assert c=={"P2":9,"P3":11,"P1":12}
assert m=={"P1":(12,7,0),"P2":(8,5,1),"P3":(9,5,2)}

陪画：P1 在0～2运行，期间 P2、P3 到达，于是2时队列为 P2、P3、P1；随后 P2 2～4、P3 4～6、P1 6～8、P2 8～9完成、P3 9～11完成、P1 11～12完成。

指标三元组按“周转、等待、响应”：P1=(12,7,0)，P2=(8,5,1)，P3=(9,5,2)；平均周转 29/3、平均等待 17/3、平均响应1。

为什么正确：ready 队列始终按就绪先后保存所有已到达未完成进程；每次只消耗最多 q 的剩余 CPU 时间，未完成者排到当前队尾。完成时间由最后片结束确定，其余指标按定义计算。

模拟时间与时间片段数成正比，队列空间 O(n)。错解反馈：运行期间新到达者应先进入队列，不能排到刚用完时间片的进程之后；等待时间=周转-实际运行，不减时间片；响应时间只算首次运行前等待。

变式答案：若每次进程切换耗时0.1，本甘特图有6个相邻片段切换，最后墙钟时间增加0.6；指标需用含开销的实际时刻重算。

下一步在银行家算法中处理“先试分配请求，再判断新状态是否安全”的完整向量题。

专题讲解：进程状态、时间片轮转与周转时间

新困难：CPU 突发结束后进程阻塞，不能继续留在就绪队列

时间片 q=2。P1 在0到达，CPU突发为3、2，中间I/O 4时间单位；P2 在1到达，只有一个CPU突发4。约定同一时刻先接纳新到达/I/O完成，再把时间片用完的进程放回队尾。求甘特图、完成时间和CPU利用率。

from collections import deque

def rr_with_io():
    # 本题逐时间单位模拟；remaining保存当前CPU突发剩余量
    cpu={'P1':[3,2],'P2':[4]}; arrivals={0:['P1'],1:['P2']}; io_time=4
    ready=deque(); blocked={}; index={'P1':0,'P2':0}; remaining={'P1':3,'P2':4}
    first={}; finish={}; running=None; quantum=0; timeline=[]; pending=None; t=0
    while len(finish)<2:
        for p in arrivals.get(t,[]): ready.append(p)
        for p,wake in list(blocked.items()):
            if wake==t: ready.append(p); del blocked[p]
        if pending is not None: ready.append(pending); pending=None
        if running is None and ready:
            running=ready.popleft(); first.setdefault(running,t); quantum=2
        if running is None: timeline.append('IDLE'); t+=1; continue
        timeline.append(running); remaining[running]-=1; quantum-=1; t+=1
        if remaining[running]==0:
            index[running]+=1
            if index[running]==len(cpu[running]): finish[running]=t
            else:
                remaining[running]=cpu[running][index[running]]; blocked[running]=t+io_time
            running=None
        elif quantum==0:
            pending=running; running=None
    return timeline,first,finish

timeline,first,finish=rr_with_io()
assert timeline==['P1','P1','P2','P2','P1','P2','P2','IDLE','IDLE','P1','P1']
assert first=={'P1':0,'P2':2} and finish=={'P2':7,'P1':11}
assert sum(x!='IDLE' for x in timeline)/len(timeline)==9/11

陪走：P1运行0～2后时间片到，P2已在1到达，故P2先于P1；P2运行2～4，P1运行4～5并结束首个CPU突发，转阻塞至9。P2再运行5～7完成；7～9没有就绪进程，CPU空闲；P1在9完成I/O，运行到11完成。P1周转11、P2周转6，响应分别0、1，CPU利用率9/11。

依据：就绪队列只保存已到达、未完成且不等待事件的进程；CPU突发归零必须转阻塞，I/O完成时才重新入队。每个时间单位恰属于某进程或IDLE，累计CPU时间等于全部CPU突发和9，这是模拟不变量。

按单位时间模拟为 O(T)，队列与进程状态空间 O(n)；事件驱动可按片段降开销。错误反馈：I/O时间不占CPU；阻塞进程不能因时间片轮到而运行；周转时间含阻塞与等待；CPU空闲区间不能从甘特图抹掉；同刻事件顺序需先声明。

迁移答案：若P1的I/O只需2单位，它在7完成I/O，与P2完成同刻重新就绪，可从7继续运行，CPU不再空闲；调度指标必须按新事件线重算，不能只把完成时间机械减2。

桥接：调度决定谁运行；下一课在多个进程并发访问有限缓冲区时，用信号量维持容量与互斥不变量。