Overload tolerance for single-processor workloads

Sanjoy K. Baruah

doi:10.1109/RTTAS.1998.683182

Overload tolerance for single-processor workloads

Sanjoy K. Baruah

Department of Computer Science & Engineering

Research output: Contribution to journal › Conference article › peer-review

14 Scopus citations

Abstract

In firm real time environments in which tasks must complete by their deadlines if they are to be of any value to the system, it is known that no uniprocessor online scheduling algorithm can guarantee to perform particularly well under conditions of overload as compared to clairvoyant algorithms. The article explores the issue of designing online scheduling algorithms that use multiple processors to compensate for their lack of clairvoyance. In particular, it is shown that given enough processors, online scheduling algorithms can be designed with performance guarantees arbitrarily close to that of optimal clairvoyant uniprocessor scheduling algorithms.

Original language	English
Article number	683182
Pages (from-to)	2-11
Number of pages	10
Journal	Real-Time Technology and Applications - Proceedings
DOIs	https://doi.org/10.1109/RTTAS.1998.683182
State	Published - 1998
Event	4th IEEE Real-Time Technology and Applications Symposium, RTAS 1998 - Denver, CO, United States Duration: Jun 3 1998 → Jun 5 1998

Keywords

competitive analysis
multiprocessor scheduling
On-line scheduling
overload tolerance

Access to Document

10.1109/RTTAS.1998.683182

Cite this

@article{eba0917f41d54069a9b3adf948bd7f76,

title = "Overload tolerance for single-processor workloads",

abstract = "In firm real time environments in which tasks must complete by their deadlines if they are to be of any value to the system, it is known that no uniprocessor online scheduling algorithm can guarantee to perform particularly well under conditions of overload as compared to clairvoyant algorithms. The article explores the issue of designing online scheduling algorithms that use multiple processors to compensate for their lack of clairvoyance. In particular, it is shown that given enough processors, online scheduling algorithms can be designed with performance guarantees arbitrarily close to that of optimal clairvoyant uniprocessor scheduling algorithms.",

keywords = "competitive analysis, multiprocessor scheduling, On-line scheduling, overload tolerance",

author = "Baruah, \{Sanjoy K.\}",

year = "1998",

doi = "10.1109/RTTAS.1998.683182",

language = "English",

pages = "2--11",

journal = "Real-Time Technology and Applications - Proceedings",

issn = "1080-1812",

note = "4th IEEE Real-Time Technology and Applications Symposium, RTAS 1998 ; Conference date: 03-06-1998 Through 05-06-1998",

}

TY - JOUR

T1 - Overload tolerance for single-processor workloads

AU - Baruah, Sanjoy K.

PY - 1998

Y1 - 1998

N2 - In firm real time environments in which tasks must complete by their deadlines if they are to be of any value to the system, it is known that no uniprocessor online scheduling algorithm can guarantee to perform particularly well under conditions of overload as compared to clairvoyant algorithms. The article explores the issue of designing online scheduling algorithms that use multiple processors to compensate for their lack of clairvoyance. In particular, it is shown that given enough processors, online scheduling algorithms can be designed with performance guarantees arbitrarily close to that of optimal clairvoyant uniprocessor scheduling algorithms.

AB - In firm real time environments in which tasks must complete by their deadlines if they are to be of any value to the system, it is known that no uniprocessor online scheduling algorithm can guarantee to perform particularly well under conditions of overload as compared to clairvoyant algorithms. The article explores the issue of designing online scheduling algorithms that use multiple processors to compensate for their lack of clairvoyance. In particular, it is shown that given enough processors, online scheduling algorithms can be designed with performance guarantees arbitrarily close to that of optimal clairvoyant uniprocessor scheduling algorithms.

KW - competitive analysis

KW - multiprocessor scheduling

KW - On-line scheduling

KW - overload tolerance

UR - https://www.scopus.com/pages/publications/0031623403

U2 - 10.1109/RTTAS.1998.683182

DO - 10.1109/RTTAS.1998.683182

M3 - Conference article

AN - SCOPUS:0031623403

SN - 1080-1812

SP - 2

EP - 11

JO - Real-Time Technology and Applications - Proceedings

JF - Real-Time Technology and Applications - Proceedings

M1 - 683182

T2 - 4th IEEE Real-Time Technology and Applications Symposium, RTAS 1998

Y2 - 3 June 1998 through 5 June 1998

ER -

Overload tolerance for single-processor workloads

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this