Updates:

  • fixed 3rd example output, missed deadlines should be only printed when they initially occur.
  • order in which missed deadlines are printed should not matter.

Description

The objective of this assignment is to implement the Earliest Deadline First (EDF) scheduling algorithm.

To avoid having to modify the Linux kernel’s own scheduler—which is quite complex and does multi-CPU scheduling and would be difficult to test—this assignment must be implemented as a user-mode program. It should compute the result of the EDF scheduling algorithm for a single CPU, without actually creating any processes or threads to be scheduled.

You are free to implement the EDF algorithm in any way you want under the following conditions:

  • You must write your solution in a single C named edf.c.
  • Your solution should compile using the provided Makefile on your Debian virtual machine, using your “known good” kernel.

The Makefile used to build your solution in the autograder is provided here.

Test files are provided in the pa3-testing.zip file. The archive contains a Python testing script which will load provided test cases from tests_partial.json, then perform output comparison and valgrind memory checks based on your solution. The script can be invoked with python3 test_edf.py as long as it is in the same directory as the ./edf executable and the tests_partial.json file.

You should make sure that Python and valgrind are available on your VM. If they are not, you can install them with:

sudo apt install valgrind python3

Requirements

Your program must do the following:

  1. Interactively ask the user to enter the number of processes to schedule via stdin (see below for examples).

    • Assume that this number is always strictly positive. There is no need to check for that in your program.

  2. For each process to schedule, ask the user the enter the CPU time required by the process and the period for the process.

    • Assume that all CPU times and periods are strictly positive, and that the period for a given process is always at least as big as the CPU time for that same process. There is no need to check for all these things in your program.
    • Assume that all the processes initially arrive in the ready queue at the same time T = 0.

  3. Once your program has read all this information from the user, your program must schedule the processes using the Earliest Deadline First algorithm and print the computed schedule on the screen (see below for examples). The printed schedule must start at time 0 and continue up to max_time, where max_time is the least common multiple of all the periods.

  4. If multiple processes have the same deadline, the process with the earliest release time takes precedence. If multiple processes have the same release time, the process with the lower PID number takes precedence.

  5. If multiple processes miss their deadline at the same time, the processes are printed in the same order as above.

When printing the schdule, your program must indicate (in this order):

  1. when a process’s time on the CPU ends

  2. when a process misses its deadline and by how much time the deadline was missed

  3. when new processes are released by showing the complete list of current processes in EDF order with corresponding release times, deadlines, and remaining CPU times

  4. when a process is preempted (replaced on the CPU) by another process

  5. when a process’s time on the CPU starts

After the complete schedule is printed, your program must also print the following information:

  • Final list of current processes
  • Number of processes created
  • Total waiting time
  • Average waiting time
  • Number of processes completed
  • Maximum lateness

The Total Waiting Time is the sum of all waiting times for all processes from time 0 to max_time (exclusive).

The Average Waiting Time is computed as the Total Waiting Time divided by the total number of processes created. It is printed as double with format precision %.2lf.

The Maximum Lateness of a schedule is the longest amount of time by which any process in the schedule misses its deadline.

Since there are many different ways to write the code, make sure that you put comments everywhere in your code explaining how your code works!

Examples

Here is a simple example showing what your program must look like when executed. This particular example corresponds to the example from the Real-Time Scheduling lecture notes. The CPU times and periods can be found there; the numbers 2, 1, 4, 3, and 5 shown here are inputs typed interactively by the user of your program:

Enter the number of processes to schedule: 2
Enter the CPU time of process 1: 1
Enter the period of process 1: 4
Enter the CPU time of process 2: 3
Enter the period of process 2: 5
0: processes: [1|p=1|r=0|d=4] [2|p=3|r=0|d=5]
0: process 1 starts
1: process 1 ends
1: process 2 starts
4: process 2 ends
4: processes: [1|p=1|r=4|d=8]
4: process 1 starts
5: process 1 ends
5: processes: [2|p=3|r=5|d=10]
5: process 2 starts
8: process 2 ends
8: processes: [1|p=1|r=8|d=12]
8: process 1 starts
9: process 1 ends
10: processes: [2|p=3|r=10|d=15]
10: process 2 starts
12: processes: [2|p=1|r=10|d=15] [1|p=1|r=12|d=16]
13: process 2 ends
13: process 1 starts
14: process 1 ends
15: processes: [2|p=3|r=15|d=20]
15: process 2 starts
16: processes: [2|p=2|r=15|d=20] [1|p=1|r=16|d=20]
18: process 2 ends
18: process 1 starts
19: process 1 ends
20: max time reached
20: processes:
Number of processes created: 9
Total waiting time: 4
Average waiting time: 0.44
Number of processes completed: 9
Maximum lateness: 0

Here is a slightly more complex example that shows some processes being preempted:

