Table of Contents

Cover

Series

Title

Dedication

PREFACE

ACKNOWLEDGMENTS

1 FUNDAMENTALS OF REAL-TIME SYSTEMS

1.1 CONCEPTS AND MISCONCEPTIONS
1.2 MULTIDISCIPLINARY DESIGN CHALLENGES
1.3 BIRTH AND EVOLUTION OF REAL-TIME SYSTEMS
1.4 SUMMARY
1.5 EXERCISES

2 HARDWARE FOR REAL-TIME SYSTEMS

2.1 BASIC PROCESSOR ARCHITECTURE
2.2 MEMORY TECHNOLOGIES
2.3 ARCHITECTURAL ADVANCEMENTS
2.4 PERIPHERAL INTERFACING
2.5 MICROPROCESSOR VERSUS MICROCONTROLLER
2.6 DISTRIBUTED REAL-TIME ARCHITECTURES
2.7 SUMMARY
2.8 EXERCISES

3 REAL-TIME OPERATING SYSTEMS

3.1 FROM PSEUDOKERNELS TO OPERATING SYSTEMS
3.2 THEORETICAL FOUNDATIONS OF SCHEDULING
3.3 SYSTEM SERVICES FOR APPLICATION PROGRAMS
3.4 MEMORY MANAGEMENT ISSUES
3.5 SELECTING REAL-TIME OPERATING SYSTEMS
3.6 SUMMARY
3.7 EXERCISES

4 PROGRAMMING LANGUAGES FOR REAL-TIME SYSTEMS

4.1 CODING OF REAL-TIME SOFTWARE
4.2 ASSEMBLY LANGUAGE
4.3 PROCEDURAL LANGUAGES
4.4 OBJECT-ORIENTED LANGUAGES
4.5 OVERVIEW OF PROGRAMMING LANGUAGES
4.6 AUTOMATIC CODE GENERATION
4.7 COMPILER OPTIMIZATIONS OF CODE
4.8 SUMMARY
4.9 EXERCISES

5 REQUIREMENTS ENGINEERING METHODOLOGIES

5.1 REQUIREMENTS ENGINEERING FOR REAL-TIME SYSTEMS
5.2 FORMAL METHODS IN SYSTEM SPECIFICATION
5.3 SEMIFORMAL METHODS IN SYSTEM SPECIFICATION
5.4 THE REQUIREMENTS DOCUMENT
5.5 SUMMARY
5.6 EXERCISES
5.7 APPENDIX 1: CASE STUDY IN SOFTWARE REQUIREMENTS SPECIFICATION

6 SOFTWARE DESIGN APPROACHES

6.1 QUALITIES OF REAL-TIME SOFTWARE
6.2 SOFTWARE ENGINEERING PRINCIPLES
6.3 PROCEDURAL DESIGN APPROACH
6.4 OBJECT-ORIENTED DESIGN APPROACH
6.5 LIFE CYCLE MODELS
6.6 SUMMARY
6.7 EXERCISES
6.8 APPENDIX 1: CASE STUDY IN DESIGNING REAL-TIME SOFTWARE

7 PERFORMANCE ANALYSIS TECHNIQUES

7.1 REAL-TIME PERFORMANCE ANALYSIS
7.2 APPLICATIONS OF QUEUING THEORY
7.3 INPUT/OUTPUT PERFORMANCE
7.4 ANALYSIS OF MEMORY REQUIREMENTS
7.5 SUMMARY
7.6 EXERCISES

8 ADDITIONAL CONSIDERATIONS FOR THE PRACTITIONER

8.1 METRICS IN SOFTWARE ENGINEERING
8.2 PREDICTIVE COST MODELING
8.3 UNCERTAINTY IN REAL-TIME SYSTEMS
8.4 DESIGN FOR FAULT TOLERANCE
8.5 SOFTWARE TESTING AND SYSTEMS INTEGRATION
8.6 PERFORMANCE OPTIMIZATION TECHNIQUES
8.7 SUMMARY
8.8 EXERCISES

9 FUTURE VISIONS ON REAL-TIME SYSTEMS

