Real-time calculus for scheduling hard real-time systems

Lothar Thiele; Samarjit Chakraborty; Martin Naedele

doi:10.1109/ISCAS.2000.858698

Real-time calculus for scheduling hard real-time systems

Lothar Thiele
, Samarjit Chakraborty
, Martin Naedele

ETH Zurich

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

479 Scopus citations

Abstract

This paper establishes a link between three areas, namely Max-Plus Linear System Theory as used for dealing with certain classes of discrete event systems, Network Calculus for establishing time bounds in communication networks, and real-time scheduling. In particular, it is shown that important results from scheduling theory can be easily derived and unified using Max-Plus Algebra. Based on the proposed network theory for real-time systems, the first polynomial algorithm for the feasibility analysis and optimal priority assignment for a general task model is derived.

Original language	English
Pages (from-to)	IV-101-IV-104
Journal	Proceedings - IEEE International Symposium on Circuits and Systems
Volume	4
DOIs	https://doi.org/10.1109/ISCAS.2000.858698
State	Published - 2000
Externally published	Yes
Event	Proceedings of the IEEE 2000 International Symposium on Circuits and Systems, ISCAS 2000 - Geneva, Switz, Switzerland Duration: 28 May 2000 → 31 May 2000

Access to Document

10.1109/ISCAS.2000.858698

Cite this

@article{ea93c6b5380546c2853a5074a2b32695,

title = "Real-time calculus for scheduling hard real-time systems",

abstract = "This paper establishes a link between three areas, namely Max-Plus Linear System Theory as used for dealing with certain classes of discrete event systems, Network Calculus for establishing time bounds in communication networks, and real-time scheduling. In particular, it is shown that important results from scheduling theory can be easily derived and unified using Max-Plus Algebra. Based on the proposed network theory for real-time systems, the first polynomial algorithm for the feasibility analysis and optimal priority assignment for a general task model is derived.",

author = "Lothar Thiele and Samarjit Chakraborty and Martin Naedele",

year = "2000",

doi = "10.1109/ISCAS.2000.858698",

language = "English",

volume = "4",

pages = "IV--101--IV--104",

journal = "Proceedings - IEEE International Symposium on Circuits and Systems",

issn = "0271-4310",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "Proceedings of the IEEE 2000 International Symposium on Circuits and Systems, ISCAS 2000 ; Conference date: 28-05-2000 Through 31-05-2000",

}

TY - JOUR

T1 - Real-time calculus for scheduling hard real-time systems

AU - Thiele, Lothar

AU - Chakraborty, Samarjit

AU - Naedele, Martin

PY - 2000

Y1 - 2000

N2 - This paper establishes a link between three areas, namely Max-Plus Linear System Theory as used for dealing with certain classes of discrete event systems, Network Calculus for establishing time bounds in communication networks, and real-time scheduling. In particular, it is shown that important results from scheduling theory can be easily derived and unified using Max-Plus Algebra. Based on the proposed network theory for real-time systems, the first polynomial algorithm for the feasibility analysis and optimal priority assignment for a general task model is derived.

AB - This paper establishes a link between three areas, namely Max-Plus Linear System Theory as used for dealing with certain classes of discrete event systems, Network Calculus for establishing time bounds in communication networks, and real-time scheduling. In particular, it is shown that important results from scheduling theory can be easily derived and unified using Max-Plus Algebra. Based on the proposed network theory for real-time systems, the first polynomial algorithm for the feasibility analysis and optimal priority assignment for a general task model is derived.

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

U2 - 10.1109/ISCAS.2000.858698

DO - 10.1109/ISCAS.2000.858698

M3 - Conference article

AN - SCOPUS:0033682521

SN - 0271-4310

VL - 4

SP - IV-101-IV-104

JO - Proceedings - IEEE International Symposium on Circuits and Systems

JF - Proceedings - IEEE International Symposium on Circuits and Systems

T2 - Proceedings of the IEEE 2000 International Symposium on Circuits and Systems, ISCAS 2000

Y2 - 28 May 2000 through 31 May 2000

ER -

Real-time calculus for scheduling hard real-time systems

Abstract

Access to Document

Other files and links

Fingerprint

Cite this