Schedulability Analysis For Fault-Tolerant Real-Time Systems

Real-time systems are widely used in the applications which have strict time-constraints on the response of the systems. Schedulability analysis is an efficient method to predict and verify whether a system can meet the time-constraints in the requirements. It can be used in the design step of real-time systems. With the enhancement of the application requirements, the design of real-time systems becomes more complex, especially when RTOS, fault-tolerance and distributed computing technologies are applied, which makes it more difficult to analyze the schedulability of a real-time system, In this paper, we study the schedulability analysis technologies for industrial real-time control systems sufficiently considering the effects of primary/alternative task fault-tolerance mechanism, distributed system architecture and OSEK/VDX specification compliant RTOS. The main contents and contributions of the work are as follows:1. Research on schedulability analysis for hybrid preemptive scheduling and group-based preemptive scheduling. Both the two scheduling schemes are recommended by the OSEK/VDX OS standand. But the schedulability analysis methods for them have not been studied before. In this paper we propose two methods to calculate tasks' worst-case response time for hybrid preemptive scheduling and group-based preemptive scheduling respectively. Based on the comparision of tasks' worst-case response time and their deadline, the schedulability of a system can be determined. Since fault-tolerance mechanisms are often adopted in real-time systems, we also extend the schedulability analysis methods by considering the effects of a primary/alternative task fault-tolerance mechanism. Based on the algorithms, we also give a method to calculate the minimum allowed time between two consecutive faults when the schedulability of a system is guaranteed.2. Research on schedulability analysis for preemptive threshold scheduling. Preemptive threshold scheduling is more general and flexible than hybrid and group-based preemptive scheduling schemes. We extend the preemptive threshold schduling with the primary/alternative task fault-tolerance mechanism and study the schedulability analysis of the fault-tolerant preemptive threshold scheduling. In order to obtain the best fault-tolerance capability, a search-based optimized algorithm and a heuristic algorithm are proposed to find the optimal assignment of all the tasks' preemptive threshold priorities for a given system.3. Research on the schedulability analysis for distributed real-time systems. In distributed real-time systems, schedulability analysis is based on the calculation of the end-to-end response time of transactions. Although current time analysis techniques can precisely analyze the response time, the performance is not quite satisfying, especially for large size distributed systems. We present a novel end-to-end worst-case and best-case response time analysis approach for hard real-time distributed systems. This technique is based on the critical instant analysis and the canonical form transformation. It extends the traditional holistic analysis technique by exploiting both the local and global precedence relations among tasks and messages. Simulation results have shown that this algorithm can achieve accurate results and offer good performance for systems with wide range of CPU utilizations and task set size, and therefore is applicable to schedulability analysis of complex distributed systems. Furthermore, the response jitter of transactions can also be achieved through the calculation of both the worst-case and the best-case end-to-end response time.4. Research on the application approach of schedulability analysis techniques. To make the schedulability analysis techniques practicable in real-time system products development, some problems need to be solved. Based on the case study of SmartOSEK, an OSEK/VDX compliant RTOS, we study how the overhead of OSEK OS can affect the response time of tasks and present a revised algorithm to accurately calculate the worst-case local response time of tasks by considering the effects from OS overhead. In order to improve the availability of the schedulability analysis methods in the development of practical systems, a development and timeliness verification procedure is proposed for OSEK/VDX compliant electronic control systems. To support this procedure, we develop SmartlDE, an embedded software development platform, which is introduced at last.