Scheduling Low-Utilized Real-Time Systems with End-to-End Timing Constraints

摘要

End-to-end delay is one of the most important timing constraints in distributed real-time systems (DRTS) [1], especially in the area of wireless sensor network (WSN) or Internet of Things (IoT). Since we may need to collect data from sensor nodes and react immediately. Thus, tasks must be executed in a distance-constrained manner. That is, the temporal distance between any two consecutive executions of a task should always be less than a certain amount of time. In DRTS, transactions are decomposed into a group of tasks, and periodic model might not be efficient enough, since the temporal distance between two consecutive executions of task could be two times of its period in the worst case. Moreover, an execution will not be always ready in a period, which might incur extra end-to-end delay in DRTS. Pinwheel scheduling algorithms have been designed to schedule tasks with distance constraint. But meeting distance constraints in a node does not guarantee minimized end-to-end delay of a transaction. Therefore, DSr, a distributed pinwheel scheduling algorithm, focuses on reducing end-to-end delay systematically and synchronously [2]. Although the pinwheel scheduling algorithms provide simple scheduling bounds and approaches for fully utilized tasks, for the simpler sensor nodes with limited hardware timer support, it might not be easy to execute the pinwheel scheduling algorithms accordingly and guarantee the synchronous results. We find that there exists a simple feasible algorithm (e.g. First In First Out, FIFO) with tight scheduling bound. Although it is always schedulable only in low-utilized systems using FIFO, it results in shorter endto- end delays than DSr in most cases with high utilization. To simplify, we focus only on the system of two nodes with the same utilization. As shown in Figure 1, we simulate the total end-to-end delay with different number of transactions, n, and utilization, ρ, and find that FIFO outperforms DSr. That means transactions can be finished earlier using FIFO. Furthermore, we also find that the relative length of execution time effects the schedulability. As shown in Figure 2, where r stands for the largest ratio of length of execution times, the smaller r, the closer length of execution times, or the lower ρ, as in WSN, outperforms. Therefore, we believe FIFO has large potential in DRTS, especially in low-utilized DRTS, which commonly presents the case of WSN [3] or IoT.