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. This paper proposes 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.