1 TYPICAL REAL-TIME APPLICATIONS 1
1.1 Digital Control 2
1.2 High-Level Controls 10
1.3 Signal Processing 14
1.4 Other Real-Time Applications 19
1.5 Summary 25
2 HARD VERSUS SOFT REAL-TIME SYSTEMS 26
2.1 Jobs and Processors 26
2.2 Release Times,Deadlines,and Timing Constraints 27
2.3 Hard and Soft Timing Constraints 27
2.4 Hard Real-Time Systems 29
2.5 Soft Real-Time Systems 31
2.6 Summary 32
3 A REFERENCE MODEL OF REAL-TIME SYSTEMS 34
3.1 Processors and Resources 35
3.2 Temporal Parameters of Real-Time Workload 37
3.3 Periodic Task Model 40
3.4 Precedence Constraints and Data Dependency 42
3.5 Other Types of Dependencies 45
3.6 Functional Parameters 48
3.7 Resource Parameters of Jobs and Parameters of Resources 51
3.8 Scheduling Hierarchy 52
3.9 Summary 56
4 COMMONLY USED APPROACHES TO REAL-TIME SCHEDULING 60
4.1 Clock-Driven Approach 60
4.2 Weighted Round-Robin Approach 61
4.3 Priority-Driven Approach 62
4.5 Effective Release Times and Deadlines 65
4.4 Dynamic versus Static Systems 65
4.6 Optimality of the EDF and LST Algorithms 67
4.7 Nonoptimality of the EDF and the LST Algorithms 70
4.8 Challenges in Validating Timing Constraints in Priority-Driven Systems 72
4.9 Off-Line versus On-Line Scheduling 77
4.10 Summary 81
4.11 Exercises 82
5 CLOCK-DRIVENSCHEDULING 85
5.1 Notations and Assumptions 85
5.2 Static,Timer-Driven Scheduler 86
5.3 General Structure of Cyclic Schedules 88
5.4 Cyclic Executives 90
5.5 Improving the Average Response Time of Aperiodic Jobs 92
5.6 Scheduling Sporadic Jobs 96
5.7 Practical Considerations and Generalizations 102
5.8 Algorithm for Constructing Static Schedules 106
5.9 Pros and Cons of Clock-Driven Scheduling 111
5.10 Summary 113
6 PRIORITY-DRIVEN SCHEDULING OF PERIODIC TASKS 115
6.1 Static Assumption 116
6.2 Fixed-Priority versus Dynamic-Priority Algorithms 117
6.3 Maximum Schedulable Utilization 124
6.4 Optimality of the RM and DM Algorithms 129
6.5 A Schedulability Test for Fixed-Priority Tasks with Short Response Times 130
6.6 Schedulability Test for Fixed-Priority Tasks with Arbitrary Response Times 140
6.7 Sufficient Schedulability Conditions for the RM and DM Algorithms 146
6.8 Practical Factors 159
6.9 Summary 179
7.1 Assumptions and Approaches 190
7 SCHEDULING APERIODIC AND SPORADIC JOBS IN PRIORITY-DRIVEN SYSTEMS 190
7.2 Deferrable Servers 195
7.3 Sporadic Servers 204
7.4 Constant Utilization,Total Bandwidth,and Weighted Fair-Queueing Servers 218
7.5 Slack Stealing in Deadline-Driven Systems 233
7.6 Slack Stealing in Fixed-Priority Systems 244
7.7 Scheduling of Sporadic Jobs 250
7.8 Real-Time Performance for Jobs with Soft Timing Constraints 259
7.9 A Two-Level Scheme for Integrated Scheduling 263
7.10 Summary 267
8 RESOURCES AND RESOURCE ACCESS CONTROL 277
8.1 Assumptions on Resources and Their Usage 277
8.2 Effects of Resource Contention and Resource Access Control 280
8.3 Nonpreemptive Critical Sections 284
8.4 Basic Priority-Inheritance Protocol 286
8.5 Basic Priority-Ceiling Protocol 290
8.6 Stack-Based,Priority-Ceiling(Ceiling-Priority) Protocol 300
8.7 Use of Priority-Ceiling Protocol in Dynamic-Priority Systems 304
8.8 Preemption-Ceiling Protocol 308
8.9 Controlling Accesses to Multiple-Unit Resources 313
8.10 Controlling Concurrent Accesses to Data Objects 317
8.11 Summary 322
9 MU TIPROCESSOR SCHEDULING,RESOURCE ACCESS CONTROL,AND SYNCHRONIZATION 330
9.1 Model ofMultiprocessor and Distributed Systems 331
9.2 Task Assignment 339
9.3 Multiprocessor Priority-Ceiling Protocol 352
9.4 Elements of Scheduling Algorithms for End-to-End Periodic Tasks 360
9.5 Schedulability of Fixed-Priority End-to-End Periodic Tasks 371
9.6 End-to-End Tasks in Heterogeneous Systems 384
9.7 Predictability and Validation of Dynamic Multiprocessor Systems 386
9.8 Summary 387
10 SCHEDULING FLEXIBLE COMPUTATIONS AND TASKS WITH TEMPORAL DISTANCE CONSTRAINTS 394
10.1 Flexible Applications 395
10.2 Tasks with Temporal Distance Constraints 411
10.3 Summary 417
11 REAL-TIME COMMUNICATION 420
11.1 Model of Real-Time Communication 421
11.2 Priority-Based Service Disciplines for Switched Networks 429
11.3 Weighted Round-Robin Service Disciplines 445
11.4 Medium Access-Control Protocols of Broadcast Networks 453
11.5 Internet and Resource Reservation Protocols 469
11.6 Real-Time Protocol 480
11.7 Communication in Multicomputer Systems 485
11.8 Summary 489
12 OPERATING SYSTEMS 497
12.1 Overview 498
12.2 Time Services and Scheduling Mechanisms 507
12.3 Other Basic Operating System Functions 523
12.4 Processor Reserves and Resource Kernel 534
12.5 Open System Architecture 538
12.6 Capabilities of Commercial Real-Time Operating Systems 549
12.7 Predictability of General-Purpose Operating Systems 556
12.8 Summary 564
APPENDIX POSIX THREAD AND REAL-TIME EXTENSIONS 571
BIBLIOGRAPHY 577
INDEX 589