https://scholars.lib.ntu.edu.tw/handle/123456789/303038
標題: | Utilization bound revisited | 作者: | Chen, Deji Mok, A.K. TEI-WEI KUO |
關鍵字: | Preemptive fixed-priority scheduling; Rate-monotonic priority assignment; Utilization bound | 公開日期: | 2003 | 卷: | 52 | 期: | 3 | 起(迄)頁: | 351-361 | 來源出版物: | IEEE Transactions on Computers | 摘要: | Utilization bound is a well-known concept introduced in the seminal paper of Liu and Layland, which provides a simple and practical way to test the schedulability of a real-time task set. The original utilization bound for the fixed-priority scheduler was given as a function of the number of tasks In the periodic task set. In this paper, we define the utilization bound as a function of the information about the task set. By making use of more than just the number of tasks, better utilization bound over the Liu and Layland bound can be achieved. We investigate in particular the bound given a set of periods for which it is still unknown if there is a polynomial algorithm for the exact bound. By investigating the relationships among the periods, we derive algorithms that yield better bounds than the Liu and Layland bound and the harmonic chain bound. Randomly generated task sets are tested against different bound algorithms. We also give a more intuitive proof of the harmonic chain bound and derive a computationally simpler algorithm. |
URI: | http://www.scopus.com/inward/record.url?eid=2-s2.0-0037341770&partnerID=MN8TOARS http://scholars.lib.ntu.edu.tw/handle/123456789/303038 |
ISSN: | 00189340 | DOI: | 10.1109/TC.2003.1183949 | SDG/關鍵字: | Algorithms; Boundary conditions; Computational complexity; Harmonic analysis; Scheduling; Rate monotonic analysis (RMA); Real time systems |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。