Busy-idle profiles and compact task graphs: compile-time support for interleaved and overlapped scheduling of real-time tasks

A new task graph representation, namely the compact task graph (CTG) is developed to aid in the scheduling of a set of communicating periodic real-time tasks. This representation exposes the potential for parallelism across tasks as well as the idle times that may be encountered within a task. Therefore using a CTG a real-time scheduler can generate schedules that are able to meet deadlines by interleaving the execution of tasks on a single processor and/or overlapping the execution of tasks on multiple processors. The construction of a CTG is based upon the busy-idle execution profiles for the tasks generated by the compiler. The profiles are computed assuming that sufficient resources are available for parallel execution of all tasks. Thus, they expose all opportunities for overlapped and interleaved execution. The compiler analyzes the profiles to identify useful opportunities for interleaving and expresses them in the CTG without explicitly partitioning the tasks. The CTG is powerful because it expresses schedules that are not expressed by existing approaches for constructing task graphs. Schedules can be generated efficiently since a CTG´s construction does not require the splitting of tasks. We also demonstrate the usefulness of our techniques by developing an approach for non-intrusive monitoring of real-time tasks