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.
Edited by:
Maryline Chetto
Imprint: ISTE Ltd and John Wiley & Sons Inc
Country of Publication: United Kingdom
Dimensions:
Height: 243mm,
Width: 164mm,
Spine: 23mm
Weight: 594g
ISBN: 9781848216655
ISBN 10: 1848216653
Pages: 308
Publication Date: 07 November 2014
Audience:
Professional and scholarly
,
Undergraduate
Format: Hardback
Publisher's Status: Active
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."