Enter the number of processes to schedule: 2
Enter the CPU time of process 1: 25
Enter the period of process 1: 50
Enter the CPU time of process 2: 35
Enter the period of process 2: 80
0: processes: [1|p=25|r=0|d=50] [2|p=35|r=0|d=80]
0: process 1 starts
25: process 1 ends
25: process 2 starts
50: processes: [2|p=10|r=0|d=80] [1|p=25|r=50|d=100]
60: process 2 ends
60: process 1 starts
80: processes: [1|p=5|r=50|d=100] [2|p=35|r=80|d=160]
85: process 1 ends
85: process 2 starts
100: processes: [1|p=25|r=100|d=150] [2|p=20|r=80|d=160]
100: process 2 preempted!
100: process 1 starts
125: process 1 ends
125: process 2 starts
145: process 2 ends
150: processes: [1|p=25|r=150|d=200]
150: process 1 starts
160: processes: [1|p=15|r=150|d=200] [2|p=35|r=160|d=240]
175: process 1 ends
175: process 2 starts
200: processes: [2|p=10|r=160|d=240] [1|p=25|r=200|d=250]
210: process 2 ends
210: process 1 starts
235: process 1 ends
240: processes: [2|p=35|r=240|d=320]
240: process 2 starts
250: processes: [1|p=25|r=250|d=300] [2|p=25|r=240|d=320]
250: process 2 preempted!
250: process 1 starts
275: process 1 ends
275: process 2 starts
300: process 2 ends
300: processes: [1|p=25|r=300|d=350]
300: process 1 starts
320: processes: [1|p=5|r=300|d=350] [2|p=35|r=320|d=400]
325: process 1 ends
325: process 2 starts
350: processes: [2|p=10|r=320|d=400] [1|p=25|r=350|d=400]
360: process 2 ends
360: process 1 starts
385: process 1 ends
400: max time reached
400: processes:
Number of processes created: 13
Total waiting time: 130
Average waiting time: 10.00
Number of processes completed: 13
Maximum lateness: 0

Here is a final example showing many missed deadlines, since this set of processes is not schedulable (note here that multiple processes with the same PID might exist at the same time, since some of these processes missed their deadline):

Enter the number of processes to schedule: 3
Enter the CPU time of process 1: 2
Enter the period of process 1: 4
Enter the CPU time of process 2: 4
Enter the period of process 2: 8
Enter the CPU time of process 3: 3
Enter the period of process 3: 6
0: processes: [1|p=2|r=0|d=4] [3|p=3|r=0|d=6] [2|p=4|r=0|d=8]
0: process 1 starts
2: process 1 ends
2: process 3 starts
4: processes: [3|p=1|r=0|d=6] [2|p=4|r=0|d=8] [1|p=2|r=4|d=8]
5: process 3 ends
5: process 2 starts
6: processes: [2|p=3|r=0|d=8] [1|p=2|r=4|d=8] [3|p=3|r=6|d=12]
8: process 1 missed deadline (2 ms left)
8: process 2 missed deadline (1 ms left)
8: processes: [2|p=1|r=0|d=8] [1|p=2|r=4|d=8] [3|p=3|r=6|d=12] [1|p=2|r=8|d=12] [2|p=4|r=8|d=16]
9: process 2 ends
9: process 1 starts
11: process 1 ends
11: process 3 starts
12: process 1 missed deadline (2 ms left)
12: process 3 missed deadline (2 ms left)
12: processes: [3|p=2|r=6|d=12] [1|p=2|r=8|d=12] [2|p=4|r=8|d=16] [1|p=2|r=12|d=16] [3|p=3|r=12|d=18]
14: process 3 ends
14: process 1 starts
16: process 1 ends
16: process 1 missed deadline (2 ms left)
16: process 2 missed deadline (4 ms left)
16: processes: [2|p=4|r=8|d=16] [1|p=2|r=12|d=16] [3|p=3|r=12|d=18] [1|p=2|r=16|d=20] [2|p=4|r=16|d=24]
16: process 2 starts
18: process 3 missed deadline (3 ms left)
18: processes: [2|p=2|r=8|d=16] [1|p=2|r=12|d=16] [3|p=3|r=12|d=18] [1|p=2|r=16|d=20] [2|p=4|r=16|d=24] [3|p=3|r=18|d=24]
20: process 2 ends
20: process 1 missed deadline (2 ms left)
20: processes: [1|p=2|r=12|d=16] [3|p=3|r=12|d=18] [1|p=2|r=16|d=20] [2|p=4|r=16|d=24] [3|p=3|r=18|d=24] [1|p=2|r=20|d=24]
20: process 1 starts
22: process 1 ends
22: process 3 starts
24: max time reached
24: processes: [3|p=1|r=12|d=18] [1|p=2|r=16|d=20] [2|p=4|r=16|d=24] [3|p=3|r=18|d=24] [1|p=2|r=20|d=24]
Number of processes created: 13
Total waiting time: 75
Average waiting time: 5.77
Number of processes completed: 8
Maximum lateness: 6

What to Submit For This Assignment

Put the following header at the top of your edf.c file and fill in all the details, including your name and the Stevens Honor pledge:

/*******************************************************************************
* Filename : edf.c
* Author :
* Date :
* Description : Earliest Deadline First Scheduling Algorithm
* Pledge :
******************************************************************************/

Once you have made sure that your C program correctly compiles and runs on the Debian virtual machine, submit only your edf.c file on Gradescope.

The autograder uses Ubuntu 22.04, but if your code compiles on your Debian VM, it is very likely to compile on Ubuntu as well, since Ubuntu is based on Debian. If you have issues with the autograder, please contact the instructor.