Real-time Systems Scheduling 1 Fundamentals

Real-time systems are used in a wide range of applications, including control, sensing, multimedia, etc.  Scheduling is a central problem for these computing/communication systems since responsible of software execution in a timely manner. This book provides state of knowledge in this domain with special emphasis on the key results obtained within the last decade.

This book addresses foundations as well as the latest advances and findings in Real-Time Scheduling, giving all references to important papers. But nevertheless the chapters will be short and not overloaded with confusing details. Coverage includes scheduling approaches for mono-core as well as multi-core platforms, dependent tasks, networks, and notably very tremendous recent advances in scheduling of energy constrained embedded systems. Other sophisticated issues such as feedback control scheduling and timing analysis of critical applications are also addressed.

This volume can serve as a textbook for courses on the topic in bachelor and in more advanced master programs. It also provides a reference for computer scientists and engineers involved in the design or the development of Cyber-Physical Systems which require up-to-date real-time scheduling solutions.

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 Frédéric 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
Cécile 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

Maryline Chetto received the degree of Docteur in control engineering and the degree of "Habilitée à Diriger des Recherches" in Computer Science from the University of Nantes, France, in 1984 and 1993, respectively. From 1984 to 1985, she held the position of Assistant professor of Computer Science at the University of Rennes, while her research was with the Institut de Recherche en Informatique et Systèmes Aléatoires, Rennes. In 1986, she returned to Nantes and is currently a professor with the Institute of Technology of the University of Nantes. She is conducting her research at IRCCyN Laboratory.? Her main research interests are scheduling and power management for real-time systems. She has published more than 80 journal articles and conference papers in the area of real-time computing.