General schedulers for the pinwheel problem based on double-integer reduction

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 symbol i within any interval of ai symbols (slots). Not all instances A can be scheduled; for example, no 'successful' schedule exists for instances whose density is larger than 1. It has been shown that any instance whose density is less than 2/3 can always be scheduled. Two new schedulers are proposed which improve this 2/3 result to a new 0.7 density threshold. These two schedulers can be viewed as a generalization of the previously known schedulers, i.e., they can handle a larger class of pinwheel instances including all instances schedulable by the previously known techniques.