|
Abstract : |
This paper presents an algorithm for off-line scheduling of communicating tasks with precedence and exclusion constraints in distributed hard real-time 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 an optimal task schedule by minimizing maximum task lateness (defined as the difference between task completion time and task deadline), and exploits the interplay between task and message scheduling to improve the quality of solution. It has the property of generating a complete schedule at each vertex in the search tree, and can be made to yield a feasible solution (found before reaching an optimal solution), or proceed until an optimal solution is found. We have conducted an extensive simulation study evaluating the performance of the proposed algorithm. The algorithm is shown to scale well with respect to system size, and degree of intertask interactions. It also offers good performance for workloads with a wide range of CPU utilizations and application concurrency. For larger systems and higher loads, we introduce a greedy heuristic that is faster but does not guarantee optimality. We have also extended the algorithm to a more general resource-constraint model thus widening its application domain. Key Words--- Real-time scheduling, combined task and message scheduling, distributed hard real-time systems, resource constraints, deadlock., |
