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)

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 Jan 1

Fingerprint

Scheduler
Scheduling
Distinct
Integer
Multiset
Subsequence
Partitioning
Schedule

Keywords

  • Density thresholds
  • Pinwheel
  • Real-time
  • Scheduling

ASJC Scopus subject areas

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

Cite this

A pinwheel scheduler for three distinct numbers with a tight schedulability bound. / Lin, Shun Shii; Lin, Kwei Jay.

In: Algorithmica (New York), Vol. 19, No. 4, 01.01.1997, p. 411-426.

Research output: Contribution to journalArticle

@article{d080552d48bb4dfc85adcf722d22c092,
title = "A pinwheel scheduler for three distinct numbers with a tight schedulability bound",
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.",
keywords = "Density thresholds, Pinwheel, Real-time, Scheduling",
author = "Lin, {Shun Shii} and Lin, {Kwei Jay}",
year = "1997",
month = "1",
day = "1",
doi = "10.1007/PL00009181",
language = "English",
volume = "19",
pages = "411--426",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "4",

}

TY - JOUR

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

AU - Lin, Shun Shii

AU - Lin, Kwei Jay

PY - 1997/1/1

Y1 - 1997/1/1

N2 - 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.

AB - 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.

KW - Density thresholds

KW - Pinwheel

KW - Real-time

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=0002086142&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002086142&partnerID=8YFLogxK

U2 - 10.1007/PL00009181

DO - 10.1007/PL00009181

M3 - Article

AN - SCOPUS:0002086142

VL - 19

SP - 411

EP - 426

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -