Implementation of algorithms for computing information propagation delays through sequences of fixed-priority periodic tasks

Abstract

Nowadays, there is a rapid increase in the complexity of large automotive and control systems because of the integration of external software modules in them. Many of these systems are based on sampled-data control theory. And because of the different timing constraints of individual modules, each module has a different sampling rate. Typically, these systems operate with periodic task sequences and the information flows between the tasks. Generally the information propagates from tasks operating at one period to tasks operating at different periods. When this happens, unusually long information propagation delays can occur which can be disastrous because the system cannot respond to the changes until this delay has been elapsed. Although for arbitrary set of task sets the delays can be very long, Howell and Mizuno (2010) considers a set of task sequences with special constraints and some very useful bounds are derived for the worst case occurrences of them. Howell and Mizuno (2011) has laid out algorithms that compute the delays for certain special cases of task sequences considered in Howell and Mizuno (2010). The purpose of this project is to understand and implement the algorithms from Howell and Mizuno (2011). The implementation is done so that it avoids the manual computation of the delays and helps in better understanding the ideas presented in Howell and Mizuno (2011). The application can be tested against any valid input that meets our assumptions, and it constructs a schedule that exhibits the worst case behavior and from the schedule it computes the worst case information propagation delays.