|Advisor:||Edward A. Lee|
Given a common time base, we can take a very different approach to task management than priority-based scheduling. One approach is to apply conservative distributed discrete-event simulation technology, not to simulation, but to embedded real-time software. In this approach, communication between components is by time-stamped messages. Because of the common time base, components can offer assurance of reacting to messages chronologically, in the order of their time stamps. As long as computational resources allow, this mechanism offers very precise timing of time-critical events without reliance on ad-hoc assignment of priorities. Moreover, synchronization is done via time stamps, not mutual exclusion or semaphores, so priority inversion is not possible. An interesting elaboration of this technique, which relies on faster than real-time computation, is to perform optimistic computation with rollback, where obviously interaction with physical actuators offers a physical barrier to rollback.
We are also exploring a second approach, in collaboration with the group of Prof. Tom Henzinger, where a common time base is used to orchestrate synchronous periodic computations in hard real-time systems. In this approach, specifications of networked systems are formally verifiable because of the common time base. Specifically, the common time base enables a precise definition of system state, and so verification techniques based on exhaustive state-space exploration, particularly model checking, are applicable. This offers the possibility of highly reliable systems with provable safety and liveness properties.
Last updated 11/02/00