Résumé
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.