product iamge

Real-Time Systems Design and Analysis

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

The leading guide to real-time systems design--revised and updated

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 methodologies Analysis techniques for commercial real-time operating system technology Hardware advances, including field-programmable gate arrays and memory technology
  • Deeper coverage of: Scheduling and rate-monotonic theories Synchronization and communication techniques Software testing and metrics

Real-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.

Author(s): Bruce Fraser
Edition: 3
Publisher: Wiley-IEEE Press
Year: 2004

Language: English
Pages: 528

TeamLiB......Page 0
Cover......Page 1
CONTENTS......Page 8
Preface to the Third Edition......Page 18
1.1 Terminology......Page 23
1.1.1 Systems Concepts......Page 24
1.1.2 Real-Time Definitions......Page 26
1.1.3 Events and Determinism......Page 29
1.1.4 CPU Utilization......Page 32
1.2 Real-Time System Design Issues......Page 34
1.3 Example Real-Time Systems......Page 35
1.4 Common Misconceptions......Page 37
1.5 Brief History......Page 38
1.5.2 Early Systems......Page 39
1.5.4 Early Software......Page 40
1.5.5 Commercial Operating System Support......Page 41
1.6 Exercises......Page 42
2.1 Basic Architecture......Page 45
2.2.1 Latching......Page 46
2.2.3 Tristate Logic......Page 47
2.2.5 Systems Interfaces and Buses......Page 48
2.3 Central Processing Unit......Page 51
2.3.2 Microcontrollers......Page 52
2.3.3 Instruction Forms......Page 53
2.3.4 Core Instructions......Page 55
2.3.5 Addressing Modes......Page 58
2.3.6 RISC versus CISC......Page 59
2.4 Memory......Page 60
2.4.2 Memory Technologies......Page 61
2.4.3 Memory Hierarchy......Page 64
2.4.4 Memory Organization......Page 65
2.5.1 Programmed Input/Output......Page 66
2.5.2 Direct Memory Access......Page 67
2.5.3 Memory-Mapped Input/Output......Page 68
2.5.4 Interrupts......Page 70
2.6.2 Cache......Page 77
2.6.3 Pipelining......Page 78
2.7.1 Applications-Specific Integrated Circuits......Page 80
2.7.3 Field-Programmable Gate Arrays......Page 81
2.7.4 Transducers......Page 84
2.8 Non-von-Neumann Architectures......Page 86
2.8.2 Flynn's Taxonomy for Parallelism......Page 87
2.9 Exercises......Page 92
3.1 Real-Time Kernels......Page 95
3.1.1 Pseudokernels......Page 96
3.1.2 Interrupt-Driven Systems......Page 101
3.1.3 Preemptive-Priority Systems......Page 104
3.1.4 Hybrid Systems......Page 105
3.1.5 The Task-Control Block Model......Page 108
3.2 Theoretical Foundations of Real-Time Operating Systems......Page 110
3.2.1 Process Scheduling......Page 112
3.2.2 Round-Robin Scheduling......Page 113
3.2.3 Cyclic Executives......Page 114
3.2.4 Fixed-Priority Scheduling–Rate-Monotonic Approach......Page 116
3.2.5 Dynamic-Priority Scheduling: Earliest-Deadline–First Approach......Page 118
3.3 Intertask Communication and Synchronization......Page 120
3.3.2 Time-Relative Buffering......Page 121
3.3.3 Ring Buffers......Page 123
3.3.4 Mailboxes......Page 124
3.3.6 Critical Regions......Page 126
3.3.7 Semaphores......Page 127
3.3.9 Deadlock......Page 133
3.3.10 Priority Inversion......Page 139
3.4.1 Process Stack Management......Page 144
3.4.4 Multiple-Stack Arrangements......Page 148
3.4.5 Memory Management in the Task-Control-Block Model......Page 149
3.4.7 Overlays......Page 150
3.4.8 Block or Page Management......Page 151
3.4.9 Replacement Algorithms......Page 153
3.4.12 Real-Time Garbage Collection......Page 154
3.4.14 Building versus Buying Real-Time Operating Systems......Page 155
3.4.15 Selecting Real-Time Kernels......Page 156
3.5.1 Threads......Page 161
3.5.2 POSIX Mutexes and Condition Variables......Page 164
3.5.3 POSIX Semaphores......Page 165
3.5.4 Using Semaphores and Shared Memory......Page 166
3.5.5 POSIX Messages......Page 167
3.5.6 Real-Time POSIX Signals......Page 170
3.5.7 Clocks and Timers......Page 171
3.5.8 Asynchronous Input and Output......Page 175
3.5.9 POSIX Memory Locking......Page 176
3.6 Exercises......Page 178
4 Software Requirements Engineering......Page 183
4.4.1 Limitations of Formal Methods......Page 189
4.2 Types of Requirements......Page 184
4.3 Requirements Specification for Real-Time Systems......Page 186
4.4 Formal Methods in Software Specification......Page 187
4.4.3 Finite State Machines......Page 190
4.4.4 Statecharts......Page 194
4.4.5 Petri Nets......Page 196
4.4.6 Requirements Analysis with Petri Nets......Page 199
4.5 Structured Analysis and Design......Page 200
4.6 Object-Oriented Analysis and the Unified Modeling Language......Page 202
4.6.1 Use Cases......Page 203
4.6.3 Recommendations on Specification Approach for Real-Time Systems......Page 204
4.7 Organizing the Requirements Document......Page 205
4.8 Organizing and Writing Requirements......Page 206
4.9 Requirements Validation and Review......Page 208
4.9.2 Automated Checking of Requirements......Page 209
4.10 Appendix: Case Study in Software Requirements Specification for Four-Way Traffic Intersection Traffic Light Controller System......Page 212
4.11 Exercises......Page 244
5.1 Properties of Software......Page 247
5.1.1 Reliability......Page 248
5.1.3 Performance......Page 250
5.1.6 Maintainability......Page 251
5.1.8 Verifiability......Page 252
5.2.2 Separation of Concerns......Page 253
5.2.3 Modularity......Page 254
5.2.4 Anticipation of Change......Page 256
5.2.7 Traceability......Page 257
5.3 The Design Activity......Page 258
5.4 Procedural-Oriented Design......Page 259
5.4.1 Parnas Partitioning......Page 260
5.4.2 Structured Design......Page 261
5.4.3 Design in Procedural Form Using Finite State Machines......Page 268
5.5 Object-Oriented Design......Page 269
5.5.1 Benefits of Object Orientation......Page 270
5.5.2 Design Patterns......Page 271
5.5.3 Object-Oriented Design Using the Unified Modeling Language......Page 272
5.6 Appendix: Case Study in Software Requirements Specification for Four-Way Traffic Intersection Traffic Light Controller System......Page 277
5.7 Exercises......Page 340
6.1 Introduction......Page 343
6.2 Assembly Language......Page 344
6.3 Procedural Languages......Page 345
6.3.2 Call-by-Value and Call-by-Reference......Page 346
6.3.5 Dynamic Memory Allocation......Page 347
6.3.6 Typing......Page 348
6.3.7 Exception Handling......Page 349
6.3.8 Modularity......Page 350
6.4 Object-Oriented Languages......Page 351
6.4.1 Synchronizing Objects......Page 352
6.4.2 Garbage Collection......Page 353
6.4.3 Cardelli's Metrics and Object-Oriented Languages......Page 355
6.4.4 Object-Oriented versus Procedural Languages......Page 356
6.5.1 Ada 95......Page 358
6.5.2 C......Page 359
6.5.3 C++......Page 360
6.5.4 C#......Page 361
6.5.5 Fortran......Page 362
6.5.6 Java......Page 363
6.5.7 Occam 2......Page 367
6.5.9 Know the Compiler and Rules of Thumb......Page 368
6.6 Coding Standards......Page 369
6.7 Exercises......Page 371
7.1.1 NP-Completeness......Page 373
7.1.2 Challenges in Analyzing Real-Time Systems......Page 374
7.1.3 The Halting Problem......Page 375
7.1.4 Amdahl's Law......Page 377
7.1.5 Gustafson's Law......Page 378
7.2.1 Code Execution Time Estimation......Page 379
7.2.4 Analysis of Round-Robin Systems......Page 386
7.2.5 Response-Time Analysis for Fixed-Period Systems......Page 389
7.2.7 Analysis of Sporadic and Aperiodic Interrupt Systems......Page 390
7.2.8 Deterministic Performance......Page 391
7.3.1 The M/M/1 Queue......Page 392
7.3.2 Service and Production Rates......Page 393
7.3.4 Response-Time Modeling......Page 394
7.3.6 Little's Law......Page 395
7.3.7 Erlang's Formula......Page 396
7.4.1 Basic Buffer-Size Calculation......Page 397
7.4.2 Variable Buffer-Size Calculation......Page 398
7.5.2 Scaled Numbers......Page 399
7.5.3 Binary Angular Measure......Page 400
7.5.4 Look-Up Tables......Page 401
7.5.5 Imprecise Computation......Page 402
7.6 Results from Compiler Optimization......Page 403
7.6.2 Reduction in Strength......Page 404
7.6.5 Constant Folding......Page 405
7.6.7 Loop Induction Elimination......Page 406
7.6.10 Flow-of-Control Optimization......Page 407
7.6.12 Dead-Store Elimination......Page 408
7.6.15 Loop Unrolling......Page 409
7.6.16 Loop Jamming......Page 410
7.6.17 More Optimization Techniques......Page 411
7.6.18 Combination Effects......Page 412
7.7 Analysis of Memory Requirements......Page 413
7.8.1 Variable Selection......Page 414
7.9 Exercises......Page 415
8.1.1 Lines of Code......Page 419
8.1.2 McCabe's Metric......Page 420
8.1.3 Halstead's Metrics......Page 421
8.1.4 Function Points......Page 423
8.1.5 Feature Points......Page 426
8.1.6 Metrics for Object-Oriented Software......Page 427
8.2 Faults, Failures, and Bugs......Page 428
8.2.2 Testing Techniques......Page 429
8.2.3 System-Level Testing......Page 435
8.3 Fault-Tolerance......Page 437
8.3.1 Spatial Fault-Tolerance......Page 438
8.3.2 Software Black Boxes......Page 439
8.3.5 CPU Testing......Page 440
8.3.7 ROM......Page 441
8.3.8 RAM......Page 442
8.3.11 Handling Spurious and Missed Interrupts......Page 444
8.3.12 The Kalman Filter......Page 445
8.4 Systems Integration......Page 446
8.4.3 System Verification......Page 447
8.4.4 System Integration Tools......Page 448
8.4.5 A Simple Integration Strategy......Page 451
8.4.6 Patching......Page 452
8.4.7 The Probe Effect......Page 453
8.4.8 Fault-Tolerant Design: A Case Study......Page 454
8.5.2 Data Clumps......Page 458
8.5.5 Duplicated Code......Page 459
8.5.10 Message-Passing Overload......Page 460
8.5.14 Unnecessary Use of Interrupts......Page 461
8.6.1 Basic COCOMO......Page 462
8.6.2 Intermediate and Detailed COCOMO......Page 463
8.6.3 COCOMO II......Page 464
8.7 Exercises......Page 465
Glossary......Page 467
Bibliography......Page 497
Index......Page 509
About the Author......Page 527