In mathematics and computer science, the pinwheel scheduling problem is a problem in real-time scheduling with repeating tasks of unit length and hard constraints on the time between repetitions.

Definition

The input to pinwheel scheduling consists of a list of tasks, each of which is assumed to take unit time per instantiation. Each task has an associated positive integer value, its minimum repeat time (the minimum time from the start of one instantiation of the task to the next). Only one task can be performed at any given time. The desired output is an infinite sequence specifying which task to perform in each unit of time. Each input task should appear infinitely often in the sequence, with the largest gap between two consecutive instantiations of a task at most equal to the repeat time of the task. For example, the infinitely repeating sequence ''...'' would be a valid pinwheel schedule for three tasks ''a'', ''b'', and ''c'' with repeat times that are at least 2, 4, and 4 respectively.

Density

If the task to be scheduled are numbered from

1

n

, let

t_i

denote the repeat time for task

i

. Then the ''density'' of a pinwheel scheduling problem is

\textstyle\sum 1/t_i

. For a solution to exist, it is necessary that the density is at most

1

. This condition on density is also sufficient for a schedule to exist in the special case that all repeat times are multiples of each other (for instance, if all are

powers of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent. In a context where only integers are considered, is restricted to non-negative ...

), because in this case one can solve the problem using a disjoint covering system. Having density at most

1

is also sufficient when there are exactly two distinct repeat times. However, it is not sufficient in other cases. In particular, there is no schedule for three items with repeat times

t_1=2

t_2=3

, and

t_3

, no matter how large

t_3

may be, even though the density of this system is only

5/6 + 1/t_3

. Every instance of pinwheel scheduling with density at most

3/4

has a solution, and it has been conjectured that every instance with density at most

5/6

has a solution. Every instance with three distinct repeat times and density at most

5/6

does have a solution.

Periodicity and complexity

When there exists a solution, the solution can be assumed to be periodic, with a period at most equal to the product of the repeat times. However, it is not always possible to find a repeating schedule of sub-exponential length. With a compact input representation that specifies, for each distinct repeat time, the number of objects that have that repeat time, pinwheel scheduling is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

Applications

Applications of pinwheel scheduling include scheduling communications between satellites and a ground station, scheduling maintenance of a collection of objects (such as oil changes for automobiles), computer processing of multimedia data, and contention resolution in real-time wireless computer networks.

References

{{reflist, refs= {{citation , last1 = Chan , first1 = M. Y. , last2 = Chin , first2 = Francis , doi = 10.1007/BF01187034 , issue = 5 , journal = Algorithmica , mr = 1212158 , pages = 425–462 , title = Schedulers for larger classes of pinwheel instances , volume = 9 , year = 1993, s2cid = 6069661 {{citation , last1 = Fishburn , first1 = P. C. , author1-link = Peter C. Fishburn , last2 = Lagarias , first2 = J. C. , author2-link = Jeffrey Lagarias , doi = 10.1007/s00453-002-0938-9 , issue = 1 , journal = Algorithmica , mr = 1912925 , pages = 14–38 , title = Pinwheel scheduling: achievable densities , volume = 34 , year = 2002, s2cid = 25561199 {{citation , last1 = Holte , first1 = Robert , last2 = Mok , first2 = Al , last3 = Rosier , first3 = Louis , last4 = Tulchinsky , first4 = Igor , last5 = Varvel , first5 = Donald , contribution = The pinwheel: a real-time scheduling problem , doi = 10.1109/hicss.1989.48075 , pages = 693–702 , publisher = IEEE Computer Society Press , title = Proceedings of the Twenty-Second Annual Hawaii International Conference on System Sciences, Volume II: Software Track , year = 1989, s2cid = 62617897 {{citation , last1 = Holte , first1 = Robert , last2 = Rosier , first2 = Louis , last3 = Tulchinsky , first3 = Igor , last4 = Varvel , first4 = Donald , doi = 10.1016/0304-3975(92)90365-M , issue = 1 , journal = Theoretical Computer Science , mr = 1171436 , pages = 105–135 , title = Pinwheel scheduling with two distinct numbers , volume = 100 , year = 1992, doi-access = . Previously announced at MFCS 1989. {{citation , last1 = Lin , first1 = Shun-Shii , last2 = Lin , first2 = Kwei-Jay , doi = 10.1007/PL00009181 , issue = 4 , journal = Algorithmica , mr = 1470043 , pages = 411–426 , title = A pinwheel scheduler for three distinct numbers with a tight schedulability bound , volume = 19 , year = 1997, s2cid = 22001959 {{citation , last1 = Wu , first1 = Jean-Lien C. , last2 = Shin , first2 = Haw-Yun , last3 = Wu , first3 = Yi-Hsien , date = June 2005 , doi = 10.1080/02533839.2005.9671037 , issue = 4 , journal = Journal of the Chinese Institute of Engineers , pages = 701–711 , title = A pinwheel packet scheduling scheme for broadband wireless networks , volume = 28, s2cid = 62761108

External links

Pinwheel scheduling (1989)
Douglas B. West, University of Illinois Processor scheduling algorithms