9.1 VISION: REAL-TIME HARDWARE
9.2 VISION: REAL-TIME OPERATING SYSTEMS
9.3 VISION: REAL-TIME PROGRAMMING LANGUAGES
9.4 VISION: REAL-TIME SYSTEMS ENGINEERING
9.5 VISION: REAL-TIME APPLICATIONS
9.6 SUMMARY
9.7 EXERCISES

GLOSSARY

ABOUT THE AUTHORS

INDEX

End User License Agreement

List of Tables

1 FUNDAMENTALS OF REAL-TIME SYSTEMS

TABLE 1.1. A Sampling of Hard, Firm, and Soft Real-Time Systems
TABLE 1.2. Taxonomy of Events and Some Typical Examples
TABLE 1.3. CPU Utilization (%) Zones
TABLE 1.4. Typical Real-Time Domains and Diverse Applications
TABLE 1.5. Landmarks in Real-Time Systems History in the United States

3 REAL-TIME OPERATING SYSTEMS

TABLE 3.1. Example Task Set for Frame-Size Calculation
TABLE 3.2. Example Task Set for RM Scheduling
TABLE 3.3. Upper Bounds of the CPU Utilization Factor, U (%), for n Periodic Tasks Scheduled Using the RMA
TABLE 3.4. Task Pair for the Example of EDF Scheduling
TABLE 3.5. Task Resource Request Table
TABLE 3.6. Resource Table Used Together with Task Resource-Request Table
TABLE 3.7. Device Ordering Scheme to Eliminate the Circular Wait Condition
TABLE 3.8. Data for the Priority Ceiling Protocol Illustration
TABLE 3.9. Summary Data for RTOS A
TABLE 3.10. Decision Table for the Inertial Measurement System

5 REQUIREMENTS ENGINEERING METHODOLOGIES

TABLE 5.1. Truth Table Used to Verify the Consistency of the Example Set of Requirements (T = True and F = False)
TABLE 5.2. Transition Matrix Representation for the Finite State Machine in Figure 5.2
TABLE 5.3. Transition Matrix Representation for the Finite State Machine in Figure 5.3
TABLE 5.4. Firing Table for the Petri Net Shown in Figure 5.8;
TABLE 5.5. Firing Table for the Petri Net Shown in Figure 5.9
TABLE 5.6. Imperatives Found in Requirements Specifications and Their Purpose (Wilson, 1997)
TABLE 5.7. Numerical Ratios Derived from Software Requirements Specifications and Their Purpose
TABLE 5.A1. Major Intersection Control System Hardware Components
TABLE 5.A2. Intersection Controller Class
TABLE 5.A3. Approach Class
TABLE 5.A4. Pedestrian Traffic Standard Class
TABLE 5.A5. Vehicle Traffic Standard Class
TABLE 5.A6. Pedestrian Service Button Class
TABLE 5.A7. Vehicle Presence Detector Class
TABLE 5.A8. Manual Override Class
TABLE 5.A9. Remote Override Class
TABLE 5.A10. Emergency Vehicle Interface Class
TABLE 5.A11. Network Interface Class
TABLE 5.A12. Traffic History Class
TABLE 5.A13. Incident Log Class

6 SOFTWARE DESIGN APPROACHES

