最短作业优先调度算法代码

最短作业优先（Shortest Job First, SJF）是一种基于CPU计算时间的进程调度算法，它总是选择当前剩余执行时间最短的进程进行调度。这是一种非抢占式调度策略，也就是说一旦一个进程开始运行，直到其完成才会让位给其他进程。

在Python中，如果我们要模拟一个简单的SJF调度算法，我们可以创建一个进程队列，每个进程都有一个到完成的时间。下面是一个简化的示例：

import heapq

class Process:
    def __init__(self, id, burst_time):
        self.id = id
        self.burst_time = burst_time
        self.arrival_time = 0  # 进程到达时间，默认为0，因为假设所有进程同时到达

    def get_waiting_time(self):
        if not self.parent:
            return 0
        else:
            return self.parent.get_remaining_time() + self.arrival_time - self.parent.finish_time

class ShortJobFirstScheduler:
    def __init__(self):
        self.processes = []
        self.heap = []

    def schedule(self, processes):
        for proc in processes:
            proc.parent = None
            heapq.heappush(self.heap, (proc.get_waiting_time(), proc))

        while self.heap:
            _, curr_proc = heapq.heappop(self.heap)
            print(f"Process {curr_proc.id} with burst time {curr_proc.burst_time} is running")
            curr_proc.finish_time = curr_proc.arrival_time + curr_proc.burst_time
            if curr_proc.parent:
                curr_proc.parent.remaining_time -= curr_proc.burst_time
                if curr_proc.parent.remaining_time == 0:
                    heapq.heappush(self.heap, (0, curr_proc.parent))  # 当父进程结束，将其放回堆中
            else:
                print("All processes completed.")

# 使用示例
scheduler = ShortJobFirstScheduler()
processes = [Process(1, 5), Process(2, 10), Process(3, 7)]
scheduler.schedule(processes)

在这个例子中，我们首先将所有进程按照剩余执行时间放入最小堆，然后持续取出剩余时间最短的进程执行。当进程完成后，如果有等待的父进程，我们会更新父进程的剩余时间，并将其放回堆中继续调度。