Embedded avionics software systems have stringent certification requirements that typically entail the validation of temporal correctness in addition to logical correctness. Informally, logical correctness means that tasks (i.e., programs) produce correct outputs, while temporal correctness means that such outputs are produced at the correct time (e.g., by specified deadlines). To validate temporal correctness, some knowledge of task execution times is required. Ideally, provable upper bounds on execution times would be used. Unfortunately, obtaining such a bound usually requires pessimistic assumptions regarding task behaviors and hardware functionality. This can cause predicted execution times to greatly exceed those that actually occur. The resulting over-provisioning can be detrimental from a size, weight, and power (SWaP) viewpoint.
A few years ago, Steve Vestal (while working in the avionics industry at Honeywell) observed that the extent of over-provisioning can be eased by tailoring execution-time assumptions to the criticality of the software component being analyzed. Specifically, he noted that real systems are usually comprised of tasks of differing criticalities; further, different execution-time estimation methods are often used for different criticality levels: for highly critical components, pessimistic tool-produced upper bounds may be required, but for less critical components, empirically estimated times might be reasonable. Vestal proposed reflecting such assumptions in validation: when validating a system at criticality level L, execution times should be assumed (for tasks at any level) commensurate with estimation methodologies appropriate for level L. The formal task model resulting from Vestal’s work has come to be known as the mixed-criticality task model.
Vestal’s observations led to a flurry of research within the real-time systems community on mixed-criticality task systems. However, this research has been almost entirely theoretical in nature and has little practical impact (which is disconcerting, given that the proposed mixed-criticality task model was suggested by someone actually working in industry). One serious limitation of prior work is that it has been mostly limited to uniprocessor platforms. Given the advent of multicore technologies, continued reliance on uniprocessor platforms in avionics systems will impede future functional advances. Prior work has also emphasized theoretical issues such as approximation ratios (which enable comparison to "ideal" allocations) over and above practical validation issues.
In this project, we are seeking to return work on mixed-criticality real-time systems to its roots by conducting research that emphasizes algorithms and techniques that can be practically applied. We also seek to expand the focus of mixed-criticality resource allocation by directly addressing issues of relevance to multicore platforms. Our research agenda includes the development of a multicore-based mixed-criticality resource allocation framework that includes analysis for checking timing constraints, and an experimental evaluation of this framework that focuses on workloads pertaining to future unmanned air vehicles (UAVs). In comparison to current UAVs, these future UAVs will have far greater autonomous capabilities and will be significantly better equipped to adapt to changing environmental conditions. They will also have intensive computational workloads (hence the need for multicore), have system components of varying criticalities, and be subject to stringent certification requirements.
The proposed mixed-criticality framework is being developed by extending prior work by the investigators and colleagues at Northrop Grumman Corp. (NGC) that resulted in the development of a basic multicore-based mixed-criticality scheduling framework called MC2 (Mixed-Criticality on MultiCore). In this project, this basic framework is being extended in several significant ways. For example, to enable dynamic workload changes to be supported in MC2, new techniques are being developed for changing a task’s time-related parameters at runtime and for analyzing the effects of such changes. Research on such techniques and other issues will proceed by following a research agenda that includes work on real-time scheduling and synchronization mechanisms of fundamental relevance to the proposed framework, work on analysis methods for certifying timing constraints, and evaluations of the resulting framework based on prototype implementations. In all of this work, interactions with colleagues at NGC will continue so that the obtained framework has real industry relevance.
Over the past decade, the U.S. Air Force and other service branches of the U.S. Armed Forces have recognized the need to efficiently utilize multicore computers aboard deployed systems. Unfortunately, the pessimism noted above regarding the validation of timing constraints has been a key stumbling block in this regard. Vestal’s proposed mixed-criticality analysis methods are a possible way forward. However, practical multicore-ready mixed-criticality frameworks must be devised for this way forward to become a reality. Such a framework will be developed and implemented in this project.
N. Kim, Combining Hardware Management with Mixed-Criticality Provisioning in Multicore Real-Time Systems, Ph.D. Dissertation, The University of North Carolina at Chapel Hill, May 2019. PDF .
N. Kim, B. Ward, M. Chisholm, C.-Y. Fu, J. Anderson, and F.D. Smith, " Attacking the One-Out-Of-m Multicore Problem by Combining Hardware Management with Mixed-Criticality Provisioning", Real-Time Systems, special issue of outstanding papers from the 22nd IEEE Real-Time and Embedded Technology and Applications Symposium, Volume 53, Number 5, pp. 709-759, September 2017. PDF .
N. Kim, S. Tang, N. Otterness, J. Anderson, F.D. Smith, and D. Porter, " Supporting I/O and IPC via Fine-Grained OS Isolation for Mixed-Criticality Real-Time Tasks", Proceedings of the 26th International Conference on Real-Time Networks and Systems, pp. 191-201, October 2018. Winner, outstanding paper award and best paper award. PDF . Longer version with appendices and all schedulability plots: PDF. PDF .
M. Chisholm, N. Kim, S. Tang, N. Otterness, J. Anderson, F.D. Smith, and D. Porter, " Supporting Mode Changes while Providing Hardware Isolation in Mixed-Criticality Multicore Systems", Proceedings of the 25th International Conference on Real-Time Networks and Systems, pp. 58-67, October 2017. PDF . Longer version with appendices and all schedulability plots: PDF. PDF .
N. Kim, M. Chisholm, N. Otterness, J. Anderson, and F.D. Smith, " Allowing Shared Libraries while Supporting Hardware Isolation in Multicore Real-Time Systems", Proceedings of the 23rd IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 223-234, April 2017. PDF . Longer version with all schedulability plots: PDF .
M. Chisholm, N. Kim, B. Ward, N. Otterness, J. Anderson, and F.D. Smith, " Reconciling the Tension Between Hardware Isolation and Data Sharing in Mixed-Criticality, Multicore Systems", Proceedings of the 37th IEEE Real-Time Systems Symposium, pp. 57-68, December 2016. PDF . Longer version with all schedulability plots: PDF . Code is available here .
N. Kim, B. Ward, M. Chisholm, C.-Y. Fu, J. Anderson, and F.D. Smith, " Attacking the One-Out-Of-m Multicore Problem by Combining Hardware Management with Mixed-Criticality Provisioning", Proceedings of the 22nd IEEE Real-Time Embedded Technology and Applications Symposium, pp. 149-160, April 2016. Winner, best student paper award. PDF . Version with all schedulability graphs: PDF .
M. Chisholm, B. Ward, N. Kim, and J. Anderson, " Cache Sharing and Isolation Tradeoffs in Multicore Mixed-Criticality Systems", Proceedings of the 36th IEEE Real-Time Systems Symposium, pp. 305-316, December 2015. PDF . Longer version with more graphs: PDF .
J. Erickson, N. Kim, and J. Anderson, " Recovering from Overload in Multicore Mixed-Criticality Systems", Proceedings of the 29th IEEE International Parallel and Distributed Processing Symposium, pp. 775-785, May 2015. PDF .
N. Kim and J. Erickson and J. Anderson, " Mixed-Criticality on Multicore (MC2): A Status Report", Proceedings of the 10th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, pp. 45-50, July 2014. PDF .
B. Ward, J. Herman, C. Kenna, and J. Anderson, " Making Shared Caches More Predictable on Multicore Platforms", Proceedings of the 25th Euromicro Conference on Real-Time Systems, pp. 157-167, July 2013. Winner, outstanding paper award. PDF .
M. Mollison and J. Anderson, " Bringing Theory into Practice: A Userspace Library for Multicore Real-Time Scheduling", Proceedings of the 19th IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 283-292, April 2013. PDF .
J. Herman, C. Kenna, M. Mollison, J. Anderson, and D. Johnson, " RTOS Support for Multicore Mixed-Criticality Systems", Proceedings of the 18th IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 197-208, April 2012. PDF .
C. Kenna, J. Herman, B. Brandenburg, A. Mills, and J. Anderson, " Soft Real-Time on Multiprocessors: Are Analysis-Based Schedulers Really Worth It?", Proceedings of the 32nd IEEE Real-Time Systems Symposium, pp. 93-103, December 2011. PDF .
M. Mollison, J. Erickson, J. Anderson, S. Baruah, and J. Scoredos, " Mixed Criticality Real-Time Scheduling for Multicore Systems", Proceedings of the 7th IEEE International Conference on Embedded Software and Systems, pp. 1864-1871, June 2010. PDF .
J. Anderson, S. Baruah, and B. Brandenburg, " Multicore Operating-System Support for Mixed Criticality", Proceedings of the Workshop on Mixed Criticality: Roadmap to Evolving UAV Certification , April 2009. Postscript . PDF .
Other papers that acknowledge the grants that supported this project can be found on the PI's Publications Page .
Last modified 15 February 2019