Improved scheduling of generalized pinwheel task systems

Sanjoy K. Baruah*, Shun Shii Lin

*此作品的通信作者

研究成果: 書貢獻/報告類型會議論文篇章

10 引文 斯高帕斯(Scopus)

摘要

The generalized pinwheel scheduling problem is defined as follows: Given a multiset {(a1, b1), (a2, b2), ..., (an, bn)} of ordered pairs of positive integers, determine whether there is an infinite sequence over the symbols {1, 2, 3, ..., n} such that, for each i, 1≤i≤n, any subsequence of bi consecutive symbols contains at least ai i's. Such an infinite sequence is called a schedule for the generalized pinwheel task system {(a1, b1), (a2, b2), ..., (an, bn)}. When all the ai's are equal to one, this problem has been previously studied as the pinwheel scheduling problem. A linear-time algorithm is presented for solving such instances which determines whether such an instance has a schedule. A fast on-line scheduler (FOLS) is also derived, which can actually generate the schedule in O(log n) time per slot given O(n) preprocessing time. When compared to traditional pinwheel scheduling algorithms, this new algorithm has a higher density threshold on a very large subclass of generalized pinwheel task systems.

原文英語
主出版物標題Proceedings of the International Workshop on Real-Time Computing Systems and Applications/RTCSA
編輯 Anon
發行者IEEE
頁面73-79
頁數7
出版狀態已發佈 - 1997
對外發佈
事件Proceedings of the 1997 4th International Workshop on Real-Time Computing Systems and Applications, RTCSA - Taipei, Taiwan
持續時間: 1997 十月 271997 十月 29

其他

其他Proceedings of the 1997 4th International Workshop on Real-Time Computing Systems and Applications, RTCSA
城市Taipei, Taiwan
期間1997/10/271997/10/29

ASJC Scopus subject areas

  • 電腦科學(全部)

指紋

深入研究「Improved scheduling of generalized pinwheel task systems」主題。共同形成了獨特的指紋。

引用此