Value-cognizant Admission Control for Real-Time Database Systems

This talk was recently given at the Real-Time Systems Symposium. The corresponding paper can be found at http://www.cs.bu.edu/students/grads/nagy/

Abstract

Admission control and overload management techniques are central to the design and implementation of Real-Time Database (RTDB) Systems. In this talk, we motivate the need for these mechanisms and present protocols for adding such capabilities to RTDB Systems.

Specifically, we propose a new transaction model and new scheduling algorithms for real-time systems. Unlike previous research, our model assumes no knowledge of a transaction's runtime characteristics (e.g. worst-case execution time or other resource requirements). However, such a transaction is always submitted to the system with a compensating task with known worst-case execution time. Our scheduling subsystem consists of two components: an admission controller and a processor scheduler. The admission controller determines whether or not a submitted transaction should be accepted for execution. This decision is based on a feedback mechanism that takes into consideration the status of the system (e.g. processor utilization, amount of conflict over database objects between transactions). If accepted, the processor scheduler guarantees that the transaction will complete before its deadline, or else its compensating task will complete before the transaction's deadline. This guarantee is achieved through the use of novel compensating task scheduling algorithms.