A pinwheel scheduler for three distinct numbers with a tight schedulability bound

Shun Shii Lin, Kwei Jay Lin

Research output: Contribution to journalArticle

16 Citations (Scopus)


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 languageEnglish
Pages (from-to)411-426
Number of pages16
JournalAlgorithmica (New York)
Issue number4
Publication statusPublished - 1997 Jan 1



  • Density thresholds
  • Pinwheel
  • Real-time
  • Scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this