Research On Mixed Estimation Of Worst-case Execution Time

With more widely use of software in safety-critical systems and increasing scale of the application, software undertake a very important role in aerospace, power systems, traffic management, nuclear power plant and so on. For the safety-critical systems, timeliness is critical. Once time of the task execution exceeds a predetermined time, the consequences would be disastrous. System operation time is affected by many factors, such as the execution environment, CPU performance, program flow. These factors make specific execution time of the program is difficult to fetch. The worst-case execution time(WCET) means the maximum of all possible execution time of a program. Therefore, the accuracy of WCET analysis determines the performance of safety-critical embedded systems. In addition, with the increasing complexity of software, how to accurately and effectively get the worst-case execution time of program has also become a problem. Therefore, safety-critical systems WCET analysis becomes an urgent problem.WCET estimation method can be divided into static analysis and dynamic analysis. Dynamic approach need the program be executed dynamically after the hardware system set up and measure time of program finish the expected task, or use the simulator simulate and estimated WCET. Static method base on processor feature, statically estimates execution time of all instructions in program by program analyzing. Dynamic methods rely on running or simulated entirely, and lack of path analysis of actual implementation of the program. So dynamic methods cannot guarantee all the paths of program be through when the program executing. the implementation of the program through the process. Static methods analyzed the characteristics of the processor, but when dealing with complex logic programs, the estimate of WCET will be too large, and loss worth of the estimate.Aiming at these problems, on the basis of the existing research methods, this paper adopt the way static analysis dynamic with instrumentation to analyze WCET of program. First, use instrumentation technology to obtain loop bound information dynamically. Then, analyze compiled binary file from target program, fetch instructions of program, establish mapping between instructions and source, and divide the basic blocks. After control flow graph established, according to the mapping between instructions and source, number of executions of basic block will be determined. Then, finishing control flow analysis in the control flow graph. According to the constraint relationship between the points and edges, build a linear function and constraints. Use integer linear programming method to determine the worst execution time.Finally, design and implement the WCET estimation system, and do some test for the system. The system provides a supporting role for the real-time systems analyst analysis program. To some extent, this system could improve the efficiency of analysis, and has important theoretical significance and application value.