TABLE 6.1. Failure probability as a Function of Operating Hours
TABLE 6.2. Software Qualities and Possible Means for Measuring Them
TABLE 6.3. A Traceability Matrix Sorted by Requirement Number
TABLE 6.4. A Mapping Matrix from Software Engineering Principles to Software Qualities in Real-Time Applications
TABLE 6.5. The Original Set of Design Patterns Popularized by the “Gang of Four”
TABLE 6.6. A Side-by-Side Comparison of SA/SD and OOAD (UML) Approaches
TABLE 6.A1. IEEE Std 1016 Design Views
TABLE 6.A2. Intersection Controller—Traffic Signal Control Collaboration Messages
TABLE 6.A3. Intersection Controller—Emergency Preempt Collaboration Messages
TABLE 6.A4. Intersection Controller—Manual Override Collaboration Messages
TABLE 6.A5. Intersection Controller—Remote Override Collaboration Messages
TABLE 6.A6. Intersection Controller—Coordinated Control Collaboration Messages
TABLE 6.A7. Intersection Controller—Maintenance Collaboration Messages
TABLE 6.A8. Active Objects
TABLE 6.A9. IntersectionController Class—Attributes
TABLE 6.A10. Intersection Controller Class—Methods
TABLE 6.A11. Approach Class—Attributes
TABLE 6.A12. Approach Class—Methods
TABLE 6.A13. Intersection Standard Class—Attributes
TABLE 6.A14. Intersection Standard Class—Methods
TABLE 6.A15. Attribute and Signal Correspondence
TABLE 6.A16. OnOff Sensor Class—Attributes
TABLE 6.A17. OnOff Sensor Class—Methods
TABLE 6.A18. VehicleDetector Class—Attributes
TABLE 6.A19. Override Class—Attributes
TABLE 6.A20. Override Class—Methods
TABLE 6.A21. RemoteOverride Class—Attributes
TABLE 6.A22. RemoteOverride Class—Methods
TABLE 6.A23. PreEmpt Class—Attributes
TABLE 6.A24. PreEmpt Class—Methods
TABLE 6.A25. Network Class—Methods
TABLE 6.A26. Maintenance Class—Attributes
TABLE 6.A27. Maintenance Class—Methods
TABLE 6.A28. Database Class—Attributes
TABLE 6.A29. Database Class—Methods
TABLE 6.A30. Architectural Requirements
TABLE 6.A31. Functional Requirements
TABLE 6.A32. Timing Requirements

7 PERFORMANCE ANALYSIS TECHNIQUES

TABLE 7.1. Memory Specifications of Low-Cost (LC) and High-Performance (HP) Motor Drive Products

8 ADDITIONAL CONSIDERATIONS FOR THE PRACTITIONER

TABLE 8.1. Quantified Answers, A1–A14, to the Complexity Factor Questionnaire for the Inertial Measurement System
TABLE 8.2. Programming Language and Lines of Code per Function Point;
TABLE 8.3. Summary of Kinds of Uncertainty in Real-Time Systems with Typical Signs, Possible Causes, and Potential Solutions
TABLE 8.4. Sample Test Log for Elevator Control System
TABLE 8.5. A Generic Function Look-Up Table Containing Both the Function and Its Derivative

List of Illustrations

1 FUNDAMENTALS OF REAL-TIME SYSTEMS

Figure 1.1. A general system with inputs and outputs.
Figure 1.2. A real-time control system including inputs from a camera and multiple sensors, as well as outputs to a display and multiple actuators.
Figure 1.3. A classic representation of a real-time system as a sequence of schedulable jobs.
Figure 1.4. A partial program flowchart showing a conditional branch as a change in flow of control.
Figure 1.5. A variety of disciplines that affect real-time systems engineering.
Figure 1.6. Mars Exploration Rover; a solar-powered, autonomous real-time system with radio-communications links and a variety of sensors and actuators.
Figure 1.7. Composition of this unique text from nine complementary chapters.

2 HARDWARE FOR REAL-TIME SYSTEMS

