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

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 , Rohit Jain , K. Jeffay, Efficient Object Sharing in Quantum-Based Real-Time Systems, Proceedings of the IEEE Real-Time Systems Symposium, p.346, December 02-04, 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: Sanjoy Baruah, The Limited-Preemption Uniprocessor Scheduling of Sporadic Task Systems, Proceedings of the 17th Euromicro Conference on Real-Time Systems, p.137-144, July 06-08, 2005 [doi>10.1109/ECRTS.2005.32]
• 5: Enrico Bini , Giorgio C. Buttazzo , Giuseppe M. Buttazzo, Rate Monotonic Analysis: The Hyperbolic Bound, IEEE Transactions on Computers, v.52 n.7, p.933-942, July 2003 [doi>10.1109/TC.2003.1214341]
• 6: Jiongxiong Chen , Ashif Harji , Peter Buhr, Solution Space for Fixed-Priority with Preemption Threshold, Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, p.385-394, March 07-10, 2005 [doi>10.1109/RTAS.2005.49]
• 7: L. George, N. Riviere, and M. Spuri. Preemptive and non-preemptive real-time uniprocessor scheduling. Technical report, INRIA, 1996.
• 8: Rony Ghattas , Alexander G. Dean, Preemption Threshold Scheduling: Stack Optimality, Enhancements and Analysis, Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium, p.147-157, April 03-06, 2007 [doi>10.1109/RTAS.2007.27]
• 9: R. Gopalakrishnan , Gurudatta M. Parulkar, Bringing real-time scheduling theory and practice closer for multimedia computing, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 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 , J. K. Strosnider, Engineering and Analysis of Fixed Priority Schedulers, IEEE Transactions on Software Engineering, v.19 n.9, p.920-934, September 1993 [doi>10.1109/32.241774]
• 13: Integrating Real-Time Synchronization Schemes into Preemption Threshold Scheduling, Proceedings of the Fifth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, p.145, April 29-May 01, 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. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 17: Yun Wang , Manas Saksena, Scheduling Fixed-Priority Tasks with Preemption Threshold, Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, p.328, December 13-15, 1999

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Keywords:
fixed priority scheduling, quantum-based scheduling, real-time, real-time scheduling