Real-Time Systems Design and Analysis

Phillip A. Laplante9780471228554, 0471228559

This third edition of Phillip Laplante’s bestselling, practical guide to building real-time systems maintains its predecessors’ unique holistic, systems-based approach devised to help engineers write problem-solving software. Dr. Laplante incorporates a survey of related technologies and their histories, complete with time-saving practical tips, hands-on instructions, C code, and insights into decreasing ramp-up times. Real-Time Systems Design and Analysis, Third Edition is essential for students and practicing software engineers who want improved designs, faster computation, and ultimate cost savings. Chapters discuss hardware considerations and software requirements, software systems design, the software production process, performance estimation and optimization, and engineering considerations. This new edition has been revised to include: Up-to-date information on object-oriented technologies for real-time including object-oriented analysis, design, and languages such as Java, C++, and C# Coverage of significant developments in the field, such as:New life-cycle methodologies and advanced programming practices for real-time, including Agile methodologiesAnalysis techniques for commercial real-time operating system technologyHardware advances, including field-programmable gate arrays and memory technology Deeper coverage of:Scheduling and rate-monotonic theoriesSynchronization and communication techniquesSoftware testing and metricsReal-Time Systems Design and Analysis, Third Edition remains an unmatched resource for students and practicing software engineers who want improved designs, faster computation, and ultimate cost savings.

---

