Scheduling real-time transactions: a performance evaluation

Reviewer: Susan Ann Mengel

The authors present a readable paper about scheduling real-time database transactions. They present appropriate motivation for their work and outline what their work does and does not address. The list of references can serve as a good starting point for those interested in the area. The paper starts by showing a motivation for real-time database transactions in the example of a database to model a financial market, where stock trading must be performed within a limited time frame or lower prices will be forfeit. The authors discuss previous work to a limited degree, relying mostly on references to papers. They present their algorithms for scheduling real-time transactions in which the release time (earliest time a transaction can start), deadline, and estimate of the duration of the transaction are factors. Their algorithms have the objective of reducing missed deadlines. The algorithms for managing overloads (whenever transaction timing constraints are violated) are “all eligible,” in which transactions are not aborted; “not tardy,” which aborts transactions that have missed deadlines; and “feasible deadlines,” in which transactions with infeasible deadlines are aborted. They can assign priorities in three ways: “First come first served” gives a high priority to the transaction with the earliest release time. “Earliest deadline” gives a high priority to the transaction with the earliest deadline. “Least slack” assigns priorities based on the amount of time a transaction has before execution must begin in order to make its deadline (the time may be evaluated once or continuously). Four concurrency control methods are presented (to serialize concurrent transactions). In the “wait” approach, all transactions must wait on a locked portion of the database regardless of priority inversion (high priority waits on low priority). In “wait promote,” priority inversion is handled by raising the priority of the lower blocking transaction. In “high priority,” a higher priority transaction preempts a lower priority transaction only if the lower priority transaction will not eventually gain a higher priority than the preempting transaction (under the least slack algorithm). “Conditional restart” is like high priority, but the transaction is not aborted if it can finish within the slack time of the higher priority transaction. IO scheduling, needed to service high-priority requests even if seek time is not minimized, is either first-in first-out (close to transaction priorities) or priority, in which high-priority transactions can leap over low-priority transactions. The algorithms are simulated in a variety of combinations, with the usual simplifying assumptions of ignoring time to detect deadlocks and execute locks. Experiments are performed with the database completely in memory and with the database on disk. Many simulation results are presented. The proliferation of abbreviations of the different algorithm combinations is sometimes confusing. When the database is disk-resident, least slack, wait promote, and priority IO scheduling are best overall. When the database is memory-resident, earliest deadline is best at lower loads, least slack is best at higher loads, and wait promote and conditional restart perform well with least slack.