Static priority scheduling of aperiodic real-time tasks

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(l)(z), L(l)(z) and a (constant) deadline T-l is an element of 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 lambda(TL), which decreases exponentially with the deadlines T-L; simple asymptotic expressions for lambda(TL) and all associated quantities (probabilities, moments,...) for large T-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. (C) 1997 John Wiley & Sons, Inc.