CONTENTSPreface to the Third Edition xvii1 Basic Real-Time Concepts 11.1 Terminology / 11.1.1 Systems Concepts / 21.1.2 Real-Time Definitions / 41.1.3 Events and Determinism / 71.1.4 CPU Utilization / 101.2 Real-Time System Design Issues / 121.3 Example Real-Time Systems / 131.4 Common Misconceptions / 151.5 Brief History / 161.5.1 Theoretical Advances / 171.5.2 Early Systems / 171.5.3 Hardware Developments / 181.5.4 Early Software / 181.5.5 Commercial Operating System Support / 191.6 Exercises / 202 Hardware Considerations 232.1 Basic Architecture / 232.2 Hardware Interfacing / 242.2.1 Latching / 242.2.2 Edge versus Level Triggered / 252.2.3 Tristate Logic / 252.2.4 Wait States / 262.2.5 Systems Interfaces and Buses / 262.3 Central Processing Unit / 292.3.1 Fetch and Execute Cycle / 302.3.2 Microcontrollers / 30viiviii CONTENTS2.3.3 Instruction Forms / 312.3.4 Core Instructions / 332.3.5 Addressing Modes / 362.3.6 RISC versus CISC / 372.4 Memory / 382.4.1 Memory Access / 392.4.2 Memory Technologies / 392.4.3 Memory Hierarchy / 422.4.4 Memory Organization / 432.5 Input/Output / 442.5.1 Programmed Input/Output / 442.5.2 Direct Memory Access / 452.5.3 Memory-Mapped Input/Output / 462.5.4 Interrupts / 482.6 Enhancing Performance / 552.6.1 Locality of Reference / 552.6.2 Cache / 552.6.3 Pipelining / 562.6.4 Coprocessors / 582.7 Other Special Devices / 582.7.1 Applications-Specific Integrated Circuits / 582.7.2 Programmable Array Logic/Programmable LogicArray / 592.7.3 Field-Programmable Gate Arrays / 592.7.4 Transducers / 622.7.5 Analog/Digital Converters / 642.7.6 Digital/Analog Converters / 642.8 Non-von-Neumann Architectures / 642.8.1 Parallel Systems / 652.8.2 Flynn’s Taxonomy for Parallelism / 652.9 Exercises / 703 Real-Time Operating Systems 733.1 Real-Time Kernels / 733.1.1 Pseudokernels / 743.1.2 Interrupt-Driven Systems / 793.1.3 Preemptive-Priority Systems / 823.1.4 Hybrid Systems / 833.1.5 The Task-Control Block Model / 863.2 Theoretical Foundations of Real-Time Operating Systems / 883.2.1 Process Scheduling / 903.2.2 Round-Robin Scheduling / 913.2.3 Cyclic Executives / 92CONTENTS ix3.2.4 Fixed-Priority SchedulingCRate-MonotonicApproach / 943.2.5 Dynamic-Priority Scheduling: Earliest-DeadlineCFirstApproach / 963.3 Intertask Communication and Synchronization / 983.3.1 Buffering Data / 993.3.2 Time-Relative Buffering / 993.3.3 Ring Buffers / 1013.3.4 Mailboxes / 1023.3.5 Queues / 1043.3.6 Critical Regions / 1043.3.7 Semaphores / 1053.3.8 Other Synchronization Mechanisms / 1113.3.9 Deadlock / 1113.3.10 Priority Inversion / 1173.4 Memory Management / 1223.4.1 Process Stack Management / 1223.4.2 Run-Time Ring Buffer / 1263.4.3 Maximum Stack Size / 1263.4.4 Multiple-Stack Arrangements / 1263.4.5 Memory Management in the Task-Control-BlockModel / 1273.4.6 Swapping / 1283.4.7 Overlays / 1283.4.8 Block or Page Management / 1293.4.9 Replacement Algorithms / 1313.4.10 Memory Locking / 1323.4.11 Working Sets / 1323.4.12 Real-Time Garbage Collection / 1323.4.13 Contiguous File Systems / 1333.4.14 Building versus Buying Real-Time OperatingSystems / 1333.4.15 Selecting Real-Time Kernels / 1343.5 Case Study: POSIX / 1393.5.1 Threads / 1393.5.2 POSIX Mutexes and Condition Variables / 1423.5.3 POSIX Semaphores / 1433.5.4 Using Semaphores and Shared Memory / 1443.5.5 POSIX Messages / 1453.5.6 Real-Time POSIX Signals / 1483.5.7 Clocks and Timers / 1493.5.8 Asynchronous Input and Output / 1533.5.9 POSIX Memory Locking / 1543.6 Exercises / 156x CONTENTS4 Software Requirements Engineering 1614.1 Requirements-Engineering process / 1614.2 Types of Requirements / 1624.3 Requirements Specification for Real-Time Systems / 1644.4 Formal Methods in Software Specification / 1654.4.1 Limitations of Formal Methods / 1674.4.2 Z / 1684.4.3 Finite State Machines / 1684.4.4 Statecharts / 1724.4.5 Petri Nets / 1744.4.6 Requirements Analysis with Petri Nets / 1774.5 Structured Analysis and Design / 1784.6 Object-Oriented Analysis and the Unified ModelingLanguage / 1804.6.1 Use Cases / 1814.6.2 Class Diagram / 1824.6.3 Recommendations on Specification Approach forReal-Time Systems / 1824.7 Organizing the Requirements Document / 1834.8 Organizing and Writing Requirements / 1844.9 Requirements Validation and Review / 1864.9.1 Requirements Validation Using Model Checking / 1874.9.2 Automated Checking of Requirements / 1874.10 Appendix: Case Study in Software Requirements Specificationfor Four-Way Traffic Intersection Traffic Light ControllerSystem / 1904.11 Exercises / 2225 Software System Design 2255.1 Properties of Software / 2255.1.1 Reliability / 2265.1.2 Correctness / 2285.1.3 Performance / 2285.1.4 Usability / 2295.1.5 Interoperability / 2295.1.6 Maintainability / 2295.1.7 Portability / 2305.1.8 Verifiability / 2305.1.9 Summary of Software Properties and AssociatedMetrics / 2315.2 Basic Software Engineering Principles / 2315.2.1 Rigor and Formality / 2315.2.2 Separation of Concerns / 231CONTENTS xi5.2.3 Modularity / 2325.2.4 Anticipation of Change / 2345.2.5 Generality / 2355.2.6 Incrementality / 2355.2.7 Traceability / 2355.3 The Design Activity / 2365.4 Procedural-Oriented Design / 2375.4.1 Parnas Partitioning / 2385.4.2 Structured Design / 2395.4.3 Design in Procedural Form Using Finite StateMachines / 2465.5 Object-Oriented Design / 2475.5.1 Benefits of Object Orientation / 2485.5.2 Design Patterns / 2495.5.3 Object-Oriented Design Using the Unified ModelingLanguage / 2505.6 Appendix: Case Study in Software Requirements Specificationfor Four-Way Traffic Intersection Traffic Light ControllerSystem / 2555.7 Exercises / 3186 Programming Languages and the Software Production Process 3216.1 Introduction / 3216.2 Assembly Language / 3226.3 Procedural Languages / 3236.3.1 Parameter Passing Techniques / 3246.3.2 Call-by-Value and Call-by-Reference / 3246.3.3 Global Variables / 3256.3.4 Recursion / 3256.3.5 Dynamic Memory Allocation / 3256.3.6 Typing / 3266.3.7 Exception Handling / 3276.3.8 Modularity / 3286.3.9 Cardelli’s Metrics and Procedural Languages / 3296.4 Object-Oriented Languages / 3296.4.1 Synchronizing Objects / 3306.4.2 Garbage Collection / 3316.4.3 Cardelli’s Metrics and Object-Oriented Languages / 3336.4.4 Object-Oriented versus Procedural Languages / 3346.5 Brief Survey of Languages / 3366.5.1 Ada 95 / 3366.5.2 C / 3376.5.3 C++ / 3386.5.4 C# / 339xii CONTENTS6.5.5 Fortran / 3406.5.6 Java / 3416.5.7 Occam 2 / 3456.5.8 Special Real-Time Languages / 3466.5.9 Know the Compiler and Rules of Thumb / 3466.6 Coding Standards / 3476.7 Exercises / 3497 Performance Analysis And Optimization 3517.1 Theoretical Preliminaries / 3517.1.1 NP-Completeness / 3517.1.2 Challenges in Analyzing Real-Time Systems / 3527.1.3 The Halting Problem / 3537.1.4 Amdahl’s Law / 3557.1.5 Gustafson’s Law / 3567.2 Performance Analysis / 3577.2.1 Code Execution Time Estimation / 3577.2.2 Analysis of Polled Loops / 3647.2.3 Analysis of Coroutines / 3647.2.4 Analysis of Round-Robin Systems / 3647.2.5 Response-Time Analysis for Fixed-Period Systems / 3677.2.6 Response-Time Analysis: RMA Example / 3687.2.7 Analysis of Sporadic and Aperiodic InterruptSystems / 3687.2.8 Deterministic Performance / 3697.3 Application of Queuing Theory / 3707.3.1 The M/M/1 Queue / 3707.3.2 Service and Production Rates / 3717.3.3 Some Buffer-Size Calculations / 3727.3.4 Response-Time Modeling / 3727.3.5 Other Results from Queuing Theory / 3737.3.6 Little’s Law / 3737.3.7 Erlang’s Formula / 3747.4 I/O Performance / 3757.4.1 Basic Buffer-Size Calculation / 3757.4.2 Variable Buffer-Size Calculation / 3767.5 Performance Optimization / 3777.5.1 Compute at Slowest Cycle / 3777.5.2 Scaled Numbers / 3777.5.3 Binary Angular Measure / 3787.5.4 Look-Up Tables / 3797.5.5 Imprecise Computation / 3807.5.6 Optimizing Memory Usage / 3817.5.7 Postintegration Software Optimization / 381CONTENTS xiii7.6 Results from Compiler Optimization / 3817.6.1 Use of Arithmetic Identifies / 3827.6.2 Reduction in Strength / 3827.6.3 Common Subexpression Elimination / 3837.6.4 Intrinsic Functions / 3837.6.5 Constant Folding / 3837.6.6 Loop Invariant Optimization / 3847.6.7 Loop Induction Elimination / 3847.6.8 Use of Registers and Caches / 3857.6.9 Removal of Dead or Unreachable Code / 3857.6.10 Flow-of-Control Optimization / 3857.6.11 Constant Propagation / 3867.6.12 Dead-Store Elimination / 3867.6.13 Dead-Variable Elimination / 3877.6.14 Short-Circuiting Boolean Code / 3877.6.15 Loop Unrolling / 3877.6.16 Loop Jamming / 3887.6.17 More Optimization Techniques / 3897.6.18 Combination Effects / 3907.6.19 Speculative Execution / 3917.7 Analysis of Memory Requirements / 3917.8 Reducing Memory Utilization / 3927.8.1 Variable Selection / 3927.8.2 Memory Fragmentation / 3937.9 Exercises / 3938 Engineering Considerations 3978.1 Metrics / 3978.1.1 Lines of Code / 3978.1.2 McCabe’s Metric / 3988.1.3 Halstead’s Metrics / 3998.1.4 Function Points / 4018.1.5 Feature Points / 4048.1.6 Metrics for Object-Oriented Software / 4058.1.7 Objections to Metrics / 4068.1.8 Best Practices / 4068.2 Faults, Failures, and Bugs / 4068.2.1 The Role of Testing / 4078.2.2 Testing Techniques / 4078.2.3 System-Level Testing / 4138.2.4 Design of Testing Plans / 4158.3 Fault-Tolerance / 4158.3.1 Spatial Fault-Tolerance / 4168.3.2 Software Black Boxes / 417xiv CONTENTS8.3.3 N-Version Programming / 4188.3.4 Built-In-Test Software / 4188.3.5 CPU Testing / 4188.3.6 Memory Testing / 4198.3.7 ROM / 4198.3.8 RAM / 4208.3.9 Other Devices / 4228.3.10 Spurious and Missed Interrupts / 4228.3.11 Handling Spurious and Missed Interrupts / 4228.3.12 The Kalman Filter / 4238.4 Systems Integration / 4248.4.1 Goals of System Integration / 4258.4.2 System Unification / 4258.4.3 System Verification / 4258.4.4 System Integration Tools / 4268.4.5 A Simple Integration Strategy / 4298.4.6 Patching / 4308.4.7 The Probe Effect / 4318.4.8 Fault-Tolerant Design: A Case Study / 4328.5 Refactoring Real-Time Code / 4368.5.1 Conditional Logic / 4368.5.2 Data Clumps / 4368.5.3 Delays as Loops / 4378.5.4 Dubious Constraints / 4378.5.5 Duplicated Code / 4378.5.6 Generalizations Based on a Single Architecture / 4388.5.7 Large Procedures / 4388.5.8 Lazy Procedure / 4388.5.9 Long Parameter List / 4388.5.10 Message-Passing Overload / 4388.5.11 Self-Modifying Code / 4398.5.12 Speculative Generality / 4398.5.13 Telltale Comments / 4398.5.14 Unnecessary Use of Interrupts / 4398.6 Cost Estimation Using COCOMO / 4408.6.1 Basic COCOMO / 4408.6.2 Intermediate and Detailed COCOMO / 4418.6.3 COCOMO II / 4428.7 Exercises / 443CONTENTS xvGlossary 445Bibliography 475Index 487About the Author 505……