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.