Preface
1 Introduction
1.1 A Car-and-Driver Example
1.2 Issues in Real-Time Computing
1.3 Structure of a Real-Time System
1.4 Task Classes
1.5 Issues Covered in this Book
1.5.1 Architecture Issues
1.5.2 Operating System Issues
1.5.3 Other Issues
2 Characterizing Real-Time Systems and Tasks
2.1 Introdoction
2.2 Performance Measures for Real-Time Systems
2.2.1 Properties of Performance Measures
2.2.2 Traditional Performance Measures
2.2.3 Performability
2.2.4 Cost Functions and Hard Deadlines
2.2.5 Discussion
2.3 Estimating Program Run Times
2.3.1 Analysis of Source Code
2.3.2 Accounting for Pipelining
2.3.3 Caches
2.3.4 Virtual Memory
2.4 Soggestions For Funher Reading
Exercises
References
3 Task Assignment and Scheduling
3.1 Invoduction
3.1.1 How to Read This Chapter
3.1.2 Notation
3.2 Classical Uniprocessor Scheduling Algorithms
3.2.l Rate-Monotonic Scheduling Algorithm
3.2.2 Preemptive Earliest Deadline First
(EDF) Algorithm
3.2.3 Allowing for Precedence and Exclusion Conditions"
3.2.4 Using Primary and Alternative Tasks
3.3 Uniprocessor Scheduling of IRIS Tasks
3.3.1 Identical Linear Reward Functions
3.3.2 Nonidentical Linear Reward Functions
3.3.3 0/1 Reward Functions
3.3.4 Identical Concave Reward Functions
(No Mandatory Portions)
3.3.5 Nonidentical Concave Reward Functions"
3.4 Task Assignment
3.4.1 Utilization-Balancing Algorithm
3.4.2 A Next-Fit Algorithm for RM Scheduling
3.4.3 A Bin-Packing Assignment Algorithm for EDF
3.4.4 A Myopic Offline Scheduling (MOS) Algorithm
3.4.5 Focused Addressing and Bidding (FAB) Algorithm
3.4.6 The Buddy Strategy
3.4.7 Assignment with Precedence Conditions
3.5 Mode Changes
3.6 Fault-Tolerant Scheduling
3.7 Suggestions for Further Reading
Exercises
References
4 Programming Languages and Tools
4.1 Introduction
4.2 Desired Language Characteristics
4.3 Data Typing
4.4 Control Structures
4.5 Facilitating Hierarchical Decomposition
4.5.1 Blocks
4.5.2 Procedures and Functions
4.6 Packages
4.7 Run-Time Error (Exception) Handling
4.8 Overloading and Generics
4.9 Multitasking
4.1O Low-Level Programming
4.11 Task Scheduling
4.11.1 Task Dispatching Policy
4.11.2 Entry Queueing Policy
4.11.3 protected Data Types
4.12 Timing Specifications
4.13 Some Experimental Languages
4.13.1 Flex
4.13.2 Euclid
4.14 Programming Environments
4.15 Run-Time Support
4.15.1 Compiler
4.15.2 Linker
4.15.3 Debagger
4.15.4 Kernel
4.16 Suggestions for Further Reading
Exercises
References
5 Real-Time Databases
5.1 Introduction
5.2 Basic Definitions
5.3 Real-Time vs. General-Purpose Databases
5.3.1 Absolute vs. Relative Consistency
5.3.2 Need for Response-Time predictability
5.3.3 Relaxing the ACID Properties
5.4 Main Memory Databases
5.5 Transaction Priorities
5.6 Transaction Aborts
5.7 Concurrency Control Issues
5.7.1 Pessimistic Concarrency Control
5.7.2 Optimistic Concanency Control
5.8 Disk Scheduling Algorithms
5.9 A Two-Phase Approach to Improve Predictability
5.1O Maintaining Serialization Consistency
5.1O.1 Serialization Consistency without Altemtion of
Serialization Order
5.1O.2 Serialization Consistency with Alteration of
Serialization Order
5.11 Databases for Hard Real-Time Systems
5.12 Suggestions for Further Reading
Exercises
References
6 Real-Time Communication
6.1 Introduction
6.1.1 Communications Media
6.2 Network Topologies
6.2.1 Sending Messages
6.2.2 Network Architecture Issues
6.3 Protocols
6.3.1 Contention-Based Ptotocols
6.3.2 Token-based Protocols
6.3.3 Stop-and-Go Multihop Protocol
6.3.4 The Polled Bus protocol
6.3.5 Hierarchical Round-Robin Protocol
6.3.6 Deadline-Based Protocols
6.3.7 Fault-Tolerant Routing
6.4 Suggestions for Further Reading
Exercises
References
7 Fault-Tolerance Techniques
7.1 Introduction
7.1.1 Definitions
7.2 What Causes Failures?
7.3 Fault Types
7.3.1 Temporal Behavior Classification
7.3.2 Output Behavior Classification
7.3.3 Independence and Correlation
7.4 Fault Detection
7.5 Fault and Error Containment
7.6 Redundancy
7.6.1 Hardware Redandancy
7.6.2 Sofiware Redundancy
7.6.3 Time Redundancy-Implementing Backward Error
Recovery
7.6.4 Information Redundancy
7.7 Data Diversity
7.8 Reversal Checks
7.9 Malicious or Byzantine Failures
7.1O Integrated Failure Handling
7.11 Suggestions for Further Reading
Exercises
References
8 Reliability Evaluation Techniques
8.1 Introduction
8.2 Obtaining Parameter Values
8.2.1 Obtaining Device-Failure Rates
8.2.2 Measuring Error-Propagation Time
8.2.3 Choosing the Best Distribution
8.3 Reliability Models for Hardware Redundancy
8.3.1 Permanent Faults Only
8.3.2 Fault Latency"
8.3.3 Introduction of Transient Faults
8.3.4 The Use of State Aggegation
8.4 Software-Error Models
8.4.1 The Limited Usefulness of Software-Error Models
8.5 Taking Time into Account
8.6 Suggestions for Further Reading
Exercises
References
9 Clock Synchronization
9.1 Introdoction
9.2 Clocks
9.2.1 Synchronization
9.3 A Nonfault-Toterant Synchronization Algorithm
9.4 Impact of Faults
9.4.1 Loss of Synchrony
9.5 Fanlt-Tolerant Synchronization in Hardware
9.5.1 Completely Connected, Zero-Propagation-Time System
9.5.2 Sparse-Interconnection, Zero-Propagation-Time System
9.5.3 Accounting for Signal-Propagation Delays
9.5.4 Multiple-Fault Classes
9.5.5 Advantages and Disadvantages of Hardware
Synchronization
9.6 Synchronization in Software
9.6.1 Interactive Convergence Averaging Algorithm, CA1
9.6.2 Interactive Convergence Averaging Algorithm, CA2
9.6.3 Convergence Nonaveraging Algorialm, CNA
9.7 Suggestions for Further Reading
Exercises
References
Appendix Review of Modeling Techniques
A.1 Review of Basic Probability Theory
A.2 Z-Transforms and Laplace Transforms
A.3 Some Important Probability Distribution Fanctions
A.3.1 The Uniform Distribution Functions
A.3.2 The Exponential Distribution Functions
A.3.3 The Poisson Process
A.3.4 The Erlangian Distribution
A.3.5 The Weibull Distribution Functions
A.4 Basics of Markov Modeling
A.4.1 Discrete-Time Markov Chains
A.4.2 Continuous-Time Markov Chains
A.4.3 Some Additional Remarks about Markov Chains
A.4.4 The Method of Stages
A.5 A Brief Glimpse of Queueing Theory
A.6 Saggestions For Further Reading
References
Index
鄂公网安备 42010302001612号 