Premium
Static priority scheduling of aperiodic real‐time tasks
Author(s) -
Schmid Ulrich
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199701/03)10:1/2<257::aid-rsa13>3.0.co;2-5
Subject(s) - aperiodic graph , computer science , priority inheritance , earliest deadline first scheduling , deadline monotonic scheduling , scheduling (production processes) , real time computing , dynamic priority scheduling , rate monotonic scheduling , distributed computing , fair share scheduling , fixed priority pre emptive scheduling , priority ceiling protocol , parallel computing , operating system , mathematical optimization , mathematics , schedule , combinatorics
We investigate deadline meeting properties of the well‐known (preemptive) static priority scheduling (SPS) algorithm, which is widespreadly used in commercial real‐time operating system kernels. A discrete‐time single server queueing system employing SPS for scheduling probabilistically arriving tasks at L priority levels is considered for this purpose. Model parameters are arrival and execution‐time distribution A ( z ), L ( z ) and a (constant) deadline T ∈ L per level l . By means of a combinatorial technique (which does not require stable‐state assumptions), we determine the probability distribution of the (random‐)time the system operates without violating any task's deadline. This distribution is asymptotically exponential with parameter λ L, which decreases exponentially with the deadlines L ; simple asymptotic expressions for λ Land all associated quantities (probabilities, moments,…) for large L are provided. Our numerical examples suggest that real‐time systems based on SPS operate reasonably well only if computing performance is (more than) adequate. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 10 , 257–303 (1997)