Round Robin调度算法代码修正请求：完成时间计算错误

我需要实现一个Round Robin调度函数，接收两个参数：输入的Process列表和时间片（time quantum），要求必须使用Queue或Priority Queue。目前存在完成时间（Completion Time）计算错误的问题，使用的自定义Process类如下（其中__lt__方法用于抢占式优先级调度、SJF等其他操作系统调度算法）：

class Process:
    def __init__(self, process_id, arrival_time, burst_time, priority):
        self.process_id = process_id
        self.arrival_time = arrival_time
        self.burst_time = burst_time
        self.priority = priority
        self.completion_time = 0
        self.waiting_time = 0
        self.turnaround_time = 0
        self.remaining_time = burst_time

    def __lt__(self, other):
        if self.priority == other.priority:
            if self.arrival_time == other.arrival_time:
                return self.process_id < other.process_id
            return self.arrival_time < other.arrival_time
        if self.priority < other.priority:
            return self.priority < other.priority
        if self.burst_time == other.burst_time:
            return self.process_id < other.process_id
        if self.arrival_time == 0 and other.arrival_time != 0:
            return True
        elif self.arrival_time != 0 and other.arrival_time == 0:
            return False
        elif self.arrival_time == other.arrival_time:
            return self.burst_time < other.burst_time
        return self.burst_time < other.burst_time

第一次实现及问题 #

我编写的第一个Round Robin函数使用Queue存储进程，当进程剩余时间不为0时将其放回队列，但计算出的完成时间不正确：

def round_robin(processes, time_quantum):
    rr = Queue()

    for process in processes:
        rr.put(process)

    waiting_time = [0] * len(processes)
    turn_around_time = [0] * len(processes)
    curr_time = 0

    while not rr.empty():
        process = rr.get()
        if process.remaining_time <= time_quantum:
            curr_time += process.remaining_time
            process.completion_time = curr_time
            process.remaining_time = 0
        else:
            curr_time += time_quantum
            process.remaining_time -= time_quantum
            rr.put(process)

        if process.remaining_time > 0:
            rr.put(process)

    for i in range(len(processes)):
        turn_around_time[i] = processes[i].completion_time - processes[i].arrival_time
        processes[i].waiting_time = turn_around_time[i] - processes[i].burst_time
        processes[i].turnaround_time = turn_around_time[i]

    return processes

测试输入 #

processes = [
        Process(1, 0, 24, 4),
        Process(2, 0, 3, 3),
        Process(3, 0, 3, 2)
    ]

time_quantum = 2

错误输出 #

Process 1 Completion Time: 30
Process 2 Completion Time: 11
Process 3 Completion Time: 12

正确输出应为 #

Process 1 Completion Time: 30
Process 2 Completion Time: 9
Process 3 Completion Time: 10

第二次实现及问题 #

我尝试了另一种实现方式，用列表存储已完成进程，上述测试用例能得到正确结果，但另一组输入仍出现错误：

def round_robin(processes: List[Process], time_quantum: int) -> List[Process]:
    queue = Queue()
    total_time = 0
    total_time_counted = 0
    wait_time = 0
    turnaround_time = 0
    completed_processes = []

    for process in processes:
        total_time += process.burst_time
        queue.put(process)

    while not queue.empty():
        current_process = queue.get()

        if current_process.remaining_time <= time_quantum:
            total_time_counted += current_process.remaining_time
            total_time -= current_process.remaining_time
            current_process.completion_time = total_time_counted
            current_process.turnaround_time = total_time_counted - current_process.arrival_time
            current_process.waiting_time = current_process.turnaround_time - current_process.burst_time
            completed_processes.append(current_process)
            current_process.remaining_time = 0
        else:
            total_time_counted += time_quantum
            total_time -= time_quantum
            current_process.remaining_time -= time_quantum
            queue.put(current_process)

    return completed_processes

测试输入 #

processes = [
        Process(1, 0, 7, 4),
        Process(2, 2, 4, 3),
        Process(3, 4, 1, 2),
        Process(3, 5, 4, 1)
    ]

time_quantum = 2

错误输出 #

Process 1 Completion Time: 16
Process 2 Completion Time: 11
Process 3 Completion Time: 5
Process 4 Completion Time: 13

正确输出应为 #

Process 1 Completion Time: 16
Process 2 Completion Time: 9
Process 3 Completion Time: 7
Process 4 Completion Time: 15

恳请帮助修正代码！

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