如何修复Round Robin调度算法中的进程排队逻辑错误？

问题描述 #

开发Round Robin调度算法计算器时，指定参数下进程排队顺序异常：P5本应在21-24时间段结束执行，实际却在24-27时间段完成，执行顺序不符合预期。

原实现代码 #

def getInput(prompt, min, max):
    while True:
        try:
            user_input = int(input(prompt))
            if min <= user_input <= max:
                return user_input
            else:
                print(f"Invalid input. Please enter a value between {min} and {max}.")
        except ValueError:
            print("Invalid input. Please enter a positive integer.")

def round_robin_calc():
    p_num = 7 #getInput("\nEnter the number of processes (1 - 7): ", min=1, max=7)
    quantum = 3 #getInput("Enter the time quantum for Round Robin (3 - 6): ", min=3, max=6)

    arrival_t = [5, 6, 5, 6, 3, 4, 7]
    burst_t = [15, 20, 9, 12, 6, 19, 10]

    '''for i in range(p_num):
        arrival = getInput(f"\nEnter the arrival time of process {i + 1}. (0 - 7): ", min=0, max=7)
        burst = getInput(f"Enter the burst time of process {i + 1}. (1 - 20): ", min=1, max=20)
        arrival_t.append(arrival)
        burst_t.append(burst)'''

    remaining_burst = burst_t.copy()
    processes = sorted(range(p_num), key=lambda k: (arrival_t[k], k))

    queue = []  
    curr_t = 0  
    gantt = []  

    completion_t = [0] * p_num
    turnaround_t = [0] * p_num
    waiting_t = [0] * p_num

    while True:
        all_processes_completed = all(remaining_burst[i] == 0 for i in processes)

        if all_processes_completed:
            break

        for i in processes:
            if remaining_burst[i] > 0 and arrival_t[i] <= curr_t:
                execute_time = min(quantum, remaining_burst[i])
                curr_t += execute_time
                remaining_burst[i] -= execute_time
                process_end = curr_t

                gantt.append((" - " * execute_time, f"P{i + 1}", process_end))

                if remaining_burst[i] == 0:
                    completion_t[i] = process_end
                    turnaround_t[i] = completion_t[i] - arrival_t[i]
                    waiting_t[i] = turnaround_t[i] - burst_t[i]

                if remaining_burst[i] > 0:
                    queue.append(i)

        if not queue:
            remaining_processes = [i for i in processes if remaining_burst[i] > 0]
            if remaining_processes:
                next_arrival = min(arrival_t[i] for i in remaining_processes)
                idle_end = min(curr_t + quantum, next_arrival)
                idle_duration = idle_end - curr_t
                idle_symbols = " + " * (idle_duration) if idle_duration > 0 else ""
                gantt.append((idle_symbols, "ID", idle_end))
                curr_t = idle_end
            else:
                break

        if queue:
            next_process = queue.pop(0)
            queue.append(next_process)

    print("\nP\tAT\tBT\tCT\tTT\tWT")
    print("===========================================")
    for i in range(p_num):
        print(f"P{i + 1}\t{arrival_t[i]}\t{burst_t[i]}\t{completion_t[i]}\t{turnaround_t[i]}\t{waiting_t[i]}")
        print("-------------------------------------------")

    print("\nGantt Chart:")
    print()
    print(" ", end="")
    for time, process, completion in gantt:
        print(f"{process:^{len(time)}}", end=" ")

    print()
    print("|", end="")
    for time, process, completion in gantt:
        print(time, end="|")
    print()
    print("0", end=" ")
    for time, process, completion in gantt:
        print(f"{completion:{len(time)}}", end=" ")

    cpu_util = round((sum(burst_t) / curr_t) * 100, 2)
    avg_turnaround = round(sum(turnaround_t) / p_num, 2)
    avg_waiting = round(sum(waiting_t) / p_num, 2)

    print("\nAdditional Information:")
    print(f"Quantum = {quantum}")
    print(f"Average Turnaround Time: {avg_turnaround}ms")
    print(f"Average Waiting Time: {avg_waiting}ms")
    print(f"CPU Utilization: {cpu_util}%")


round_robin_calc()

原运行结果 #

P       AT      BT      CT      TT      WT
===========================================
P1      5       15      82      77      62
-------------------------------------------
P2      6       20      94      88      68
-------------------------------------------
P3      5       9       54      49      40
-------------------------------------------
P4      6       12      75      69      57
-------------------------------------------
P5      3       6       27      24      18
-------------------------------------------
P6      4       19      92      88      69
-------------------------------------------
P7      7       10      76      69      59
-------------------------------------------

问题根源 #

原代码核心逻辑完全违背Round Robin调度规则：