Figure 2.1. Von Neumann computer architecture without an explicit input/output element.
Figure 2.2. Internal structure of a simplified CPU. The Instruction Access and Data Access are merged pairwise to form the common address and data buses.
Figure 2.3. Sequential instruction cycle with five phases.
Figure 2.4. Von Neumann architecture with slightly enhanced system bus for programmed input/output.
Figure 2.5. Interface lines of a generic memory component (Write is not used with ROM devices). The memory capacity is 2^m⁺¹ × (n + 1) bits.
Figure 2.6. Timing diagram of a memory-read bus cycle. The angles “< >” shown in the data and address buses indicate that multiple lines with different logic states are involved during this period.
Figure 2.7. Typical memory map showing allocated regions (not to scale). Note, a large proportion of the memory space is not allocated for any specific purpose.
Figure 2.8. Hierarchical memory organization with two cache levels, L1 and L2, between the CPU and main memory.
Figure 2.9. Harvard architecture with different bus widths.
Figure 2.10. Pipelined instruction processing in a five-stage pipeline.
Figure 2.11. Superscalar architecture with two parallel instruction pipelines.
Figure 2.12. Quad-core processor architecture with individual on-chip caches and a common on-chip cache (“I” = instruction and “D” = data).
Figure 2.13. Interface lines of a generic peripheral input/output unit with three internal registers.
Figure 2.14. Interrupt-identification procedure between the CPU and PIU using vectored interrupt.
Figure 2.15. Handling multiple interrupts with an external priority interrupt controller; the circled numbers are referring to the 10-step procedure described in the text.
Figure 2.16. Establishing a data-transfer connection between an I/O device and main memory using DMA.
Figure 2.17. Quantization of an analog ramp signal using a 3-bit A/D converter. The quantization error varies between -1/2 LSB (least significant bit) and +1/2 LSB, and it is thus proportional to the number of bits in the conversion process.
Figure 2.18. Block diagram of a digital input channel intended for an operating environment with high EMI levels.
Figure 2.19. Principal evolution paths of processor technology.
Figure 2.20. Block diagram of a watchdog timer with its inputs and output.
Figure 2.21. Conceptual architecture of an FPGA device with 6 logic cells (Mayer-Baese, 2007). In reality, the number of logic cells may be even more than 100,000.
Figure 2.22. Bus (a), ring (b), star (c), and tree (d) topologies used commonly in fieldbus networks.
Figure 2.23. Time-triggered architecture with three nodes and two redundant broadcast channels.

3 REAL-TIME OPERATING SYSTEMS

Figure 3.1. Hierarchical relationships between the system, multiple processes, and multiple threads.
Figure 3.2. The role of the kernel in operating systems; moving up the taxonomy stack shows the additional functionality provided and indicates the relative closeness to hardware versus users.
Figure 3.3. An interrupt-driven foreground/background system.
Figure 3.4. The behavior of stack during context saving and restoring; here, the context is solely four registers.
Figure 3.5. A typical task-control block.
Figure 3.6. A representative task state diagram as a partially defined finite state machine.
Figure 3.7. Hybrid (round-robin/preemptive) scheduling of three tasks with two priority levels.
Figure 3.8. Rate-monotonic task schedule for the task set of Table 3.2.
Figure 3.9. Earliest deadline-first task schedule for the task pair of Table 3.4.
Figure 3.10. Readers and writers problem, with n readers and m writers; the shared resource is a bounded buffer.
Figure 3.11. Double-buffering; two identical buffers are filled and emptied by alternating tasks; switching is accomplished by either software or hardware.
Figure 3.12. A ring buffer; tasks write data to the buffer at the tail index and read from the head index.
Figure 3.13. Deadlock realization as a loop in a resource diagram.
Figure 3.14. A typical priority-inversion scenario.
Figure 3.15. Illustration of the priority-inheritance protocol.
Figure 3.16. Illustration of the priority-ceiling protocol.
Figure 3.17. Architecture of an elevator bank control system.
Figure 3.18. Real-time structure of an elevator controller.
Figure 3.19. Multiple-stack arrangement.
Figure 3.20. Linked-lists management in the task-control-block model.
Figure 3.21. Fragmented memory (a) before and (b) after compaction; the unmovable blocks represent the root program of the real-time operating system.
Figure 3.22. Individual criterion weights (white) and weighted criterion ratings for RTOS D (black) and RTOS E (gray).

4 PROGRAMMING LANGUAGES FOR REAL-TIME SYSTEMS

Figure 4.1. Mainstream usage of real-time programming languages over the years (the year limits are approximate).
Figure 4.2. Pentacle diagram for illustrating the Cardelli criteria of various economies (the gray pentacle corresponds to assembly language).
Figure 4.3. The Java interpreter as a model of a virtual machine.
Figure 4.4. A three-step evolution path, (a) ? (b) ? (c), from programmer-generated code to automatically generated code.

5 REQUIREMENTS ENGINEERING METHODOLOGIES

