Theoretical Modeling Method on Worst-Case Execution Time in Real-Time IC Systems

摘要

A real-time I&C (instrumentation and control) system used in safety systems in nuclear power plants should have predictable and deterministic characteristics. The main issue of a predictable real-time system is to prove whether it satisfies its deadline. The deadline is a fixed time by which a task invocation must have completed its computation, measured relative to its arrival time. One way to prove whether a real-time I&C system satisfies its deadline is a schedulability analysis of the real-time scheduler. The schedulability analysis is to determine whether or not a given set of real-time tasks under a particular scheduling discipline can meet all of its timing constraints. To analyze the schedulability, a worst-case execution time (WCET), which is the upper bound of the execution times for the C program, is required. This paper presents a theoretical modeling method of the WCET. The C program is transformed into assembly instructions through a compiler. Using these assembly instructions corresponding to a C statement, the execution cycles required to execute a C statement can be calculated. Furthermore, the total cycles required to execute the C program can be computed. The work to map a C statement into assembly instructions and define their execution cycles is performed. An abstract syntax tree (AST) is constructed for extracting information to analyze C program. To predict the WCET, nodes of the AST include the elements of the C program and the elements to predict the WCET. As each node of the AST is traversed sequentially, an extended C program to calculate the WCET is generated. By executing the extended C program, the execution time per execution path can be measured. The WCET of the C program based on theoretical model and the WCET of the C program in a real environment is calculated. The deviation between two WCETs is analyzed. Through a deviation analysis, the fact that the WCET, based on theoretical model, is the upper bound of the WCET of the C program in a real environment is shown and used in evaluating the schedulability of a real-time scheduler.