Real-Time Systems Design and Analysis

PHILLIP A. LAPLANTE, PhD, PE, is Professor of Software Engineering at Penn State, where he specializes in software and systems engineering, project management, and software testing and security. Dr. Laplante spent several years as a software engineer and project manager working on avionics, computer-aided design, and software test systems. He has authored or edited twenty-seven books and has published more than 200 scholarly articles. SEPPO J. OVASKA, DSc, is Professor of Industrial Electronics at Aalto University, Finland. He has served as a visiting scholar at Utah State University, Virginia Tech, and the University of Passau, Germany, and has published more than 100 articles in peer-reviewed journals. Prior to his academic career, Dr. Ovaska developed control systems for high-rise elevators; those contributions led to nine international patents.

• Preface xv Acknowledgments xxi1 Fundamentals of Real-Time Systems 11.1 Concepts and Misconceptions, 21.1.1 Definitions for Real-Time Systems, 21.1.2 Usual Misconceptions, 141.2 Multidisciplinary Design Challenges, 151.2.1 Influencing Disciplines, 161.3 Birth and Evolution of Real-Time Systems, 161.3.1 Diversifying Applications, 171.3.2 Advancements behind Modern Real-Time Systems, 191.4 Summary, 211.5 Exercises, 24References, 252 Hardware for Real-Time Systems 272.1 Basic Processor Architecture, 282.1.1 Von Neumann Architecture, 292.1.2 Instruction Processing, 302.1.3 Input/Output and Interrupt Considerations, 332.2 Memory Technologies, 362.2.1 Different Classes of Memory, 362.2.2 Memory Access and Layout Issues, 382.2.3 Hierarchical Memory Organization, 412.3 Architectural Advancements, 432.3.1 Pipelined Instruction Processing, 452.3.2 Superscalar and Very Long Instruction Word Architectures, 462.3.3 Multi-Core Processors, 482.3.4 Complex Instruction Set versus Reduced Instruction Set, 502.4 Peripheral Interfacing, 522.4.1 Interrupt-Driven Input/Output, 532.4.2 Direct Memory Access, 562.4.3 Analog and Digital Input/Output, 582.5 Microprocessor versus Microcontroller, 622.5.1 Microprocessors, 622.5.2 Standard Microcontrollers, 642.5.3 Custom Microcontrollers, 662.6 Distributed Real-Time Architectures, 682.6.1 Fieldbus Networks, 682.6.2 Time-Triggered Architectures, 712.7 Summary, 732.8 Exercises, 74References, 763 Real-Time Operating Systems 793.1 From Pseudokernels to Operating Systems, 803.1.1 Miscellaneous Pseudokernels, 823.1.2 Interrupt-Only Systems, 873.1.3 Preemptive Priority Systems, 903.1.4 Hybrid Scheduling Systems, 903.1.5 The Task Control Block Model, 953.2 Theoretical Foundations of Scheduling, 973.2.1 Scheduling Framework, 983.2.2 Round-Robin Scheduling, 993.2.3 Cyclic Code Scheduling, 1003.2.4 Fixed-Priority Scheduling: Rate-Monotonic Approach, 1023.2.5 Dynamic Priority Scheduling: Earliest Deadline First Approach, 1043.3 System Services for Application Programs, 1063.3.1 Linear Buffers, 1073.3.2 Ring Buffers, 1093.3.3 Mailboxes, 1103.3.4 Semaphores, 1123.3.5 Deadlock and Starvation Problems, 1143.3.6 Priority Inversion Problem, 1183.3.7 Timer and Clock Services, 1223.3.8 Application Study: A Real-Time Structure, 1233.4 Memory Management Issues, 1273.4.1 Stack and Task Control Block Management, 1273.4.2 Multiple-Stack Arrangement, 1283.4.3 Memory Management in the Task Control Block Model, 1293.4.4 Swapping, Overlaying, and Paging, 1303.5 Selecting Real-Time Operating Systems, 1333.5.1 Buying versus Building, 1343.5.2 Selection Criteria and a Metric for Commercial Real-Time Operating Systems, 1353.5.3 Case Study: Selecting a Commercial Real-Time Operating System, 1383.5.4 Supplementary Criteria for Multi-Core and Energy-Aware Support, 1403.6 Summary, 1423.7 Exercises, 143References, 1464 Programming Languages for Real-Time Systems 1494.1 Coding of Real-Time Software, 1504.1.1 Fitness of a Programming Language for Real-Time Applications, 1514.1.2 Coding Standards for Real-Time Software, 1524.2 Assembly Language, 1544.3 Procedural Languages, 1564.3.1 Modularity and Typing Issues, 1564.3.2 Parameter Passing and Dynamic Memory Allocation, 1574.3.3 Exception Handling, 1594.3.4 Cardelli’s Metrics and Procedural Languages, 1614.4 Object-Oriented Languages, 1624.4.1 Synchronizing Objects and Garbage Collection, 1624.4.2 Cardelli’s Metrics and Object-Oriented Languages, 1644.4.3 Object-Oriented versus Procedural Languages, 1654.5 Overview of Programming Languages, 1674.5.1 Ada, 1674.5.2 C, 1694.5.3 C++, 1704.5.4 C#, 1714.5.5 Java, 1724.5.6 Real-Time Java, 1744.5.7 Special Real-Time Languages, 1774.6 Automatic Code Generation, 1784.6.1 Toward Production-Quality Code, 1784.6.2 Remaining Challenges, 1804.7 Compiler Optimizations of Code, 1814.7.1 Standard Optimization Techniques, 1824.7.2 Additional Optimization Considerations, 1884.8 Summary, 1924.9 Exercises, 193References, 1955 Requirements Engineering Methodologies 1975.1 Requirements Engineering for Real-Time Systems, 1985.1.1 Requirements Engineering as a Process, 1985.1.2 Standard Requirement Classes, 1995.1.3 Specifi cation of Real-Time Software, 2015.2 Formal Methods in System Specification, 2025.2.1 Limitations of Formal Methods, 2055.2.2 Finite State Machines, 2055.2.3 Statecharts, 2105.2.4 Petri Nets, 2135.3 Semiformal Methods in System Specification, 2175.3.1 Structured Analysis and Structured Design, 2185.3.2 Object-Oriented Analysis and the Unified Modeling Language, 2215.3.3 Recommendations on Specification Approach, 2245.4 The Requirements Document, 2255.4.1 Structuring and Composing Requirements, 2265.4.2 Requirements Validation, 2285.5 Summary, 2325.6 Exercises, 2335.7 Appendix 1: Case Study in Software Requirements Specification, 2355.7.1 Introduction, 2355.7.2 Overall Description, 2385.7.3 Specific Requirements, 245References, 2656 Software Design Approaches 2676.1 Qualities of Real-Time Software, 2686.1.1 Eight Qualities from Reliability to Verifiability, 2696.2 Software Engineering Principles, 2756.2.1 Seven Principles from Rigor and Formality to Traceability, 2756.2.2 The Design Activity, 2816.3 Procedural Design Approach, 2846.3.1 Parnas Partitioning, 2846.3.2 Structured Design, 2866.3.3 Design in Procedural Form Using Finite State Machines, 2926.4 Object-Oriented Design Approach, 2936.4.1 Advantages of Object Orientation, 2936.4.2 Design Patterns, 2956.4.3 Design Using the Unified Modeling Language, 2986.4.4 Object-Oriented versus Procedural Approaches, 3016.5 Life Cycle Models, 3026.5.1 Waterfall Model, 3036.5.2 V-Model, 3056.5.3 Spiral Model, 3066.5.4 Agile Methodologies, 3076.6 Summary, 3116.7 Exercises, 3126.8 Appendix 1: Case Study in Designing Real-Time Software, 3146.8.1 Introduction, 3146.8.2 Overall Description, 3156.8.3 Design Decomposition, 3166.8.4 Requirements Traceability, 371References, 3757 Performance Analysis Techniques 3797.1 Real-Time Performance Analysis, 3807.1.1 Theoretical Preliminaries, 3807.1.2 Arguments Related to Parallelization, 3827.1.3 Execution Time Estimation from Program Code, 3857.1.4 Analysis of Polled-Loop and Coroutine Systems, 3917.1.5 Analysis of Round-Robin Systems, 3927.1.6 Analysis of Fixed-Period Systems, 3947.1.7 Analysis of Nonperiodic Systems, 3967.2 Applications of Queuing Theory, 3987.2.1 Single-Server Queue Model, 3987.2.2 Arrival and Processing Rates, 4007.2.3 Buffer Size Calculation, 4017.2.4 Response Time Modeling, 4027.2.5 Other Results from Queuing Theory, 4037.3 Input/Output Performance, 4057.3.1 Buffer Size Calculation for Time-Invariant Bursts, 4057.3.2 Buffer Size Calculation for Time-Variant Bursts, 4067.4 Analysis of Memory Requirements, 4087.4.1 Memory Utilization Analysis, 4087.4.2 Optimizing Memory Usage, 4107.5 Summary, 4117.6 Exercises, 413References, 4158 Additional Considerations for the Practitioner 4178.1 Metrics in Software Engineering, 4188.1.1 Lines of Source Code, 4198.1.2 Cyclomatic Complexity, 4208.1.3 Halstead’s Metrics, 4218.1.4 Function Points, 4238.1.5 Feature Points, 4278.1.6 Metrics for Object-Oriented Software, 4288.1.7 Criticism against Software Metrics, 4288.2 Predictive Cost Modeling, 4298.2.1 Basic COCOMO 81, 4298.2.2 Intermediate and Detailed COCOMO 81, 4318.2.3 COCOMO II, 4338.3 Uncertainty in Real-Time Systems, 4338.3.1 The Three Dimensions of Uncertainty, 4348.3.2 Sources of Uncertainty, 4358.3.3 Identifying Uncertainty, 4378.3.4 Dealing with Uncertainty, 4388.4 Design for Fault Tolerance, 4388.4.1 Spatial Fault-Tolerance, 4408.4.2 Software Black Boxes, 4438.4.3 N-Version Programming, 4438.4.4 Built-in-Test Software, 4448.4.5 Spurious and Missed Interrupts, 4478.5 Software Testing and Systems Integration, 4478.5.1 Testing Techniques, 4488.5.2 Debugging Approaches, 4548.5.3 System-Level Testing, 4568.5.4 Systems Integration, 4588.5.5 Testing Patterns and Exploratory Testing, 4628.6 Performance Optimization Techniques, 4658.6.1 Scaled Numbers for Faster Execution, 4658.6.2 Look-Up Tables for Functions, 4678.6.3 Real-Time Device Drivers, 4688.7 Summary, 4708.8 Exercises, 471References, 4739 Future Visions on Real-Time Systems 4779.1 Vision: Real-Time Hardware, 4799.1.1 Heterogeneous Soft Multi-Cores, 4819.1.2 Architectural Issues with Individual Soft Cores, 4839.1.3 More Advanced Fieldbus Networks and Simpler Distributed Nodes, 4849.2 Vision: Real-Time Operating Systems, 4859.2.1 One Coordinating System Task and Multiple Isolated Application Tasks, 4869.2.2 Small, Platform Independent Virtual Machines, 4879.3 Vision: Real-Time Programming Languages, 4889.3.1 The UML++ as a Future “Programming Language”, 4899.4 Vision: Real-Time Systems Engineering, 4919.4.1 Automatic Verification of Software, 4919.4.2 Conservative Requirements Engineering, 4929.4.3 Distance Collaboration in Software Projects, 4929.4.4 Drag-and-Drop Systems, 4939.5 Vision: Real-Time Applications, 4939.5.1 Local Networks of Collaborating Real-Time Systems, 4949.5.2 Wide Networks of Collaborating Real-Time Systems, 4959.5.3 Biometric Identification Device with Remote Access, 4959.5.4 Are There Any Threats behind High-Speed Wireless Communications?, 4979.6 Summary, 4979.7 Exercises, 499References, 500Glossary 503About the Authors 535Index 537