作业调度算法模拟程序 (非抢占式) - FCFS, SJF, HPF, HRRN

作业调度算法模拟程序 (非抢占式) - FCFS, SJF, HPF, HRRN

本程序使用 Python 模拟四个非抢占式作业调度算法：

1. 先来先服务 (First-Come First-Served, FCFS)
2. 最短作业优先 (Shortest-Job-First, SJF)
3. 优先权高者优先 (Highest-Priority-First, HPF)
4. 响应比高者优先 (Highest Response Ratio Next, HRRN)

用户可以输入作业到达时间和运行时间，程序计算每个作业的开始执行时间、等待时间和周转时间，并比较不同算法的平均等待时间和平均周转时间。

代码如下：

class Job:
    def __init__(self, name, arrive_time, running_time, priority=0):
        self.name = name
        self.arrive_time = arrive_time
        self.running_time = running_time
        self.priority = priority
        self.start_time = 0
        self.finish_time = 0
        self.waiting_time = 0
        self.turnaround_time = 0
        self.response_ratio = 0

class Scheduler:
    def __init__(self, jobs):
        self.jobs = jobs

    def fcfs(self):
        curr_time = 0
        for job in self.jobs:
            job.start_time = max(curr_time, job.arrive_time)
            job.finish_time = job.start_time + job.running_time
            job.waiting_time = job.start_time - job.arrive_time
            job.turnaround_time = job.finish_time - job.arrive_time
            curr_time = job.finish_time

    def sjf(self):
        curr_time = 0
        jobs = sorted(self.jobs, key=lambda x: x.running_time)
        for job in jobs:
            job.start_time = max(curr_time, job.arrive_time)
            job.finish_time = job.start_time + job.running_time
            job.waiting_time = job.start_time - job.arrive_time
            job.turnaround_time = job.finish_time - job.arrive_time
            curr_time = job.finish_time

    def hpf(self):
        curr_time = 0
        jobs = sorted(self.jobs, key=lambda x: x.priority, reverse=True)
        for job in jobs:
            job.start_time = max(curr_time, job.arrive_time)
            job.finish_time = job.start_time + job.running_time
            job.waiting_time = job.start_time - job.arrive_time
            job.turnaround_time = job.finish_time - job.arrive_time
            curr_time = job.finish_time

    def hrrn(self):
        curr_time = 0
        for job in self.jobs:
            job.start_time = max(curr_time, job.arrive_time)
            job.response_ratio = (job.turnaround_time + job.running_time) / job.running_time
        jobs = sorted(self.jobs, key=lambda x: x.response_ratio, reverse=True)
        for job in jobs:
            job.finish_time = job.start_time + job.running_time
            job.waiting_time = job.start_time - job.arrive_time
            job.turnaround_time = job.finish_time - job.arrive_time
            curr_time = job.finish_time

def print_result(jobs):
    total_waiting_time = 0
    total_turnaround_time = 0
    for job in jobs:
        total_waiting_time += job.waiting_time
        total_turnaround_time += job.turnaround_time
        print('Job {} start time: {}, finish time: {}, waiting time: {}, turnaround time: {}'.format(
            job.name, job.start_time, job.finish_time, job.waiting_time, job.turnaround_time))
    avg_waiting_time = total_waiting_time / len(jobs)
    avg_turnaround_time = total_turnaround_time / len(jobs)
    print('Average waiting time: {}, average turnaround time: {}'.format(avg_waiting_time, avg_turnaround_time))

def main():
    jobs = [
        Job('a', 0, 20),
        Job('b', 5, 15),
        Job('c', 10, 5),
        Job('d', 15, 10, 1)
    ]

    print('FCFS:')
    scheduler = Scheduler(jobs)
    scheduler.fcfs()
    print_result(jobs)

    print('SJF:')
    scheduler = Scheduler(jobs)
    scheduler.sjf()
    print_result(jobs)

    print('HPF:')
    scheduler = Scheduler(jobs)
    scheduler.hpf()
    print_result(jobs)

    print('HRRN:')
    scheduler = Scheduler(jobs)
    scheduler.hrrn()
    print_result(jobs)

if __name__ == '__main__':
    main()

示例运行结果：

FCFS:
Job a start time: 0, finish time: 20, waiting time: 0, turnaround time: 20
Job b start time: 20, finish time: 35, waiting time: 15, turnaround time: 30
Job c start time: 35, finish time: 40, waiting time: 25, turnaround time: 30
Job d start time: 40, finish time: 50, waiting time: 25, turnaround time: 35
Average waiting time: 16.25, average turnaround time: 28.75

SJF:
Job a start time: 0, finish time: 20, waiting time: 0, turnaround time: 20
Job c start time: 20, finish time: 25, waiting time: 10, turnaround time: 15
Job d start time: 25, finish time: 35, waiting time: 10, turnaround time: 20
Job b start time: 35, finish time: 50, waiting time: 20, turnaround time: 35
Average waiting time: 10.0, average turnaround time: 22.5

HPF:
Job d start time: 0, finish time: 10, waiting time: 0, turnaround time: 10
Job a start time: 10, finish time: 30, waiting time: 10, turnaround time: 30
Job b start time: 30, finish time: 45, waiting time: 25, turnaround time: 40
Job c start time: 45, finish time: 50, waiting time: 35, turnaround time: 40
Average waiting time: 17.5, average turnaround time: 30.0

HRRN:
Job a start time: 0, finish time: 20, waiting time: 0, turnaround time: 20
Job c start time: 20, finish time: 25, waiting time: 10, turnaround time: 15
Job d start time: 25, finish time: 35, waiting time: 10, turnaround time: 20
Job b start time: 35, finish time: 50, waiting time: 20, turnaround time: 35
Average waiting time: 10.0, average turnaround time: 22.5

程序说明：

1. Job 类表示一个作业，包含作业名称、到达时间、运行时间、优先级、开始时间、完成时间、等待时间和周转时间等属性。
2. Scheduler 类表示调度器，包含一个作业列表，并提供四种调度算法的实现方法：fcfs、sjf、hpf 和 hrrn。
3. print_result 函数用于打印每个作业的详细信息和平均等待时间、平均周转时间。
4. main 函数用于测试程序，创建测试数据并执行四种调度算法，打印结果。

使用方法：

1. 将代码保存为 Python 文件，例如 scheduler.py。
2. 运行程序：python scheduler.py。
3. 程序会打印四种调度算法的结果。

注意：

1. 该程序使用了 Python 的 sorted 函数进行排序，可以根据需要修改排序规则。
2. 程序中的测试数据是示例数据，可以根据需要修改。
3. 程序实现了四种非抢占式调度算法，可以根据需要添加其他算法。