Constructing predictable real time systems

Author(s)

• Halang, Wolfgang A.
• Stoyenko, Alexander D.

Bibliographic Information

Constructing predictable real time systems

by Wolfgang A. Halang, Alexander D. Stoyenko

（The Kluwer international series in engineering and computer science, SECS 146）（The Kluwer international series in engineering and computer science, . Real-time systems）

Kluwer Academic Publishers, c1991

• : acid-free paper

Note

Includes bibliographical references (p. 287-303) and index

Description and Table of Contents

Description

Vorwort In der Natur entwickelten sich die Echtzeitsysteme seit einigen 100 Mil- Honen Jahren. Tierische Nervensysteme haben zur Aufgabe, auf die Nachrichten aus der Umwelt die Steuerungsbefehle an die aktiven Or- gane zu geben. Dabei spielen zum Beispiel bedingte Reflexe eine wichtige Rolle. Vielleicht kann man die Entstehung des Menschen etwa zu der Zeit ansetzen, als sein sich allmahlich entwickelndes Gehirn Gedanken entwickelte, deren Bedeutung in vorausplanender Weise iiber die gerade vorliegende Situation hinausging. Das fiihrte schliesslich unter anderem zum heutigen Wissenschaftler, der seine Theorien und Systeme aufgrund langwieriger Uberlegungen aufbaut. Die Entwicklung der Computer ging im wesentlichen den umgekehrten Weg. Zunachst diente sie nur der Durchfiihrung "starrer" Programme, wie z.B. das erste programmgesteuerte Rechengerat Z3, das der Unterzeichner im Jahre 1941 vorfiihren konnte. Es folgte unter an- derem ein Spezialgerat zur Fliigelvermessung, das man als den ersten Prozessrechner bezeichnen kann. Es wurden etwa vierzig als Analog- Digital-Wandler arbeitende Messuhren yom Rechnerautomaten abgele- sen und im Rahmen eines Programms als Variable verarbeitet. Abel' auch das erfolgte noch in starrer Reihenfolge. Die echte Prozesssteuerung - heute auch Echtzeitsysteme genannt - erfordert aber ein Reagieren auf bestandig wechselnde Situationen.

Table of Contents

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.

by "Nielsen BookData"

Details

• NCID: BA13365913
• ISBN:
  • 0792392027
• LCCN: 91019988
• Country Code: us
• Title Language Code: eng
• Text Language Code: eng
• Place of Publication: Boston
• Pages/Volumes: xxix, 311 p.
• Size: 25 cm
• Classification:
  • LCC : QA76.54
  • DC20 : 004/.33
• Subject Headings:
  • LCSH : Real-time data processing
  • LCSH : System design
• Parent Bibliography ID:
  • BA0004729X
  • BA0004729X