HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Timing analysis of compound scheduling policies: application to Posix1003.1b

Jörn Migge 1 Alain Jean-Marie 2, 1 Nicolas Navet 1
1 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper we introduce the {\em layered preemptive priority } scheduling policy, LPP for short. It allows to combine different policies in a layered structure, based on the fixed preemptive priority scheduling policy, FPP for short. The techniques used in the timing analysis of FPP have evolved with the attempts of accounting more precisely for the characteristics of real-world systems. In this paper we introduce a framework that synthesizes the essential ideas of these techniques. We apply the framework to the analysis of the LPP policy, of which the FPP policy is a special case. The FPP policy was initially analyzed by Liu and Layland \cite{LiLa73} for periodic tasks with deadlines equal to their period. It has been shown that the maximal response time of a task occurs after the {\em critical instant}, defined as a time where all tasks are released simultaneously. Only this response time needs to be analyzed to decide upon feasibility. A task set is said to be feasible if each task allways meets its deadlines at run-time. A sufficient feasibility test has been derived from this property, based on a bound of the tasks's average processor utilization. A necessary and sufficient feasibility test has been derived by Lehoczky et al. \cite{LeShDi89}, based on a test-function, that must be evaluated at certain times between the release and the deadline of a task. A different approach was introduced by Joseph and Pandya in \cite{JoPa86}. Their idea is to compute the response time of a task after the critical instant and to compare it with the deadline. The actual computations however are quite similar in both cases. In order to apply the test-function based approach in the case where deadlines are set beyond the task periods, Lehoczky introduced in \cite{Leho90} the concept of {\em busy period}, which was then also used for the analysis based on response time computation in \cite{TiBuWe94} by Tindel et al. Basically, the busy period that starts with the critical instant has to be analyzed to determine the worst case response time. More generally, the critical instant can be seen as the beginning of a worst case release pattern.
Document type :
Journal articles
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 9:37:56 AM
Last modification on : Friday, February 4, 2022 - 3:18:47 AM


  • HAL Id : inria-00099506, version 1


Jörn Migge, Alain Jean-Marie, Nicolas Navet. Timing analysis of compound scheduling policies: application to Posix1003.1b. Journal of Scheduling, Springer Verlag, 2003, 6 (5), pp.457-482. ⟨inria-00099506⟩



Record views