Real–time Systems Scheduling Volume 1

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