Approximative real-time analysis [Elektronische Ressource] / Karsten Albers

Sujets

• Informatik

Informations

• Publié par: universitat_ulm
• Publié le: 01 janvier 2011
• Nombre de lectures: 5
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Approximative Real-Time Analysis
DISSERTATION
zur Erlangung des akademischen Grades eines
Dr. rer. nat.
der Fakultät für Ingenieurwissenschaften und Informatik
der Universität Ulm
vorgelegt von
Karsten Albers
aus Erlangen
Institut für Eingebettete Systeme / Echtzeitsystem, 20112
Amtierender Dekan: Prof. Dr.-Ing. Klaus Dietmayer
Universität Ulm, Deutschland
Gutachter: Prof. Dr.-Ing. Frank Slomka
Universität Ulm, Deutschland
Gutachter: Prof. Dr. Helmuth A. Partsch
Universität Ulm, Deutschland
Externer Gutachter: Prof. Dr. Lothar Thiele
ETH Zürich, Schweiz
Tag der Promotion: 08.04.2011Contents
List of Figures 5
List of symbols 9
Chapter 1. Introduction 11
Chapter 2. Related Work 15
2.1. Schedulability analysis for task sets with static priorities 17
2.2. Schedulability analysis for task sets with dynamic priorities 20
2.3. Event models 32
Chapter 3. Approximation for dynamic priorities 49
3.1. Periodic task system 50
3.2. Capacity calculation for the period task model 56
3.3. Event Stream Model 57
3.4. Proofs 60
3.5. Approximation error 66
3.6. Complexity 69
3.7. Comparison to related work 70
Chapter 4. Adaptive schedulability tests 73
4.1. Dynamic error analysis 73
4.2. All-approximated algorithm 77
4.3. Generalization of the maximum test interval 82
4.4. Complexity 82
Chapter 5. Approximation for static priority scheduling 85
5.1. Exact schedulability analysis 85
5.2. Exceeding costs 91
5.3. Approximation of Static Priorities 95
5.4. Dynamic adaptive test 99
5.5. Complexity 103
Chapter 6. Evaluations 105
6.1. General setup of the experiments 105
6.2. Superposition approximation 107
6.3. Dynamic Approximation Approaches 116
6.4. Approximation and Dynamic approximation for static priorities 127
34 CONTENTS
6.5. Previous approaches 132
Chapter 7. Hierarchical event spectra 139
7.1. Limitations of the event stream model 139
7.2. Spectra 141
7.3. Reduction and normalization of hierarchical event spectra 148
7.4. Capacity Function 150
7.5. Modeling common event models with event spectra 152
7.6. Event Spectra Algebra 154
7.7. Schedulability analysis 161
7.8. Limitations of the hierarchical event stream model 165
Chapter 8. Approximation of hierarchical event spectra 167
8.1. First approach: Separate approximation for each element 168
8.2. Second approach: Global approximation for each element 172
8.3. Summarizing Examples 183
Chapter 9. Case-Study 189
Chapter 10. Summary and Outlook 197
Zusammenfassung 201
Bibliography 211List of Figures
1.0.1 Example of a distributed hard-real time system published in [77] 12
2.0.1 Example task set 17
2.2.1 Example demand bound function 23
2.2.2 Example demand bound function with large ratio 31
2.3.1 Example Event Sequence 34
2.3.2 Example event bound function 35
2.3.3 Example event streams ( [60]) 37
2.3.4 Transformation periodic event sequence into event stream 37
2.3.5 Scheduling network for real-time calculus 44
2.3.6 Real-Time Calculus of single task 44
3.1.1 Approximation of a single task 52
3.1.2 Adding two approximated demand bound functions 53
3.1.3 Visualization of the approximation bound 54
3.4.1 Visualization of lemma 3.4.3 63
3.5.1 Approximation related to the time 68
4.1.1 Exact demand bound function 73
4.1.2 Graphical visualization for an example of the dynamic error test 74
4.2.1 Graphical visualization of the all-approximation algorithm 79
5.1.1 Example of satisfaction intervals 89
5.1.2 Worst-case response-time with satisfaction intervals 90
5.2.1 Task set example for exceeding costs 92
6.2.1 Superposition: ratio of schedulable task sets for different utilizations 107
6.2.2 Superposition: ratio of schedulable task sets (50 tasks) 108
6.2.3 Superposition: ratio of schedulable task sets (500 tasks) 109
6.2.4 Superposition: ration of schedulable task sets for different average gaps 110
6.2.5 Superposition: ratio of schedulable task sets for different ratios between the
largest and smallest task in the task set (100 tasks per task set) 111
56 LIST OF FIGURES
6.2.6 Superposition: average run-time for different utilizations 111
6.2.7 Superposition: average run-time for different utilizations (500 tasks) 112
6.2.8 Superposition: average run-time for different utilizations for only the
schedulable task sets 113
6.2.9 Superposition: maximum run-time for different utilizations (with PDC) 114
6.2.10 Superposition: maximum run-time for different utilizations (50 tasks) 114
6.2.11 Superposition: maximum run-time for different utilizations with PDC (500
tasks) 115
6.2.12 Superposition: maximum run-time for different ratios between smallest and
largest task in the task set 115
6.2.13 Superposition: Average run-time for different utilizations with exponential
distribution of periods 116
6.2.14 Superposition: maximum run-time for different utilizations with exponential
distribution of periods 117
6.2.15Superposition: run-time for different number of tasks in the task sets 117
6.3.1 Adaptive analysis: maximum run-time 118
6.3.2 Maximum computation time of adaptive analysis (50 tasks) 119
6.3.3 Adaptive analysis: maximum run-time - exponential distribution of periods 119
6.3.4 Adaptive analysis: average run-time 120
6.3.5 Adaptive analysis: maximum run-time (500 tasks) 121
6.3.6 Adaptive analysis: average run-time (500 tasks) 121
6.3.7 Adaptive analysis: maximum run-time for different ratios between largest and
smallest period for 98% utilization 122
6.3.8 Adaptive analysis: maximum run-time of the test for different number of tasks
in the task set for 98% utilization 124
6.3.9 All-approximation test: different kind of orders 124
6.4.1 Static analysis: ratio schedulable task sets - normal distribution of periods 128
6.4.2 Static analysis: maximum required computation time for exact static analyses -
normal distributed periods 128
6.4.3 Static analysis: average run-time - normal distributed periods 129
6.4.4 Static analysis: average run-time - normal distributed periods (500 tasks) 130
6.4.5 Static analysis: maximum run-time for different number of tasks - normal
distributed periods 130
6.4.6 Static analysis: maximum required run-time for approximative static analyses
algorithms - exponential distributed periods 131
6.4.7 Static analysis: average run-time - exponential distributed periods 131
6.5.1 EDF: acceptance ratio of the approach of Masrur et al. (normal distribution) 132LIST OF FIGURES 7
6.5.2 EDF: max run-time compared of approach of Masrur et al. (normal distribution)133
6.5.3 EDF: acceptance ratio of the approach of Masrur et al. (exp. distribution) 133
6.5.4 EDF: max run-time compared of approach of Masrur et al. (exp. distribution) 134
6.5.5 EDF: average run-time of the previous approaches 134
6.5.6 EDF: maximum run-time of the previous approaches 135
6.5.7 Static priorities: average run-time of previous approaches 136
6.5.8 Static priorities: maximum runtime of previous approaches 136
7.1.1 Example Event Spectrum 140
7.1.2 Example task graph generating bursts 141
ˆ7.2.1 Hierarchical event spectrum 1436
7.2.2 Example for overlapping events of different periods 145
7.2.3 Example event spectrum 146
7.2.4 Example simple periodic event sequence 147
7.4.1 Example service bound functions 151
8.1.1 Approximated hierarchical spectrum bound function 170
8.2.1 Case one simple event spectrum element 173
8.2.2 One-level event spectrum element 175
8.2.3 Approximation for hierarchical event spectra 179
8.3.1 Example 8.1.2: Approximated hierarchical event bound function 184
8.3.2 Example 8.1.2: Periodic model with minimum separation distance 185
8.3.3 Example 8.1.2: Approximation of the real-time calculus 186
9.0.1 Example of a distributed hard-real time system published in [77] 189
10.0.1 Approximation einer einfachen Task 207
10.0.2 Anteil der als planbar klassifizierten Tasksets 208
10.0.3 Maximale Laufzeit der Echtzeitanalysen für verschieden Approximationstufen 208
10.0.4 Rechenzeiten der dynamischen Approximation und des Processor-Demand-
Criterion 209
QList of symbols
descriptor meaning First defined in
task chapter2
task set chapter 2
j- th job of a task chapter 2i, j i
p period chapter 2
c execution-time chapter 2
+c worst-case execution-time chapter 2
−c best-case execution-time chapter 2
d relative deadline chapter 2
U utilization chapter 2
t interval section 2.1
r response time section 2.1
hp( ) set of tasks with a higher priority than section 2.1
j jitter section 2.1
S scheduling point set section 2.1
() demand bound function section 2.2.2
() capacity bound function section 2.2.2
t maximum test interval section 2.2.3max
t least-common multiple of periods interval section 2.2.3LCM
B() busy period function section 2.2.3
n number of tasks section 2.2.4
() event bound function section 2.3.2
periodic event sequence section 2.3.2
event element section 2.3.2
a offset / initial interval section 2.3.2
() interval bound function section 2.3.2
s minimum separation distance section 2.3.4
arrival curve section 2.3.6
u upper arrival curve section 2.3.6
l lower arrival curve section 2.3.6
service curve