Overview

Real-time systems are ones in which correctness depends not only on logical correctness but also on timeliness. In the real-time systems community, substantial research efforts have concentrated on the schedulability analysis problem, which determines whether timing requirements imposed on the system can be satisfied. However, there is no widely accepted technique that supports the compositionality of timing requirements, i.e., how component-level timing requirements can be independently analyzed, abstracted, and composed into the system-level timing requirements.

We have developed a compositional real-time scheduling framework for supporting the compositionality of timing requirements. Fundamental to such a framework is the problem of computing the minimum resource requirements necessary for guaranteeing the collective timing requirements of a component or a component assembly. We have addressed this problem systematically, by developing sufficient and necessary schedulability conditions for the two most popular real-time scheduling algorithms: EDF (earliest deadline first) and RM (rate-monotonic).

Our compositional scheduling framework is supported by the CARTS tool and the Real-Time Xen virtualization platform.

Current Members Prof. Insup Lee Prof. Oleg Sokolsky Dr. Linh Thi Xuan Phan Sanjian Chen Jaewoo Lee

Former Members Madhukar Anand Arvind Easwaran Sebastian Fischmeister Insik Shin

Publications

• Sanjian Chen, Linh T. X. Phan, Jaewoo Lee, Insup Lee and Oleg Sokolsky, Removing Abstraction Overhead in the Composition of Hierarchical Real-Time Systems, Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2011), Chicago, IL, April 12-14, 2011
• Linh T.X. Phan, Insup Lee, and Oleg Sokolsky, A Semantic Framework for Multi-Mode Systems, Proceedings of the 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2011), Chicago, IL, April 12-14, 2011
• Jaewoo Lee, Linh T.X. Phan, Sanjian Chen, Oleg Sokolsky, and Insup Lee "Improving Resource Utilization for Compositional Scheduling using DPRM Interfaces" The 3rd Workshop on Compositional Theory and Technology for Real-Time Embedded Systems (CRTS 2010), San Diego, CA, USA, November 30, 2010
• Arvind Easwaran, Insup Lee, Oleg Sokolsky, and Steve Vestal "A Compositional Scheduling Framework for Digital Avionics Systems" Real-Time Computing Systems and Applications (RTCSA 2009), Beijing, China, August 24-26, 2009
  An expanded version is available here in Technical Report No. MS-CIS-09-04 January 2009
• Insik Shin, Arvind Easwaran, and Insup Lee "Hierarchical Scheduling Framework for Virtual Clustering of Multiprocessors" Euromicro Conference on Real-Time Systems, ECRTS 2008, July 2-4, Prague, Czech Republic
• Madhukar Anand and Insup Lee "Robust and Sustainable Schedulability Analysis of Embedded Software," Proceedings of the ACM SIGPLAN/SIGBED 2008 Conference on Languages, Compilers, and Tools for Embedded Systems, LCTES 2008, Tucson, AZ, Jun 12-13, 2008.
• Arvind Easwaran, Insup Lee, and Oleg Sokolsky "Interface Algebra for Analysis of Hierarchical Real-Time Systems," International Workshop on Foundations in Interface Technology, FIT 2008, April 5, Budapest, Hungary.
• Insik Shin and Insup Lee "Compositional Real-Time Scheduling Framework with Periodic Model," ACM Transactions on Embedded Computing Systems (TECS), vol 7, no 3, April 2008
• Madhukar Anand, Arvind Easwaran, Sebastian Fischmeister, and Insup Lee "Compositional Feasibility Analysis of Conditional Real-Time Task Models," International Symposium on Object-Oriented Real-Time Distributed Computing, ISORC 2008, May 5-7, Florida, USA
• Arvind Easwaran, Madhukar Anand, and Insup Lee "Compositional Analysis Framework using EDP Resource Models," IEEE Real-Time Systems Symposium, RTSS 2007, Dec 3-6, Tucson, Arizona, USA.
• Arvind Easwaran, Insup Lee, Insik Shin, and Oleg Sokolsky "Compositional Schedulability Analysis of Hierarchical Real-Time Systems," International Symposium on Object-Oriented Real-Time Distributed Computing, ISORC 2007, May 7-9, Santorini Island, Greece.
• Arvind Easwaran, Insik Shin, Oleg Sokolsky, and Insup Lee "Incremental Schedulability Analysis of Hierarchical Real-Time Components," International ACM & IEEE Conference on Embedded Software, EMSOFT 2006, October 22-25, Seoul, South Korea.
• Insik Shin, Insup Lee, Sang Lyul Min, "A Design Approach for Real-Time Embedded Systems with Energy and Code Size Constraints," Proceedings of 10th Real-time and Embedded Computing Systems and Applications Conference, RTCSA 2004, Gothenburg, Sweden, August 25-27, 2004.
• Insik Shin, Insup Lee, "Compositional Real-Time Scheduling Framework," Proceedings of the 25th IEEE Real-Time Systems Symposium, RTSS 2004, pp. 57-67, Lisbon, Portugal, December 6-8, 2004.
• Insik Shin, Insup Lee, "Periodic Resource Model for Compositional Real-Time Guarantees," Proceedings of the 24th IEEE Real-Time Systems Symposium, RTSS 2003, Cancun, Mexico, December 3-5, 2003. Technical report. Awarded as the Best Paper of RTSS 2003.
• Insik Shin, Insup Lee, Sang Lyul Min, "Embedded System Design Framework for Minimizing Code Size and Guaranteeing Real-Time Requirements," Proceedings of the 23rd IEEE Real-Time Systems Symposium, RTSS 2002, pp. 201-211, Austin, TX, December 2-5, 2002.

Acknowledgements

This material is based upon work supported by the National Science Foundation under grant CNS-0720703 and by the Army Research Office under grant W911NF-11-1-0403.