## Abstract

The generalized pinwheel scheduling problem is defined as follows: Given a multiset {(a_{1}, b_{1}), (a_{2}, b_{2}), ..., (a_{n}, b_{n})} 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 b_{i} consecutive symbols contains at least a_{i} i's. Such an infinite sequence is called a schedule for the generalized pinwheel task system {(a_{1}, b_{1}), (a_{2}, b_{2}), ..., (a_{n}, b_{n})}. When all the a_{i}'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 language | English |
---|---|

Pages | 73-79 |

Number of pages | 7 |

Publication status | Published - 1997 |

Externally published | Yes |

Event | Proceedings of the 1997 4th International Workshop on Real-Time Computing Systems and Applications, RTCSA - Taipei, Taiwan Duration: 1997 Oct 27 → 1997 Oct 29 |

### Other

Other | Proceedings of the 1997 4th International Workshop on Real-Time Computing Systems and Applications, RTCSA |
---|---|

City | Taipei, Taiwan |

Period | 1997/10/27 → 1997/10/29 |

## ASJC Scopus subject areas

- Computer Science(all)