Real-time calculus for scheduling hard real-time systems

Author

Thiele, Lothar ; Chakraborty, Samarjit ; Naedele, Martin

Author_Institution

Comput. Eng. & Networks Lab., Swiss Fed. Inst. of Technol., Zurich, Switzerland

Volume

4

fYear

2000

fDate

2000

Firstpage

101

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

Keywords

algebra; calculus of communicating systems; discrete event systems; distributed processing; real-time systems; scheduling; system theory; communication networks; discrete event systems; feasibility analysis; general task model; hard real-time systems; max-plus algebra; max-plus linear system theory; network calculus; optimal priority assignment; polynomial algorithm; preemptive task scheduling; real-time calculus; real-time scheduling; time bounds; Algebra; Calculus; Communication networks; Computer networks; Discrete event systems; Linear systems; Polynomials; Processor scheduling; Real time systems; Scheduling algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. The 2000 IEEE International Symposium on

Conference_Location

Geneva

Print_ISBN

0-7803-5482-6

Type

conf

DOI

10.1109/ISCAS.2000.858698

Filename

858698