SCHEDULERS FOR LARGER CLASSES OF PINWHEEL INSTANCES

The pinwheel is a hard-real-time scheduling problem for scheduling sat ellite ground stations to service a number of satellites without data loss. Given a multiset of positive integers (instance) A = (a1, ..., a (n)), the problem is to find an infinite sequence (schedule) of symbol s from {1, 2, ..., n) such that there is at least one symbol i within any interval of a(i) symbols (slots). Not all instances A can be sched uled; for example, no ''successful'' schedule exists for instances who se density, rho(A) = SIGMA(i = 1)n(1/a(i), is larger than 1. It has be en shown that all instances whose densities are less than a 0.5 densit y threshold can always be scheduled. If a schedule exists, another con cern is the design of a fast on-line scheduler (FOLS) which can genera te each symbol of the schedule in constant time. Based on. the idea of ''integer reduction,'' two new FOLSs which can schedule different cla sses of pinwheel instances, are proposed in this paper. One uses ''sin gle-integer reduction'' and the other uses ''double-integer'' reductio n. They both improve the previous 0.5 result and have density threshol ds of 13/20 and 2/3 respectively. In particular, if the elements in A are large, the density thresholds will asymptotically approach ln 2 an d 1/square-root 2, respectively.