https://scholars.lib.ntu.edu.tw/handle/123456789/323645
標題: | A faster exact schedulability analysis for fixed-priority scheduling | 作者: | Hsieh, Jen-Wei Shih, Wei-Kuan TEI-WEI KUO WAN-CHEN LU |
關鍵字: | Fixed-priority preemptive scheduling; Periodic tasks; Real-time systems; Schedulability analysis | 公開日期: | 2006 | 卷: | 79 | 期: | 12 | 起(迄)頁: | 1744-1753 | 來源出版物: | Journal of Systems and Software | 摘要: | Real-time scheduling for task sets has been studied, and the corresponding schedulability analysis has been developed. Due to the considerable overheads required to precisely analyze the schedulability of a task set (referred to as exact schedulability analysis), the trade-off between precision and efficiency is widely studied. Many efficient but imprecise (i.e., sufficient but not necessary) analyses are discussed in the literature. However, how to precisely and efficiently analyze the schedulability of task sets remains an important issue. The Audsley's Algorithm was shown to be effective in exact schedulability analysis for task sets under rate-monotonic scheduling (one of the optimal fixed-priority scheduling algorithms). This paper focuses on reducing the runtime overhead of the Audsley's Algorithm. By properly partitioning a task set into two subsets and differently treating these two subsets during each iteration, the number of iterations required for analyzing the schedulability of the task set can be significantly reduced. The capability of the proposed algorithm was evaluated and compared to related works, which revealed up to a 55.5% saving in the runtime overhead for the Audsley's Algorithm when the system was under a heavy load. © 2006 Elsevier Inc. All rights reserved. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-33750942274&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/323645 |
ISSN: | 01641212 | DOI: | 10.1016/j.jss.2006.03.023 | SDG/關鍵字: | Algorithms; Iterative methods; Scheduling; Set theory; Fixed-priority preemptive scheduling; Schedulability analysis; Real time systems |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。