Deadline and Period Assignment for Update Transactions in Co-Scheduling Environment

Abstract

Deriving deadline and period for update transactions to maintain temporal consistency has long been recognized as an important problem in real-time database research. Despite years of active study, most of the past work only focuses on the scheduling of update transactions, and neglects the impact of control transactions by assuming an <i>Update First</i> policy where control transactions are always assigned lower priorities than the update transactions. On the other hand, most existing work on co-scheduling of update and control transactions has been focused on meeting the deadlines of all the control transactions while maximizing the quality of data of the real-time data objects. In this paper, we study the co-scheduling problem of update and control transactions by satisfying the deadline constraints of control transactions and the temporal validity constraints of update transactions simultaneously. Specifically, we consider the problem of how to derive deadline and period for update transactions to maintain the temporal consistency of real-time data objects, while guaranteeing the hybrid transaction set to be EDF-schedulable. To address this problem, we first borrow the idea from <inline-formula><tex-math notation="LaTeX">$\mathsf{minD}$</tex-math> </inline-formula> <xref ref-type="bibr" rid="ref14">[14]</xref> to derive a solution called <inline-formula><tex-math notation="LaTeX">$\mathsf{minD}^\ast$</tex-math></inline-formula> , which can compute deadline and period for update transactions effectively. Next, based on a sufficient condition to derive the minimum possible deadline for each update transaction, we propose a more efficient algorithm <i>Minimum Deadline Calculation </i> ( <inline-formula><tex-math notation="LaTeX">$\mathsf{MDC}$</tex-math></inline-formula> ), which can guarantee to derive a solution, given that one does exist. Finally, the effectiveness and efficiency of the proposed algorithms are validated through extensive simulation experiments.