Quality and utility [Elektronische Ressource] : on the use of time-value functions to integrate quality and timeliness flexible aspects in a dynamic real-time scheduling environment / Thomas Schwarzfischer

Sujets

• Informatik

Informations

• Publié par: universitat_passau
• Publié le: 01 janvier 2005
• Nombre de lectures: 36
• Langue: English
• Poids de l'ouvrage: 5 Mo

Extrait

Quality and Utility
On the Use of Time-Value Functions to
Integrate Quality and Timeliness Flexible
Aspects in a Dynamic Real-Time
Scheduling Environment
Thesis
in partial fulfillment of the requirements of the degree of
Doctor of Science (Dr. rer. nat.)
at the
Faculty of Mathematics and Informatics
of the
University of Passau
Thomas Schwarzfischer
October 2004
Day of Oral Exam: 21 January 2005Abstract
Scheduling methodologies for real-time applications have been of keen interest to diverse research com-
munities for several decades. Depending on the application area, algorithms have been developed that are
tailored to specific requirements with respect to both the individual components of which an application
is made up and the computational platform on which it is to be executed. Many real-time scheduling algo-
rithms base their decisions solely or partly on timing constraints expressed by deadlines which must be met
even under worst-case conditions. The increasing complexity of computing hardware means that worst-
case execution time analysis becomes increasingly pessimistic. Scheduling hard real-time computations
according to their worst-case execution times (which is common practice) will thus result, on average,
in an increasing amount of spare capacity. The main goal of flexible real-time scheduling is to exploit
this otherwise wasted capacity. Flexible scheduling schemes have been proposed to increase the ability
of a real-time system to adapt to changing requirements and nondeterminism in the application behav-
iour. These models can be categorised as those whose source of flexibility is the quality of computations
and those which are flexible regarding their timing constraints. This work describes a novel model which
allows to specify both flexible timing constraints and quality profiles for an application. Furthermore, it
demonstrates the applicability of this specification method to real-world examples and suggests a set of
feasible scheduling algorithms for the proposed problem class.
Zusammenfassung
Einplanungsverfahren fu¨r Echtzeitanwendungen stehen seit Jahrzehnten im Interesse verschiedener For-
schungsgruppen. Abha¨ngig vom Anwendungsgebiet wurden Algorithmen entwickelt, welche an die spe-
zifischen Anforderungen sowohl hinsichtlich der einzelnen Komponenten, aus welchen eine Anwendung
besteht, als auch an die Rechnerplattform, auf der diese ausgefu¨hrt werden sollen, angepasst sind. Viele
Echtzeit-Einplanungsverfahren gru¨nden ihre Entscheidungen ausschließlich oder teilweise auf Zeitbe-
dingungen, welche auch bei Auftreten maximaler Ausfu¨hrungszeiten eingehalten werden mu¨ssen. Die
zunehmende Komplexita¨t von Rechner-Hardware bedeutet, dass die Worst-Case-Analyse in steigendem
Maße pessimistisch wird. Die Einplanung harter Echtzeit-Berechnungen anhand ihrer maximalen Aus-
fu¨hrungszeiten (was die ga¨ngige Praxis darstellt) resultiert daher im Regelfall in einer frei verfu¨gbaren
Rechenkapazita¨t in steigender Ho¨he. Das Hauptziel flexibler Echtzeit-Einplanungsverfahren ist es, diese
ansonsten verschwendete Kapazita¨t auszunutzen. Flexible Einplanungsverfahren wurden vorgeschlagen,
welche die Fa¨higkeit eines Echtzeitsystems erho¨hen, sich an vera¨nderte Anforderungen und Nichtdeter-
minismus im Verhalten der Anwendung anzupassen. Diese Modelle ko¨nnen unterteilt werden in solche,
deren Quelle der Flexibilita¨t die Qualita¨t der Berechnungen ist, und jene, welche flexibel hinsichtlich ihrer
Zeitbedingungen sind. Diese Arbeit beschreibt ein neuartiges Modell, welches es erlaubt, sowohl flexible
Zeitbedingungen als auch Qualita¨tsprofile fu¨r eine Anwendung anzugeben. Außerdem demonstriert sie
die Anwendbarkeit dieser Spezifikationsmethode auf reale Beispiele und schla¨gt eine Reihe von Einpla-
nungsalgorithmen fu¨r die vorgestellte Problemklasse vor.Acknowledgements
The best way to become acquainted with a
subject is to write a book about it.
Benjamin Disraeli
Gratitude is merely the secret hope of fur-
ther favours.
Franc¸ois de La Rochefou-
cauld
As is the case in most circumstances in life, achievements are not normally possible with-
out the assistance of numerous well-meaning people. The same was true for the undertaking of
carrying out my PhD research.
Representing so many who contributed to the successful completion of this work either
through active help or by mental support, I would like to thank the following persons by name.
I thank Prof. Dr.-Ing. Werner Grass for his long lasting assistance and guidance, numerous im-
pulses to gain new insights and especially for helping me place my work into a bigger context.
I am grateful to Prof. Dr.-Ing. Ju¨rgen Teich of Friedrich-Alexander University in Erlangen for
acting as an external referee, and to Prof. Dr. Gottlieb Leha, Prof. Christian Lengauer, PhD,
and Prof. Dr. Volker Weispfenning to sit on the committee for the oral examination. The advice
of Prof. Dr. Niels Schwartz was essential for coming to terms with formal requirements of the
graduation process. I say my thanks to all the people in our group, especially to Dr. Bernhard
Sick for his cooperation, Martin Grajcar for various spontaneous ideas and Markus Ramsauer for
numerous fruitful discussions while working on the same project. I extend my thanks to Franz
Rautmann for keeping our technical equipment running most of the time and Eva Kapfer for her
constant effort to establish a hearty and welcoming climate at the institute.
I thank our students for their participation in the PaSchA project: Christian Ju¨nger, Klaus
Ehrnbo¨ck, Jakob Flierl, Kerstin Meyerhofer, Selc¸uk Demirci, Robert Schiller, Katrin Limpo¨ck,
Diana Lucic, Matthias Weindler, Peter Zach, Bettina Riedmann, Barbara Busse, Christian Mu¨ller,
Ralf Zimmermann and others I might have forgotten to mention.
I also greatly appreciated the comments of Prof. Dr. Hiroshi Nagamochi, Dr. Koji Nonobe
and Dr. Mutsunori Yagiura of the University of Kyoto during the final stages of my PhD project,
when I could spend interesting months at their institute.I thank all those who encouraged me to carry on with endless patience every time I had
lost the necessary confidence, first of all Michiko Araseki for all her love. Finally, I am deeply
indebted to my parents, Agnes and Karl Schwarzfischer, who gave me the opportunity to pursue
my studies, and to God for providing me with the abilities to do so.
Passau, January 2005
Thomas SchwarzfischerContents
1 Introduction 1
1.1 The Relationship between Planning and Scheduling . . . . . . . . . . . . . . . . 2
1.2 Basic Real-Time Scheduling Terminology . . . . . . . . . . . . . . . . . . . . . 3
1.3 The Quality of Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 The Run-to-Completion Assumption . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Quality-Flexible Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 The Timeliness of Computations . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 Traditional Timing Constraints in Scheduling . . . . . . . . . . . . . . . 8
1.4.2 Timeliness-Flexible Scheduling . . . . . . . . . . . . . . . . . . . . . . 9
1.5 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Aims of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.9 Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 The Basic Quality / Utility Scheduling Problem 15
2.1 Basic Quality / Utility Scheduling Problem . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Application Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Quality and Utility Functions . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.3 Local Time Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.1.4 Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Dynamic Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Time-Variant Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Properties of Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Example Value Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.1 Pointwise Sum of Product of Utility and Quality Functions with Outer
Hold Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
v2.5.2 Pointwise Sum of Product of Utility and Quality Functions with Inner
Hold Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5.3 Pointwise Sum of Product of Quality and Utility Functions with Addi-
tional Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.3.1 Background Anytime Tasks . . . . . . . . . . . . . . . . . . . 35
2.5.3.2 Tasks with Mandatory and Optional Service Times . . . . . . . 35
2.5.4 Pointwise Maximum of Product of Utility and Quality Functions . . . . . 36
3 Scheduling Algorithms 37
3.1 Reactive Unconditional Scheduling . . . . . . . . . . . . . . . . . . .