Python实现Round Robin调度算法Gantt Chart不符，求代码问题排查

我编写了一段实现Round Robin调度算法的Python代码，但生成的甘特图与GeeksforGeek网站上的示例结果不一致，请帮忙排查代码问题。

我的代码 #

def round_robin(processes, burst_time, arrival_time, time_quantum):
    n = len(processes)
    
    # Waiting times
    waiting_time = [0] * n
    # remaining burst time
    rem_burst = list(burst_time)
    # remaining arrival time
    rem_arrival = list(arrival_time)
    # Gantt chart
    gantt_chart = []
    
    t = 0
    while True:
        done = True
        for i in range(n):
            if rem_arrival[i] <= t and rem_burst[i] > 0:
                done = False
                if rem_burst[i] > time_quantum:
                    t += time_quantum
                    rem_burst[i] -= time_quantum
                    rem_arrival[i] = t
                    gantt_chart.append((processes[i], t))
                else:
                    t += rem_burst[i]
                    waiting_time[i] = t - burst_time[i] - arrival_time[i]
                    rem_burst[i] = 0
                    rem_arrival[i] = t
                    gantt_chart.append((processes[i], t))
        if done:
            break
    
    # Calculate Turnaround Time
    turnaround_time = [waiting_time[i] + burst_time[i] for i in range(n)]
    
    return gantt_chart, waiting_time, turnaround_time

参考说明 #

• 正确甘特图结果
• 我的代码生成的甘特图结果
• GeeksforGeek上的示例场景

代码问题分析 #

1. 错误修改进程到达时间 #

代码中定义的rem_arrival变量完全多余，且每次处理进程后将rem_arrival[i] = t，这会破坏进程到达时间的原始值，导致后续判断进程是否就绪的逻辑混乱。进程到达时间是固定值，无需修改，直接用原始arrival_time[i]判断即可。

2. 未使用就绪队列维护调度顺序 #

当前代码通过循环遍历所有进程的方式调度，不符合Round Robin的核心逻辑：应该用队列维护就绪进程，每次取出队首进程运行一个时间片，未完成则放回队尾。直接遍历所有进程会导致同一时间窗口内，到达的进程被连续处理，打乱轮询顺序。

3. 等待时间计算逻辑不严谨 #

代码仅在进程完成时一次性计算等待时间，虽然公式最终结果可能正确，但依赖完成时间的准确性；而如果调度逻辑出错（比如时间推进错误），等待时间也会随之出错。更严谨的方式是通过周转时间（完成时间-到达时间）减去总执行时间来计算等待时间。

修正后的代码 #

def round_robin(processes, burst_time, arrival_time, time_quantum):
    n = len(processes)
    waiting_time = [0] * n
    turnaround_time = [0] * n
    rem_burst = list(burst_time)
    gantt_chart = []
    ready_queue = []
    t = 0
    # 标记进程是否已加入就绪队列
    added = [False] * n

    while True:
        # 将当前时间点已到达的未加入队列的进程加入就绪队列
        for i in range(n):
            if arrival_time[i] <= t and not added[i] and rem_burst[i] > 0:
                ready_queue.append(i)
                added[i] = True
        
        if not ready_queue:
            # 无就绪进程时，直接跳转到下一个进程的到达时间
            next_arrivals = [arrival_time[i] for i in range(n) if rem_burst[i] > 0]
            if not next_arrivals:
                break  # 所有进程已完成
            t = min(next_arrivals)
            continue
        
        # 取出队首进程调度
        current_idx = ready_queue.pop(0)
        start_time = t

        if rem_burst[current_idx] > time_quantum:
            t += time_quantum
            rem_burst[current_idx] -= time_quantum
            gantt_chart.append((processes[current_idx], t))
            # 未完成的进程重新加入队列尾部
            ready_queue.append(current_idx)
        else:
            t += rem_burst[current_idx]
            rem_burst[current_idx] = 0
            gantt_chart.append((processes[current_idx], t))
            # 计算周转时间和等待时间
            turnaround_time[current_idx] = t - arrival_time[current_idx]
            waiting_time[current_idx] = turnaround_time[current_idx] - burst_time[current_idx]
        
        # 检查当前进程运行期间是否有新进程到达，加入就绪队列
        for i in range(n):
            if arrival_time[i] > start_time and arrival_time[i] <= t and not added[i] and rem_burst[i] > 0:
                ready_queue.append(i)
                added[i] = True

    return gantt_chart, waiting_time, turnaround_time

内容的提问来源于stack exchange，提问作者Jseok Y.