Worst-Case Execution Time Analysis Of Real-Time Systems

Different from non-real-time systems, the correctness of real-time systems depends not only on the correctness of the produced results, but also on the time when they produce them. The outputs of real-time systems are valid only when they are produced in the predefined time durations. Timing behaviors are crucial for real-time systems.The purpose of Worst-Case Execution Time (WCET) analysis is to provide apriori information about the worst-case execution time of a program or a code segment before it is deployed. With apriori WCET estimates of the tasks, we can conduct task scheduling and schedulability analysis of the real-time systems concerned, and check whether the performance of the real-time systems meet the requirements.The most common method to get the WCET estimates of programs is static analysis. By analyzing the processor's characteristics, static WCET analysis computes the upper bounds of the execution times that the processors take to execute the code segments. WCET analysis should be safe and tight. A tight WCET analysis can help save project resources. To acquire tight WCET estimates, we should get necessary program flow information such as the bound of loop iteration. Automatically analyzing program flow information is the key issue in automatic WCET analysis.By thoroughly examining the state-of-the-art on WCET analysis with an emphasis on program flow analysis, this thesis addresses the following issues:The analysis of variable value range information and the methods of deriving program flow information for WCET analysis;WCET analysis based on program modes. It is observed that when the input parameters range on some specific spectrum, the execution of the program follows some specific trajectory which is a sequence of ordered nodes of the program. Each of such trajectories corresponds to a program mode. Under each program mode, we may compute a WCET estimate. If we know which mode the program will follow, the WCET estimate computed based on this mode will be more accurate than the estimate that is not based on any program mode, as is conducted by most existing methods. The methods of automatically finding program modes and calculating the WCET estimates based on modes are investigated;WCET analysis of object-oriented program. It is a tendency for real-time systems to be designed with object-oriented modeling languages and implemented with object-oriented programming languages. However, the unpredictability of polymorphism makes it even harder to carry out WCET analysis. The methods of calculating the WCET estimates of object-oriented program with polymorphism are researched;The methods of calibrating the time changed by assertion instrumentation in real-timetesting. To thoroughly test a real-time program, the program under test needs to beinstrumented such that the internal states can be collected. However, the assertion instrumentation will change the timing behaviors of the program under test. The methods of calculating the instrumented assertion precisely and calibrating the test time changed are studied.The main contributions of this thesis are as follows:1. Based on generic monotone dataflow framework and abstract interpretation, the thesis proposes a value range analysis method. The method propagates the program variable information rapidly and guarantees the correctness of analyzed value range. Based on the value range information, an automatic program flow analysis method is proposed to compute the information such as the minimum and maximum numbers of iterations of loops and the numbers of paths and basic blocks therein, and infeasible paths in loops. Such information lays a solid foundation for accurate WCET analysis.2. Based on program slicing and path-wise test data generation techniques, the dissertation presents a novel method to automatically find program modes and calculate the WCET estimates of programs. As for RISC processors with pipelines and caches, our method can automatically compute the WCET estimate of each mode. As for CISC processors, our method can generate conditional symbolic expressions of WCET estimates.3. By introducing UML design information into WCET analysis, this dissertation presents a solution to solve the unpredictability problems that are caused by the polymorphism of object-oriented programs. By specifying the multiplicity of the association roles and establishing the mappings from association relations to their program implementations, we compute the execution count of a loop structure with polymorphism, and determine the number of objects of each concrete class in a super (virtual) class call site. Thus, we can calculate the WCET estimates of programs written in object-oriented languages with polymorphism characteristics.4. The above methods are implemented in a WCET analysis prototype tool named WCET Analyzer. The tool can automatically calculate the program flow information and program modes written in C/C++. It can also compute the WCET estimates of a module or a whole program on the requests of users.5. By applying WCET analysis technique and WCETAnalyzer, the dissertation proposes a method to calculate the time change caused by the instrumented assertions. Based on the method, time calibration can be carried out.Experimental results showed that the proposed methods increase the precision of the WCET analysis and enable WCET analysis on object-oriented programs. Since these methods can be automated, they have a bright future for industry applications.