Abstract
Given a multiset of positive integers A = {a1, a2, . . . , an}, the pinwheel problem is to find an infinite sequence over {1, 2, . . . , n} such that there is at least one symbol i within any subsequence of length ai. The density of A is defined as ρ (A) = ∑i=1n(1/ai). In this paper we limit ourselves to instances composed of three distinct integers. The best scheduler [5] published previously can schedule all instances with a density of less than 0.77. A new and fast scheduling scheme based on spectrum partitioning is presented in this paper which improves the 0.77 result to a new 5/6 ≈ 0.83 density threshold. This scheduler has achieved the tight schedulability bound of this problem.
Original language | English |
---|---|
Pages (from-to) | 411-426 |
Number of pages | 16 |
Journal | Algorithmica (New York) |
Volume | 19 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1997 |
Keywords
- Density thresholds
- Pinwheel
- Real-time
- Scheduling
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics