-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathalgorithms.py
More file actions
146 lines (108 loc) · 5.83 KB
/
algorithms.py
File metadata and controls
146 lines (108 loc) · 5.83 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
"""
This module contains the scheduling algorithms used in the scheduling API.
It provides implementations for both Least Deadline First (LDF) and Earliest Deadline First (EDF) scheduling strategies, applicable in single-core and multi-core processor environments. Functions within are designed to be called with specific application and platform data structures.
Functions:
- ldf_singlecore: Schedules tasks on a single-core processor using LDF.
- edf_singlecore: Schedules tasks on a single-core processor using EDF.
- rms_singlecore: Schedules tasks on a single-core processor using RMS.
- ll_singlecore: Schedules tasks on a single-core processor using LL.
- ldf_multicore: Schedules tasks on multiple cores using LDF.
- edf_multicore: Schedules tasks on multiple cores using EDF.
"""
import networkx as nx
# just an eample for the structure of the schedule to be returned and to check the frontend and backend connection
example_schedule = [
{
"task_id": 3,
"node_id": 0,
"end_time": 20,
"deadline": 256,
"start_time": 0,
},
{
"task_id": 2,
"node_id": 0,
"end_time": 40,
"deadline": 300,
"start_time": 20,
},
{
"task_id": 1,
"node_id": 0,
"end_time": 60,
"deadline": 250,
"start_time": 40,
},
{
"task_id": 0,
"node_id": 0,
"end_time": 80,
"deadline": 250,
"start_time": 60,
},
]
def ldf_single_node(application_data):
"""
Schedule jobs on a single node using the Latest Deadline First (LDF) strategy.
This function schedules jobs based on their latest deadlines after sorting them and considering dependencies through a directed graph representation.
.. todo:: Implement Latest Dealine First Scheduling (LDF) algorithm for single compute node.
Args:
application_data (dict): Contains jobs and messages that indicate dependencies among jobs.
Returns:
list of dict: Scheduling results with each job's details, including execution time, node assignment,
and start/end times relative to other jobs.
"""
return {"schedule": example_schedule, "missed_deadlines": [], "name": "LDF Single-node"}
def edf_single_node(application_data):
"""
Schedule jobs on single node using the Earliest Deadline First (EDF) strategy.
This function processes application data to schedule jobs based on the earliest
deadlines. It builds a dependency graph and schedules accordingly, ensuring that jobs with no predecessors are
scheduled first, and subsequent jobs are scheduled based on the minimum deadline of available nodes.
.. todo:: Implement Earliest Deadline First Scheduling (EDF) algorithm for single compute node.
Args:
application_data (dict): Job data including dependencies represented by messages between jobs.
Returns:
list of dict: Contains the scheduled job details, each entry detailing the node assigned, start and end times,
and the job's deadline.
"""
return {"schedule": example_schedule, "missed_deadlines": [], "name": "EDF Single-node"}
def ll_multinode_no_delay(application_data, platform_data):
"""
Schedule jobs on a distributed system with multiple compute nodes using the Least Laxity (LL) strategy.
This function schedules jobs based on their laxity, with the job having the least laxity being scheduled first.
.. todo:: Implement Least Laxity (LL) algorithm to schedule jobs on multiple node in a distributed system.
Args:
application_data (dict): Job data including dependencies represented by messages between jobs.
Returns:
list of dict: Contains the scheduled job details, each entry detailing the node assigned, start and end times,
and the job's deadline.
"""
return {"schedule": example_schedule, "missed_deadlines": [], "name": "LL(without delay)"}
def ldf_multinode_no_delay(application_data, platform_data):
"""
Schedule jobs on a distributed system with multiple compute nodes using the Latest Deadline First(LDF) strategy.
This function schedules jobs based on their periods and deadlines, with the shortest period job being scheduled first.
.. todo:: Implement Latest Deadline First(LDF) algorithm to schedule jobs on multiple nodes in a distributed system.
Args:
application_data (dict): Job data including dependencies represented by messages between jobs.
platform_data (dict): Contains information about the platform, nodes and their types, the links between the nodes and the associated link delay.
Returns:
list of dict: Contains the scheduled job details, each entry detailing the node assigned, start and end times,
and the job's deadline.
"""
return {"schedule": example_schedule, "missed_deadlines": [], "name": "LDF Multinode(without delay)"}
def edf_multinode_no_delay(application_data, platform_data):
"""
Schedule jobs on a distributed system with multiple compute nodes using the Earliest Deadline First (EDF) strategy.
This function processes application data to schedule jobs based on the earliest
deadlines.
.. todo:: Implement Earliest Deadline First(EDF) algorithm to schedule jobs on multiple nodes in a distributed system.
Args:
application_data (dict): Job data including dependencies represented by messages between jobs.
platform_data (dict): Contains information about the platform, nodes and their types, the links between the nodes and the associated link delay.
Returns:
list of dict: Contains the scheduled job details, each entry detailing the node assigned, start and end times,
and the job's deadline.
"""
return {"schedule": example_schedule, "missed_deadlines": [], "name": "EDF Multinode(without delay)"}