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

TY - JOUR

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

AU - Burns, Alan

AU - Gutierrez, Marina

AU - Aldea, Mario

AU - Harbour, Michael Gonzalez

PY - 2014/5/7

Y1 - 2014/5/7

N2 - Earliest Deadline First (EDF) is the most widely studied optimal dynamic scheduling algorithm for uniprocessor real-time systems. For realistic programs, tasks must be allowed to exchange data and use other forms of resources that must be accessed under mutual exclusion. With EDF scheduled systems, access to such resources is usually controlled by the use of Baker's Stack Resource Protocol (SRP). In this paper we propose an alternative 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 current absolute deadline is subject to an immediately reduction to reflect the resource's deadline floor. On exit the original deadline for the task is restored. 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, removes the need to support preemption levels and we demonstrate that it can be implemented more efficiently.

AB - Earliest Deadline First (EDF) is the most widely studied optimal dynamic scheduling algorithm for uniprocessor real-time systems. For realistic programs, tasks must be allowed to exchange data and use other forms of resources that must be accessed under mutual exclusion. With EDF scheduled systems, access to such resources is usually controlled by the use of Baker's Stack Resource Protocol (SRP). In this paper we propose an alternative 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 current absolute deadline is subject to an immediately reduction to reflect the resource's deadline floor. On exit the original deadline for the task is restored. 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, removes the need to support preemption levels and we demonstrate that it can be implemented more efficiently.

UR - http://www.scopus.com/inward/record.url?scp=84926652861&partnerID=8YFLogxK

U2 - 10.1109/TC.2014.2322619

DO - 10.1109/TC.2014.2322619

M3 - Article

AN - SCOPUS:84926652861

SN - 0018-9340

VL - 64

SP - 1241

EP - 1253

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 5

M1 - 6812156

ER -