Technical Report Number
Distributed real-time and embedded (DRE) systems have stringent constraints on timeliness and other properties whose assurance is crucial to correct system behavior. Our previous research has shown that detailed models of essential middleware mechanisms can be developed, composed, and for constrained examples verified tractably, using state of the art timed automata model checkers. However, to apply model checking to a wider range of real-time systems, particularly those involving more general forms of preemptive concurrency, new techniques are needed to address decidability and tractability concerns. This paper makes three contributions to research on formal verification and validation of DRE systems. First, it describes how bounded fair scheduling policies introduce a quasi-cyclic structure in the state space of multi-threaded real-time systems. Second, it shows that bounds on the divergence of threads' execution can be determined for that quasi-cyclic structure, which then can be exploited to reduce the complexity of model checking. Third, it presents a case study involving progress-based fair scheduling of multi-threaded processing pipelines, with which the approach is evaluated.
Tidwell, Terry; Gill, Christopher; and Subramonian, Venkita, "Scheduling Induced Bounds and the Verification of Preemptive Real-Time Systems" Report Number: WUCSE-2007-34 (2007). All Computer Science and Engineering Research.
Research at Washington University was supported in part by NSF awards CCF-0615341 (EHS) and CCF-0448562 (CAREER).Permanent URL: http://dx.doi.org/10.7936/K71G0JHQ