Chain-Based Fixed-Priority Scheduling of Loosely-Dependent Tasks

Many cyber-physical applications consist of chains of tasks. Such tasks are often loosely dependent, meaning task execution is time-triggered and independent of the update rate of input data. Since meaningful output can be obtained after processing all the intermediate tasks of a chain, the end-to-end latency of the chain is an important metric that can affect the correctness and quality of the system. In this paper, we present a chain-based fixed-priority preemptive scheduler for multicore real-time systems. The scheduler identifies effective chain instances contributing to the generation of updated output, and employs a runtime policy to improve the end-to-end latency of chains. Based on our scheduler, an analysis method is proposed with two parts: (i) bounding the start and finish time of each job, and (ii) analyzing the end-to-end latency of effective chain instances. Experimental results show that our chain-based scheduler achieves up to 83% reduction in end-to-end latency compared to the state-of-the-art and yields a significant benefit in inter-chain distance over chain-unaware schedulers. Furthermore, our analysis method can be easily adapted to chain-unaware schedulers and provides tighter bounds than prior work.