Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.11.2017 | Ausgabe 1/2018 Open Access

Real-Time Systems 1/2018

Automated competitive analysis of real-time scheduling with graph games

Real-Time Systems > Ausgabe 1/2018
Krishnendu Chatterjee, Andreas Pavlogiannis, Alexander Kößler, Ulrich Schmid
Wichtige Hinweise
Preliminary versions of this paper have appeared in Chatterjee et al. (2013, 2014).


This paper is devoted to automatic competitive analysis of real-time scheduling algorithms for firm-deadline tasksets, where only completed tasks contribute some utility to the system. Given such a taskset \({\mathcal {T}}\), the competitive ratio of an on-line scheduling algorithm \({\mathcal {A}}\) for \({\mathcal {T}}\) is the worst-case utility ratio of \({\mathcal {A}}\) over the utility achieved by a clairvoyant algorithm. We leverage the theory of quantitative graph games to address the competitive analysis and competitive synthesis problems. For the competitive analysis case, given any taskset \({\mathcal {T}}\) and any finite-memory on-line scheduling algorithm \({\mathcal {A}}\), we show that the competitive ratio of \({\mathcal {A}}\) in \({\mathcal {T}}\) can be computed in polynomial time in the size of the state space of \({\mathcal {A}}\). Our approach is flexible as it also provides ways to model meaningful constraints on the released task sequences that determine the competitive ratio. We provide an experimental study of many well-known on-line scheduling algorithms, which demonstrates the feasibility of our competitive analysis approach that effectively replaces human ingenuity (required for finding worst-case scenarios) by computing power. For the competitive synthesis case, we are just given a taskset \({\mathcal {T}}\), and the goal is to automatically synthesize an optimal on-line scheduling algorithm \({\mathcal {A}}\), i.e., one that guarantees the largest competitive ratio possible for \({\mathcal {T}}\). We show how the competitive synthesis problem can be reduced to a two-player graph game with partial information, and establish that the computational complexity of solving this game is Np-complete. The competitive synthesis problem is hence in Np in the size of the state space of the non-deterministic labeled transition system encoding the taskset. Overall, the proposed framework assists in the selection of suitable scheduling algorithms for a given taskset, which is in fact the most common situation in real-time systems design.

Unsere Produktempfehlungen

Premium-Abo der Gesellschaft für Informatik

Sie erhalten uneingeschränkten Vollzugriff auf alle acht Fachgebiete von Springer Professional und damit auf über 45.000 Fachbücher und ca. 300 Fachzeitschriften.

Über diesen Artikel

Weitere Artikel der Ausgabe 1/2018

Real-Time Systems 1/2018 Zur Ausgabe

Premium Partner