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

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

莊智堯(Chih-Yao Chuang)

指導教授 ： 薛智文

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2016年)

https://doi.org/10.6342/NTU201603152

摘要

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

關鍵字

分散式 ； 即時系統 ； 端對端 ； pinwheel ； FIFO

並列摘要

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.

並列關鍵字

distributed ； real-time system ； end-to-end ； pinwheel ； FIFO

參考文獻

[1] R. Bettati, ”End-to-End Scheduling to Meet Deadlines in Distributed Systems.” PhD dissertation, Technical Report UIUCDCS-R-94-1840, Univ. of Illinois at Urbana-Champaign, Aug. 1994.

[2] de Freitas, Edison Pignaton, et al. ”Mobile agents model and performance analysis of a wireless sensor network target tracking application.” Smart Spaces and Next Generation Wired/Wireless Networking. Springer Berlin Heidelberg, pp.274-286, 2011.

[3] C. L. Liu and J. Layland, ”Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” Journal of the ACM, vol. 10, no. 1, pp.46–61, Jan. 1973.

[4] R. Holte, A. Mok, L.Rosier, I. Tulchinsky, and D. Varvel, ”The Pinwheel: A RealTime Scheduling Problem,” Proc. of the 22nd Hawaii International Conference on System Science, pp.693-702, Jan. 1989.

[5] C.-C. Han and K.-J. Lin, ”Scheduling Distance-Constrained Real-Time Tasks,” Proc. IEEE Real-Time Systems Symp., pp. 300-308, Dec. 1992.