在端對端時限下對分散式低負載即時系統排程

Abstract

端對端延遲在分散式即時系統中是最重要的時間限制之一，在有大量節點的無線感測網路或是物聯網的應用中更是如此。在分散式Pinwheel 模型中，已經有利用時距限制來降低端對端延遲的演算法，也證明了可排性的上限，但都是針對滿載的系統做分析。我們發現在低附載的系統中使用貪婪的演算法 (ASr) 更能減少端對端延遲，同時也證明了其可排的條件。我們也分析了執行時間的相對長度對於可排性、端對端的影響。因為其簡單性且能有效地減少端對端延遲，我們認為 ASr 在分散式即時系統中有很大的應用潛力，尤其是在無限感測網路或是物聯網這種低負載的系統更是如此。

End-to-end delay is one of the most important timing constraints in distributed real-time systems (DRTS), especially in the area of wireless sensor network (WSN) or Internet of Things (IoT), which has many nodes in the system. The distributed pinwheel scheduling algorithms have been designed to schedule tasks with distance constraint and end-to-end delay. However, distributed pinwheel scheduling algorithms provide simple scheduling bounds and approaches only for fully utilized tasks. We find there exists a simple feasible algorithm with scheduling bound, and it results in shorter end-to-end delay in many low-utilized cases, compared with distributed pinwheel scheduling algorithms. We also analyze the effect of the relative length of execution times on end-to-end delay, and schedulability. We believe ASr has large potential in shorter end-to-end delay and easier use, especially in low-utilized DRTS, which commonly presents the case of WSN or IoT.