如何修复循环算法中的逻辑

Question

我正在尝试制作一个循环调度算法计算器，但是，当使用这些特定值时，进程排队的顺序是错误的。

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
-------------------------------------------

P5 应该在时间 21-24 结束，P7 紧随其后，但情况正好相反，所以它在时间 24-27 结束。

我该如何解决这个问题？

Answer 1

您似乎在处理队列中的进程时遇到问题。当一个进程被抢占并添加回队列时，它应该被放置在队列的末尾。但是，在您的代码中，进程被添加到队列的末尾，然后立即再次移动到前面。这会打乱预期的执行顺序。

next_process

正在从队列的前面删除，然后立即添加回队列的末尾。这不是循环调度的正确行为。相反，只有当进程在其时间片到期后仍有剩余突发时间并且尚未在队列中时，才应将其添加到队列中。你可以尝试这样的事情：

while True:
        ...

        for i in processes:
            if remaining_burst[i] > 0 and arrival_t[i] <= curr_t:
                if i not in queue:
                    queue.append(i)  # Add process to the queue
                execute_time = min(quantum, remaining_burst[i])
                curr_t += execute_time
                remaining_burst[i] -= execute_time
                process_end = curr_t
                ...

                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]
                    queue.remove(i)  # Remove the process from the queue if it's completed

        if queue:
            next_process = queue.pop(0)  # Only remove the process from the front
            if remaining_burst[next_process] > 0:
                queue.append(next_process)  # Re-add to the end only if it has remaining burst time