PREFACE xi
LIST OF FIGURES xv
LIST OF TABLES xxi
CHAPTER 1. INTRODUCTION TO REAL-TIME SCHEDULING 1
Emmanuel GROLLEAU
1.1. Real-time systems 1
1.2. Material architectures 5
1.2.1. CPUs 5
1.2.2. Communication networks 7
1.2.3. Sensors and actuators 9
1.3. Operating systems 9
1.3.1. Generalities 10
1.3.2. Real-time operating systems 10
1.3.3. Primitives provided by the kernel 12
1.4. Scheduling 14
1.4.1. Online and offline scheduling 14
1.4.2. Task characterization 16
1.4.3. Criticality 19
1.4.4. Metrics related to scheduling 20
1.4.5. Practical factors 22
1.4.6. Multi-core scheduling 27
1.5. Real-time application modeling and analysis 30
1.5.1. Modeling 30
1.5.2. Analysis 31
1.6. System architecture and schedulability 34
CHAPTER 2. UNIPROCESSOR ARCHITECTURE SOLUTIONS 39
Laurent GEORGE and Jean-François HERMANT
2.1. Introduction 40
2.2. Characterization of a scheduling problem 42
2.2.1. Task model 42
2.2.2. Temporal constraint models 45
2.2.3. Scheduling model 46
2.2.4. Concepts and notations 50
2.3. Scheduling algorithms/optimality 52
2.3.1. FP fixed-job priority algorithms 52
2.3.2. JFP algorithms 55
2.3.3. Dynamic priority algorithms 57
2.4. Busy periods and worst-case scenarios 58
2.4.1. Busy periods 58
2.4.2. Worst-case scenarios 60
2.5. Feasibility conditions 66
2.5.1. FP feasibility conditions 66
2.5.2. JFP feasibility conditions 70
2.6. Sensitivity analysis 75
2.6.1. Sensitivity of WCETs 78
2.6.2. Sensitivity of periods 88
2.6.3. Sensitivity of deadlines 90
2.7. Conclusion 95
2.8. Bibliography 97
CHAPTER 3. MULTIPROCESSOR ARCHITECTURE SOLUTIONS
105
Joël GOOSSENS and Pascal RICHARD
3.1. Introduction 105
3.1.1. Application modeling 106
3.1.2. Platform modeling 108
3.2. Scheduler classification 108
3.2.1. Online and offline schedulers 108
3.2.2. Task preemption and migration 109
3.2.3. Priorities of tasks 111
3.2.4. Classification 111
3.3. Properties of schedulers 111
3.3.1. Qualitative properties 112
3.3.2. Quantitative properties 117
3.4. Partitioned scheduling 121
3.4.1. Partitioning algorithms 121
3.4.2. Evaluation of partitioning algorithms 126
3.5. Global scheduling 131
3.5.1. Proportionate fair algorithms 132
3.5.2. Generalization of uniprocessor scheduling algorithms
142
3.6. Conclusion 143
3.7. Bibliography 143
CHAPTER 4. SYNCHRONIZATIONS: SHARED RESOURCE ACCESS PROTOCOLS
149
Serge MIDONNET and Frederic FAUBERTEAU
4.1. Introduction 150
4.2. Terminology and notations 150
4.2.1. Diagrams 152
4.2.2. Synchronization protocols 153
4.3. Synchronization problems 160
4.3.1. Unbounded priority inversion 160
4.3.2. Deadlock 166
4.3.3. Chained blocking 172
4.4. Calculating the blocking factor 177
4.4.1. The case of uniprocessor architectures 177
4.4.2. The case of multiprocessor architectures 180
4.5. Conclusion 187
4.6. Bibliography 188
CHAPTER 5. ESTIMATION OF EXECUTION TIME AND DELAYS
193
Claire MAIZA, Pascal RAYMOND and Christine ROCHANGE
5.1. Worst-case execution time analysis: an example 195
5.1.1. Embedded system architecture analysis 197
5.1.2. Execution path analysis 206
5.2. Going further 211
5.2.1. Multi-task: the cost of preemption 211
5.2.2. Multi-core and other complex architectures 215
5.2.3. Influence of critical embedded systems design methods
218
5.2.4. Tools 224
5.3. Conclusion 225
5.4. Bibliography 225
CHAPTER 6. OPTIMIZATION OF ENERGY CONSUMPTION 231
Cecile BELLEUDY
6.1. Introduction 232
6.2. State of the art 235
6.2.1. General comments 235
6.2.2. Modeling the consumption of an operating system 237
6.2.3. Consumption management strategies within multicore
systems 238
6.3. Modeling consumption 242
6.3.1. Characterization platform: hardware and software 242
6.3.2. Power consumption modeling 243
6.3.3. Context switch 244
6.3.4. Inter-process communication 247
6.4. Low consumption scheduling 249
6.4.1. Simulation environment 250
6.4.2. Low power consumption scheduling policy 251
6.5. Experimental results 255
6.5.1. Application test: H.264 decoder 255
6.5.2. Analysis of the simulation results 258
6.6. Conclusion 262
6.7. Bibliography 262
LIST OF AUTHORS 269
INDEX 271
SUMMARY OF VOLUME 2 275
