Research Assistant: L. C. Shu
An increasing proportion of all computers do not sit in air-conditioned computer centers or even on desktops; they are embedded in automobiles, lathes, microwave ovens, clothes dryers, aluminum rolling mills, and airplane cockpits. The software systems in these computer systems must meet hard deadlines, e.g., a flight control surface must be adjusted several times each second to keep some new aircraft stable. Guaranteeing that these systems meet their deadlines is a problem of great practical importance as well as a significant scientific challenge.
Real-time systems are inherently concurrent and typically manage shared data resources, so they require synchronization to ensure both logical and timing correctness. Mutual exclusion at a coarse level leads to unacceptable blocking, while fine-grain locking does not guarantee consistency. For the class of hard-real-time systems addressed by our research, one desires mechanisms and policies that ensure consistency and minimize worst-case blocking without incurring any unbounded or excessive run-time overheads.
Since most recent work in maintaining integrity of shared data has been carried out in the context of database systems, it is natural to consider adapting database concurrency control techniques to the domain of hard-real-time systems. But since virtually all database concurrency control approaches have been designed to optimize average-case performance rather than worst-case latency, these techniques must be adapted and extended for our purposes. Our approach to adapting concurrency control techniques employs semantic information that is necessarily available at design time for the class of hard-real-time system requiring analytic guarantees of schedulability. For example, we have devised a variant of the version pool algorithm that uses knowledge of task periods and data access sets to reduce blocking and enable predictable, low-overhead implementations with simple data structures.
We have also considered a combination of offline scheduling with online preemptive scheduling based on rate-monotonic scheduling theory. We partition a set of tasks and derive a cyclic schedule for each partition containing more than one task. These cyclic schedules are derived automatically to optimize rate-monotonic schedulability of the whole task set. By "scheduling away" some resource contention and avoiding worst-case phasing of tasks, the hybrid approach can produce schedules superior to pure online scheduling while preserving its main advantages. A prototype tool for deriving cyclic schedules has been constructed.