Question

Suppose that we have 3 periodic real-time tasks: T1(1, 3), T2 (2, 4), and T3(1, 6). Generate the schedule within LCM with EDF scheduling.

Answer 1

Given Task :T1(1, 3), T2 (2, 4), and T3(1, 6).

Task	CPU Time	Deadline
T1	1	3
T2	2	4
T3	1	6

Step1 : Calculate the Hyperperiod (Since period is not given we can consider deadline as period)

Hyperperiod= LCM of Deadlines of all three process/task

= LCM(3,4,6) = 12

Step2 : Let see how Earliest deadline First works with below algorithm

For each time unit { For each ready process { Process with closest deadline will execute first } }

Now at Time t=0 , all process are ready for execution

Lets mark the deadline for each process

Now from the above we can see T1’s deadline is closest to t=0

So T1 executes for 1 time unit and it completes

Now we are left with T2 and T3 as ready Process

T2 has closest deadline to t=1

Now T2 executes from 1 time unit

Again at t=2 the process with closest deadline will be checked and it is T2 again

Now T2 executes for 1 time unit and completes

Now at t=3 , T1 and T3 are in ready queue

Again T1 is closest hence it will execute for 1 time unit

Now at t=4 , T2 and T3 are in ready queue

T3’s deadline is closest hence T3 executes for 1 time unit and completes

At t=5 , only T2 in ready queue

Now T2 executes for 1 time unit

At t=6 , T1 , T2 and T3 all three are in ready queue, but T2’s deadline is closest

Now T2 executes for 1 time unit and completes

At t=7 , T 1 and T3 in ready queue, T1’s deadline is closest

T1 executes for 1 time unit and it completes

At t=8, T2 and T3 are in ready queue, but both have same deadline so we will check for CPU time

Since T3 has less CPU time it will execute for 1 time unit and completes

At t=9, T1 and T2 are in ready queue , but both have same deadline so we will check for CPU time

Since T1 has less CPU time it will execute for 1 time unit and completes

At t =10 , only T2 in ready queue

T2 executes for one time unit and again for one time unit as there is no other process in ready queue