Sojourn Time and Waiting Time Distributions for M/GI/1 Queues with Preemption-Distance Priorities

Scheduling strategies for real-time systems often employ semipreemptive priorities, allowing for a deadline enforcement by preemptive priorities while avoiding the overhead of unnecessary interrupts. A variety of these strategies can be described by preemption-distance priorities in a straightforward and flexible fashion. A preemption-distance is a globally assigned positive integer number. An arriving task must exceed the priority of the task being served by at least the preemption-distance to cause a preemption. We derive the Laplace-Stieltjes transforms of the marginal waiting and sojourn time distributions for each task class in M/GI/1 single-server queues with preemption-distance priorities. The solutions generalize results for the classical M/GI/1 preemptive and nonpreemptive priority queues and cover a variety of priority systems working under different service policies. The basic derivations are straightforward and lead to solutions which are easy to interpret with respect to the influence of the different system properties. Since the basic equations are modular, solutions for different service policies can be obtained by rederiving auxiliary measures using different mathematical techniques. The modeling power of preemption-distance priorities is illustrated by an example taken from the scheduling of real-time process control systems. This example also validates the derived solutions.