Representation and Analysis of Real-Time Control Structures.
Abstract
A new notation is introduced for representing real-time scheduling at the task and event level. These schedules are called control structures. The primary constructs included which direct the flow of control are sequencing, iteration, and preemption. Additional notation allows the representation of interrupt masking, task termination by external events, task restart as well as resumption from the point of preemption and codestripping. Algorithms are given for finding the preemption structure of a given control structure in the notation. The types of representable control structures are classified by the topology of their Control Flow Graphs. A terminology for describing real-time properties of control structures is developed, and it is seen that without certain assumptions about task execution times and event timings, conclusions cannot be drawn regarding real-time performance of a control structure. A series of algorithms is presented which make use of these assumptions, and find values for task execution times in the presence of preemption. The algorithms can analyze control structures containing the principal control features; suggestions are given for further development of algorithms which can analyze any representable control structure.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1980
- Accession Number
- ADA089828
Entities
People
- Rowland F. Archer Jr
Organizations
- Massachusetts Institute of Technology