Improving scalability of task allocation and scheduling in large distributed real-time systems using shared buffers

Scheduling precedence-constrained tasks in a distributed real-time system is an NP-hard problem. As a result, the task allocation and scheduling algorithms that use these heuristics do not scale when applied to large distributed systems. In this paper we propose a novel approach that eliminates inter-task dependencies using shared buffers between dependent tasks. The system correctness, with respect to data-dependency, is ensured by having each dependent task poll the shared buffers at a fixed rate. Tasks can, therefore, be allocated and scheduled independently of their predecessors. To meet the timing constraints of the original dependent-task system, we have developed a method to iteratively derive the polling rates based on end-to-end deadline constraints. The overheads associated with the shared buffers and the polling mechanism are minimized by clustering tasks according to their communication and timing constraints. Our simulation results with the task allocation based on a simple first-fit bin packing algorithm showed that the proposed approach scales almost linearly with the system size, and clustering tasks greatly reduces the polling overhead.