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.

• PREFACE xiLIST OF FIGURES xvLIST OF TABLES xxiCHAPTER 1. INTRODUCTION TO REAL-TIME SCHEDULING 1Emmanuel GROLLEAU1.1. Real-time systems 11.2. Material architectures 51.2.1. CPUs 51.2.2. Communication networks 71.2.3. Sensors and actuators 91.3. Operating systems 91.3.1. Generalities 101.3.2. Real-time operating systems 101.3.3. Primitives provided by the kernel 121.4. Scheduling 141.4.1. Online and offline scheduling 141.4.2. Task characterization 161.4.3. Criticality 191.4.4. Metrics related to scheduling 201.4.5. Practical factors 221.4.6. Multi-core scheduling 271.5. Real-time application modeling and analysis 301.5.1. Modeling 301.5.2. Analysis 311.6. System architecture and schedulability 34CHAPTER 2. UNIPROCESSOR ARCHITECTURE SOLUTIONS 39Laurent GEORGE and Jean-François HERMANT2.1. Introduction 402.2. Characterization of a scheduling problem 422.2.1. Task model 422.2.2. Temporal constraint models 452.2.3. Scheduling model 462.2.4. Concepts and notations 502.3. Scheduling algorithms/optimality 522.3.1. FP fixed-job priority algorithms 522.3.2. JFP algorithms 552.3.3. Dynamic priority algorithms 572.4. Busy periods and worst-case scenarios 582.4.1. Busy periods 582.4.2. Worst-case scenarios 602.5. Feasibility conditions 662.5.1. FP feasibility conditions 662.5.2. JFP feasibility conditions 702.6. Sensitivity analysis 752.6.1. Sensitivity of WCETs 782.6.2. Sensitivity of periods 882.6.3. Sensitivity of deadlines 902.7. Conclusion 952.8. Bibliography 97CHAPTER 3. MULTIPROCESSOR ARCHITECTURE SOLUTIONS 105Joël GOOSSENS and Pascal RICHARD3.1. Introduction 1053.1.1. Application modeling 1063.1.2. Platform modeling 1083.2. Scheduler classification 1083.2.1. Online and offline schedulers 1083.2.2. Task preemption and migration 1093.2.3. Priorities of tasks 1113.2.4. Classification 1113.3. Properties of schedulers 1113.3.1. Qualitative properties 1123.3.2. Quantitative properties 1173.4. Partitioned scheduling 1213.4.1. Partitioning algorithms 1213.4.2. Evaluation of partitioning algorithms 1263.5. Global scheduling 1313.5.1. Proportionate fair algorithms 1323.5.2. Generalization of uniprocessor scheduling algorithms 1423.6. Conclusion 1433.7. Bibliography 143CHAPTER 4. SYNCHRONIZATIONS: SHARED RESOURCE ACCESS PROTOCOLS 149Serge MIDONNET and Frédéric FAUBERTEAU4.1. Introduction 1504.2. Terminology and notations 1504.2.1. Diagrams 1524.2.2. Synchronization protocols 1534.3. Synchronization problems 1604.3.1. Unbounded priority inversion 1604.3.2. Deadlock 1664.3.3. Chained blocking 1724.4. Calculating the blocking factor 1774.4.1. The case of uniprocessor architectures 1774.4.2. The case of multiprocessor architectures 1804.5. Conclusion 1874.6. Bibliography 188CHAPTER 5. ESTIMATION OF EXECUTION TIME AND DELAYS 193Claire MAIZA, Pascal RAYMOND and Christine ROCHANGE5.1. Worst-case execution time analysis: an example 1955.1.1. Embedded system architecture analysis 1975.1.2. Execution path analysis 2065.2. Going further 2115.2.1. Multi-task: the cost of preemption 2115.2.2. Multi-core and other complex architectures 2155.2.3. Influence of critical embedded systems design methods 2185.2.4. Tools 2245.3. Conclusion 2255.4. Bibliography 225CHAPTER 6. OPTIMIZATION OF ENERGY CONSUMPTION 231Cécile BELLEUDY6.1. Introduction 2326.2. State of the art 2356.2.1. General comments 2356.2.2. Modeling the consumption of an operating system 2376.2.3. Consumption management strategies within multicore systems 2386.3. Modeling consumption 2426.3.1. Characterization platform: hardware and software 2426.3.2. Power consumption modeling 2436.3.3. Context switch 2446.3.4. Inter-process communication 2476.4. Low consumption scheduling 2496.4.1. Simulation environment 2506.4.2. Low power consumption scheduling policy 2516.5. Experimental results 2556.5.1. Application test: H.264 decoder 2556.5.2. Analysis of the simulation results 2586.6. Conclusion 2626.7. Bibliography 262LIST OF AUTHORS 269INDEX 271SUMMARY 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.

