Scheduling Low-Utilized Real-Time Systems with End-to-End Timing Constraints
Scheduling Low-Utilized Real-Time Systems with End-to-End Timing Constraints
复制标题
具有端到端时序约束的低利用率实时系统的调度
DOI：
10.1109/rtcsa.2016.53
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Chih
中科院分区：
文献类型：
--
作者：
Chih;Yung;Chih
端到端时延是分布式实时系统（DRTS）中最重要的时序约束之一，特别是在无线传感器网络（WSN）或物联网（IoT）领域。因为我们可能需要从传感器节点收集数据并立即做出反应。因此，任务必须以距离受限的方式执行。也就是说，任何两个连续执行任务之间的时间间隔应该始终小于一定的时间。在DRTS中，事务被分解为一组任务，周期模型可能不够有效，因为在最坏的情况下，两次连续执行任务之间的时间距离可能是其周期的两倍。此外，执行并不总是在一段时间内准备好，这可能会在DRTS中导致额外的端到端延迟。风车调度算法被设计用于有距离约束的任务调度。但是满足节点中的距离限制并不能保证最小化事务的端到端延迟。因此，DSr是一种分布式风车调度算法，其重点是系统地、同步地减少端到端延迟。虽然风车调度算法为充分利用的任务提供了简单的调度界限和方法，但对于硬件定时器支持有限的较简单的传感器节点，可能不容易相应地执行风车调度算法并保证同步结果。我们发现存在一种简单可行的算法（如先进先出，FIFO），具有紧密的调度边界。虽然它总是可调度的，只有在低利用率的系统中使用先进先出，但在大多数高利用率的情况下，它比DSr产生更短的端到端延迟。为了简化，我们只关注具有相同利用率的两个节点的系统。如图1所示，我们模拟了具有不同事务数n和利用率ρ的总端到端延迟，发现FIFO优于DSr。这意味着使用FIFO可以更早地完成事务。此外，我们还发现相对执行时间的长度会影响可调度性。如图2所示，其中r表示执行时间长度的最大比率，r越小，执行时间长度越接近，或者ρ越低，如在WSN中，表现越好。因此，我们认为FIFO在DRTS中具有很大的潜力，特别是在低利用率的DRTS中，通常出现在WSN[3]或IoT的情况下。
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.