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

Shun Shii Lin*, Kwei Jay Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)

Abstract

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)
Volume19
Issue number4
DOIs
Publication statusPublished - 1997

Keywords

  • Density thresholds
  • Pinwheel
  • Real-time
  • Scheduling

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A pinwheel scheduler for three distinct numbers with a tight schedulability bound'. Together they form a unique fingerprint.

Cite this