• PREFACE xiLIST OF FIGURES xvLIST OF TABLES xxiCHAPTER 1. INTRODUCTION TO REAL-TIME SCHEDULING 1Emmanuel GROLLEAU1.1. Real-time systems 11.2. Material architectures 51.2.1. CPUs 51.2.2. Communication networks 71.2.3. Sensors and actuators 91.3. Operating systems 91.3.1. Generalities 101.3.2. Real-time operating systems 101.3.3. Primitives provided by the kernel 121.4. Scheduling 141.4.1. Online and offline scheduling 141.4.2. Task characterization 161.4.3. Criticality 191.4.4. Metrics related to scheduling 201.4.5. Practical factors 221.4.6. Multi-core scheduling 271.5. Real-time application modeling and analysis 301.5.1. Modeling 301.5.2. Analysis 311.6. System architecture and schedulability 34CHAPTER 2. UNIPROCESSOR ARCHITECTURE SOLUTIONS 39Laurent GEORGE and Jean-François HERMANT2.1. Introduction 402.2. Characterization of a scheduling problem 422.2.1. Task model 422.2.2. Temporal constraint models 452.2.3. Scheduling model 462.2.4. Concepts and notations 502.3. Scheduling algorithms/optimality 522.3.1. FP fixed-job priority algorithms 522.3.2. JFP algorithms 552.3.3. Dynamic priority algorithms 572.4. Busy periods and worst-case scenarios 582.4.1. Busy periods 582.4.2. Worst-case scenarios 602.5. Feasibility conditions 662.5.1. FP feasibility conditions 662.5.2. JFP feasibility conditions 702.6. Sensitivity analysis 752.6.1. Sensitivity of WCETs 782.6.2. Sensitivity of periods 882.6.3. Sensitivity of deadlines 902.7. Conclusion 952.8. Bibliography 97CHAPTER 3. MULTIPROCESSOR ARCHITECTURE SOLUTIONS 105Joël GOOSSENS and Pascal RICHARD3.1. Introduction 1053.1.1. Application modeling 1063.1.2. Platform modeling 1083.2. Scheduler classification 1083.2.1. Online and offline schedulers 1083.2.2. Task preemption and migration 1093.2.3. Priorities of tasks 1113.2.4. Classification 1113.3. Properties of schedulers 1113.3.1. Qualitative properties 1123.3.2. Quantitative properties 1173.4. Partitioned scheduling 1213.4.1. Partitioning algorithms 1213.4.2. Evaluation of partitioning algorithms 1263.5. Global scheduling 1313.5.1. Proportionate fair algorithms 1323.5.2. Generalization of uniprocessor scheduling algorithms 1423.6. Conclusion 1433.7. Bibliography 143CHAPTER 4. SYNCHRONIZATIONS: SHARED RESOURCE ACCESS PROTOCOLS 149Serge MIDONNET and Frédéric FAUBERTEAU4.1. Introduction 1504.2. Terminology and notations 1504.2.1. Diagrams 1524.2.2. Synchronization protocols 1534.3. Synchronization problems 1604.3.1. Unbounded priority inversion 1604.3.2. Deadlock 1664.3.3. Chained blocking 1724.4. Calculating the blocking factor 1774.4.1. The case of uniprocessor architectures 1774.4.2. The case of multiprocessor architectures 1804.5. Conclusion 1874.6. Bibliography 188CHAPTER 5. ESTIMATION OF EXECUTION TIME AND DELAYS 193Claire MAIZA, Pascal RAYMOND and Christine ROCHANGE5.1. Worst-case execution time analysis: an example 1955.1.1. Embedded system architecture analysis 1975.1.2. Execution path analysis 2065.2. Going further 2115.2.1. Multi-task: the cost of preemption 2115.2.2. Multi-core and other complex architectures 2155.2.3. Influence of critical embedded systems design methods 2185.2.4. Tools 2245.3. Conclusion 2255.4. Bibliography 225CHAPTER 6. OPTIMIZATION OF ENERGY CONSUMPTION 231Cécile BELLEUDY6.1. Introduction 2326.2. State of the art 2356.2.1. General comments 2356.2.2. Modeling the consumption of an operating system 2376.2.3. Consumption management strategies within multicore systems 2386.3. Modeling consumption 2426.3.1. Characterization platform: hardware and software 2426.3.2. Power consumption modeling 2436.3.3. Context switch 2446.3.4. Inter-process communication 2476.4. Low consumption scheduling 2496.4.1. Simulation environment 2506.4.2. Low power consumption scheduling policy 2516.5. Experimental results 2556.5.1. Application test: H.264 decoder 2556.5.2. Analysis of the simulation results 2586.6. Conclusion 2626.7. Bibliography 262LIST OF AUTHORS 269INDEX 271SUMMARY 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.

