Pinwheel scheduling with three distinct numbers

Shun-Shii Lin, Kwei Jay Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 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). We limit ourselves to instances composed of three distinct integers. Currently, the best scheduler [5] can schedule such instances with a density less than 0.77. A new and fast scheduling scheme based on spectrum partitioning is proposed which improves the 0.77 result to a new 5/6 ≈ 0.83 density threshold. This scheduler has achieved the exact theoretical bound of this problem.

Original languageEnglish
Title of host publicationProceedings - 6th Euromicro Workshop on Real-Time Systems, ECRTS 1994
Pages174-179
Number of pages6
DOIs
Publication statusPublished - 1994 Dec 1
Event6th Euromicro Workshop on Real-Time Systems, ECRTS 1994 - Vaesteraas, Sweden
Duration: 1994 Jun 151994 Jun 17

Publication series

NameProceedings - Euromicro Conference on Real-Time Systems
ISSN (Print)1068-3070

Other

Other6th Euromicro Workshop on Real-Time Systems, ECRTS 1994
CountrySweden
CityVaesteraas
Period94/6/1594/6/17

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Pinwheel scheduling with three distinct numbers'. Together they form a unique fingerprint.

  • Cite this

    Lin, S-S., & Lin, K. J. (1994). Pinwheel scheduling with three distinct numbers. In Proceedings - 6th Euromicro Workshop on Real-Time Systems, ECRTS 1994 (pp. 174-179). [336846] (Proceedings - Euromicro Conference on Real-Time Systems). https://doi.org/10.1109/EMWRTS.1994.336846