Multi-core mixed-criticality real-time scheduling

Modern safety-critical real-time systems are realized via integration of multiple system components having varying criticality, designated based on consequence of failures, onto a single shared hardware platform. Such systems are known as ‘Mixed-Criticality Systems’. These systems are subjected to different certification standards that require high confidence (or assurance level against failures) for critical components (e.g., flight control) and relatively low confidence for less/non-critical components (e.g., cabin light control). The correctness of a mixed-criticality system depends on the correct functional behavior of the components with their corresponding assurance level at different criticality levels. To guarantee correctness, conventional real-time scheduling techniques that statically reserve resources to the components can be used. However, conservative reservation at all criticality levels often leads to under-utilization of system resources as the components do not necessarily require them at all times. To address this problem, mixed-criticality scheduling model was proposed. The fundamental objective is to efficiently allocate resources while ensuring safe execution of the critical components. The mixed-criticality scheduling requirement is as follows: all components must be scheduled to meet their deadlines as long as sufficient processing capacity is available and once the system demand is increased, critical components must be prioritized to meet their deadlines, whereas less/non-critical components can be penalized to meet the system demand. Although the problem of mixed-criticality scheduling on single-core platforms has been well studied, for multi-core platforms it has largely remained open. With this objective in focus, this thesis addresses some important problems of scheduling mixed-criticality systems on multi-core processors. Multi-core scheduling can broadly be classified as global and partitioned scheduling. Global scheduling allows components to execute on any core and migrate between cores at runtime. Partitioned scheduling statically assigns components to an individual core and does not allow them to migrate at runtime. Most existing global scheduling algorithms for mixed-criticality systems suffer from poor schedulability. To address this problem, a fluid execution rate based scheduling algorithm with a bounded analytical performance for mixed-criticality systems has been proposed earlier. However, the proposed fluid scheduling algorithm still suffer from schedulability issues. To this end, we first focus on the design of a global scheduling algorithm that is capable of scheduling a large class of such systems on multi-core platforms and has bounded analytical performance. We propose a multiple fluid execution rate based scheduling model for mixed-criticality systems and derive the analytical test for the algorithm. The proposed model considers different execution rates based on the system operation mode. Thus, by considering mode based dynamic execution rates the proposed algorithm is able to achieve better schedulability compared to existing algorithms. Furthermore, the proposed algorithm also has an optimal performance bound in terms of processor speedup. Most studies in mixed-criticality scheduling make an unrealistic assumption that all the less critical components can be abandoned or discarded when the critical components demand for additional processing resources. However, this method seriously impacts the performance of the less critical components which may not be suitable for many practical systems that require minimum service guarantees for these components. To address this issue, we focus on the partitioned scheduling for mixed-criticality systems which is preferred in the industry due to its strong iso- lation (freedom from interference) feature. The components executing on a core are unaffected by the critical components executing on another core unlike in global scheduling. Partitioning scheduling comprises components-to-core mapping (partitioning) strategy and scheduling algorithm on each core. Existing studies use classical partitioning strategies which are not efficient for the mixed-criticality setting. To address this problem, we propose an efficient partitioning strategy that has good performance for a wide variety of single-core mixed-criticality scheduling algorithms. This technique distributes the additional demand of the critical components evenly among all processing cores. By evenly distributing it, the scheduling capability of each core is increased, thus increasing the overall schedulability. To support maximum less critical components in the partitioned environment, we propose the semi-partitioned mixed-criticality scheduling model. In this model, the less critical components are migrated at runtime from a core which has insufficient processing capacity to another that has sufficient processing capacity. The resources corresponding to the migrating components are statically reserved on the core to which they migrate. Thus, by migrating these components at runtime, we are able to support maximum less critical components for a longer duration. These components will be eventually suspended from execution if the processing cores are not capable of supporting them.Doctor of Philosoph