• PREFACE xiLIST OF FIGURES xvLIST OF TABLES xxiCHAPTER 1. INTRODUCTION TO REAL-TIME SCHEDULING 1Emmanuel GROLLEAU1.1. Real-time systems 11.2. Material architectures 51.2.1. CPUs 51.2.2. Communication networks 71.2.3. Sensors and actuators 91.3. Operating systems 91.3.1. Generalities 101.3.2. Real-time operating systems 101.3.3. Primitives provided by the kernel 121.4. Scheduling 141.4.1. Online and offline scheduling 141.4.2. Task characterization 161.4.3. Criticality 191.4.4. Metrics related to scheduling 201.4.5. Practical factors 221.4.6. Multi-core scheduling 271.5. Real-time application modeling and analysis 301.5.1. Modeling 301.5.2. Analysis 311.6. System architecture and schedulability 34CHAPTER 2. UNIPROCESSOR ARCHITECTURE SOLUTIONS 39Laurent GEORGE and Jean-François HERMANT2.1. Introduction 402.2. Characterization of a scheduling problem 422.2.1. Task model 422.2.2. Temporal constraint models 452.2.3. Scheduling model 462.2.4. Concepts and notations 502.3. Scheduling algorithms/optimality 522.3.1. FP fixed-job priority algorithms 522.3.2. JFP algorithms 552.3.3. Dynamic priority algorithms 572.4. Busy periods and worst-case scenarios 582.4.1. Busy periods 582.4.2. Worst-case scenarios 602.5. Feasibility conditions 662.5.1. FP feasibility conditions 662.5.2. JFP feasibility conditions 702.6. Sensitivity analysis 752.6.1. Sensitivity of WCETs 782.6.2. Sensitivity of periods 882.6.3. Sensitivity of deadlines 902.7. Conclusion 952.8. Bibliography 97CHAPTER 3. MULTIPROCESSOR ARCHITECTURE SOLUTIONS 105Joël GOOSSENS and Pascal RICHARD3.1. Introduction 1053.1.1. Application modeling 1063.1.2. Platform modeling 1083.2. Scheduler classification 1083.2.1. Online and offline schedulers 1083.2.2. Task preemption and migration 1093.2.3. Priorities of tasks 1113.2.4. Classification 1113.3. Properties of schedulers 1113.3.1. Qualitative properties 1123.3.2. Quantitative properties 1173.4. Partitioned scheduling 1213.4.1. Partitioning algorithms 1213.4.2. Evaluation of partitioning algorithms 1263.5. Global scheduling 1313.5.1. Proportionate fair algorithms 1323.5.2. Generalization of uniprocessor scheduling algorithms 1423.6. Conclusion 1433.7. Bibliography 143CHAPTER 4. SYNCHRONIZATIONS: SHARED RESOURCE ACCESS PROTOCOLS 149Serge MIDONNET and Frédéric FAUBERTEAU4.1. Introduction 1504.2. Terminology and notations 1504.2.1. Diagrams 1524.2.2. Synchronization protocols 1534.3. Synchronization problems 1604.3.1. Unbounded priority inversion 1604.3.2. Deadlock 1664.3.3. Chained blocking 1724.4. Calculating the blocking factor 1774.4.1. The case of uniprocessor architectures 1774.4.2. The case of multiprocessor architectures 1804.5. Conclusion 1874.6. Bibliography 188CHAPTER 5. ESTIMATION OF EXECUTION TIME AND DELAYS 193Claire MAIZA, Pascal RAYMOND and Christine ROCHANGE5.1. Worst-case execution time analysis: an example 1955.1.1. Embedded system architecture analysis 1975.1.2. Execution path analysis 2065.2. Going further 2115.2.1. Multi-task: the cost of preemption 2115.2.2. Multi-core and other complex architectures 2155.2.3. Influence of critical embedded systems design methods 2185.2.4. Tools 2245.3. Conclusion 2255.4. Bibliography 225CHAPTER 6. OPTIMIZATION OF ENERGY CONSUMPTION 231Cécile BELLEUDY6.1. Introduction 2326.2. State of the art 2356.2.1. General comments 2356.2.2. Modeling the consumption of an operating system 2376.2.3. Consumption management strategies within multicore systems 2386.3. Modeling consumption 2426.3.1. Characterization platform: hardware and software 2426.3.2. Power consumption modeling 2436.3.3. Context switch 2446.3.4. Inter-process communication 2476.4. Low consumption scheduling 2496.4.1. Simulation environment 2506.4.2. Low power consumption scheduling policy 2516.5. Experimental results 2556.5.1. Application test: H.264 decoder 2556.5.2. Analysis of the simulation results 2586.6. Conclusion 2626.7. Bibliography 262LIST OF AUTHORS 269INDEX 271SUMMARY OF VOLUME 2 275