In this tutorial, we will talk about the latest release time Scheduling Algorithm or LRT. It is used to schedule aperiodic tasks along with period tasks. The main concept behind this Scheduling algorithm is to steak slack time of periodic tasks until they don’t miss deadlines.
Aperiodic Tasks Introduction
Unlike periodic tasks, aperiodic tasks do not have any deadline requirement and can occur at any random time. Other scheduling algorithms such as rate monotonic and earliest deadline first algorithms schedule period tasks. But, the unpredictability of aperiodic tasks makes them difficult to schedule. Least Release time scheduler is used to optimize the execution of aperiodic tasks along with period tasks so that periodic tasks do not miss the deadline.
LRT Scheduler Introduction
LRT is a dynamic scheduler based on the slack stealing method. As you know that the purpose of real time systems is to schedule all periodic tasks in such a way that all tasks do not miss the deadlines. However, it is also possible to schedule all periodic tasks some time late but they must meet the deadline.
LRT Example
For example, we have a Task with a period of 10, deadline of 6 and execution time of 2. It doesn’t impact the real time system either; this task completes its execution at t=2 or t=6. Unless the task meets a deadline, this task is perfectly schedulable and doesn’t have performance degradation. Therefore, by delaying real time tasks to the end of the deadlines, we make space for the aperiodic tasks.
Unlike the earliest deadline first scheduling algorithm, LRT schedules jobs backwards. That means, in case of LRT, Release time of the task is equal to the deadline and the deadline is considered as release time.
Latest Release Time Scheduling Example
For example, we want to schedule these three jobs with LRT.
| r | e | D | |
|---|---|---|---|
| J1 | 0 | 3 | 6 |
| J2 | 5 | 2 | 8 |
| J3 | 2 | 2 | 7 |
In this table, e is the execution time, D is a deadline time and r is the release time of each job. Moreover, job J2 is dependent on job J1 and Job J3 is an independent Task.
In this example, we will schedule these jobs for 8-time instants. LRT schedules jobs backward. Therefore the latest release time is for job J2 = 5. Because the latest release time is considered as the highest priority. Therefore, J2 is the highest priority and it will schedule first backward from time t=8 to t=6.
After that the next job is J3. Because it has a release time of 2. Hence, it has second highest priority. Now, LRT schedules J3 from time t=6 to t=4.
At the end, the only job left to schedule is J1. Hence, it schedules from time t=4, t=1.
As you can see LRT schedules the jobs as late as possible without missing deadlines. Therefore, it can execute aperiodic jobs at the start and also without affecting the execution of period tasks with deadline constraints.
In Summary, the Latest release time scheduler makes execution of periodic tasks closer to their deadlines and make execution unit free for aperiodic tasks.