| |
| |
| Preface to the Third Edition | |
| |
| |
| Basic Real-Time Concepts | |
| |
| |
| Terminology | |
| |
| |
| Systems Concepts | |
| |
| |
| Real-Time Definitions | |
| |
| |
| Events and Determinism | |
| |
| |
| CPU Utilization | |
| |
| |
| Real-Time System Design Issues | |
| |
| |
| Example Real-Time Systems | |
| |
| |
| Common Misconceptions | |
| |
| |
| Brief History | |
| |
| |
| Theoretical Advances | |
| |
| |
| Early Systems | |
| |
| |
| Hardware Developments | |
| |
| |
| Early Software | |
| |
| |
| Commercial Operating System Support | |
| |
| |
| Exercises | |
| |
| |
| Hardware Considerations | |
| |
| |
| Basic Architecture | |
| |
| |
| Hardware Interfacing | |
| |
| |
| Latching | |
| |
| |
| Edge versus Level Triggered | |
| |
| |
| Tristate Logic | |
| |
| |
| Wait States | |
| |
| |
| Systems Interfaces and Buses | |
| |
| |
| Central Processing Unit | |
| |
| |
| Fetch and Execute Cycle | |
| |
| |
| Microcontrollers | |
| |
| |
| Instruction Forms | |
| |
| |
| Core Instructions | |
| |
| |
| Addressing Modes | |
| |
| |
| RISC versus CISC | |
| |
| |
| Memory | |
| |
| |
| Memory Access | |
| |
| |
| Memory Technologies | |
| |
| |
| Memory Hierarchy | |
| |
| |
| Memory Organization | |
| |
| |
| Input/Output | |
| |
| |
| Programmed Input/Output | |
| |
| |
| Direct Memory Access | |
| |
| |
| Memory-Mapped Input/Output | |
| |
| |
| Interrupts | |
| |
| |
| Enhancing Performance | |
| |
| |
| Locality of Reference | |
| |
| |
| Cache | |
| |
| |
| Pipelining | |
| |
| |
| Coprocessors | |
| |
| |
| Other Special Devices | |
| |
| |
| Applications-Specific Integrated Circuits | |
| |
| |
| Programmable Array Logic/Programmable Logic Array | |
| |
| |
| Field-Programmable Gate Arrays | |
| |
| |
| Transducers | |
| |
| |
| Analog/Digital Converters | |
| |
| |
| Digital/Analog Converters | |
| |
| |
| Non-von-Neumann Architectures | |
| |
| |
| Parallel Systems | |
| |
| |
| Flynn's Taxonomy for Parallelism | |
| |
| |
| Exercises | |
| |
| |
| Real-Time Operating Systems | |
| |
| |
| Real-Time Kernels | |
| |
| |
| Pseudokernels | |
| |
| |
| Interrupt-Driven Systems | |
| |
| |
| Preemptive-Priority Systems | |
| |
| |
| Hybrid Systems | |
| |
| |
| The Task-Control Block Model | |
| |
| |
| Theoretical Foundations of Real-Time Operating Systems | |
| |
| |
| Process Scheduling | |
| |
| |
| Round-Robin Scheduling | |
| |
| |
| Cyclic Executives | |
| |
| |
| Fixed-Priority Scheduling-Rate-Monotonic Approach | |
| |
| |
| Dynamic-Priority Scheduling: Earliest-Deadline-First Approach | |
| |
| |
| Intertask Communication and Synchronization | |
| |
| |
| Buffering Data | |
| |
| |
| Time-Relative Buffering | |
| |
| |
| Ring Buffers | |
| |
| |
| Mailboxes | |
| |
| |
| Queues | |
| |
| |
| Critical Regions | |
| |
| |
| Semaphores | |
| |
| |
| Other Synchronization Mechanisms | |
| |
| |
| Deadlock | |
| |
| |
| Priority Inversion | |
| |
| |
| Memory Management | |
| |
| |
| Process Stack Management | |
| |
| |
| Run-Time Ring Buffer | |
| |
| |
| Maximum Stack Size | |
| |
| |
| Multiple-Stack Arrangements | |
| |
| |
| Memory Management in the Task-Control-Block Model | |
| |
| |
| Swapping | |
| |
| |
| Overlays | |
| |
| |
| Block or Page Management | |
| |
| |
| Replacement Algorithms | |
| |
| |
| Memory Locking | |
| |
| |
| Working Sets | |
| |
| |
| Real-Time Garbage Collection | |
| |
| |
| Contiguous File Systems | |
| |
| |
| Building versus Buying Real-Time Operating Systems | |
| |
| |
| Selecting Real-Time Kernels | |
| |
| |
| Case Study: POSIX | |
| |
| |
| Threads | |
| |
| |
| POSIX Mutexes and Condition Variables | |
| |
| |
| POSIX Semaphores | |
| |
| |
| Using Semaphores and Shared Memory | |
| |
| |
| POSIX Messages | |
| |
| |
| Real-Time POSIX Signals | |
| |
| |
| Clocks and Timers | |
| |
| |
| Asynchronous Input and Output | |
| |
| |
| POSIX Memory Locking | |
| |
| |
| Exercises | |
| |
| |
| Software Requirements Engineering | |
| |
| |
| Requirements-Engineering process | |
| |
| |
| Types of Requirements | |
| |
| |
| Requirements Specification for Real-Time Systems | |
| |
| |
| Formal Methods in Software Specification | |
| |
| |
| Limitations of Formal Methods | |
| |
| |
| Z | |
| |
| |
| Finite State Machines | |
| |
| |
| Statecharts | |
| |
| |
| Petri Nets | |
| |
| |
| Requirements Analysis with Petri Nets | |
| |
| |
| Structured Analysis and Design | |
| |
| |
| Object-Oriented Analysis and the Unified Modeling Language | |
| |
| |
| Use Cases | |
| |
| |
| Class Diagram | |
| |
| |
| Recommendations on Specification Approach for Real-Time Systems | |
| |
| |
| Organizing the Requirements Document | |
| |
| |
| Organizing and Writing Requirements | |
| |
| |
| Requirements Validation and Review | |
| |
| |
| Requirements Validation Using Model Checking | |
| |
| |
| Automated Checking of Requirements | |
| |
| |
| Appendix: Case Study in Software Requirements Specification for Four-Way Traffic Intersection Traffic Light Controller System | |
| |
| |
| Exercises | |
| |
| |
| Software System Design | |
| |
| |
| Properties of Software | |
| |
| |
| Reliability | |
| |
| |
| Correctness | |
| |
| |
| Performance | |
| |
| |
| Usability | |
| |
| |
| Interoperability | |
| |
| |
| Maintainability | |
| |
| |
| Portability | |
| |
| |
| Verifiability | |
| |
| |
| Summary of Software Properties and Associated Metrics | |
| |
| |
| Basic Software Engineering Principles | |
| |
| |
| Rigor and Formality | |
| |
| |
| Separation of Concerns | |
| |
| |
| Modularity | |
| |
| |
| Anticipation of Change | |
| |
| |
| Generality | |
| |
| |
| Incrementality | |
| |
| |
| Traceability | |
| |
| |
| The Design Activity | |
| |
| |
| Procedural-Oriented Design | |
| |
| |
| Parnas Partitioning | |
| |
| |
| Structured Design | |
| |
| |
| Design in Procedural Form Using Finite State Machines | |
| |
| |
| Object-Oriented Design | |
| |
| |
| Benefits of Object Orientation | |
| |
| |
| Design Patterns | |
| |
| |
| Object-Oriented Design Using the Unified Modeling Language | |
| |
| |
| Appendix: Case Study in Software Requirements Specification for Four-Way Traffic Intersection Traffic Light Controller System | |
| |
| |
| Exercises | |
| |
| |
| Programming Languages and the Software Production Process | |
| |
| |
| Introduction | |
| |
| |
| Assembly Language | |
| |
| |
| Procedural Languages | |
| |
| |
| Parameter Passing Techniques | |
| |
| |
| Call-by-Value and Call-by-Reference | |
| |
| |
| Global Variables | |
| |
| |
| Recursion | |
| |
| |
| Dynamic Memory Allocation | |
| |
| |
| Typing | |
| |
| |
| Exception Handling | |
| |
| |
| Modularity | |
| |
| |
| Cardelli's Metrics and Procedural Languages | |
| |
| |
| Object-Oriented Languages | |
| |
| |
| Synchronizing Objects | |
| |
| |
| Garbage Collection | |
| |
| |
| Cardelli's Metrics and Object-Oriented Languages | |
| |
| |
| Object-Oriented versus Procedural Languages | |
| |
| |
| Brief Survey of Languages | |
| |
| |
| Ada 95 | |
| |
| |
| C | |
| |
| |
| C++ | |
| |
| |
| C# | |
| |
| |
| Fortran | |
| |
| |
| Java | |
| |
| |
| Occam 2 | |
| |
| |
| Special Real-Time Languages | |
| |
| |
| Know the Compiler and Rules of Thumb | |
| |
| |
| Coding Standards | |
| |
| |
| Exercises | |
| |
| |
| Performance Analysis And Optimization | |
| |
| |
| Theoretical Preliminaries | |
| |
| |
| NP-Completeness | |
| |
| |
| Challenges in Analyzing Real-Time Systems | |
| |
| |
| The Halting Problem | |
| |
| |
| Amdahl's Law | |
| |
| |
| Gustafson's Law | |
| |
| |
| Performance Analysis | |
| |
| |
| Code Execution Time Estimation | |
| |
| |
| Analysis of Polled Loops | |
| |
| |
| Analysis of Coroutines | |
| |
| |
| Analysis of Round-Robin Systems | |
| |
| |
| Response-Time Analysis for Fixed-Period Systems | |
| |
| |
| Response-Time Analysis: RMA Example | |
| |
| |
| Analysis of Sporadic and Aperiodic Interrupt Systems | |
| |
| |
| Deterministic Performance | |
| |
| |
| Application of Queuing Theory | |
| |
| |
| The M/M/1 Queue | |
| |
| |
| Service and Production Rates | |
| |
| |
| Some Buffer-Size Calculations | |
| |
| |
| Response-Time Modeling | |
| |
| |
| Other Results from Queuing Theory | |
| |
| |
| Little's Law | |
| |
| |
| Erlang's Formula | |
| |
| |
| I/O Performance | |
| |
| |
| Basic Buffer-Size Calculation | |
| |
| |
| Variable Buffer-Size Calculation | |
| |
| |
| Performance Optimization | |
| |
| |
| Compute at Slowest Cycle | |
| |
| |
| Scaled Numbers | |
| |
| |
| Binary Angular Measure | |
| |
| |
| Look-Up Tables | |
| |
| |
| Imprecise Computation | |
| |
| |
| Optimizing Memory Usage | |
| |
| |
| Postintegration Software Optimization | |
| |
| |
| Results from Compiler Optimization | |
| |
| |
| Use of Arithmetic Identifies | |
| |
| |
| Reduction in Strength | |
| |
| |
| Common Subexpression Elimination | |
| |
| |
| Intrinsic Functions | |
| |
| |
| Constant Folding | |
| |
| |
| Loop Invariant Optimization | |
| |
| |
| Loop Induction Elimination | |
| |
| |
| Use of Registers and Caches | |
| |
| |
| Removal of Dead or Unreachable Code | |
| |
| |
| Flow-of-Control Optimization | |
| |
| |
| Constant Propagation | |
| |
| |
| Dead-Store Elimination | |
| |
| |
| Dead-Variable Elimination | |
| |
| |
| Short-Circuiting Boolean Code | |
| |
| |
| Loop Unrolling | |
| |
| |
| Loop Jamming | |
| |
| |
| More Optimization Techniques | |
| |
| |
| Combination Effects | |
| |
| |
| Speculative Execution | |
| |
| |
| Analysis of Memory Requirements | |
| |
| |
| Reducing Memory Utilization | |
| |
| |
| Variable Selection | |
| |
| |
| Memory Fragmentation | |
| |
| |
| Exercises | |
| |
| |
| Engineering Considerations | |
| |
| |
| Metrics | |
| |
| |
| Lines of Code | |
| |
| |
| McCabe's Metric | |
| |
| |
| Halstead's Metrics | |
| |
| |
| Function Points | |
| |
| |
| Feature Points | |
| |
| |
| Metrics for Object-Oriented Software | |
| |
| |
| Objections to Metrics | |
| |
| |
| Best Practices | |
| |
| |
| Faults, Failures, and Bugs | |
| |
| |
| The Role of Testing | |
| |
| |
| Testing Techniques | |
| |
| |
| System-Level Testing | |
| |
| |
| Design of Testing Plans | |
| |
| |
| Fault-Tolerance | |
| |
| |
| Spatial Fault-Tolerance | |
| |
| |
| Software Black Boxes | |
| |
| |
| N-Version Programming | |
| |
| |
| Built-In-Test Software | |
| |
| |
| CPU Testing | |
| |
| |
| Memory Testing | |
| |
| |
| ROM | |
| |
| |
| RAM | |
| |
| |
| Other Devices | |
| |
| |
| Spurious and Missed Interrupts | |
| |
| |
| Handling Spurious and Missed Interrupts | |
| |
| |
| The Kalman Filter | |
| |
| |
| Systems Integration | |
| |
| |
| Goals of System Integration | |
| |
| |
| System Unification | |
| |
| |
| System Verification | |
| |
| |
| System Integration Tools | |
| |
| |
| A Simple Integration Strategy | |
| |
| |
| Patching | |
| |
| |
| The Probe Effect | |
| |
| |
| Fault-Tolerant Design: A Case Study | |
| |
| |
| Refactoring Real-Time Code | |
| |
| |
| Conditional Logic | |
| |
| |
| Data Clumps | |
| |
| |
| Delays as Loops | |
| |
| |
| Dubious Constraints | |
| |
| |
| Duplicated Code | |
| |
| |
| Generalizations Based on a Single Architecture | |
| |
| |
| Large Procedures | |
| |
| |
| Lazy Procedure | |
| |
| |
| Long Parameter List | |
| |
| |
| Message-Passing Overload | |
| |
| |
| Self-Modifying Code | |
| |
| |
| Speculative Generality | |
| |
| |
| Telltale Comments | |
| |
| |
| Unnecessary Use of Interrupts | |
| |
| |
| Cost Estimation Using COCOMO | |
| |
| |
| Basic COCOMO | |
| |
| |
| Intermediate and Detailed COCOMO | |
| |
| |
| COCOMO II | |
| |
| |
| Exercises | |