CS3800 Final Project - Scheduling Algorithms
Introduction
This is the final project for Operating Systems CS3800 Spring 2025. This project's main focus is to properly implement randomized tasks, scheduling algorithm logic, and then collect enough data to determine which algorithm works best with the specifications given (in our case, generally considered a 'worst case' scenario).
Note: STM32CubeIDE generates a lot of boilerplate code. All of the relevant work was done in the main file, in the functions main and task_fn.
Key Components & Variables
NUM_TASKS: Variable that sets the amount of tasks to be generated.
SIMULATION_END: Maximum time that the simulation is allowed to run for.
MIN_EXECUTION_TIME: Minimum time that a task is allowed to execute for.
MAX_EXECUTION_TIME: Maximum time that a task is allowed to execute for.
Codes are tested with two maximum execution time values.
SIMULATION_END / NUM_TASKS ensures that each task, at the maximum, gets the same amount of duration for the entire simulation time. It would get a 1 / NUM_TASKS share of the simulation time.
2 * (SIMULATION_END / NUM_TASKS), this is a more dangerous value to implement, since in a worst-case scenario where each tasks takes a maximum of its execution time, the entire workload will be double the possible simulation time. This creates intentional overload, which allows us to test how each algorithm and the real-time scheduler works under pressure.
USE_SHORTEST_JOB_FIRST: Boolean variable that determines if SJF is the algorithm we want to use for this pass.
USE_EDF: Boolean variables that determines if EDF is the algorithm we want to use for this pass.
SEED: Variable that determines the randomizer seed, for consistent task generation for all algorithms.
- Execution & Deadline Assignment: Each task gets a randomly generated execution time and deadline.
This is a random value that is added to the MIN_EXECUTION_TIME. If the randomly generated executed time exceeds the SIMULATION_END time, that tasks execution time is automatically set to MIN_EXEUCITON_TIME as a fallback. - Scheduling Algorithms: This project consists of a total of three scheduling algorithms. All tasks are generated and released simultaenously.
- FIFO (First in, first out): Tasks are scheduled in the order they were created, with no regard for execution time or set deadlines. This is non-optimal for minimizing execution time or missed deadlines, since it is mostly random.
- EDF (Earliest Deadline First): Tasks are scheduled with the earliest deadline going first at every opportunity. Since this simulation does not load new tasks past the start, the tasks are ordered before the kernel begins. EDF works most efficient when deadlines are known upfront, as in our scenario.
- SJF (Shortest Job First): Scheduler will always pick the task with the shortest execution time. This will optimize average completion time. The tasks all loading in simultaenously is the best possible outcome for SJF, but its lack of consideration for deadlines so it may fail real-time constraints.
- Tasks: Tasks are structured and generated before the kernel begins running. They are a struct, and the main loop creates task objects and assigns each a deadline, an execution time, and an index (also its name).
Table Data
Below are three tables, each for a separate scheduling algorithm. Visualized data is attached below.
FIFO
| Seed | Max Exec Time | Tasks | Deadline Misses |
|---|---|---|---|
| 999 | SIM_END / NUM_TASKS | 8 | 3 |
| 999 | SIM_END / NUM_TASKS | 16 | 5 |
| 999 | SIM_END / NUM_TASKS | 32 | 4 |
| 888 | SIM_END / NUM_TASKS | 8 | 3 |
| 888 | SIM_END / NUM_TASKS | 16 | 3 |
| 888 | SIM_END / NUM_TASKS | 32 | 10 |
| 777 | SIM_END / NUM_TASKS | 8 | 1 |
| 777 | SIM_END / NUM_TASKS | 16 | 4 |
| 777 | SIM_END / NUM_TASKS | 32 | 10 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 8 | 6 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 16 | 5 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 32 | 17 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 8 | 2 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 16 | 8 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 32 | 15 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 8 | 3 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 16 | 9 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 32 | 17 |
Shortest Job First
| Seed | Max Exec Time | Tasks | Deadline Misses |
|---|---|---|---|
| 999 | SIM_END / NUM_TASKS | 8 | 2 |
| 999 | SIM_END / NUM_TASKS | 16 | 5 |
| 999 | SIM_END / NUM_TASKS | 32 | 4 |
| 888 | SIM_END / NUM_TASKS | 8 | 2 |
| 888 | SIM_END / NUM_TASKS | 16 | 1 |
| 888 | SIM_END / NUM_TASKS | 32 | 5 |
| 777 | SIM_END / NUM_TASKS | 8 | 2 |
| 777 | SIM_END / NUM_TASKS | 16 | 2 |
| 777 | SIM_END / NUM_TASKS | 32 | 6 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 8 | 2 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 16 | 4 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 32 | 12 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 8 | 2 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 16 | 3 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 32 | 11 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 8 | 3 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 16 | 8 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 32 | 9 |
Earliest Deadline First
| Seed | Max Exec Time | Tasks | Deadline Misses |
|---|---|---|---|
| 999 | SIM_END / NUM_TASKS | 8 | 0 |
| 999 | SIM_END / NUM_TASKS | 16 | 1 |
| 999 | SIM_END / NUM_TASKS | 32 | 0 |
| 888 | SIM_END / NUM_TASKS | 8 | 0 |
| 888 | SIM_END / NUM_TASKS | 16 | 0 |
| 888 | SIM_END / NUM_TASKS | 32 | 2 |
| 777 | SIM_END / NUM_TASKS | 8 | 1 |
| 777 | SIM_END / NUM_TASKS | 16 | 0 |
| 777 | SIM_END / NUM_TASKS | 32 | 4 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 8 | 6 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 16 | 1 |
| 999 | 2 × (SIM_END / NUM_TASKS) | 32 | 15 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 8 | 0 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 16 | 0 |
| 888 | 2 × (SIM_END / NUM_TASKS) | 32 | 25 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 8 | 2 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 16 | 15 |
| 777 | 2 × (SIM_END / NUM_TASKS) | 32 | 21 |
Results
The metric we were recording for results is the amount of tasks that missed their deadlines.
General Trends
- EDF will consistently outperform SJF and FIFO when execution times are more constrained. It would produce near-zero missed deadlines overall, especially with lower task counts.
- However, when execution time is increased and tasks are allowed to generate higher execution times, EDF struggles. As MAX_EXECUTION_TIME increases, the range for possible deadlines for new tasks shrinks. So by pure probability, these long tasks tend to get earlier deadlines -- and thus, EDF chooses them first and suffers poor performance.
- FIFO showed increasing deadlines missed as task amount increased, particularly with higher execution times.
- SJF remained relatively stable, performing better than FIFO but worse than EDF with regular execution times. Under higher execution time, SJF performed the best out of all three algorithms. This is due to the fact that SJF inherently favors shorter tasks, which can help avoid bottlenecks.
Average Completion
Seed 999 (Regular Execution Time)
| Tasks | FIFO | SJF | EDF |
|---|---|---|---|
| 8 | 3 | 2 | 0 |
| 16 | 5 | 5 | 1 |
| 32 | 4 | 4 | 0 |
Seed 888 (Regular Execution Time)
| Tasks | FIFO | SJF | EDF |
|---|---|---|---|
| 8 | 3 | 2 | 0 |
| 16 | 3 | 1 | 0 |
| 32 | 10 | 5 | 2 |
Seed 777 (Regular Execution Time)
| Tasks | FIFO | SJF | EDF |
|---|---|---|---|
| 8 | 1 | 2 | 1 |
| 16 | 4 | 2 | 0 |
| 32 | 10 | 6 | 4 |
Average Missed Deadlines Calculation
For FIFO:
[ \text{Average FIFO} = \frac{(3 + 5 + 4) + (3 + 3 + 10) + (1 + 4 + 10)}{9} = \frac{43}{9} \approx 4.78 ]
For SJF:
[ \text{Average SJF} = \frac{(2 + 5 + 4) + (2 + 1 + 5) + (2 + 2 + 6)}{9} = \frac{29}{9} \approx 3.22 ]
For EDF:
[ \text{Average EDF} = \frac{(0 + 1 + 0) + (0 + 0 + 2) + (1 + 0 + 4)}{9} = \frac{8}{9} \approx 0.89 ]
Final Comparison (Regular Execution)
- FIFO: Average missed deadlines = 4.78
- SJF: Average missed deadlines = 3.22
- EDF: Average missed deadlines = 0.89