Combined task and message scheduling in distributed real-time systems

This paper presents an algorithm for off-line scheduling of communicating t asks with precedence and exclusion constraints in distributed hard real-tim e systems. Tasks are assumed to communicate via message passing based on a time-bounded communication paradigm, such as the real-time channel [1]. The algorithm uses a branch-and-bound (B&B) technique to search for a task sch edule by minimizing maximum task lateness (defined as the difference betwee n task completion time and task deadline), and exploits the interplay betwe en task and message scheduling to improve the quality of solution. It gener ates a complete schedule at each vertex in the search tree, and can be made to yield a feasible schedule (found before reaching an optimal solution), or proceed until an optimal task schedule is found. We have conducted an ex tensive simulation study to evaluate the performance of the proposed algori thm. The algorithm is shown to scale well with respect to system size and d egree of intertask interactions. It also offers good performance for worklo ads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is fa ster but has no optimality properties. We have also extended the algorithm to a more general resource-constraint model, thus widening its application domain.