Real-timesystemsdesignandanalysis3e

CONTENTS
Preface to the Third Edition xvii
1 Basic Real-Time Concepts 1
1.1 Terminology / 1
1.1.1 Systems Concepts / 2
1.1.2 Real-Time Definitions / 4
1.1.3 Events and Determinism / 7
1.1.4 CPU Utilization / 10
1.2 Real-Time System Design Issues / 12
1.3 Example Real-Time Systems / 13
1.4 Common Misconceptions / 15
1.5 Brief History / 16
1.5.1 Theoretical Advances / 17
1.5.2 Early Systems / 17
1.5.3 Hardware Developments / 18
1.5.4 Early Software / 18
1.5.5 Commercial Operating System Support / 19
1.6 Exercises / 20
2 Hardware Considerations 23
2.1 Basic Architecture / 23
2.2 Hardware Interfacing / 24
2.2.1 Latching / 24
2.2.2 Edge versus Level Triggered / 25
2.2.3 Tristate Logic / 25
2.2.4 Wait States / 26
2.2.5 Systems Interfaces and Buses / 26
2.3 Central Processing Unit / 29
2.3.1 Fetch and Execute Cycle / 30
2.3.2 Microcontrollers / 30
vii
viii CONTENTS
2.3.3 Instruction Forms / 31
2.3.4 Core Instructions / 33
2.3.5 Addressing Modes / 36
2.3.6 RISC versus CISC / 37
2.4 Memory / 38
2.4.1 Memory Access / 39
2.4.2 Memory Technologies / 39
2.4.3 Memory Hierarchy / 42
2.4.4 Memory Organization / 43
2.5 Input/Output / 44
2.5.1 Programmed Input/Output / 44
2.5.2 Direct Memory Access / 45
2.5.3 Memory-Mapped Input/Output / 46
2.5.4 Interrupts / 48
2.6 Enhancing Performance / 55
2.6.1 Locality of Reference / 55
2.6.2 Cache / 55
2.6.3 Pipelining / 56
2.6.4 Coprocessors / 58
2.7 Other Special Devices / 58
2.7.1 Applications-Specific Integrated Circuits / 58
2.7.2 Programmable Array Logic/Programmable Logic
Array / 59
2.7.3 Field-Programmable Gate Arrays / 59
2.7.4 Transducers / 62
2.7.5 Analog/Digital Converters / 64
2.7.6 Digital/Analog Converters / 64
2.8 Non-von-Neumann Architectures / 64
2.8.1 Parallel Systems / 65
2.8.2 Flynn’s Taxonomy for Parallelism / 65
2.9 Exercises / 70
3 Real-Time Operating Systems 73
3.1 Real-Time Kernels / 73
3.1.1 Pseudokernels / 74
3.1.2 Interrupt-Driven Systems / 79
3.1.3 Preemptive-Priority Systems / 82
3.1.4 Hybrid Systems / 83
3.1.5 The Task-Control Block Model / 86
3.2 Theoretical Foundations of Real-Time Operating Systems / 88
3.2.1 Process Scheduling / 90
3.2.2 Round-Robin Scheduling / 91
3.2.3 Cyclic Executives / 92
CONTENTS ix
3.2.4 Fixed-Priority SchedulingCRate-Monotonic
Approach / 94
3.2.5 Dynamic-Priority Scheduling: Earliest-DeadlineCFirst
Approach / 96
3.3 Intertask Communication and Synchronization / 98
3.3.1 Buffering Data / 99
3.3.2 Time-Relative Buffering / 99
3.3.3 Ring Buffers / 101
3.3.4 Mailboxes / 102
3.3.5 Queues / 104
3.3.6 Critical Regions / 104
3.3.7 Semaphores / 105
3.3.8 Other Synchronization Mechanisms / 111
3.3.9 Deadlock / 111
3.3.10 Priority Inversion / 117
3.4 Memory Management / 122
3.4.1 Process Stack Management / 122
3.4.2 Run-Time Ring Buffer / 126
3.4.3 Maximum Stack Size / 126
3.4.4 Multiple-Stack Arrangements / 126
3.4.5 Memory Management in the Task-Control-Block
Model / 127
3.4.6 Swapping / 128
3.4.7 Overlays / 128
3.4.8 Block or Page Management / 129
3.4.9 Replacement Algorithms / 131
3.4.10 Memory Locking / 132
3.4.11 Working Sets / 132
3.4.12 Real-Time Garbage Collection / 132
3.4.13 Contiguous File Systems / 133
3.4.14 Building versus Buying Real-Time Operating
Systems / 133
3.4.15 Selecting Real-Time Kernels / 134
3.5 Case Study: POSIX / 139
3.5.1 Threads / 139
3.5.2 POSIX Mutexes and Condition Variables / 142
3.5.3 POSIX Semaphores / 143
3.5.4 Using Semaphores and Shared Memory / 144
3.5.5 POSIX Messages / 145
3.5.6 Real-Time POSIX Signals / 148
3.5.7 Clocks and Timers / 149
3.5.8 Asynchronous Input and Output / 153
3.5.9 POSIX Memory Locking / 154
3.6 Exercises / 156
x CONTENTS
4 Software Requirements Engineering 161
4.1 Requirements-Engineering process / 161
4.2 Types of Requirements / 162
4.3 Requirements Specification for Real-Time Systems / 164
4.4 Formal Methods in Software Specification / 165
4.4.1 Limitations of Formal Methods / 167
4.4.2 Z / 168
4.4.3 Finite State Machines / 168
4.4.4 Statecharts / 172
4.4.5 Petri Nets / 174
4.4.6 Requirements Analysis with Petri Nets / 177
4.5 Structured Analysis and Design / 178
4.6 Object-Oriented Analysis and the Unified Modeling
Language / 180
4.6.1 Use Cases / 181
4.6.2 Class Diagram / 182
4.6.3 Recommendations on Specification Approach for
Real-Time Systems / 182
4.7 Organizing the Requirements Document / 183
4.8 Organizing and Writing Requirements / 184
4.9 Requirements Validation and Review / 186
4.9.1 Requirements Validation Using Model Checking / 187
4.9.2 Automated Checking of Requirements / 187
4.10 Appendix: Case Study in Software Requirements Specification
for Four-Way Traffic Intersection Traffic Light Controller
System / 190
4.11 Exercises / 222
5 Software System Design 225
5.1 Properties of Software / 225
5.1.1 Reliability / 226
5.1.2 Correctness / 228
5.1.3 Performance / 228
5.1.4 Usability / 229
5.1.5 Interoperability / 229
5.1.6 Maintainability / 229
5.1.7 Portability / 230
5.1.8 Verifiability / 230
5.1.9 Summary of Software Properties and Associated
Metrics / 231
5.2 Basic Software Engineering Principles / 231
5.2.1 Rigor and Formality / 231
5.2.2 Separation of Concerns / 231
CONTENTS xi
5.2.3 Modularity / 232
5.2.4 Anticipation of Change / 234
5.2.5 Generality / 235
5.2.6 Incrementality / 235
5.2.7 Traceability / 235
5.3 The Design Activity / 236
5.4 Procedural-Oriented Design / 237
5.4.1 Parnas Partitioning / 238
5.4.2 Structured Design / 239
5.4.3 Design in Procedural Form Using Finite State
Machines / 246
5.5 Object-Oriented Design / 247
5.5.1 Benefits of Object Orientation / 248
5.5.2 Design Patterns / 249
5.5.3 Object-Oriented Design Using the Unified Modeling
Language / 250
5.6 Appendix: Case Study in Software Requirements Specification
for Four-Way Traffic Intersection Traffic Light Controller
System / 255
5.7 Exercises / 318
6 Programming Languages and the Software Production Process 321
6.1 Introduction / 321
6.2 Assembly Language / 322
6.3 Procedural Languages / 323
6.3.1 Parameter Passing Techniques / 324
6.3.2 Call-by-Value and Call-by-Reference / 324
6.3.3 Global Variables / 325
6.3.4 Recursion / 325
6.3.5 Dynamic Memory Allocation / 325
6.3.6 Typing / 326
6.3.7 Exception Handling / 327
6.3.8 Modularity / 328
6.3.9 Cardelli’s Metrics and Procedural Languages / 329
6.4 Object-Oriented Languages / 329
6.4.1 Synchronizing Objects / 330
6.4.2 Garbage Collection / 331
6.4.3 Cardelli’s Metrics and Object-Oriented Languages / 333
6.4.4 Object-Oriented versus Procedural Languages / 334
6.5 Brief Survey of Languages / 336
6.5.1 Ada 95 / 336
6.5.2 C / 337
6.5.3 C++ / 338
6.5.4 C# / 339
xii CONTENTS
6.5.5 Fortran / 340
6.5.6 Java / 341
6.5.7 Occam 2 / 345
6.5.8 Special Real-Time Languages / 346
6.5.9 Know the Compiler and Rules of Thumb / 346
6.6 Coding Standards / 347
6.7 Exercises / 349
7 Performance Analysis And Optimization 351
7.1 Theoretical Preliminaries / 351
7.1.1 NP-Completeness / 351
7.1.2 Challenges in Analyzing Real-Time Systems / 352
7.1.3 The Halting Problem / 353
7.1.4 Amdahl’s Law / 355
7.1.5 Gustafson’s Law / 356
7.2 Performance Analysis / 357
7.2.1 Code Execution Time Estimation / 357
7.2.2 Analysis of Polled Loops / 364
7.2.3 Analysis of Coroutines / 364
7.2.4 Analysis of Round-Robin Systems / 364
7.2.5 Response-Time Analysis for Fixed-Period Systems / 367
7.2.6 Response-Time Analysis: RMA Example / 368
7.2.7 Analysis of Sporadic and Aperiodic Interrupt
Systems / 368
7.2.8 Deterministic Performance / 369
7.3 Application of Queuing Theory / 370
7.3.1 The M/M/1 Queue / 370
7.3.2 Service and Production Rates / 371
7.3.3 Some Buffer-Size Calculations / 372
7.3.4 Response-Time Modeling / 372
7.3.5 Other Results from Queuing Theory / 373
7.3.6 Little’s Law / 373
7.3.7 Erlang’s Formula / 374
7.4 I/O Performance / 375
7.4.1 Basic Buffer-Size Calculation / 375
7.4.2 Variable Buffer-Size Calculation / 376
7.5 Performance Optimization / 377
7.5.1 Compute at Slowest Cycle / 377
7.5.2 Scaled Numbers / 377
7.5.3 Binary Angular Measure / 378
7.5.4 Look-Up Tables / 379
7.5.5 Imprecise Computation / 380
7.5.6 Optimizing Memory Usage / 381
7.5.7 Postintegration Software Optimization / 381
CONTENTS xiii
7.6 Results from Compiler Optimization / 381
7.6.1 Use of Arithmetic Identifies / 382
7.6.2 Reduction in Strength / 382
7.6.3 Common Subexpression Elimination / 383
7.6.4 Intrinsic Functions / 383
7.6.5 Constant Folding / 383
7.6.6 Loop Invariant Optimization / 384
7.6.7 Loop Induction Elimination / 384
7.6.8 Use of Registers and Caches / 385
7.6.9 Removal of Dead or Unreachable Code / 385
7.6.10 Flow-of-Control Optimization / 385
7.6.11 Constant Propagation / 386
7.6.12 Dead-Store Elimination / 386
7.6.13 Dead-Variable Elimination / 387
7.6.14 Short-Circuiting Boolean Code / 387
7.6.15 Loop Unrolling / 387
7.6.16 Loop Jamming / 388
7.6.17 More Optimization Techniques / 389
7.6.18 Combination Effects / 390
7.6.19 Speculative Execution / 391
7.7 Analysis of Memory Requirements / 391
7.8 Reducing Memory Utilization / 392
7.8.1 Variable Selection / 392
7.8.2 Memory Fragmentation / 393
7.9 Exercises / 393
8 Engineering Considerations 397
8.1 Metrics / 397
8.1.1 Lines of Code / 397
8.1.2 McCabe’s Metric / 398
8.1.3 Halstead’s Metrics / 399
8.1.4 Function Points / 401
8.1.5 Feature Points / 404
8.1.6 Metrics for Object-Oriented Software / 405
8.1.7 Objections to Metrics / 406
8.1.8 Best Practices / 406
8.2 Faults, Failures, and Bugs / 406
8.2.1 The Role of Testing / 407
8.2.2 Testing Techniques / 407
8.2.3 System-Level Testing / 413
8.2.4 Design of Testing Plans / 415
8.3 Fault-Tolerance / 415
8.3.1 Spatial Fault-Tolerance / 416
8.3.2 Software Black Boxes / 417
xiv CONTENTS
8.3.3 N-Version Programming / 418
8.3.4 Built-In-Test Software / 418
8.3.5 CPU Testing / 418
8.3.6 Memory Testing / 419
8.3.7 ROM / 419
8.3.8 RAM / 420
8.3.9 Other Devices / 422
8.3.10 Spurious and Missed Interrupts / 422
8.3.11 Handling Spurious and Missed Interrupts / 422
8.3.12 The Kalman Filter / 423
8.4 Systems Integration / 424
8.4.1 Goals of System Integration / 425
8.4.2 System Unification / 425
8.4.3 System Verification / 425
8.4.4 System Integration Tools / 426
8.4.5 A Simple Integration Strategy / 429
8.4.6 Patching / 430
8.4.7 The Probe Effect / 431
8.4.8 Fault-Tolerant Design: A Case Study / 432
8.5 Refactoring Real-Time Code / 436
8.5.1 Conditional Logic / 436
8.5.2 Data Clumps / 436
8.5.3 Delays as Loops / 437
8.5.4 Dubious Constraints / 437
8.5.5 Duplicated Code / 437
8.5.6 Generalizations Based on a Single Architecture / 438
8.5.7 Large Procedures / 438
8.5.8 Lazy Procedure / 438
8.5.9 Long Parameter List / 438
8.5.10 Message-Passing Overload / 438
8.5.11 Self-Modifying Code / 439
8.5.12 Speculative Generality / 439
8.5.13 Telltale Comments / 439
8.5.14 Unnecessary Use of Interrupts / 439
8.6 Cost Estimation Using COCOMO / 440
8.6.1 Basic COCOMO / 440
8.6.2 Intermediate and Detailed COCOMO / 441
8.6.3 COCOMO II / 442
8.7 Exercises / 443
CONTENTS xv
Glossary 445
Bibliography 475
Index 487
About the Author 505