Figure 5.1. The requirements engineering process;
Figure 5.2. A diagrammatic representation of a finite state machine for the elevator door-control subsystem.
Figure 5.3. A fully connected Mealy FSM with states S1, S2, and S3, inputs E1, E2, and E3, and outputs O1, O2, and O3.
Figure 5.4. Statechart format where A and B are states, x is an event that causes the transition marked by the arrow, y is an optional event triggered by x, and e₁, … e_n are optional conditions qualifying the primary event;
Figure 5.5. A statechart depicting insideness;
Figure 5.6. Navigation subsystem containing four orthogonal tasks.
Figure 5.7. A statechart depicting a chain reaction;
Figure 5.8. A simple Petri net before (m₀) and after (m₁) firing;
Figure 5.9. Sequential behavior of a Petri net with both “consumer” and “producer” transitions.
Figure 5.10. Race-condition identification with a Petri net.
Figure 5.11. Deadlock in Figure 3.13 illustrated using a Petri net.
Figure 5.12. Models and elements of structured analysis and structured design.
Figure 5.13. Context diagram for the elevator control system.
Figure 5.14. Use-case diagram for the elevator control system.
Figure 5.15. Recommended table of contents for the SRS from the IEEE Std 830–1998 (IEEE, 1998).
Figure 5.16. Triangle-, hourglass-, and diamond-shaped requirements structures.
Figure 5.A1. Intersection topography.
Figure 5.A2. Intersection controller hardware (not all details and interconnects shown).
Figure 5.A3. Top-level use case diagram.
Figure 5.A4. Preliminary intersection controller class diagram.
Figure 5.A5. Statechart for intersection controller phase sequence.
Figure 5.A6. Traffic standard aspects for each phase.
Figure 5.A7. Minimum presence pulse width.
Figure 5.A8. Minimum gap pulse width.

6 SOFTWARE DESIGN APPROACHES

Figure 6.1. A model of failure represented by the exponential failure function
Figure 6.2. A software failure function represented by the bathtub curve
Figure 6.3. Modular decomposition of code units. The arrows represent inputs and outputs in the procedural paradigm. In the object-oriented paradigm, they represent associations. The boxes represent encapsulated data and procedures in the procedural paradigm. In the object-oriented paradigm, they represent classes
Figure 6.4. Software structures with (a) high cohesion and low coupling, and (b) low cohesion and high coupling. The inside squares represent statements or data; connecting lines indicate functional dependency.
Figure 6.5. Coupling and cohesion. The right way: low coupling and high cohesion. The wrong way: high coupling and low cohesion.
Figure 6.6. Parnas partitioning of graphics rendering software.
Figure 6.7. Evolution path from the context diagram to level 0 DFD to level 1 DFD, and finally to a P-SPEC.
Figure 6.8. Level 0 DFD for the elevator control system. * This incoming data flow is connected to two processes.
Figure 6.9. The relationship between control and process models
Figure 6.10. A generic pseudocode that can implement the behavior of finite state machines
Figure 6.11. Finite-state-machine code for executing a single operational process; each process can exist in multiple states, allowing partitioning of the program code into appropriate modules
Figure 6.12. The role of UML in specification and design;
Figure 6.13. Sequential waterfall model with optional feedback enhancements.
Figure 6.14. V-model with quality assurance activities.
Figure 6.15. Spiral model with early prototyping efforts;
Figure 6.16. A sample flow of a software development project using iterative agile methodologies;
Figure 6.A1. Intersection topography.
Figure 6.A2. Intersection controller software architecture.
Figure 6.A3. Intersection controller collaborations.
Figure 6.A4. Traffic signal control.
Figure 6.A5. Emergency preempt.
Figure 6.A6. Manual override.
Figure 6.A7. Remote override.
Figure 6.A8. Coordinated control.
Figure 6.A9. Maintenance.
Figure 6.A10. Intersection controller class diagram.
Figure 6.A11. Intersection controller class.
Figure 6.A12. Black box representation of adaptive algorithm.
Figure 6.A13. Traffic signal control sequence diagram.
Figure 6.A14. Statechart for intersection controller phase sequence.
Figure 6.A15. Statechart for phases 4 and 8.
Figure 6.A16. Approach class.
Figure 6.A17. IntersectionStandard class.
Figure 6.A18. OnOffSensor class.
Figure 6.A19. OnOffSensor sequence diagram.
Figure 6.A20. OnOffSensor statechart.
Figure 6.A21. VehicleDetector class.
Figure 6.A22. VehicleDetector class sequence diagram.
Figure 6.A23. VehicleDetector class statechart.
Figure 6.A24. Override class.
Figure 6.A25. Override class sequence diagram.
Figure 6.A26. Remote override class.
Figure 6.A27. PreEmpt class.
Figure 6.A28. PreEmpt sequence diagram.
Figure 6.A29. Network class.
Figure 6.A30. Maintenance class.
Figure 6.A31. Database class.
Figure 6.A32. Record class.
Figure 6.A33. Record class—attributes.
Figure 6.A34. Record class—methods.
Figure 6.A35. ErrorHandler class—methods.
Figure 6.A36. Noncritical error sequence diagram.
Figure 6.A37. Critical error sequence diagram.
Figure 6.A38. Split class.
Figure 6.A39. Parameters class.
Figure 6.A40. Status class.
Figure 6.A41. Phase class.
Figure 6.A42. Aspect class.
Figure 6.A43. Indication class.
Figure 6.A44. Mode class.
Figure 6.A45. OverrideType class.

