python实现插队算法
时间: 2023-09-30 22:02:55 浏览: 86
插队算法是一种常用的调度算法,它可以使短作业尽快完成,从而提高系统吞吐量和响应时间。下面是一个简单的Python实现:
```python
class Job:
def __init__(self, name, arrive_time, service_time):
self.name = name
self.arrive_time = arrive_time
self.service_time = service_time
def __str__(self):
return f"{self.name} ({self.arrive_time}, {self.service_time})"
def sjf(job_list):
job_queue = []
current_time = 0
total_wait_time = 0
total_turnaround_time = 0
for job in job_list:
while job.arrive_time > current_time:
if job_queue:
current_job = job_queue.pop(0)
total_wait_time += current_time - current_job.arrive_time
total_turnaround_time += current_time - current_job.arrive_time + current_job.service_time
current_time += current_job.service_time
else:
current_time = job.arrive_time
job_queue.append(job)
job_queue.sort(key=lambda x: x.service_time)
while job_queue:
current_job = job_queue.pop(0)
total_wait_time += current_time - current_job.arrive_time
total_turnaround_time += current_time - current_job.arrive_time + current_job.service_time
current_time += current_job.service_time
n = len(job_list)
print(f"Average wait time: {total_wait_time / n:.2f}")
print(f"Average turnaround time: {total_turnaround_time / n:.2f}")
if __name__ == '__main__':
job_list = [
Job('A', 0, 5),
Job('B', 1, 3),
Job('C', 2, 1),
Job('D', 3, 2),
]
sjf(job_list)
```
在这个实现中,我们定义了一个`Job`类来表示作业,其中包含作业名称、到达时间和服务时间。我们还定义了一个`sjf`函数来实现插队算法。首先,我们将作业按照到达时间排序,然后遍历作业列表,将到达时间小于当前时间的作业加入作业队列。如果队列不为空,我们就从队列中取出服务时间最短的作业并执行,同时累计等待时间和周转时间。最后,我们统计所有作业的平均等待时间和平均周转时间。
阅读全文