[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Threshold-based interventions to optimize performance in preemptive priority queues

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

This paper studies a single-server priority queueing model in which preemptions are allowed during the early stages of service. Once enough service effort has been rendered, however, further preemptions are blocked. The threshold where the change occurs is either a proportion of the service requirement, or time-based. The Laplace–Stieltjes transform and mean of each class sojourn time are derived for a model which employs this hybrid preemption policy. Both preemptive resume and preemptive repeat service disciplines are considered. Numerical examples show that it is frequently the case that a good combination of preemptible and nonpreemptible service performs better than both the standard preemptive and nonpreemptive queues. In a number of these cases, the thresholds that optimize performance measures such as overall average sojourn time are determined.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. I. Adiri and I. Domb, A single server queueing system working under mixed priority disciplines, Oper. Res. 30 (1982) 97–115.

    Google Scholar 

  2. I. Adiri and I. Domb, Mixing of nonpreemptive and preemptive repeat priority disciplines, European J. Oper. Res. 18 (1984) 86–97.

    Article  Google Scholar 

  3. B. Avi-Itzhak, I. Brosh and P. Naor, On discretionary priority queueing, Z. Angew. Math. Mech. 6 (1964) 235–242.

    Google Scholar 

  4. T.P. Baker, Stack-based scheduling of realtime processes, Real-Time Systems 3 (1991) 67–99.

    Article  Google Scholar 

  5. W. Chang, Preemptive priority queues, Oper. Res. 13 (1965) 820–827.

    Google Scholar 

  6. Y.Z. Cho, An efficient priority-scheduling algorithm for integrated services packet networks, Ph.D. dissertation, Korea Advanced Institute of Science and Technology (1988).

  7. Y.Z. Cho and C.K. Un, Analysis of the M/G/1 queue under a combined preemptive/nonpreemptive priority discipline, IEEE Trans. Commun. 41 (1993) 132–141.

    Article  Google Scholar 

  8. R.W. Conway, W.L. Maxwell and L.W. Miller, Theory of Scheduling (Addison-Wesley, Reading, MA, 1967).

    Google Scholar 

  9. J.N. Daigle and S.D. Whitehead, Transmission facility sharing for integrated services, in: Proc. for the IEEE INFOCOM '84 (1984) pp. 236–245.

  10. S. Drekic and D.A. Stanford, Reducing delay in preemptive repeat priority queues, Oper. Res., to appear.

  11. E. Gelenbe and I. Mitrani, Analysis and Synthesis of Computer Systems (Academic Press, London, 1980).

    Google Scholar 

  12. C. Goerg, Evaluation of the optimal SRPT strategy with overhead, IEEE Trans. Commun. 34 (1986) 338–344.

    Article  Google Scholar 

  13. S.H. Hong and H. Takagi, Analysis of transmission delay for a structured-priority packet-switching system, Comput. Networks ISDN Systems 29 (1997) 701–715.

    Article  Google Scholar 

  14. N.K. Jaiswal, Priority Queues (Academic Press, New York, 1968).

    Google Scholar 

  15. H. Kesten and J.Th. Runnenburg, Priority in waiting line problems, I and II, Proc. Koninkl. Nederlandse Akademie van Wetenschappen Series A 60 (1957) 312–324 and 325–336.

    Google Scholar 

  16. L. Kleinrock, A delay dependent queue discipline, Naval Res. Logistics Quart. 11 (1964) 329–341.

    Google Scholar 

  17. J.Y.T. Leung and J. Whitehead, On the complexity of fixed-priority scheduling of periodic real-time tasks, Performance Evaluation 2 (1982) 237–250.

    Article  Google Scholar 

  18. C.L. Liu and J.W. Layland, Scheduling algorithms for multiprogramming in a hard-real-time environment, J. Assoc. Comput. Mach. 20 (1973) 46–61.

    Google Scholar 

  19. M. Paterok and A. Ettl, Sojourn time and waiting time distributions for M/G/1 queues with preemption-distance priorities, Oper. Res. 42 (1994) 1146–1161.

    Article  Google Scholar 

  20. L. Schrage, Analysis and optimization of a queueing model of a real-time computer control system, IEEE Trans. Comput. 18 (1969) 997–1003.

    Google Scholar 

  21. H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Vol. 1: Vacation and Priority Systems, Part 1 (North-Holland, Amsterdam, 1991).

    Google Scholar 

  22. H. Takagi and Y. Kodera, Analysis of preemptive loss priority queues with preemption distance,Queueing Systems 22 (1996) 367–381.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Statistical and Actuarial Sciences, The University of Western Ontario, London, Ontario, Canada, N6A 5B7

    Steve Drekic & David A. Stanford

Authors
  1. Steve Drekic
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David A. Stanford
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Drekic, S., Stanford, D.A. Threshold-based interventions to optimize performance in preemptive priority queues. Queueing Systems 35, 289–315 (2000). https://doi.org/10.1023/A:1019106530558

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019106530558

Search

Navigation