Improved response-time analysis calculations

Abstract

Schedulability analysis of fixed priority preemptive scheduled systems can be performed by calculating the worst-case response-time of the involved processes. The system is deemed schedulable if the calculated response-time for each process is less than its corresponding deadline. It is desirable that the Response-Time Analysis (RTA) can be efficiently performed. This is particularly important in dynamic real-time systems when a fast response is needed to decide whether a new job can be accommodated, or when the RTA is extensively applied, e.g., when used to guide the heuristics in a higher level optimiser. This paper presents a set of methods to improve the efficiency of RTA calculations. The methods are proved correct, in the sense that they give the same results as traditional (non-improved) RTA. We also present an evaluation of the improvements, by applying them to the particularly time-consuming traffic model used in RTA for ATM communication networks. Our evaluation shows that the proposed methods can give an order of magnitude reduction of the execution time of RTA.