Pfair scheduling of generalized pinwheel task systems

Sanjoy K. Baruah, Shun Shii Lin

Research output: Contribution to journalArticle

34 Citations (Scopus)

Abstract

The scheduling of generalized pinwheel task systems is considered. It is shown that pinwheel scheduling is closely related to the fair scheduling of periodic task systems. This relationship is exploited to obtain new scheduling algorithms for generalized pinwheel task systems. When compared to traditional pinwheel scheduling algorithms, these new algorithms are both more efficient from a run-time complexity point of view, and have a higher density threshold, on a very large subclass of generalized pinwheel task systems.

Original languageEnglish
Pages (from-to)812-816
Number of pages5
JournalIEEE Transactions on Computers
Volume47
Issue number7
DOIs
Publication statusPublished - 1998 Dec 1

Fingerprint

Scheduling
Scheduling algorithms
Scheduling Algorithm
Time varying systems
Periodic Tasks
Time Complexity

Keywords

  • Density threshold
  • Fairness
  • Generalized pinwheels
  • Real-time scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

Pfair scheduling of generalized pinwheel task systems. / Baruah, Sanjoy K.; Lin, Shun Shii.

In: IEEE Transactions on Computers, Vol. 47, No. 7, 01.12.1998, p. 812-816.

Research output: Contribution to journalArticle

@article{908e39e30d2b4bfe9542ed564150c0d4,
title = "Pfair scheduling of generalized pinwheel task systems",
abstract = "The scheduling of generalized pinwheel task systems is considered. It is shown that pinwheel scheduling is closely related to the fair scheduling of periodic task systems. This relationship is exploited to obtain new scheduling algorithms for generalized pinwheel task systems. When compared to traditional pinwheel scheduling algorithms, these new algorithms are both more efficient from a run-time complexity point of view, and have a higher density threshold, on a very large subclass of generalized pinwheel task systems.",
keywords = "Density threshold, Fairness, Generalized pinwheels, Real-time scheduling",
author = "Baruah, {Sanjoy K.} and Lin, {Shun Shii}",
year = "1998",
month = "12",
day = "1",
doi = "10.1109/12.709381",
language = "English",
volume = "47",
pages = "812--816",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "7",

}

TY - JOUR

T1 - Pfair scheduling of generalized pinwheel task systems

AU - Baruah, Sanjoy K.

AU - Lin, Shun Shii

PY - 1998/12/1

Y1 - 1998/12/1

N2 - The scheduling of generalized pinwheel task systems is considered. It is shown that pinwheel scheduling is closely related to the fair scheduling of periodic task systems. This relationship is exploited to obtain new scheduling algorithms for generalized pinwheel task systems. When compared to traditional pinwheel scheduling algorithms, these new algorithms are both more efficient from a run-time complexity point of view, and have a higher density threshold, on a very large subclass of generalized pinwheel task systems.

AB - The scheduling of generalized pinwheel task systems is considered. It is shown that pinwheel scheduling is closely related to the fair scheduling of periodic task systems. This relationship is exploited to obtain new scheduling algorithms for generalized pinwheel task systems. When compared to traditional pinwheel scheduling algorithms, these new algorithms are both more efficient from a run-time complexity point of view, and have a higher density threshold, on a very large subclass of generalized pinwheel task systems.

KW - Density threshold

KW - Fairness

KW - Generalized pinwheels

KW - Real-time scheduling

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

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

U2 - 10.1109/12.709381

DO - 10.1109/12.709381

M3 - Article

AN - SCOPUS:0001002280

VL - 47

SP - 812

EP - 816

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 7

ER -