ISSN:
1432-0541
Keywords:
Pinwheel
;
Scheduling
;
Real-time
;
Satellite communication
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract The pinwheel is a hard-real-time scheduling problem for scheduling satellite ground stations to service a number of satellites without data loss. Given a multiset of positive integers (instance)A={a1,..., an}, the problem is to find an infinite sequence (schedule) of symbols from {1,2,...,n} such that there is at least one symboli within any interval of ai symbols (slots). Not all instancesA can be scheduled; for example, no “successful” schedule exists for instances whose density,ρ(A)=∑ i i (l/ai), is larger than 1. It has been shown that all instances whose densities are less than a 0.5 density threshold can always be scheduled. If a schedule exists, another concern is the design of a fast on-line scheduler (FOLS) which can generate each symbol of the schedule in constant time. Based on the idea of “integer reduction,” two new FOLSs which can schedule different classes of pinwheel instances, are proposed in this paper. One uses “single-integer reduction” and the other uses “double-integer” reduction. They both improve the previous 0.5 result and have density thresholds of 13/20 and2/3, respectively. In particular, if the elements inA are large, the density thresholds will asymptotically approach In 2 and 1/R2, respectively.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01187034
Permalink
