Python实现SJF CPU调度：二次排序逻辑实现求助

核心逻辑梳理 #

你需要的是非抢占式SJF调度的核心逻辑：每次从已到达（到达时间AT ≤ 当前系统时间）且未执行的进程中，选择Burst Time（BT）最短的进程执行，而非单纯沿用初始按AT排序的顺序。

具体实现步骤 #

1. 维护一个未执行进程列表，初始为按AT排序后的进程集合
2. 维护当前系统时间（初始设为0即可）
3. 循环处理直到所有进程执行完毕：
   • 从未执行列表中筛选出所有AT ≤ 当前系统时间的进程，组成就绪队列
   • 若就绪队列不为空，按BT升序排序，取出第一个进程执行
   • 计算该进程的退出时间ET（当前时间 + 进程BT），并记录ET、TAT（ET - AT）、WT（TAT - BT）
   • 更新当前系统时间为ET，将该进程从未执行列表中移除
   • 若就绪队列为空（无已到达进程），直接将当前系统时间跳转到下一个未执行进程的AT

完整代码实现 #

def inputNumber(prompt):
    # 确保输入为整数的辅助函数
    while True:
        try:
            num = int(input(prompt))
            return num
        except ValueError:
            print("请输入有效的整数！")

number_of_process = inputNumber("Enter number of processes: ")
print()

dictionary = dict()

for i in range(number_of_process):
    process_id = i + 1
    key = "P" + str(process_id)
    
    ArrivalTime = inputNumber(f"Enter Arrival Time of process {process_id}: ")
    BurstTime = inputNumber(f"Enter Burst Time for process {process_id}: ")
    print()

    dictionary[key] = [ArrivalTime, BurstTime]

# 初始按AT排序，得到未执行进程列表
unexecuted_processes = sorted(dictionary.items(), key=lambda item: (item[1][0], item[1][1]))
ET = [] # Exit Time
TAT = [] # Turn Around Time
WT = [] # Waiting Time
current_time = 0
execution_order = [] # 记录执行顺序

while unexecuted_processes:
    # 筛选已到达的进程
    ready_queue = [proc for proc in unexecuted_processes if proc[1][0] <= current_time]
    
    if ready_queue:
        # 按BT升序排序，选择最短作业
        ready_queue_sorted = sorted(ready_queue, key=lambda x: x[1][1])
        selected_proc = ready_queue_sorted[0]
        proc_id, (at, bt) = selected_proc
        
        # 计算时间参数
        exit_time = current_time + bt
        tat = exit_time - at
        wt = tat - bt
        
        # 记录数据
        ET.append(exit_time)
        TAT.append(tat)
        WT.append(wt)
        execution_order.append(proc_id)
        
        # 更新状态
        current_time = exit_time
        unexecuted_processes.remove(selected_proc)
    else:
        # 无已到达进程，跳转到下一个进程的到达时间
        next_at = min(proc[1][0] for proc in unexecuted_processes)
        current_time = next_at

# 输出结果
print("执行顺序：", " ".join(execution_order))
print("退出时间（ET）：", ET)
print("周转时间（TAT）：", TAT)
print("等待时间（WT）：", WT)

关键代码说明 #

• unexecuted_processes：始终保存未执行的进程，每次执行后移除已完成的进程
• ready_queue：每次循环动态筛选已到达的进程，确保只处理符合条件的进程
• ready_queue_sorted：对就绪队列按BT升序排序，这是实现短作业优先的核心逻辑

用你期望的测试数据运行这段代码，就能得到P4 P1 P3 P5 P2的执行顺序。

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