Worst-case timing analysis of concurrently executing dma i/o and programs
Jane W. S. Liu, Taiyi Huang · 1997
A hard-real-time system is required to process tasks with timing constraints that must be met to ensure the safety and correctness of the system. The analysis which determines the ability of a particular system to meet its timing constraints requires that the worst-case execution time (WCET) of each task be known in advance. The dynamic architectural features such as cache memory and instruction pipeline introduce variations in program execution times. The interference of concurrently executing cycle-stealing DMA I/O operations further complicates the problem of determining the WCET of a program. This dissertation presents methods for bounding the worst-case interference between an executing program and a cycle-stealing DMA I/O operation. We first develop a method for bounding the WCET of a program executing concurrently with cycle-stealing DMA I/O. Our method converts the problem of bounding the WCET to one of solving a integer linear programming problem. We implement our method in a timing tool and conduct extensive experiments with the timing tool to demonstrate the merits of our method. A cycle-stealing DMA I/O task is allowed to proceed only when the CPU does not need the system bus. As a result, the execution time of a cycle-stealing DMA I/O task is affected by a set of CPU tasks which execute concurrently with the I/O task. We discuss the problem of bounding the WCET of a cycle-stealing DMA I/O task under a workload which consists of a set of independent CPU tasks. Each CPU task has an arbitrary release time. We use the dynamic programming technique to bound the WCET of the I/O task.