An Admission Control Paradigm for Real-Time Databases?
Computer Science Department
Boston, MA 02215
We propose and evaluate an admission control paradigm for RTDBS, in which
a transaction is submitted to the system as a pair of processes: a primary task,
and a recovery block. The execution requirements of the primary task are not
known a priori, whereas those of the recovery block are known a priori. Upon
the submission of a transaction, an Admission Control Mechanism is employed
to decide whether to admit or reject that transaction. Once admitted, a transaction
is guaranteed to finish executing before its deadline. A transaction is
considered to have finished executing if exactly one of two things occur: Either
its primary task is completed (successful commitment), or its recovery
block is completed (safe termination). Committed transactions bring a profit
to the system, whereas a terminated transaction brings no profit. The goal
of the admission control and scheduling protocols (e.g., concurrency control,
I/O scheduling, memory management) employed in the system is to maximize
system profit. We describe a number of admission control strategies and contrast
(through simulations) their relative performance.
Keywords: Admission control; real-time databases; concurrency control;
scheduling; and resource management.
?This work has been partially supported by NSF (grant CCR-9308344).
The main challenge involved in scheduling transactions in a Real-Time DataBase Management System (RTDBS) is that the resources needed to execute a transaction are not known a priori. For example, the set of objects to be read (written) by a transaction may be dependent on user input (e.g., in a stock market application) or dependent on sensory inputs (e.g., in a process control application). Therefore, the a priori reservation of resources (e.g., read/write locks on data objects) to guarantee a particular Worst Case Execution Time (WCET) becomes impossible|and the non-deterministic delays associated with the on-the-fly acquisition of such resources pose the real challenge of integrating scheduling and concurrency control techniques.
Current real-time concurrency control mechanisms resolve the above challenge by relaxing the deadline semantics (thus suggesting best-effort mechanisms for concurrency control in the presence of soft and firm, but not hard deadlines), or by restricting the set of acceptable transactions to a finite set of transactions with execution requirements that are known a priori (thus reducing the concurrency control problem to that of resource management and scheduling).1