Predicting the Worst-Case Execution Time of the Concurrent Execution of Instructions and Cycle-Stealing DMA I/O Operations.
Taiyi Huang, Jane W. S. Liu · 1995
This paper describes an efficient algorithm which gives a bound on the worst-case execution times of the concurrent execution of CPU instructions and cycle-stealing DMA I/O operations. Simulations of several programs were conducted to evaluate this algorithm. Compared with the traditional pessimistic approach, the bound on the worst-case execution time produced by the algorithm is significantly tighter. For a sample program that multiplies two matrices while the I/O bus is fully utilized, our algorithm achieves a 39% improvement in the accuracy of the prediction. 1 Introduction Algorithms for scheduling tasks in hard-real-time systems typically assume that their worst-case execution times are known. Such a system is deigned to ensure that all tasks can complete by their deadlines as long as no task in a system executes longer than its worst-case execution time (WCET). A task which overruns may lead to missed deadlines and the failure of the whole system. For this reason, how to bound ...