Scheduling within temporal partitions: response-time analysis and server design

ABSTRACT

As the bandwidth of CPUs and networks continues to grow, it becomes more attractive, for efficiency reasons, to share such resources among several applications with the minimum level of interference. This can be achieved using temporal partitions, with each application assigned to its own partition and executing as if it was executing alone on a resource with lower bandwidth. The partitions are associated to servers that execute the application tasks according to a given application-level scheduler. On the other hand, the set of servers is scheduled by a system-level scheduler. This paper addresses the particular case of fixed priorities-based application-level schedulers together with a periodic server model at the system level. It starts with an adequate response time analysis based on the notion of server availability for a known server. Then it addresses the inverse problem of designing a server with minimum system-level resource requirements to fulfill the application time constraints. In this context, the paper shows that response time based schedulability tests with linear time bounds do not need to consider all tasks but just a small subset, which may lead to substantial speed-ups. The proposed method goes a step further with respect to other recent works in the literature by considering a more complete task model, effectively computing the server parameters and establishing a better trade-off concerning complexity and tightness.

REFERENCES

• 1: Almeida L., P. Pedreiras, J. A. Fonseca, The FTT-CAN Protocol: Why and How, IEEE Transactions on Industrial Electronics, 49(6), December 2002.
• 2: Luís Almeida , José A. Fonseca, Analysis of a Simple Model for Non-Preemptive Blocking-Free Scheduling, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.233, June 13-15, 2001
• 3: Audsley, N., A. Burns, M. Richardson, K. Tindell and A. Wellings. Applying New Scheduling Theory to Static Priority Pre-Emptive Scheduling. Software Engineering Journal, 8(5): 285--292, 1993.
• 4: Lipari G. and E. Bini. Resource Partitioning among Real-Time Applications. Proc. of ECRTS'03 (EUROMICRO Conf. on Real-Time Systems). Porto, Portugal. July 2003.
• 5: Jia Xu , David Parnas, Scheduling Processes with Release Times, Deadlines, Precedence and Exclusion Relations, IEEE Transactions on Software Engineering, v.16 n.3, p.360-369, March 1990 [doi>10.1109/32.48943]
• 6: Saowanee Saewong , Ragunathan (Raj) Rajkumar , John P. Lehoczky , Mark H. Klein, Analysis of Hierar hical Fixed-Priority Scheduling, Proceedings of the 14th Euromicro Conference on Real-Time Systems, p.173, June 19-21, 2002
• 7: Xiang (Alex) Feng , Aloysius K. Mok, A Model of Hierarchical Real-Time Virtual Resources, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.26, December 03-05, 2002
• 8: Rushby, J., A Comparison of Bus Architectures for Safety-Critical Embedded Systems, CSL Technical Report, SRI International, September 2001.
• 9: Rodney R. Howell , Muralidhar K. Venkatrao, On non-preemptive scheduling of recurring tasks using inserted idle times, Information and Computation, v.117 n.1, p.50-62, Feb. 15, 1995 [doi>10.1006/inco.1995.1028]
• 10: Almeida, L. Response-Time Analysis and Server Design for Hierarchical Scheduling. Proc. of the Work-in-Progress session of RTSS'03 (IEEE Real-Time Systems Symposium). Cancun, Mexico. December 2003.
• 11: Insik Shin , Insup Lee, Periodic Resource Model for Compositional Real-Time Guarantees, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.2, December 03-05, 2003
• 12: M. González Harbour , J. C. Palencia, Response Time Analysis for Tasks Scheduled under EDF within Fixed Priorities, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.200, December 03-05, 2003
• 13: Pedreiras, P. and L. Almeida. Combining Time and Event-triggered Traffic in FTT-CAN. Proc. of WFCS'00 (IEEE Work. Factory Communication Systems). Porto, Portugal. Sept 2000.
• 14: Aloysius K. Mok , Alex Xiang Feng, Real-Time Virtual Resource: A Timely Abstraction for Embedded Systems, Proceedings of the Second International Conference on Embedded Software, p.182-196, October 07-09, 2002

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Design, Theory

Keywords:
hierarchical scheduling, real-time scheduling, real-time systems, response-time analysis