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

Martin Paterok and Markus Ettl
Additional contact information
Martin Paterok: IBM European Networking Center, Heidelberg, Germany
Markus Ettl: University of Erlangen-Nuremberg, Erlangen, Germany

Operations Research, 1994, vol. 42, issue 6, 1146-1161

Abstract: 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.

Keywords: probability: distributions; queues: priority (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.6.1146 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:6:p:1146-1161

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().