Deadline Floor Inheritance Protocol for Earliest Deadline First resource sharing

In a previous posting, I mentioned the Deadline Floor Inheritance Protocol for resource sharing in EDF schedulers. In this blog post, I describe how this works.

Earliest Deadline First (EDF) scheduling is an optimal preemptive scheduling algorithm for single core processors. What optimal means in this case is that all deadlines will be met, provided that the total CPU utilization is less than or equal to 100%. The more frequently-used rate-monotonic (RM) scheduling can only guarantee this if CPU utilization is 69.3% or less. The downside for EDF is that exceeding 100% utilization means that some tasks miss their deadlines. Unlike RM, it isn't possible to predict which tasks miss their deadlines if the system becomes unschedulable - so it's important to take this into account when selecting a scheduling algorithm for a given task.

In EDF, the priority of tasks varies depending on how soon their deadline is. So the task with the shortest deadline has the highest priority. A number of policies for sharing resources have been proposed for EDF, the most popular of which is Stack Resource Protocol (SRP). Unfortunately, SRP is complex, as evidenced by the difficulties of implementing it correctly for Ada 2005 (see our previous posting for more details). The Deadline Floor Inheritance Protocol (DFP) has been proposed as an alternative solution for resource sharing. It has the advantage of being relatively simple to implement, while providing a number of useful properties:

1. no job can be blocked after it starts;
2. there can be no transitive blocking or deadlock;
3. no job can be blocked for longer than the execution time of one outermost critical section;
4. if the oldest earliest deadline job is blocked, it will become unblocked no later than the first instant when the currently executing job is not holding any resource

Under DFP, if multiple tasks share a single resource, the resource inherits the earliest deadline of the sharing tasks. While a task accesses the resource, it is treated as if it's deadline is the resource's inherited deadline.

For example, if a system includes three tasks T1, T2, and T3. The deadline of the tasks are as follows:

• T1: 10 ticks after task release
• T2: 20 ticks after task release
• T3: 30 ticks after task release

If T3 is released at time t=0, its deadline is 30.

At t=1, it accesses a resource that is shared with T2. The deadline of the resource is calculated as the lower of T3's deadline or the soonest possible deadline for T2, which is 21 (assuming that T2 is released this instant). Therefore, T3 is executed with an inherited deadline of 21.

At t=2, T2 is released. It's deadline is 22 (t + deadline, 2+10). Because the deadline is later than the current deadline of T3, it doesn't preempt T3.

At t=3, T1 is released with deadline 13 (3+10). It preempts T3 as it has the shortest deadline. T1 executes for 9, completing at 12.

Execution resumes with T3 at t=12. At t=14, T3 relinquishes the resource, and its deadline returns to 30, which allows T2 to preempt it, and then run to completion.

This is illustrated below.

Further information on DFP can be found in http://www-users.cs.york.ac.uk/burns/YCS476.pdf