An Empirical Investigation of Four Strategies for Serializing Schedules in Transaction Processing

Abstract

A database management system (DBMS) is a very large program that allows users to create and maintain databases. A DBMS has many capabilities. This study will focus on the capability known as transaction management, the capability to provide correct, concurrent access to the database by many users at the same time. If a DBMS did not provide transaction management, livelocks, deadlocks, and non-serializable schedules could occur. A livelock can occur when a transaction is waiting on a locked data item, and another transaction appears. After the data item is unlocked, the second transaction locks the data item, which causes the first transaction to continue waiting. Conceivably, the first transaction could wait indefinitely to lock the data item. This situation is called livelock. Deadlock is a situation in which each member of a set of two or more transactions is waiting to lock an item currently locked by some other transaction in the set. None of the transactions can proceed, so they all wait indefinitely. A schedule is serial if for every pair of transactions, all of the operations of one transaction execute before any of the operations of the other transaction. A schedule is serializable if its effect on the database is the same as some serial execution of the same set of transactions. A schedule is nonserializable if its effect on the database is not equivalent to that of any serial schedule which processes the same transactions. The scheduler is a component of the DBMS, and it is responsible for resolving any livelocks, deadlocks, or non-serializable schedules that occur. This study looks specifically at non-serializable schedules. There are many methods by which the scheduler can serialize non-serializable schedules. This study proposes and examines four strategies to detect and resolve non-serializable schedules. Computer simulation is used to examine the four strategies. These strategies reduce a nonserializable schedule to a serializable or a serial schedule, thus eliminating the possibility of incorrectly updating data items within a database. It is shown experimentally that, of the four strategies, the one that delays the transaction which has executed the least number of steps until non-serializability is detected is the best.