Research On WCET Of Real-Time Software Based On Abstract Interpretation

Correctness of real-time systems, in contrast to other applications, not only depends on the correctness of the output, but also the time required to produce the result. The output of the real-time system is available before deadline, so that it's important for scheduling of the real-time system to get the worst case execution time of the task ahead.WCET analysis requires safe and as tight as possible. As the dynamic meausurement method of WCET can not guarantee that WCET estimation is safe, static analysis is the common method for obtaining WCET value. The method of static analysis contain: gain the flow information of the program,model the charater of processor and compute the worst case estimation time. This paper provides a WCET analysis method based on extension of abstract interpretation theory.In the program flow analysis,this paper proposes a method based on abstract execution and common data flow monotone framework to analysis the program value range. This method can calculate the bound of the loop;identify the infeasible path and other information about program flow.the theory based on abstract interpretation is approximate representation of the program semantics, so this method can guarantee the correctness and automatically calculate iformation of programs used for WCET analysis without annotation.In the paper, we divide the low-level analysis into tow stages:global low-level analysis and local low-level analysis. Global low-level analysis is used to construct abstact cache model, abstract the mapping of the cache and memory, then analyze cache hit or cache miss, in the cache analysis,we use must analysis and may analsis in abstract domain to get the cache information. Based on the result of global low-level analysis, local low-level analysis run on the hardware model in simulation, then construct the timing model of WCET analysis.Reference to the WCET method given above, we proposes WCET analysis tool model based on ARM9 processor. Recording to the experiment,using the WCET to analysis,we can get the WCET analysis value.