A deadline-floor inheritance protocol for edf scheduled embedded real-time systems with resource sharing

Earliest Deadline First (EDF) is the most widely studied optimal dynamic scheduling algorithm for uniprocessor real-time systems. For realistic pro-grams, tasks must be allowed to exchange data and use other forms of re-sources that must be accessed under mutual exclusion. With EDF sched-uled systems, access to such resources is usually controlled by the use of Baker’s Stack Resource Protocol (SRP). In this paper we propose an alterna-tive scheme based on deadline inheritance. Shared resources are assigned a relative deadline equal to the minimum (floor) of the relative deadlines of all tasks that use the resource. On entry to the resource a task’s relative deadline (and hence its current absolute deadline) is immediately reduced to reflect the resource’s deadline floor. On exit the original deadline for the task is re-stored. We show that the worst-case behaviour of the new protocol (termed DFP – Deadline Floor inheritance Protocol) is the same as SRP. Indeed it leads to the same blocking term in the scheduling analysis. We argue that the new scheme is however more intuitive and easier and more efficient to implement.