Research On Dependability-Aware Schedulings For Mission-Critical Real-Time Systems

Mission-Critical Real-time Systems (MCRTSs) have been widely applied in national information domains, such as aeronautics, avionics, weapon devices, nuclear systems, industrial systems, automobile electronics, electronic finance and government, power grid systems, and so on. High dependability is indispensable for those MCRTSs, because undependable MCRTSs will bring great threats to the nation, the human society, and even result in great loss of finance and human lifes, or damage to our living environments. With the rapidly evolution of mission-critical real-time applications, dependable factors such as energy efficiency, reliability and security have become serious restricts for most of the MCRTSs. Therefore, high dependable real-time systems have been considered to be the trend for future development. As a key approach to ensure the time-critical performance and dependability of MCRTS, real-time scheduling has been a hot research topic recently. By incorprating traditional real-time scheduling methods with dependability-enhancing mechanisms of task, the system-level schedulings will become an efficient approach for designing dependable real-time systems.With the purpose of designing real-time task schedulings, traditional real-time scheduling algorithms are systematically summarized and analyzed in ths dissertation. As a conclusion, this dissertation points out that real-time scheduling for improving the dependability of MCRTS is actually lack of investigation, especially without integrated concepts for system-level scheduling. Then the mechanisms for improving tasks' dependablilty are analyzied, and a dependability-aware scheduling frame is proposed. For low energy consumption, high reliability, and high security mission-critical applications, four key design problems are idendified and solved. These problems include:energy-aware scheduling for uniprocessor real-time tasks; reliability-aware energy-efficient scheduling for distributed independent tasks; security-aware scheduling for uniprocessor real-time tasks; security-aware scheduling for distributed collaborative tasks with energy constraints. Main works and contributions of this dissertation are as follows: (1) A system-level dependability-aware application architecture (referred as DAAA) is proposed, and in the core of DAAA, a novel dependability-aware real-time scheduling frame (DARTSF for short) is designed. DAAA bridges the mission-critical application requirements with the embedded hardware/software systems; DARTSF is a flexible scheduling frame, which effectively intregrates real-time scheduling, energy-aware scheduling, reliabibily-aware scheduling, and security-aware task schedulings together.(2) An energy-optimized real-time scheduling algorithm is proposed for a class of simple but widely existed real-time applications. The application model of serving multiple users in a finite time interval is established, and then a lazy scheduling method with polynomial time conplexity is designed and strictly proved to be optimal.(3) A reliability-aware and energy-aeare real-time scheduling algorithm is proposed for mission-critical distributed systems. Based on dynamic voltage scaling, task re-exection, and the perfect admission control mechanisms, the proposed algorithm can minimize the online energy consumption of arriving tasks without sacrisfying the reliability and real-time constraints of the task. In conjunction with the local slack reclaim mechanism, the algorithm can futher reduce energy consumption and the task rejection ratio while maintaining the reliability goal of each task.(4) To support security-critical real-time applications, a security risk driven uniprocessor scheduling approach is proposed. The security risk is firstly presented to quantify the security quality of real-time tasks, and then the schedulability of real-time tasks is analyzied. Based on CPU utilization control policies, algorithms (ASRMA and RSTS) with minimum system security risk are designed for both periodic tasks and aperiodic tasks respectively. Both of ASRMA and RSTS are dynamic programming based approximated algotihm, and can obtain near-optimal solutions with guaranteed security performance in fully polynomial time complexity.(5) A security-aware and energy-aware task mapping and scheduling algorithm (called SEATMS) is proposed for security-critical heterogeneous distributed systems. A security risk model is established for tasks confronting multiple security threats. Based on the bottom up policy, a 3-stage heuristic mapping and scheduling mechanism with polynomial time complexity is designed. SEATMS is able to reduce the system security risk as much as possible, while satisfying the deadline and energy constraints of collaborative tasks. Comparing to state-of-the-art, experiments show obviou superiority of SEATMS in terms of providing low security risk, real-time guarantee, and energy budget guarantee.At present, dependability computing attracts many investigations, but the researches on improving depenbality of real-time system from the task scheduling level are still in the early age. The dependability-aware real-time scheduling models and algorithms proposed in this dissertation may provide some contributions to improve the dependability of MCRTS.