CNS Core: Small: Schedulability Analysis of Safety-Critical Real-Time Systems: Beyond Pseudo-polynomial Time Algorithms

Washington University, Saint Louis MO

Investigators

Abstract

Safety-critical systems should be validated correct prior to their deployment; schedulability analysis is the process of validating timing properties of such systems. This project will investigate the use of Integer Linear Program (ILP) solvers for developing schedulability analysis algorithms that are efficient enough for use in practice. It will do so by identifying the relationships between the inherent computational complexity of fundamental problems that arise in real-time schedulability analysis and their suitability for representation as ILPs that are efficiently solvable by ILP-solvers. A general methodology will be developed for determining whether particular schedulability analysis problems can be efficiently represented as such ILPs; this methodology will be applied to common schedulability analysis problems; and ILP-based algorithms will be developed and evaluated for those problems that are determined to be efficiently representable in this manner. There have been vast improvements in the performance of ILP-solvers in recent years. Hence, successful completion of this project will greatly expand the class of real-time systems upon which it is computationally feasible to do schedulability analysis. This will enable the development of safer safety-critical systems, such as airplanes, cars, and medical devices, which are able to offer more advanced features than is currently possible. Project findings will be disseminated via participation in conference workshops and panels and the organization of cross-disciplinary events with industrial participation. New teaching materials incorporating such findings will be developed for graduate courses at Washington University and shared with interested instructors elsewhere. Undergraduate research based upon this project will be integrated into Washington University's well-established summer REU program, which incorporates extensive research engagement with technical and social activities for participants. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.