## 摘要

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.

原文 | 英語 |
---|---|

頁面 | 73-79 |

頁數 | 7 |

出版狀態 | 已發佈 - 1997 |

對外發佈 | 是 |

事件 | Proceedings of the 1997 4th International Workshop on Real-Time Computing Systems and Applications, RTCSA - Taipei, Taiwan 持續時間: 1997 10月 27 → 1997 10月 29 |

### 其他

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

城市 | Taipei, Taiwan |

期間 | 1997/10/27 → 1997/10/29 |

## ASJC Scopus subject areas

- 一般電腦科學