Constructing Predictable Real Time Systems

1 Introduction.
- 1.1 Motivation.
- 1.1.1 A Chemical Process Application.
- 1.1.2 A Power Plant Application.
- 1.1.3 A Fighter Aircraft Application.
- 1.1.4 Real Time System Requirements.
- 1.2 Predictability and Simplicity.
- 1.3 Constructing Predictable Real Time SystemsNew Thinking Categories and Optimality Criteria.
- 1.4 Guiding Principles for Predictable, Verifiable Real Time Software and Hardware.
- 1.4.1 Language Assumptions.
- 1.4.2 System Software and Hardware Assumptions.
- 1.5 Book Outline.- 2 Real Time Features of High Level Languages.
- 2.1 A Representative Real Time Application Design.
- 2.2 Historical Development of Real Time Languages.
- 2.3 Requirements of a Real Time Language.
- 2.4 Review of Existing Languages.
- 2.4.1 Pseudocodes and Assembly Languages.
- 2.4.2 FORTRAN.
- 2.4.3 JOVIAL.
- 2.4.4 RTL/1 and RTL/2.
- 2.4.5 PEARL.
- 2.4.6 ILIAD.
- 2.4.7 Modula and Modula-2.
- 2.4.8 PORTAL.
- 2.4.9 Ada.
- 2.4.10 Forth.
- 2.4.11 Languages for Programmable Logic Controllers.
- 2.4.12 Experimental Hard Real Time Languages.
- 2.4.13 Survey Summary.
- 2.5 Taking a Closer Look at Real-Time Euclid.
- 2.5.1 Language Structure.
- 2.5.2 Real Time Units and Time Functions.
- 2.5.3 Absence of Dynamic Data Structures.
- 2.5.4 Time-Bounded Loops.
- 2.5.5 Absence of Recursion.
- 2.5.6 Processes.
- 2.5.7 Condition Variables.
- 2.5.8 Monitors, Signals, Waits and Broadcasts.
- 2.5.9 Exception Handling.
- 2.5.10 Summary.
- 2.6 A Second Review - Focusing on Real Time Features.
- 2.6.1 Selection of Reviewed Languages.
- 2.6.2 A Survey of Real Time Features Supported.
- 2.6.3 A Discussion of Additional Real Time FeaturesNeeded.
- 2.6.4 Summary.
- 2.7 Taking a Closer Look at Ada.
- 2.7.1 Ada's Limitations.
- 2.7.2 Changing Ada.
- 2.8 Taking a Closer Look at PEARL.
- 2.8.1 An Overview of Basic PEARL.
- 2.8.2 PEARL's Limitations.
- 2.8.3 An Overview of Distributed PEARL.
- 2.9 Proposal for an Extension of PEARL.
- 2.9.1 Locks and Timeouts.
- 2.9.2 Timed Synchronisation.
- 2.9.3 Time-Bounded Loops.
- 2.9.4 Status Operators.
- 2.9.5 Surveillance of Event Occurrences.
- 2.9.6 Parallel Processing and Precedence Relations of Tasks Sets.
- 2.9.7 Expressing Timing Constraints.
- 2.9.8 Overload Detection and Handling.
- 2.9.9 Hierarchical Deadlock Prevention.
- 2.9.10 Support of Task-Oriented Hierarchical Storage Management.
- 2.9.11 Exact Timing of Operations.
- 2.9.12 Tracing and Event Recording.
- 2.9.13 Restriction to Static Language Features.
- 2.9.14 Application-Oriented Simulation.
- 2.9.15 Graceful System Degradation Using the Conceptof Imprecise Results.
- 2.9.15.1 Transient Overloads.
- 2.9.15.2 Diversity Based Error Detection and Handling.
- 2.9.16 Synopsis of PEARL Language Extensions.
- 2.9.17 Summary.- 3 Language-Independent Schedulability Analysis of Real Time Programs.
- 3.1 Front End of the Schedulability Analyser.
- 3.1.1 Front End Segment Trees.
- 3.1.2 Condition, Bracket, Subprogram and Process Records.
- 3.1.3 Front End Statistics.
- 3.2 Back End of the Schedulability Analyser.
- 3.2.1 Resolving Segment Trees.
- 3.2.2 Converting Process Trees.
- 3.2.3 A Real Time Model.
- 3.2.3.1 A High Level Model Description.
- 3.2.3.2 A Survey of Real Time Modeling.
- 3.2.3.3 Frame Superimposition Our Solutionof the Model.
- 3.2.3.4 Delays.
- 3.2.3.5 Interruptible Slow-downs.
- 3.2.3.6 Overall Solution Algorithm.
- 3.3 Schedulability Analysis of Real-Time Euclid and Ex-tended PEARL.
- 3.4 Summary.- 4 A Real Time Hardware Architecture.
- 4.1 Useful Analogies.
- 4.2 Properties and Architectural Implications of Comprehen-sive Deadline-Driven Scheduling.
- 4.2.1 Implications of Employing Earliest DeadlineScheduling.
- 4.2.2 Sufficient Conditions for Feasible Task Executabil-ity under Resource Constraints.
- 4.2.3 Non-pre-emptive Deadline Scheduling.
- 4.2.4 Avoiding Context-Switches Without Violation ofFeasibility.
- 4.3 The Layered Structure of Real Time Operating Systems.
- 4.4 Outline of the Architecture.
- 4.5 Comparison with other Architectures.
- 4.6 Task-Oriented and Predictable Storage Management.
- 4.7 Direct Memory Access Without Cycle Stealing.
- 4.7.1 Synchronous Direct Memory Access.
- 4.7.2 Dynamic Bus Subdivision.
- 4.7.3 Integration of a DMA Facility into Dynamic RAM Chips.
- 4.8 Precisely Timed Peripherals.
- 4.8.1 Required Functions and their Invocation in PEARL.
- 4.8.2 Implementation of Hardware Support.
- 4.8.3 Operating System Support.
- 4.8.4 Clock Synchronisation in a Distributed System.
- 4.9 Summary.- 5 An Operating System Kernel and its Dedicated Processor.
- 5.1 Hardware Organisation.
- 5.1.1 Time-Dependent Elements.
- 5.1.2 Event Recognition Modules.
- 5.2 Primary Event Reaction.
- 5.2.1 Representation of Time Schedules.
- 5.2.2 Algorithms and Data Structures of the Time Management.
- 5.2.3 Algorithms and Data Structures of the Event Management.
- 5.2.4 Implementation of Other Features.
- 5.3 Secondary Event Reaction.
- 5.3.1 Functions.
- 5.3.2 Control Programs.
- 5.3.3 Task Control Blocks.
- 5.3.4 Kernel Algorithms.
- 5.4 Summary.- 6 Implementation.
- 6.1 Real-Time Euclid.
- 6.1.1 Compiler.
- 6.1.1.1 Kernel.
- 6.1.1.2 Schedulability Analyser.
- 6.1.1.3 Hardware.
- 6.2 Extended PEARL.
- 6.2.1 Compiler Functions.
- 6.2.2 Run-Time Features.
- 6.3 Summary.- 7 Evaluation.
- 7.1 Real-Time Euclid and its Schedulability Analyser.
- 7.1.1 Applications.
- 7.1.1.1 A Simulated Power Station.
- 7.1.1.2 A Simulated Packet-Level Handshakingin X.25.
- 7.1.1.3 Schedulability Analyser Evaluation.
- 7.2 Qualitative Evaluation of the Co-processor Architecture..
- 7.3 Summary.- 8 Outlook.
- 8.1 Summary of Contributions.
- 8.2 Directions for Future Research.

` I ... therefore highly highly recommend this book for industrial and academic use. '
Media Reviews, February 1993