Propagation Delays in Fixed-Priority Scheduling of Periodic Tasks

In many multi-rate periodic control systems, information flows from control modules driven at lower rates to modules driven at higher rates (i.e., from lower-priority tasks to higher-priority tasks when rate monotonic scheduling is used). If such information flow occurs in the system, unexpectedly long delays in information propagation (longer than the sum of the periods) may be observed. This could cause a serious problem because the system cannot start responding to the change in the input until more than this delay has elapsed. This paper analyzes the information propagation delay for multi-rate periodic control systems in which periods are harmonically related (i.e., are multiples of all smaller periods). We show that, although the information propagation delay may be arbitrarily longer than the longest period, if the information flows from lower-priority tasks to progressively higher-priority tasks, the delay is always less than three times the longest period in the sequence. Furthermore, if the processor utilization is small, we show that the upper bound on the delay can drop to below twice the longest period. We show that these bounds are tight.