Extensive work has been done in
the area of real-time transaction scheduling on single-level transaction models, but only
limited work has been done on nested models. For many advanced applications, transactions
are long, complicated, and access data items at various network sites. In conventional
real-time single-level transaction models, a transaction is considered as a flat single
unit of tasks that consists of a sequence of primitive actions with a given deadline.
Priorities in such systems are usually assigned according to the given deadlines of
individual transactions. Schedulers may use these priorities to determine how to allocate
resources. Because of the atomicity requirement of transactions, if there is a failure
during one’s execution, it is rolled back and restarted. Therefore, even if all
transactions are initially schedulable, these rollbacks and restarts may cause them to
miss their deadlines. Thus, a transaction model beyond the flat model is desired to
maximize system performance.
In this project, we have provided solutions
for the scheduling problem that exists in distributed real-time database systems using a
nested transaction model. In this model, a transaction may consist of several
subtransactions, each of which acts as a unit of work. We have proposed two priority
assignment schemes to derive CPU usage and data conflict resolution priorities that are
based on either top-level transactions’ deadlines or individual subtransactions’
work amounts. Nested two-phase locking is used for concurrency control. As this locking
protocol is integrated with the priority-driven preemptive scheduling approach, a problem
known as priority inversion may arise. In order to prevent this problem, two resolution
protocols, priority abort and priority inheritance, are most widely used for flat
transactions. In this project, we have developed two conflict resolution schemes based on
these two protocols for a real-time nested transaction environment. We have conducted
simulations to measure the overall system performance when integrating the priority
assignment schemes and conflict resolution protocols. The simulation results indicate the
following: 1) For nested transactions, if there is high data contention, the priority
assignment scheme which assigns all members of a transaction with the same deadline works
best to derive priorities for both CPU usage and data conflict resolution; otherwise,
individual subtransactions’ deadlines based on their execution times should be used
for CPU usage priority assignment. The abort-based conflict resolution protocol performs
better when the system load is low, while the block-based protocol performs better when
the load is high. 2) For flat transactions, the priority scheme that assigns the same
deadline to all members of a transaction has the best performance, and the abort-based
conflict resolution protocol consistently outperforms the block-based one.
