Dynamic transaction scheduling and reallocation in overloaded real-time database systems

Abstract

We introduce a novel scheduling architecture with a new algorithm for dynamically resolving transient overloads, that is executed when a new transaction cannot be admitted to the system due to scarce resources. The resolver algorithm generates a cost effective overload resolution plan which, in order to admit the new transaction, finds the required time by de-allocating time among the previously admitted but not yet completed transactions. Considering the cost efficiency of executing the plan and the importance of the new transaction a decision is made whether to execute the plan and admit the new transaction, or to reject it. We consider a multi-class transaction workload consisting of hard critical and firm transactions, where critical transactions have contingency transactions that can be invoked during overloads. We present a performance analysis showing to what degree the overload resolver enforces predictability and ensures the timeliness of critical transactions when handling extreme overload scenarios in real-time database systems.