7 PERFORMANCE ANALYSIS TECHNIQUES

Figure 7.1. Gustafson’s unbound speedup compared with Amdahl’s saturating speedup (? 2) when 50% of code is suitable for parallelization.
Figure 7.2. Pipeline simulation trace for Path 1.
Figure 7.3. Pipeline simulation trace for Path 2.
Figure 7.4. Pipeline simulation trace for Path 3.
Figure 7.5. Delay components of polled-loop response time.
Figure 7.6. Tracing the execution path in a two-task coroutine system. A central dispatcher calls task_1() and task_2() by turns, and a switch statement in each task (not shown) steps the phase-driven code.
Figure 7.7. A simple single-server queuing model for analyzing real-time systems.

8 ADDITIONAL CONSIDERATIONS FOR THE PRACTITIONER

Figure 8.1. Correspondence of language statements and flow graphs;
Figure 8.2. Flow graph for gyro compensation code of the inertial measurement system
Figure 8.3. Person-month, PM, estimates for different types of software as a function of the KLOC measure, L ? {2, 5, 10, 20, 40}.
Figure 8.4. A real-time system with uncertainty can be viewed as having dimensions of time, space, and behavior, and some uncertainty margin in all these dimensions.
Figure 8.5. Fault-tolerant version of the elevator bank control system.
Figure 8.6. Checkpoint implementation
Figure 8.7. Recovery block implementation
Figure 8.8. Black- and white-box views of a software module for the tester.
Figure 8.9. Hierarchical bottom-up sequence of software testing phases.
Figure 8.10. A logic analyzer connected to the system under test (SUT).
Figure 8.11. A straightforward integration strategy
Figure 8.12. A 16-bit BAM word.
Figure 8.13. Typical functions of a real-time device driver that is interacting closely with the RTOS.

9 FUTURE VISIONS ON REAL-TIME SYSTEMS

Figure 9.1. An example of the vision confidence pentacle.
Figure 9.2. A heterogeneous soft multi-core architecture for future embedded systems (only Core 1 is shown with internal details for clarity).
Figure 9.3. A distributed control architecture for future large-scale plants.
Figure 9.4. An example of coordinated message broadcasting from Task 1 to Tasks 2–4.
Figure 9.5. The procedure of generating an application-specific HSMC platform and the corresponding program code for the individual soft cores using the UML++ design engine.

PREFACE

This book is an introductory text about real-time systems—systems where timeliness is a crucial part of the correctness of the system. Real-time software designers must be familiar with computer architecture and organization, operating systems and related services, programming languages, systems and software engineering, as well as performance analysis and optimization techniques. The text provides a pragmatic discussion of these subjects from the perspective of the real-time systems designer. Because this is a staggering task, depth is occasionally sacrificed for breadth. Nevertheless, thoughtful suggestions for additional literature are provided where depth has been sacrificed due to the available page budget or other reasons.

This book is intended for junior–senior level and graduate computer science, computer engineering and electrical engineering students, as well as practicing software, systems and computer engineers. It can be used as a graduate level text if it is supplemented with an advanced reader or a focused selection of scholarly articles on a specific topic (which could be gathered from the up-to-date bibliographies of this edition). Our book is especially useful in an industrial setting for new real-time systems designers who need to get “up to speed” very quickly. Earlier editions of this book have been used in this way to teach short courses for several industrial clients. Finally, we intend for the book to be a desk reference of long-lasting value, even for experienced real-time systems designers and project managers.

