A hybrid approach for derivation of tight execution time bounds of program-segments and service time bounds of simple object methods in real-time distributed computing systems.

摘要

Improved techniques for deriving tight execution time bounds of program-segments in real-time distributed computing applications have been introduced in this dissertation. A direction for developing hybrid approaches that combine analytical derivation and statistical derivation in a symbiotic form was suggested in recent years by Kane Kim at UCI. The proposed techniques are meant to be the first concrete step forward in realizing such a hybrid approach in a form that can be of practical help to real-time distributed computing software developers. Instead of establishing accurate timing models for modern microprocessors, which is very time-consuming and error-prone, execution times of program-segments will be measured directly on a target platform in a sequence of steps aimed for deriving tight execution time bounds. To avoid exhaustive searches and to maximize the chances that a limited number of test-runs cover the worst-case execution scenario, acyclic path enumeration technique, which is an extension of the conventional implicit path enumeration technique to accommodate partial execution history into the worst-case execution time analysis, has been introduced. A code translation technique has been proposed to obtain a measured execution time bound of a specific path without generating or identifying input data sets belonging to the specified path. A curve fitting algorithm has been used to give application designers a guideline for determining execution time bounds of the program-segments based on the results obtained through the measurement. Also, a procedure for combining tight service time bounds of software modules has been adopted.; Once the execution time bounds of program-segments and service time bounds of OS activities are available, it is possible that candidates of the worst-case execution path of a given service can be found by applying the proposed techniques for deriving tight execution time bounds of program-segments. Then, the service time of identified paths will, again, be measured on a target platform directly for deriving tighter service time bounds. Such procedures can be iteratively applied to higher services that consist of multiple sub-services for deriving tighter service time bounds. The case study demonstrates how proposed technique can derive service time bounds of the real-world applications. (Abstract shortened by UMI.)