Table of contents :
Team DDU……Page 1
CONTENTS……Page 10
Preface to the Third Edition……Page 20
1.1 Terminology……Page 26
1.1.1 Systems Concepts……Page 27
1.1.2 Real-Time Definitions……Page 29
1.1.3 Events and Determinism……Page 32
1.1.4 CPU Utilization……Page 35
1.2 Real-Time System Design Issues……Page 37
1.3 Example Real-Time Systems……Page 38
1.4 Common Misconceptions……Page 40
1.5 Brief History……Page 41
1.5.2 Early Systems……Page 42
1.5.4 Early Software……Page 43
1.5.5 Commercial Operating System Support……Page 44
1.6 Exercises……Page 45
2.1 Basic Architecture……Page 48
2.2.1 Latching……Page 49
2.2.3 Tristate Logic……Page 50
2.2.5 Systems Interfaces and Buses……Page 51
2.3 Central Processing Unit……Page 54
2.3.2 Microcontrollers……Page 55
2.3.3 Instruction Forms……Page 56
2.3.4 Core Instructions……Page 58
2.3.5 Addressing Modes……Page 61
2.3.6 RISC versus CISC……Page 62
2.4 Memory……Page 63
2.4.2 Memory Technologies……Page 64
2.4.3 Memory Hierarchy……Page 67
2.4.4 Memory Organization……Page 68
2.5.1 Programmed Input/Output……Page 69
2.5.2 Direct Memory Access……Page 70
2.5.3 Memory-Mapped Input/Output……Page 71
2.5.4 Interrupts……Page 73
2.6.2 Cache……Page 80
2.6.3 Pipelining……Page 81
2.7.1 Applications-Specific Integrated Circuits……Page 83
2.7.3 Field-Programmable Gate Arrays……Page 84
2.7.4 Transducers……Page 87
2.8 Non-von-Neumann Architectures……Page 89
2.8.2 Flynn’s Taxonomy for Parallelism……Page 90
2.9 Exercises……Page 95
3.1 Real-Time Kernels……Page 98
3.1.1 Pseudokernels……Page 99
3.1.2 Interrupt-Driven Systems……Page 104
3.1.3 Preemptive-Priority Systems……Page 107
3.1.4 Hybrid Systems……Page 108
3.1.5 The Task-Control Block Model……Page 111
3.2 Theoretical Foundations of Real-Time Operating Systems……Page 113
3.2.1 Process Scheduling……Page 115
3.2.2 Round-Robin Scheduling……Page 116
3.2.3 Cyclic Executives……Page 117
3.2.4 Fixed-Priority Scheduling¨CRate-Monotonic Approach……Page 119
3.2.5 Dynamic-Priority Scheduling: Earliest-Deadline¨CFirst Approach……Page 121
3.3 Intertask Communication and Synchronization……Page 123
3.3.2 Time-Relative Buffering……Page 124
3.3.3 Ring Buffers……Page 126
3.3.4 Mailboxes……Page 127
3.3.6 Critical Regions……Page 129
3.3.7 Semaphores……Page 130
3.3.9 Deadlock……Page 136
3.3.10 Priority Inversion……Page 142
3.4.1 Process Stack Management……Page 147
3.4.4 Multiple-Stack Arrangements……Page 151
3.4.5 Memory Management in the Task-Control-Block Model……Page 152
3.4.7 Overlays……Page 153
3.4.8 Block or Page Management……Page 154
3.4.9 Replacement Algorithms……Page 156
3.4.12 Real-Time Garbage Collection……Page 157
3.4.14 Building versus Buying Real-Time Operating Systems……Page 158
3.4.15 Selecting Real-Time Kernels……Page 159
3.5.1 Threads……Page 164
3.5.2 POSIX Mutexes and Condition Variables……Page 167
3.5.3 POSIX Semaphores……Page 168
3.5.4 Using Semaphores and Shared Memory……Page 169
3.5.5 POSIX Messages……Page 170
3.5.6 Real-Time POSIX Signals……Page 173
3.5.7 Clocks and Timers……Page 174
3.5.8 Asynchronous Input and Output……Page 178
3.5.9 POSIX Memory Locking……Page 179
3.6 Exercises……Page 181
4.1 Requirements-Engineering process……Page 186
4.2 Types of Requirements……Page 187
4.3 Requirements Specification for Real-Time Systems……Page 189
4.4 Formal Methods in Software Specification……Page 190
4.4.1 Limitations of Formal Methods……Page 192
4.4.3 Finite State Machines……Page 193
4.4.4 Statecharts……Page 197
4.4.5 Petri Nets……Page 199
4.4.6 Requirements Analysis with Petri Nets……Page 202
4.5 Structured Analysis and Design……Page 203
4.6 Object-Oriented Analysis and the Unified Modeling Language……Page 205
4.6.1 Use Cases……Page 206
4.6.3 Recommendations on Specification Approach for Real-Time Systems……Page 207
4.7 Organizing the Requirements Document……Page 208
4.8 Organizing and Writing Requirements……Page 209
4.9 Requirements Validation and Review……Page 211
4.9.2 Automated Checking of Requirements……Page 212
4.10 Appendix: Case Study in Software Requirements Specification for Four-Way Traffic Intersection Traffic Light Controller System……Page 215
4.11 Exercises……Page 247
5.1 Properties of Software……Page 250
5.1.1 Reliability……Page 251
5.1.3 Performance……Page 253
5.1.6 Maintainability……Page 254
5.1.8 Verifiability……Page 255
5.2.2 Separation of Concerns……Page 256
5.2.3 Modularity……Page 257
5.2.4 Anticipation of Change……Page 259
5.2.7 Traceability……Page 260
5.3 The Design Activity……Page 261
5.4 Procedural-Oriented Design……Page 262
5.4.1 Parnas Partitioning……Page 263
5.4.2 Structured Design……Page 264
5.4.3 Design in Procedural Form Using Finite State Machines……Page 271
5.5 Object-Oriented Design……Page 272
5.5.1 Benefits of Object Orientation……Page 273
5.5.2 Design Patterns……Page 274
5.5.3 Object-Oriented Design Using the Unified Modeling Language……Page 275
5.6 Appendix: Case Study in Software Requirements Specification for Four-Way Traffic Intersection Traffic Light Controller System……Page 280
5.7 Exercises……Page 343
6.1 Introduction……Page 346
6.2 Assembly Language……Page 347
6.3 Procedural Languages……Page 348
6.3.2 Call-by-Value and Call-by-Reference……Page 349
6.3.5 Dynamic Memory Allocation……Page 350
6.3.6 Typing……Page 351
6.3.7 Exception Handling……Page 352
6.3.8 Modularity……Page 353
6.4 Object-Oriented Languages……Page 354
6.4.1 Synchronizing Objects……Page 355
6.4.2 Garbage Collection……Page 356
6.4.3 Cardelli’s Metrics and Object-Oriented Languages……Page 358
6.4.4 Object-Oriented versus Procedural Languages……Page 359
6.5.1 Ada 95……Page 361
6.5.2 C……Page 362
6.5.3 C++……Page 363
6.5.4 C#……Page 364
6.5.5 Fortran……Page 365
6.5.6 Java……Page 366
6.5.7 Occam 2……Page 370
6.5.9 Know the Compiler and Rules of Thumb……Page 371
6.6 Coding Standards……Page 372
6.7 Exercises……Page 374
7.1.1 NP-Completeness……Page 376
7.1.2 Challenges in Analyzing Real-Time Systems……Page 377
7.1.3 The Halting Problem……Page 378
7.1.4 Amdahl’s Law……Page 380
7.1.5 Gustafson’s Law……Page 381
7.2.1 Code Execution Time Estimation……Page 382
7.2.4 Analysis of Round-Robin Systems……Page 389
7.2.5 Response-Time Analysis for Fixed-Period Systems……Page 392
7.2.7 Analysis of Sporadic and Aperiodic Interrupt Systems……Page 393
7.2.8 Deterministic Performance……Page 394
7.3.1 The M/M/1 Queue……Page 395
7.3.2 Service and Production Rates……Page 396
7.3.4 Response-Time Modeling……Page 397
7.3.6 Little’s Law……Page 398
7.3.7 Erlang’s Formula……Page 399
7.4.1 Basic Buffer-Size Calculation……Page 400
7.4.2 Variable Buffer-Size Calculation……Page 401
7.5.2 Scaled Numbers……Page 402
7.5.3 Binary Angular Measure……Page 403
7.5.4 Look-Up Tables……Page 404
7.5.5 Imprecise Computation……Page 405
7.6 Results from Compiler Optimization……Page 406
7.6.2 Reduction in Strength……Page 407
7.6.5 Constant Folding……Page 408
7.6.7 Loop Induction Elimination……Page 409
7.6.10 Flow-of-Control Optimization……Page 410
7.6.12 Dead-Store Elimination……Page 411
7.6.15 Loop Unrolling……Page 412
7.6.16 Loop Jamming……Page 413
7.6.17 More Optimization Techniques……Page 414
7.6.18 Combination Effects……Page 415
7.7 Analysis of Memory Requirements……Page 416
7.8.1 Variable Selection……Page 417
7.9 Exercises……Page 418
8.1.1 Lines of Code……Page 422
8.1.2 McCabe’s Metric……Page 423
8.1.3 Halstead’s Metrics……Page 424
8.1.4 Function Points……Page 426
8.1.5 Feature Points……Page 429
8.1.6 Metrics for Object-Oriented Software……Page 430
8.2 Faults, Failures, and Bugs……Page 431
8.2.2 Testing Techniques……Page 432
8.2.3 System-Level Testing……Page 438
8.3 Fault-Tolerance……Page 440
8.3.1 Spatial Fault-Tolerance……Page 441
8.3.2 Software Black Boxes……Page 442
8.3.5 CPU Testing……Page 443
8.3.7 ROM……Page 444
8.3.8 RAM……Page 445
8.3.11 Handling Spurious and Missed Interrupts……Page 447
8.3.12 The Kalman Filter……Page 448
8.4 Systems Integration……Page 449
8.4.3 System Verification……Page 450
8.4.4 System Integration Tools……Page 451
8.4.5 A Simple Integration Strategy……Page 454
8.4.6 Patching……Page 455
8.4.7 The Probe Effect……Page 456
8.4.8 Fault-Tolerant Design: A Case Study……Page 457
8.5.2 Data Clumps……Page 461
8.5.5 Duplicated Code……Page 462
8.5.10 Message-Passing Overload……Page 463
8.5.14 Unnecessary Use of Interrupts……Page 464
8.6.1 Basic COCOMO……Page 465
8.6.2 Intermediate and Detailed COCOMO……Page 466
8.6.3 COCOMO II……Page 467
8.7 Exercises……Page 468
Glossary……Page 470
Bibliography……Page 500
Index……Page 512
About the Author……Page 530