1. 错误的调度逻辑：主循环直接遍历所有已排序进程，执行所有当前到达的进程，而非通过队列按顺序调度，导致进程执行顺序混乱。
2. 队列无效使用：队列仅在进程执行后被加入元素，后续又将元素取出再放回，未起到调度下一个进程的作用。
3. 进程重复加入：每次循环都遍历所有进程，将已到达的进程重复加入队列，进一步打乱执行顺序。

修复方案 #

重构主循环逻辑，严格遵循Round Robin队列调度规则：

1. 每次循环先将所有到达当前时间、未完成且未在队列中的进程加入队列
2. 队列非空时，取出队首进程执行一个时间片
3. 执行后若进程还有剩余时间，将其放回队列尾部
4. 队列空时，处理空闲时间并跳转到下一个进程的到达时间

修复后的完整代码 #

def getInput(prompt, min, max):
    while True:
        try:
            user_input = int(input(prompt))
            if min <= user_input <= max:
                return user_input
            else:
                print(f"Invalid input. Please enter a value between {min} and {max}.")
        except ValueError:
            print("Invalid input. Please enter a positive integer.")

def round_robin_calc():
    p_num = 7 #getInput("\nEnter the number of processes (1 - 7): ", min=1, max=7)
    quantum = 3 #getInput("Enter the time quantum for Round Robin (3 - 6): ", min=3, max=6)

    arrival_t = [5, 6, 5, 6, 3, 4, 7]
    burst_t = [15, 20, 9, 12, 6, 19, 10]

    remaining_burst = burst_t.copy()
    # 标记进程是否已在队列，避免重复添加
    in_queue = [False] * p_num
    curr_t = 0  
    gantt = []  

    completion_t = [0] * p_num
    turnaround_t = [0] * p_num
    waiting_t = [0] * p_num
    queue = []

    while True:
        all_processes_completed = all(remaining_burst[i] == 0 for i in range(p_num))
        if all_processes_completed:
            break

        # 将符合条件的进程加入队列
        for i in range(p_num):
            if remaining_burst[i] > 0 and arrival_t[i] <= curr_t and not in_queue[i]:
                queue.append(i)
                in_queue[i] = True

        if queue:
            current_p = queue.pop(0)
            in_queue[current_p] = False
            # 计算本次执行时间
            execute_time = min(quantum, remaining_burst[current_p])
            curr_t += execute_time
            remaining_burst[current_p] -= execute_time
            process_end = curr_t

            gantt.append((" - " * execute_time, f"P{current_p + 1}", process_end))

            if remaining_burst[current_p] == 0:
                completion_t[current_p] = process_end
                turnaround_t[current_p] = completion_t[current_p] - arrival_t[current_p]
                waiting_t[current_p] = turnaround_t[current_p] - burst_t[current_p]
            else:
                # 进程未完成，重新加入队列
                queue.append(current_p)
                in_queue[current_p] = True
        else:
            # 队列空，处理空闲时间
            remaining_processes = [i for i in range(p_num) if remaining_burst[i] > 0]
            if remaining_processes:
                next_arrival = min(arrival_t[i] for i in remaining_processes)
                idle_duration = next_arrival - curr_t
                idle_symbols = " + " * idle_duration if idle_duration > 0 else ""
                gantt.append((idle_symbols, "ID", next_arrival))
                curr_t = next_arrival
            else:
                break

    print("\nP\tAT\tBT\tCT\tTT\tWT")
    print("===========================================")
    for i in range(p_num):
        print(f"P{i + 1}\t{arrival_t[i]}\t{burst_t[i]}\t{completion_t[i]}\t{turnaround_t[i]}\t{waiting_t[i]}")
        print("-------------------------------------------")

    print("\nGantt Chart:")
    print()
    print(" ", end="")
    for time, process, completion in gantt:
        print(f"{process:^{len(time)}}", end=" ")

    print()
    print("|", end="")
    for time, process, completion in gantt:
        print(time, end="|")
    print()
    print("0", end=" ")
    for time, process, completion in gantt:
        print(f"{completion:{len(time)}}", end=" ")

    cpu_util = round((sum(burst_t) / curr_t) * 100, 2)
    avg_turnaround = round(sum(turnaround_t) / p_num, 2)
    avg_waiting = round(sum(waiting_t) / p_num, 2)

    print("\nAdditional Information:")
    print(f"Quantum = {quantum}")
    print(f"Average Turnaround Time: {avg_turnaround}ms")
    print(f"Average Waiting Time: {avg_waiting}ms")
    print(f"CPU Utilization: {cpu_util}%")


round_robin_calc()

修复后的关键运行结果 #

P       AT      BT      CT      TT      WT
===========================================
...
P5      3       6       24      21      15
...

此时P5的完成时间为24，符合21-24时间段结束的预期。

内容的提问来源于stack exchange，提问作者Andre Ryan