請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48983完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 薛智文(Chih-Wen Hsueh) | |
| dc.contributor.author | Chih-Yao Chuang | en |
| dc.contributor.author | 莊智堯 | zh_TW |
| dc.date.accessioned | 2021-06-15T11:12:58Z | - |
| dc.date.available | 2016-10-26 | |
| dc.date.copyright | 2016-10-26 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-08-21 | |
| dc.identifier.citation | [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. [6] C.-W. Hsueh and K.-J. Lin, ”Scheduling Real-Time Systems with End-to-End Timing Constraints Using the Distributed Pinwheel Model,” IEEE Trans. Comput., vol. 50, no. 1, pp. 51–66, Jan. 2001. [7] A. Zanella, N. Bui, A. Castellani, and L. Vangelista, ”Internet of Things for smart cities”, IEEE Internet Things J., vol. 1, no. 1, pp. 22–32, Feb. 2014. [8] Feng Zhao and Leonidas Guibas, ”Wireless sensor networks”, Morgan Kaufmann Publishers, 2004. [9] S. Hong, R. Gerber, and M. Saksena, ”Guaranteeing End-to-End Timing Constraints by Calibrating Intermediate Processes”, Proc. IEEE Real-Time Systems Symp., pp. 192-203, Dec. 1994. [10] L. Sha and S.S. Sathaye, ”A Systematic Approach to Designing Distributed Real-Time Systems”, Computer, vol. 26, no. 9, pp. 68- 78, Sept. 1993. [11] J. Sun, R. Bettati, and J.W.-S. Liu, ”An End-to-End Approach to Schedule Tasks with Shared Resources in Multiprocessor Systems”, Proc. 11th IEEE Workshop Real-Time Operating Systems and Software, May 1994. [12] H. Leontyev and J. Anderson. ”Tardiness bounds for FIFO scheduling on multiprocessors”. In Proceedings of the 19th Euromicro Conference on Real-Time Systems, pp. 71- 80, July 2007. [13] L. George and P. Minet. ”A FIFO worst case analysis for a hard real-time distributed problem with consistency constraints”. In Proc. of the 17th International Conference on Distributed Computing Systems, pages 441–448, May 1997. [14] N. C. Audsley, ”Optimal priority assignement and Feasibility of static priority tasks with arbitrary start times”, Dept. Comp. Science Report YCS 164, University of York, 1991. [15] C. Hsueh , K.-J. Lin and N. Fan, ”Distributed pinwheel scheduling with end-to-end timing constraints”, Proc. IEEE Real-Time Systems Symposium, pp. 172-181, 1995 [16] Y.-C. Lee and C.-W. Hsueh, ”An Efficient Scheduling Mechanism for Building Energy Management Systems,” IEEE International Conference on Building Efficiency and Sustainable Technologies, Sep. 2015. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48983 | - |
| dc.description.abstract | 端對端延遲在分散式即時系統中是最重要的時間限制之一，在有大量節點的無線感測網路或是物聯網的應用中更是如此。在分散式Pinwheel 模型中，已經有利用時距限制來降低端對端延遲的演算法，也證明了可排性的上限，但都是針對滿載的系統做分析。我們發現在低附載的系統中使用貪婪的演算法 (ASr) 更能減少端對端延遲，同時也證明了其可排的條件。我們也分析了執行時間的相對長度對於可排性、端對端的影響。因為其簡單性且能有效地減少端對端延遲，我們認為 ASr 在分散式即時系統中有很大的應用潛力，尤其是在無限感測網路或是物聯網這種低負載的系統更是如此。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T11:12:58Z (GMT). No. of bitstreams: 1 ntu-105-R03944005-1.pdf: 519121 bytes, checksum: e02d8925eee8c35d00927f429e304752 (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | Contents 口試委員會審定書 ii 摘要 iii Abstract iv 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Related Works 6 2.1 Scheduler RMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Scheduler FIFO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Scheduler FIFO/DM . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Distance-Constrained Task System . . . . . . . . . . . . . . . . . . . 8 2.5 WSN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.6 End-to-end Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.7 Pinwheel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.8 Scheduler Sr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.9 Scheduler DSr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Analysis 15 3.1 Analysis of DSr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 The Inefficiency of DSr in Simple Cases . . . . . . . . . . . . . . . . . 16 3.3 Scheduler ASr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 Analysis of ASr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.5 Method of Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4 Experiments 22 4.1 Schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 End-To-End Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Analyze the Relative Length of Execution Times . . . . . . . . . . . 26 4.3.1 Schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.3.2 End-To-End Delay . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3.3 Relative Distance of Consecutive Executions . . . . . . . . . . 30 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5 Conclusions 35 6 Future Works 36 Bibliography 37 Appendix 39 A.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 | |
| dc.language.iso | en | |
| dc.subject | 即時系統 | zh_TW |
| dc.subject | 分散式 | zh_TW |
| dc.subject | pinwheel | zh_TW |
| dc.subject | 端對端 | zh_TW |
| dc.subject | FIFO | zh_TW |
| dc.subject | end-to-end | en |
| dc.subject | FIFO | en |
| dc.subject | pinwheel | en |
| dc.subject | real-time system | en |
| dc.subject | distributed | en |
| dc.title | 在端對端時限下對分散式低負載即時系統排程 | zh_TW |
| dc.title | Scheduling Low-Utilized Distributed Real-Time Systems with End-to-End Timing Constraints | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳敬(Jing Chen),蔡孟峰(Meng-Feng Tsai),徐讚昇(Tsan-sheng Hsu) | |
| dc.subject.keyword | 分散式,即時系統,端對端,pinwheel,FIFO, | zh_TW |
| dc.subject.keyword | distributed,real-time system,end-to-end,pinwheel,FIFO, | en |
| dc.relation.page | 40 | |
| dc.identifier.doi | 10.6342/NTU201603152 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-08-22 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
| 顯示於系所單位： | 資訊網路與多媒體研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf 未授權公開取用 | 506.95 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。