Introduction to Timestamp & Deadlock Prevention Schemes | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

Introduction

Deadlock occurs when each transaction T in a schedule of two or more transaction waiting for some item locked by some other transaction T‘ in the set. Thus, both end up in a deadlock situation, waiting for the other to release the lock on the item. Deadlocks are a common problem and we have introduced the problem while solving the Concurrency Control by the introduction of Locks. Deadlock avoidance is a major issue and some protocols were suggested to avoid them, like Conservative 2-PL and Graph Based protocols but some drawbacks are still there.
Here, we will discuss a new concept of Transaction Timestamp TS(T_i). A timestamp is a unique identifier created by the DBMS to identify a transaction. They are usually assigned in the order in which they are submitted to the system, so a timestamp may be thought of as the transaction start time.
There may be different ways of generating timestamps such as

• A simple counter that increments each time its value is assigned to a transaction. They may be numbered 1, 2, 3…. Though we’ll have to reset the counter from time to time to avoid overflow.
• Using the current date/time from the system clock. Just ensuring that no two transactions are given the same value in the same clock tick, we will always get a unique timestamp. This method is widely used.

Deadlock Prevention Schemes based on Timestamp…

As discussed, Timestamps are unique identifiers assigned to each transaction. They are based on the order in which Transactions are started. Say if T₁ starts before T₂ then TS(T₁) will be less then(<) TS(T₂).
There are two schemes to prevent deadlock called wound-wait and wait-die. Say there are two transactions T_i and T_j, now say T_i tries to lock an item X but item X is already locked by some T_j, now in such a conflicting situation the two schemes which prevents deadlock. We’ll use this context shortly.

• Wait_Die: An older transaction is allowed to wait for a younger transaction, whereas a younger transaction requesting an item held by an older transaction is aborted and restarted.
  From the context above, if TS(T_i) < TS(T_j), then (T_i older than T_j) T_i is allowed to wait; otherwise abort T_i (T_i younger than T_j) and restart it later with the same timestamp.
• Wound_Wait: It is just the opposite of the Wait_Die technique. Here, a younger transaction is allowed to wait for an older one, whereas if an older transaction requests an item held by the younger transaction, we preempt the younger transaction by aborting it.
  From the context above, if TS(Ti) < TS(Tj), then (Ti older than Tj) Tj is aborted (i.e., Ti wounds Tj) and restarts it later with the same Timestamp; otherwise (Ti younger than Tj) Ti is allowed to wait.

Thus, both the schemes end up in aborting the younger of the two transactions that may be involved in a deadlock. It is done on the basis of the assumption that aborting the younger transaction will waste less processing which is logical. In such a case there cannot be a cycle since we are waiting linearly in both the cases.
Another group of protocols which prevents deadlock but does not require Timestamps. They are discussed below:

• No-waiting Algorithm: This follows a simple approach, if a Transaction is unable to obtain a lock, it is immediately aborted and then restarted after a certain time delay without checking if a deadlock will occur or not. Here, no Transaction ever waits so there is no possibility for deadlock.
  This method is somewhat not practical. It may cause transaction to abort and restart unnecessarily.
• Cautious Waiting: If T_i tries to lock an item X but is not able to do because X is locked by some T_j. In such a conflict, if T_j is not waiting for some other locked item, then T_i is allowed to wait, otherwise abort T_i.

Another approach, to deal with deadlock is deadlock detection, we can use Wait-for-Graph. This uses a similar approach when we used to check for cycles while checking for serializablity.

Starvation: One problem that may occur when we use locking is starvation which occurs when a transaction cannot proceed for an indefinite period of time while other transactions in the system continue normally. This may occur if the waiting scheme for locked items is unfair, giving priority to some transactions over others. We may have some solutions for Starvation. One is using a first come first serve queue; transactions are enabled to lock an item in the order in which they originally requested the lock. This is a widely used mechanism to reduce starvation. Our Concurrency Control Manager is responsible to schedule the transactions, so it employs different methods to overcome them.

Implementation of Locking in DBMS

Locking protocols are used in database management systems as a means of concurrency control. Multiple transactions may request a lock on a data item simultaneously. Hence, we require a mechanism to manage the locking requests made by transactions. Such a mechanism is called as Lock Manager. It relies on the process of message passing where transactions and lock manager exchange messages to handle the locking and unlocking of data items.

Data structure used in Lock Manager
The data structure required for implementation of locking is called as Lock table.

1. It is a hash table where name of data items are used as hashing index.
2. Each locked data item has a linked list associated with it.
3. Every node in the linked list represents the transaction which requested for lock, mode of lock requested (mutual/exclusive) and current status of the request (granted/waiting).
4. Every new lock request for the data item will be added in the end of linked list as a new node.
5. Collisions in hash table are handled by technique of separate chaining.

Consider the following example of lock table:

Explanation: In the above figure, the locked data items present in lock table are 5, 47, 167 and 15.
The transactions which have requested for lock have been represented by a linked list shown below them using a downward arrow.
Each node in linked list has the name of transaction which has requested the data item like T33, T1, T27 etc.
The colour of node represents the status i.e. whether lock has been granted or waiting.

Note that a collision has occurred for data item 5 and 47. It has been resolved by separate chaining where each data item belongs to a linked list. The data item is acting as header for linked list containing the locking request.

Working of Lock Manager

• Initially the lock table is empty as no data item is locked.
• Whenever lock manager receives a lock request from a transaction T_i on a particular data item Qi following cases may arise:
  1. If Q_i is not already locked, a linked list will be created and lock will be granted to the requesting transaction T_i.
  2. If the data item is already locked, a new node will be added at the end of its linked list containing the information about request made by T_i.

• If the lock mode requested by T_i is compatible with lock mode of transaction currently having the lock, T_i will acquire the lock too and status will be changed to ‘granted’. Else, status of T_i’s lock will be ‘waiting’.
• If a transaction T_i wants to unlock the data item it is currently holding, it will send an unlock request to the lock manager. The lock manager will delete T_i’s node from this linked list. Lock will be granted to the next transaction in the list.
• Sometimes transaction T_i may have to be aborted. In such a case all the waiting request made by T_i will be deleted from the linked lists present in lock table. Once abortion is complete, locks held by T_i will also be released.