The reader is assumed to have basic knowledge in programming in one of the more popular languages, but other than this, the prerequisites for this text are minimal. Some familiarity with discrete mathematics is helpful in understanding some of the formalizations, but it is not essential.

Since there are several preferred languages for real-time systems design, such as Ada, C, C++, C#, and increasingly, Java, it would be unjust to focus this book on one language, say C, when the theory and framework should be language independent. However, for uniformity of discussion, certain points are illustrated, as appropriate, in generic assembly language and C.

While the provided program codes are not intended to be ready-to-use, they can be easily adapted with a little tweaking for use in a real system.

This book is organized into nine chapters that are largely self-contained. Thus, the material can be rearranged or omitted depending on the background and interests of the instructor or reader. It is advised, however, that Chapter 1 would be explored first, because it contains an introduction to real-time systems as well as the necessary terminology.

Each of the chapters contains both easy and more challenging exercises that stimulate the reader to confront actual problems. The exercises, however, cannot serve as a substitute for carefully planned laboratory work or practical experience.

The first chapter provides an overview of the nature of real-time systems. Much of the basic vocabulary relating to real-time systems is developed along with a discussion of the main challenges facing the real-time system designer. Besides, a brief historical review is given. The purpose of this chapter is to foreshadow the rest of the book as well as quickly acquaint the reader with pertinent terminology.

The second chapter presents a detailed review of central computer architecture concepts from the perspective of the real-time systems designer. Specifically, the impact of advanced architectural features on real-time performance is discussed. The remainder of the chapter outlines different memory technologies, input/output techniques, and peripheral support for embedded systems. The intent here is to increase the reader’s awareness of the impact of the computer architecture on various design considerations.

Chapter 3 provides the core of the text for those who are building practical real-time systems. This comprehensive chapter describes the three principal real-time kernel services: scheduling/dispatching, intertask communication/synchronization, and memory management. It also covers special problems inherent in these designs, such as deadlock and priority inversion.

Chapter 4 begins with a discussion of specific language features desirable in good software engineering practice in general and real-time systems design in particular. An evaluative review of several widely used programming languages in real-time systems design, with respect to these features, follows. Our intent is to provide explicit criteria for rating a language’s ability to support real-time systems and to alert the user to the possible drawbacks of using each language in real-time applications.

In Chapter 5, the nature of requirements engineering is first discussed. Then a collection of rigorous techniques in real-time system specification is presented with illustrative examples. Such rigorous methods are particularly useful when automatic design and code-generation approaches are to be used later in the development life cycle. Next, structured and object-oriented methodologies are discussed as alternative paradigms for requirements writing. At the end of this chapter, an extensive case study is provided.

Chapter 6 surveys several commonly applied design specification techniques used in both structured and object-oriented design. An emphasis on their applicability to real-time systems is made throughout. No single technique is a silver bullet, and the reader is encouraged to adopt his or her own formulation of specification techniques for the given application. A comprehensive design case study is also provided.

Chapter 7 discusses performance analysis techniques based on diverse estimation approaches. The proposed toolset is fully usable even before it is possible to perform any direct measurements. Moreover, a pragmatic discussion on the use of classical queuing theory for analyzing real-time systems is provided. Input/output performance issues are considered with an emphasis on buffer-size calculation. Finally, a focused analysis of memory utilization in real-time systems is presented.

Chapter 8 discusses additional software engineering considerations, including the use of software metrics and techniques for improving the fault-tolerance and overall reliability of real-time systems. Later in the chapter, different techniques for improving reliability through rigorous testing are discussed. Systems integration and performance optimization issues are also considered.

In Chapter 9, we look to the future of real-time systems hardware, software, and applications. Much of this chapter is speculative, and we had great fun imagining things yet to come and the way things ought to be with respect to real-time systems technology. This chapter forms a fruitful basis for class discussions, debates, and student projects.

