Improved scheduling of generalized pinwheel task systems

Sanjoy K. Baruah, Shun Shii Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the International Workshop on Real-Time Computing Systems and Applications/RTCSA
Editors Anon
PublisherIEEE
Pages73-79
Number of pages7
Publication statusPublished - 1997
Externally publishedYes
EventProceedings of the 1997 4th International Workshop on Real-Time Computing Systems and Applications, RTCSA - Taipei, Taiwan
Duration: 1997 Oct 271997 Oct 29

Other

OtherProceedings of the 1997 4th International Workshop on Real-Time Computing Systems and Applications, RTCSA
CityTaipei, Taiwan
Period97/10/2797/10/29

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improved scheduling of generalized pinwheel task systems'. Together they form a unique fingerprint.

  • Cite this

    Baruah, S. K., & Lin, S. S. (1997). Improved scheduling of generalized pinwheel task systems. In Anon (Ed.), Proceedings of the International Workshop on Real-Time Computing Systems and Applications/RTCSA (pp. 73-79). IEEE.