Transaction scheduling in firm real-time database systems
Jayant R. Haritsa · Minds at UW (University of Wisconsin) · 1992
A growing number of database applications are having to meet real-time requirements. These timing requirements may be expressed at the database system interface by assigning completion deadlines to transactions. In this thesis, we study the problem of transaction scheduling in database systems supporting such real-time applications. In particular, we focus on applications with firm deadlines. Firm-deadline applications consider transactions that do not complete by their deadlines to be worthless and therefore discard late transactions. Within the firm-deadline context, two cases that differ in the utility associated with completing a transaction before its deadline are examined here. In the same-value case, all transactions have equal utility from the application's perspective and the goal of the real-time database system is to maximize the number of in-time transactions. In the multiple-value case, different transactions have different utilities to the application and the goal of the real-time database system is to maximize the total value of the in-time transactions. In this thesis, we present new real-time concurrency control protocols and priority assignment policies for transaction scheduling in the same-value and the multiple-value cases. The concurrency control protocols are based on the optimistic approach to maintaining database consistency. The priority policies are based on simple real-time scheduling observations and adapt their priority assignment to match the database operating environment. Results from a wide range of simulation experiments indicate that the real-time optimistic concurrency control protocols are fundamentally better suited than their locking-based counterparts to the firm-deadline environment. The results also show that the adaptive priority policies provide better performance than fixed priority policies. In particular, for the multiple-value case, priority policies that adaptively change the relative importance of transaction values and deadlines deliver considerably better performance than policies that establish fixed tradeoffs between these characteristics. In summary, this thesis sheds light on issues involved in real-time transaction scheduling, and presents new scheduling algorithms that come closer to meeting the challenges of the real-time domain.