Improved response time analysis of tasks scheduled under preemptive Round-Robin

ABSTRACT

Round-Robin scheduling is the most popular time triggered scheduling policy, and has been widely used in communication networks for the last decades. It is an efficient scheduling technique for integration of unrelated system parts, but the worst-case timing depends on the system properties in a very complex way. The existing works on response time analysis of task scheduled under Round-Robin determine very pessimistic response time bounds, without considering in detail the interactions between tasks. This may lead to a degradation of the efficiency of Round-Robin scheduling algorithm, and becomes a practical obstacle to its application in real-time systems. In this paper we present an approach to compute much tighter best-case and worst-case response time bounds of tasks scheduled under preemptive Round-Robin, including also the effects of the scheduling algorithm.

REFERENCES

• 1: Ravi Budruk , Don Anderson , Ed Solari, PCI Express System Architecture, Pearson Education, 2003
• 2: FlexRay. http://www.flexray.com/
• 3: J. P. Gutierrez, J. J. G. Garcia, and M. G. Harbour. Best-Case Analysis for Improving the Worst-Case Schedulability Test for Distributed Hard RealTime Systems. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), 1998.
• 4: Sven Heithecker , Amilcar do Carmo Lucas , Rolf Ernst, A high-end real-time digital film processing reconfigurable platform, EURASIP Journal on Embedded Systems, v.2007 n.1, p.12-12, January 2007 [doi>10.1155/2007/85318]
• 5: K. Jeffay , F. D. Smith , A. Moorthy , J. Anderson, Proportional Share Scheduling of Operating System Services for Real-Time Applications, Proceedings of the IEEE Real-Time Systems Symposium, p.480, December 02-04, 1998
• 6: M. Joseph and P. Pandya. Finding Response Times in a Real-Time System. The Computer Journal, 29(5):390--395, 1986.
• 7: Salil S. Kanhere , Harish Sethu, On the Latency Bound of Pre-Order Deficit Round Robin, Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, p.508-517, November 06-08, 2002
• 8: H. Kopetz and G. Bauer. The Time-Triggered Architecture. Proceedings of the IEEE, Special Issue on Modeling and Design of Embedded Software, 2001.
• 9: J. Lehoczky. Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines. In Proceedings of the Real-Time Systems Symposium, pages 201--209, 1990.
• 10: 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]
• 11: J. Migge. Real-time scheduling: a trajectory based model. PhD thesis, Nice University, Nancy, France, 1999.
• 12: Jörn Migge , Alain Jean-Marie , Nicolas Navet, Timing analysis of compound scheduling policies: application to posix1003.1b, Journal of Scheduling, v.6 n.5, p.457-482, September/October 2003 [doi>10.1023/A:1024806606443]
• 13: S. Mukherjee, D. Saha, M. Saksena, and S. K. Tripathi. A Bandwidth Allocation Scheme for Time Constrained Message Transmission on a Slotted Ring LAN. In IEEE Real-Time Systems Symposium, Raleigh-Durham, NC, 1993.
• 14: A. Raha , S. Kamat , Wei Zhao, Guaranteeing end-to-end deadlines in ATM networks, Proceedings of the 15th International Conference on Distributed Computing Systems, p.60, May 30-June 02, 1995
• 15: K. Richter. Compositional Performance Analysis. PhD thesis, Technical University of Braunschweig, 2004.
• 16: M. Shreedhar , George Varghese, Efficient fair queueing using deficit round robin, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.231-242, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 17: B. Sprunt, L. Sha, and J. Lehoczky. Aperiodic Task Scheduling for Hard Real-Time Systems. Journal of Real-Time Systems, 1(1):27--60, 1989.
• 18: Hideaki Takagi, Exact analysis of round-robin schedulng of services, IBM Journal of Research and Development, v.31 n.4, p.484-488, July 1, 1987
• 19: K. W. Tindell , A. Burns , A. J. Wellings, An extendible approach for analyzing fixed priority hard real-time tasks, Real-Time Systems, v.6 n.2, p.133-151, March 1994 [doi>10.1007/BF01088593]
• 20: R. Wu and Y.-B. Chen. Analysis of a loop Transmission System with Round-Robin Scheduling of Services. IBM J. Res. Dev., 19(5):486--493, 1975.
• 21: R. Yates. High Speed Round Robin Queueing Networks. PhD thesis, MIT, Dept. of Electrical Engineering and Computer Science, 1990.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance, Reliability, Verification

Keywords:
Round-Robin, response time analysis