Timing analysis of compound scheduling policies : application to Posix1003.1b
Identifieur interne : 007910 ( Main/Merge ); précédent : 007909; suivant : 007911Timing analysis of compound scheduling policies : application to Posix1003.1b
Auteurs : Jörn Migge ; Alain Jean-Marie ; Nicolas NavetSource :
- Journal of Scheduling ; 2003.
English descriptors
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 \& 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 \& 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.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 003725
- to stream Crin, to step Curation: 003725
- to stream Crin, to step Checkpoint: 000A63
Links to Exploration step
CRIN:migge00cLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="556">Timing analysis of compound scheduling policies : application to Posix1003.1b</title></titleStmt><publicationStmt><idno type="RBID">CRIN:migge00c</idno><date when="2003" year="2003">2003</date><idno type="wicri:Area/Crin/Corpus">003725</idno><idno type="wicri:Area/Crin/Curation">003725</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">003725</idno><idno type="wicri:Area/Crin/Checkpoint">000A63</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000A63</idno><idno type="wicri:Area/Main/Merge">007910</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Timing analysis of compound scheduling policies : application to Posix1003.1b</title><author><name sortKey="Migge, Jorn" sort="Migge, Jorn" uniqKey="Migge J" first="Jörn" last="Migge">Jörn Migge</name></author><author><name sortKey="Jean Marie, Alain" sort="Jean Marie, Alain" uniqKey="Jean Marie A" first="Alain" last="Jean-Marie">Alain Jean-Marie</name></author><author><name sortKey="Navet, Nicolas" sort="Navet, Nicolas" uniqKey="Navet N" first="Nicolas" last="Navet">Nicolas Navet</name></author></analytic><series><title level="j">Journal of Scheduling</title><imprint><date when="2003" type="published">2003</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>fixed preemptive priorities</term><term>posix1003.1b</term><term>real-time scheduling</term><term>round-robin</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="4245">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 \& 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 \& 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.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007910 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 007910 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= CRIN:migge00c
|texte= Timing analysis of compound scheduling policies : application to Posix1003.1b
}}
| This area was generated with Dilib version V0.6.33. |  |