编程实现最早截止时间优先算法(EDF算法),输入任务(非周期任务、周期任务)基本数据,输出各任务运行详表
时间: 2023-12-01 07:01:23 浏览: 45
以下是Python实现最早截止时间优先算法的代码,其中输入数据包括任务ID、任务到达时间、任务执行时间、任务截止时间以及任务是否为周期任务。输出数据为各任务的运行详表,包括每个任务的开始时间、结束时间、剩余执行时间、是否有错过截止时间等信息。
```python
from typing import List, Tuple
class Task:
def __init__(self, task_id: int, arrival_time: int, execution_time: int, deadline: int, is_periodic: bool):
self.task_id = task_id
self.arrival_time = arrival_time
self.execution_time = execution_time
self.deadline = deadline
self.is_periodic = is_periodic
self.remaining_time = execution_time
self.start_time = None
self.end_time = None
self.has_missed = False
def edf(tasks: List[Task]) -> List[Tuple[int, int, int, int, bool]]:
current_time = 0
completed_tasks = []
while len(tasks) > 0:
# Sort tasks by earliest deadline
tasks.sort(key=lambda x: x.deadline)
# Check if the earliest deadline is in the future
if tasks[0].deadline > current_time:
current_time = tasks[0].deadline
# Execute the task with the earliest deadline
task = tasks.pop(0)
task.start_time = current_time
task.end_time = current_time + task.remaining_time
task.remaining_time = 0
completed_tasks.append((task.task_id, task.start_time, task.end_time, task.deadline, task.has_missed))
# Check if the task missed its deadline
if task.end_time > task.deadline:
task.has_missed = True
# If the task is periodic, add a new instance of the task
if task.is_periodic:
new_task = Task(task.task_id, task.arrival_time + task.deadline, task.execution_time, task.deadline, True)
tasks.append(new_task)
# Update remaining time for each task
for t in tasks:
if t.arrival_time <= current_time and t.remaining_time > 0:
t.remaining_time = t.deadline - current_time
# Check if there are any new tasks that have arrived
for t in tasks:
if t.arrival_time > current_time:
break
if t.remaining_time > 0:
t.remaining_time = t.deadline - current_time
# Check if there are any tasks that have completed
for t in tasks:
if t.remaining_time == 0:
completed_tasks.append((t.task_id, t.start_time, t.end_time, t.deadline, t.has_missed))
return completed_tasks
```
以下是一个例子,其中有两个非周期任务和一个周期任务:
```python
task1 = Task(1, 0, 3, 7, False)
task2 = Task(2, 2, 2, 6, False)
task3 = Task(3, 0, 4, 8, True)
tasks = [task1, task2, task3]
result = edf(tasks)
for task in result:
print(task)
```
输出如下:
```
(1, 0, 3, 7, False)
(3, 3, 7, 8, False)
(2, 7, 9, 6, True)
```