When our book is used in a university course, typically students are asked to build a real-time multitasking system of their choice. Usually, it is a game on a PC, but some students can be expected to build embedded hardware controllers of moderate complexity. The authors’ assignment to the reader would be to build such a game or simulation, using at least the coroutine model. The application should be useful or at least pleasing, so some sort of a game is a good choice. The mini-project should take no more than 20 hours and cover all phases of the software life cycle model discussed in the text. Hence, those readers who have never built a real-time system will have the benefit of the instructive experience.

Real-time systems engineering is based on more than 50 years of experience and global contributions by numerous individuals and organizations. Rather than clutter the text with endless citations for the origin of each idea, the authors chose to cite only the key ideas where the reader would want to seek out the source for further reading. Some of the text is adapted from two other books written by the first author on software engineering and computer architecture, Laplante (2003) and Gilreath and Laplante (2003), respectively. Where this has been done, it is so noted.

Many solid theoretical treatments of real-time systems exist, and where applicable, they are noted. Nonetheless, these books or journal articles are sometimes too theoretical for practicing software engineers and students who are often impatient to wade through the derivations for the resultant payoff. They want results that they can use now in the trenches, and they want to see how they can be used, not just know that they exist. In this text, an attempt is made to distill the most valuable of the theoretical results, combined with practical experience and insight to provide a toolkit for the practitioner.

This book contains extensive bibliographies at the end of each chapter. Where verbatim phrases were used, and where a figure came from another source, the authors tried to cite it appropriately. However, if any were inadvertently overlooked, the authors wish to correct the unfortunate error. Please notify the authors if you find any errors of omission, commission, citation, and so forth by e-mail, at plaplante@psu.edu or seppo.ovaska@aalto.fi, and they will be corrected at the next possible opportunity.

Since 1992, thousands of copies of the first three editions of this book have been sold to the college text and professional markets throughout the world. The only thing more gratifying than its adoption at such prestigious universities as Carnegie Mellon University, the University of Illinois at Urbana-Champaign, Princeton University, the United States Air Force Academy, Polytechnic University, and many others around the world, has been the enthusiastic feedback received from numerous individuals thankful for the influence that the book has had on them. The continuing international success of the first three editions along with recent technological advancements demanded that a fourth edition be produced.

The most fundamental change in the fourth edition is a new co-author, Dr. Seppo Ovaska, whose vast experience greatly complements that of the first author and adds a strong and timely international perspective.

The fourth edition addresses the important changes that have occurred in the theory and practice in the construction of real-time systems since the publishing of the third edition in 2004. Chapters 1–8 have been carefully revised to incorporate new material, correction of errors, and elimination of outdated material. Moreover, Chapter 9 is a brand-new chapter devoted to future visions on real-time systems. Totally new or substantially revised discussions include:

Multidisciplinary design challenges
Birth and evolution of real-time systems
Memory technologies
Architectural advancements
Peripheral interfacing
Distributed real-time architectures
System services for application programs
Supplementary criteria for multi-core and energy-aware support
Automatic code generation
Life cycle models
Arguments related to parallelization
Uncertainty in real-time systems
Testing patterns and exploratory testing
Real-time device drivers
Future visions on real-time systems

While approximately 30% of previous material has been discarded, another 40% has been added, resulting in a unique and modern text. In addition, several new examples have been included to illustrate various important points. Hence, it is with pride and a sense of accomplishment that we are presenting this timely and carefully composed book to students and practicing engineers.

PHILLIP A. LAPLANTE

West Chester, Pennsylvania

Seppo J. Ovaska

Hyvinkää, Finland

August 2011

REFERENCES

W. F. Gilreath and P. A. Laplante, Computer Architecture: A Minimalist Approach. Norwell, MA: Kluwer Academic Publishers, 2003.

P. A. Laplante, Software Engineering for Image Processing. Boca Raton, FL: CRC Press, 2003.

R. Abhari	M. El-Hawary	O. P. Malik
J. Anderson	B-M. Haemmerli	S. Nahavandi
G. W. Arnold	M. Lanzerotti	T. Samad
F. Canavero	D. Jacobson	G. Zobrist

REAL-TIME SYSTEMS DESIGN AND ANALYSIS

Tools for the Practitioner

PREFACE

REFERENCES

ACKNOWLEDGMENTS