Multiversion Integrated Concurrency Control

for Hard Real-Time Systems

SERC{TR{132{P

Lih-Chyun Shu
Michal Young

Software Engineering Research Center
Department of Computer Sciences
Purdue University

November 1992

Abstract

We describe an integrated multi-version concurrency control protocol for hard real-time systems. The new protocol is based on a combination of protocols originally developed for database systems, but is extended to permit predictable low-overhead implementation with analytical guarantees of worstcase blocking when used with rate-monotonic scheduling. A useful property of the protocol is that long queries do not block short update tasks.

The specific contributions of the paper include formalizing a common implementation strategy (buffering) in a way that facilitates reasoning about correctness and schedulability. More generally, it illustrates an approach to adapting concurrency control protocols to hard-real-time systems by using semantic information (task rates and access patterns, in this case) that is typically available to real-time system designers.

This research was supported by the Software Engineering Research Center, an NSF Industry/University Cooperative Research Center. Additional support for the first author was provided by the Purdue Research Foundation under the David Ross Fellowship program.