skip to main content
10.1145/1516241.1516351acmconferencesArticle/Chapter ViewAbstractPublication PagesicuimcConference Proceedingsconference-collections
research-article

Analysis on quantum-based fixed priority scheduling of real-time tasks

Published: 15 February 2009 Publication History

Abstract

Fixed priority schedulers are widely used for real-time systems, and there were efforts to improve the schedulability. Preemption threshold scheduling is one of such efforts with a dual priority scheme. It increases the schedulability by introducing priority inversion during task execution. In this paper, we analyze another scheduling model, quantum-based scheduling. When quantum-based scheduling is combined with priority-based scheduling, the quantum introduces a partially non-preemptive region. We show that the non-preemptiveness introduced by quantum-based scheduling can improve the schedulability of fixed priority tasks, and there is a task set which is not schedulable by preemption threshold scheduling but is schedulable by quantum-based scheduling. This paper presents a method to calculate the worst case response time of tasks in quantum-based scheduling. Based on the previous research results for preemptive and non-preemptive scheduling, we present a priority assignment method for quantum-based scheduling also.

References

[1]
J. H. Anderson, R. Jain, and K. Jeffay. Efficient object sharing in quantum-based real-time systems. In Proceedings of the 19th IEEE Real-Time Systems Symposium, pages 346--355, Dec. 1998.
[2]
N. C. Audsley. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical report, Department of Computer Science, University of York, 1991.
[3]
N. C. Audsley, A. Burns, M. Richardson, and A. Wellings. Hard real-time scheduling: The deadline monotonic approach. In Proceedings of IEEE Workshop on Real-Time Operating Systems and Software, pages 133--137, May 1991.
[4]
S. Baruah. The limited-preemption uniprocessor scheduling of sporadic task systems. In Proceedings of the 17th Euromicro Conference on Real-Time Systems, pages 137--144, July 2005.
[5]
E. Bini, G. C. Buttazzo, and G. M. Buttazzo. Rate monotonic analysis: The hyperbolic bound. IEEE Transactions on Computers, 52(7):933--942, 2003.
[6]
J. Chen, A. Harji, and P. Buhr. Solution space for fixed-priority with preemption threshold. In Proceedings of the 11th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 385--394, Mar. 2005.
[7]
L. George, N. Riviere, and M. Spuri. Preemptive and non-preemptive real-time uniprocessor scheduling. Technical report, INRIA, 1996.
[8]
R. Ghattas and A. G. Dean. Preemption threshold scheduling: Stack optimality, enhancements and analyis. In Proceedings of the 13th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 147--157, Apr. 2007.
[9]
R. Gopalakrishnan and G. M. Parulkar. Bringing real-time scheduling theory and practice closer for multimedia computing. In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 1--12, May 1996.
[10]
D.-Z. He, F.-Y. Wang, and W. Li. Dynamic preemption threshold scheduling for specific real-time control systems. In Proceedings of the IEEE International Conference on Networking, Sensing and Control, pages 395--400, Mar. 2005.
[11]
K. Jeffay, D. F. Stanat, and C. U. Martel. On non-preemptive scheduling of periodic and sporadic tasks. In Proceedings of IEEE Real-Time Systems Symposium, pages 129--139, Dec. 1991.
[12]
D. I. Katcher, H. Arakawa, and J. K. Strosnider. Engineering and analysis of fixed priority schedulers. IEEE Transactions on Software Engineering, 19(9):920--934, 1993.
[13]
S. Kim, S. Hong, and T.-H. Kim. Integrating real-time synchronization schemes into preemption threshold scheduling. In Proceedings of the 5th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, page 145, Apr. 2002.
[14]
J. P. Lehoczky. Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings of IEEE Real-Time Systems Symposium, pages 201--209, 1990.
[15]
T. M. Lim, B.-S. Lee, and C. K. Yeo. Quantum-based earliest deadline first scheduling for multiservices. IEEE Transactions on Multimedia, 9(1):157--168, 2007.
[16]
C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of ACM, 20(1):46--61, 1973.
[17]
Y. Wang and M. Saksena. Scheduling fixed-priority tasks with preemption threshold. In Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications, pages 328--335, Dec. 1999.

Cited By

View all
  • (2009)Integration of Preemption Threshold and Quantum-Based Scheduling for Schedulability Enhancement of Fixed Priority TasksProceedings of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2009.60(503-510)Online publication date: 24-Aug-2009

Index Terms

  1. Analysis on quantum-based fixed priority scheduling of real-time tasks

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication
      February 2009
      704 pages
      ISBN:9781605584058
      DOI:10.1145/1516241
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 15 February 2009

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. fixed priority scheduling
      2. quantum-based scheduling
      3. real-time
      4. real-time scheduling

      Qualifiers

      • Research-article

      Conference

      ICUIMC '09
      Sponsor:

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 13 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2009)Integration of Preemption Threshold and Quantum-Based Scheduling for Schedulability Enhancement of Fixed Priority TasksProceedings of the 2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications10.1109/RTCSA.2009.60(503-510)Online publication date: 24-Aug-2009

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media