Real-time scheduler design for safety-critical systems : A supervisory control approach
No Thumbnail Available
In safety-critical real-time systems, failure to meet task deadlines may lead to consequences that are deemed to be unacceptable. Reliability of such systems are typically guaranteed by enforcing all timing and safety-related requirements to be honored, even under the assumption of the worst-case request arrival behavior and service requirements. Hence, static on-line schedulers are often preferred in safety critical systems in order to achieve better predictability. In addition, on-line computation also allow exhaustive solution space enumeration to pre-compute optimal schedules at design time, thus ensuring lower design costs through higher resource utilization. To ensure correctness and completeness of the enumeration process, formal mechanisms such as automata/model-based approaches are often preferred. In recent years, researchers have shown that on-line formal approaches such as Supervisory Control of Timed Discrete Event Systems (SCTDES) can be used to synthesize optimal schedulers for real-time systems. In this dissertation, we present a few novel real-time scheduler designs for safety-critical systems consisting of various types of task and execution platform scenarios, using SCTDES as the underlying formalism. The entire thesis work is composed of multiple distinct contributions which are categorized into five phases. In the first phase, both non-preemptive as well as preemptive scheduling strategies for uniprocessor systems have been considered. The second phase extends the uniprocessor scheduling mechanisms designed in the first to provide fault-tolerance in homogeneous multi-processor / multi-core systems, against permanent processor faults. Apart from guaranteeing timing and resource constraints, safety-critical systems implemented on multi-core platforms need to satisfy stringent power dissipation constraints such as Thermal Design Power thresholds. Hence, in the third phase, we have developed a scheduler synthesis framework which guarantees adherence to a system level peak power constraint. While the first three phases dealt with the design of scheduling approaches for independent tasks, in the fourth phase, we have endeavored towards the development of an optimal real-time scheduler synthesis scheme for precedence-constrained task graphs executing on homogeneous multicores. Further, this scheme has been extended to provide robustness against multiple transient processor faults. In the final phase, we have developed models that are able to accurately capture the execution of tasks on a heterogeneous platform. Experimental results have demonstrated the versatility and efficacy of the proposed scheduler synthesis approaches.
Supervisors: Arnab Sarkar and Santosh Biswas
COMPUTER SCIENCE AND ENGINEERING