Module-3

Concurrency Control Techniques:

• Concurrency control protocols(sets of rules) that guarantee serializability.
• One important set of protocols—two-phase locking protocols— employs the technique
of locking data items to prevent multiple transactions from accessing the items
concurrently.
• Another set of concurrency control protocols uses timestamps. A timestamp is a unique
identifier for each transaction, generated by the system. Timestamp values are generated
in the same order as the transaction start times.

• Two-Phase Locking Techniques for Concurrency Control:

• Some of the main techniques used to control concurrent execution of transactions are
based on the concept of locking data items.
• A lock is a variable associated with a data item that describes the status of the item with
respect to possible operations that can be applied to it. Generally, there is one lock for
each data item in the database.
• Locks are used as a means of synchronizing the access by concurrent transactions to the
database items.
Types of Locks
Binary Locks:
• A binary lock can have two states or values: locked and unlocked (or 1 and 0, for
simplicity).
• A distinct lock is associated with each database item X.
• If the value of the lock on X is 1, item X cannot be accessed by a database operation that
requests the item.
• If the value of the lock on X is 0, the item can be accessed when requested, and the lock
value is changed to 1.
• We refer to the current value (or state) of the lock associated with item X as lock(X).
• Two operations, lock_item and unlock_item, are used with binary locking.
• A transaction requests access to an item X by first issuing a lock_item(X) operation.
• Transaction T must unlock any items it had locked before T terminates
• It is simple to implement a binary lock; all that is needed is a binary-valued variable,
LOCK, associated with each data item X in the database.
• If the simple binary locking scheme described here is used, every transaction must obey
the following rules:

1. A transaction T must issue the operation lock_item(X) before any read_item(X) or

write_item(X) operations are performed in T.

2. A transaction T must issue the operation unlock_item(X) after all read_item(X) and
write_item(X) operations are completed in T.

3. A transaction T will not issue a lock_item(X) operation if it already holds the lock on
item X.

4. A transaction T will not issue an unlock_item(X) operation unless it already holds the
lock on item X.
2. Shared/Exclusive (or Read/Write) Locks:
• The preceding binary locking scheme is too restrictive for database items because at most
one transaction can hold a lock on a given item.
• A different type of lock, called a multiple-mode lock, also called shared/exclusive or
read/write locks is used.
• There are three locking operations: read_lock(X), write_lock(X), and unlock(X).
• A lock associated with an item X, LOCK(X), now has three possible states: read-locked,
write-locked, or unlocked.
• A read-locked item is also called share-locked because other transactions are allowed to
read the item, whereas a write-locked item is called exclusive-locked because a single
transaction exclusively holds the lock on the item.
When we use the shared/exclusive locking scheme, the system must enforce the following rules:

1. A transaction T must issue the operation read_lock(X) or write_lock(X) before any read_item(X)
operation is performed in T.

2. A transaction T must issue the operation write_lock(X) before any write_item(X) operation is performed
in T.

3. A transaction T must issue the operation unlock(X) after all read_item(X) and write_item(X) operations
are completed in T.

4. A transaction T will not issue a read_lock(X) operation if it already holds a read (shared) lock or a write
(exclusive) lock on item X.

5. A transaction T will not issue a write_lock(X) operation if it already holds a read (shared) lock or write
(exclusive) lock on item X.

6. A transaction T will not issue an unlock(X) operation unless it already holds a read (shared) lock or a write
(exclusive) lock on item X.
3. Conversion (Upgrading, Downgrading) of Locks:

• It is desirable to relax conditions 4 and 5 in the preceding list in order to allow lock
conversion; that is, a transaction that already holds a lock on item X is allowed under
certain conditions to convert the lock from one locked state to another.
• For example, it is possible for a transaction T to issue a read_lock(X) and then later to
upgrade the lock by issuing a write_lock(X) operation.
• It is also possible for a transaction T to issue a write_lock(X) and then later to downgrade
the lock by issuing a read_lock(X) operation.
Guaranteeing Serializability by Two-Phase Locking

• A transaction is said to follow the two-phase locking protocol if all locking operations
(read_lock, write_lock) precede the first unlock operation in the transaction.
• Such a transaction can be divided into two phases: an expanding or growing (first)
phase, during which new locks on items can be acquired but none can be released; and a
shrinking (second) phase, during which existing locks can be released but no new locks
can be acquired.
• The above transactions do not follow the two-phase locking protocol because the
write_lock(X) operation follows the unlock(Y) operation in T1, and similarly the
write_lock(Y) operation follows the unlock(X) operation in T2.
• If we enforce two-phase locking, the transactions can be rewritten as T1′ and T2′
• There are a number of variations of two-phase locking (2PL). The technique just
described is known as basic 2PL.
• A variation known as conservative 2PL (or static 2PL) requires a transaction to lock all
the items it accesses before the transaction begins execution, by predeclaring its read-set
and write-set.
• Conservative 2PL is a deadlock-free protocol.
• The most popular variation of 2PL is strict 2PL, which guarantees strict schedules. In
this variation, a transaction T does not release any of its exclusive (write) locks until after
it commits or aborts. Hence, no other transaction can read or write an item that is written
by T unless T has committed, leading to a strict schedule for recoverability. Strict 2PL is
not deadlock-free.
• A more restrictive variation of strict 2PL is rigorous 2PL, which also guarantees strict
schedules. In this variation, a transaction T does not release any of its locks (exclusive or
shared) until after it commits or aborts, and so it is easier to implement than strict 2PL.
Deadlock:
• The use of locks can cause two additional problems: deadlock and starvation.

• Deadlock occurs when each transaction T in a set of two or more transactions is waiting for some item that is locked by
some other transaction T1 in the set. Hence, each transaction in the set is in a waiting queue, waiting for one of the other
transactions in the set to release the lock on an item. But because the other transaction is also waiting, it will never
release the lock.

• Where the two transactions T1 and T2 are deadlocked in a partial schedule;T1 is in the waiting queue for X, which is
locked by T2, while T2 is in the waiting queue for Y, which is locked by T1. Meanwhile, neither T1 nor T2 nor any other
transaction can access items X and Y.
• Deadlock Prevention Protocols:
1. One deadlock prevention protocol:
• used in conservative two-phase locking.
• that every transaction lock all the items it needs in advance (which is generally not
a practical assumption).
• if any of the items cannot be obtained, none of the items are locked.
• the transaction waits and then tries again to lock all the items it needs.
2. A second protocol:
• limits concurrency.
• it involves ordering all the items in the database and making sure that a transaction
that needs several items will lock them according to that order.
• it requires that the programmer (or the system) is aware of the chosen order of the
items, which is also not practical in the database context.
• A number of other deadlock prevention schemes have been proposed that make a
decision about what to do with a transaction involved in a possible deadlock
situation:
• Should it be blocked and made to wait
• or should it be aborted,
• or should the transaction preempt and abort another transaction? .

• Some of these techniques use the concept of transaction timestamp TS(T), which
is a unique identifier assigned to each transaction.
• The timestamps are typically based on the order in which transactions are started;
hence, if transaction T1 starts before transaction T2, then TS(T1) < TS(T2).
• Notice that the older transaction (which starts first) has the smaller timestamp
value.
• Two schemes that prevent deadlock based on timestamp are called wait-die and wound-
wait.

• Suppose that transaction Ti tries to lock an item X but is not able to because X is locked by
some other transaction Tj with a conflicting lock. The rules followed by these schemes are
• In 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.

• The wound-wait approach does the opposite: A younger transaction is allowed to wait for
an older one, whereas an older transaction requesting an item held by a younger
transaction preempts the younger transaction by aborting it. Both schemes end up aborting
the younger of the two transactions (the transaction that started later) that may be involved
in a deadlock, assuming that this will waste less processing.

• It can be shown that these two techniques are deadlock-free, since in wait-die, transactions
only wait for younger transactions so no cycle is created.

• Similarly, in wound-wait, transactions only wait for older transactions so no cycle is

created.

• However, both techniques may cause some transactions to be aborted and restarted
needlessly, even though those transactions may never actually cause a deadlock.
• Another group of protocols that prevent deadlock do not require timestamps.
• no waiting (NW) algorithms.
• cautious waiting (CW) algorithms.

• no waiting (NW) algorithms.

• In the no waiting algorithm, if a transaction is unable to obtain a lock, it is
immediately aborted and then restarted after a certain time delay without checking
whether a deadlock will actually occur or not.
• In this case, no transaction ever waits, so no deadlock will occur.
• This scheme can cause transactions to abort and restart needlessly.
• cautious waiting (CW) algorithms.
• The cautious waiting algorithm was proposed to try to reduce the number of needless
aborts/restarts.
• Suppose that transaction Ti tries to lock an item X but is not able to do so because X is locked by
some other transaction Tj with a conflicting lock.
• The cautious waiting rules are as follow

• It can be shown that cautious waiting is deadlock-free, because no transaction will ever wait for another
blocked transaction.
Deadlock Detection:

• A second, more practical approach to dealing with deadlock is deadlock detection, where
the system checks if a state of deadlock actually exists.
• This solution is attractive if we know there will be little interference among the
transactions—that is, if different transactions will rarely access the same items at the
same time.
• This can happen if the transactions are short and each transaction locks only a few
items, or if the transaction load is light.

• On the other hand, if transactions are long and each transaction uses many items, or if the
transaction load is quite heavy, it may be advantageous to use a deadlock prevention
scheme.
• A simple way to detect a state of deadlock is for the system to construct and maintain a
wait-for graph.
• One node is created in the wait-for graph for each transaction that is currently
executing.
• Whenever a transaction Ti is waiting to lock an item X that is currently locked by a
transaction Tj , a directed edge (Ti → Tj ) is created in the wait-for graph.
• When Tj releases the lock(s) on the items that Ti was waiting for, the directed edge is
dropped from the wait-for graph.
• We have a state of deadlock if and only if the wait-for graph has a cycle.
• One problem with this approach is the matter of determining when the system
should check for a deadlock.
• One possibility is to check for a cycle every time an edge is added to the wait-
for graph, but this may cause excessive overhead.
• If the system is in a state of deadlock, some of the transactions causing the
deadlock must be aborted. Choosing which transactions to abort is known as victim
selection.
• The algorithm for victim selection should generally avoid selecting transactions
that have been running for a long time and that have performed many updates, and
it should try instead to select transactions that have not made many changes
(younger transactions).
Timeouts:

• Another simple scheme to deal with deadlock is the use of timeouts.

• This method is practical because of its low overhead and simplicity.

• In this method, if a transaction waits for a period longer than a system-defined timeout
period, the system assumes that the transaction may be deadlocked and aborts it—
regardless of whether a deadlock actually exists or not.
Starvation.
• Another 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.
• One solution for starvation is to have a fair waiting scheme, such as using a first-come-first-served queue;
transactions are enabled to lock an item in the order in which they originally requested the lock.
• Another scheme allows some transactions to have priority over others but increases the priority of a
transaction the longer it waits, until it eventually gets the highest priority and proceeds.
• Starvation can also occur because of victim selection if the algorithm selects the same transaction as victim
repeatedly, thus causing it to abort and never finish execution.
• The algorithm can use higher priorities for transactions that have been aborted multiple times to avoid this
problem.
• The wait-die and wound-wait schemes discussed previously avoid starvation, because they restart a
transaction that has been aborted with its same original timestamp, so the possibility that the same
transaction is aborted repeatedly is slim.
Concurrency control based on timestamp ordering:

• If a transaction needs an item that is already locked, it may be forced to wait until the item is released. Some
transactions may be aborted and restarted because of the deadlock problem.

• A different approach that guarantees serializability involves using transaction timestamps to order transaction
execution for an equivalent serial schedule.

Timestamps:

• A timestamp is a unique identifier created by the DBMS to identify a transaction. Typically, timestamp
values are assigned in the order in which the transactions are submitted to the system, so a timestamp can
be thought of as the transaction start time.

• The timestamp of transaction T as TS(T).

• Concurrency control techniques based on timestamp ordering do not use locks; hence, deadlocks cannot
occur.
Timestamps can be generated in several ways:
• One possibility is to use a counter that is incremented each time its value is assigned
to a transaction.
• The transaction timestamps are numbered 1, 2, 3, ... in this scheme.
• A computer counter has a finite maximum value, so the system must periodically reset
the counter to zero when no transactions are executing for some short period of time.
• Another way to implement timestamps is to use the current date/time value of the
system clock and ensure that no two timestamp values are generated during the same
tick of the clock.
The Timestamp Ordering Algorithm:
• The idea for this scheme is to order the transactions based on their timestamps.
• The timestamp-ordering protocol ensures serializability among transactions in their
conflicting read and write operations. This is the responsibility of the protocol system that
the conflicting pair of tasks should be executed according to the timestamp values of
the transactions. This is called timestamp ordering (TO).
• The algorithm must ensure that, for each item accessed by conflicting operations in the
schedule, the order in which the item is accessed does not violate the timestamp
order.
The algorithm associates with each database item X two timestamp (TS) values:

read_TS(X):
The read timestamp of item X is the largest timestamp among all the timestamps of
transactions that have successfully read item X—that is, read_TS(X) = TS(T), where T is
the youngest transaction that has read X successfully.

write_TS(X):
The write timestamp of item X is the largest of all the timestamps of transactions that
have successfully written item X—that is, write_TS(X) = TS(T), where T is the youngest
transaction that has written X successfully.
Basic Timestamp Ordering (TO):

• Whenever some transaction T tries to issue a read_item(X) or a write_item(X) operation, the basic TO
algorithm compares the timestamp of T with read_TS(X) and write_TS(X) to ensure that the timestamp order
of transaction execution is not violated.

• If this order is violated, then transaction T is aborted and resubmitted to the system as a new transaction
with a new timestamp. If T is aborted and rolled back, any transaction T1 that may have used a value written
by T must also be rolled back. Similarly, any transaction T2 that may have used a value written by T1 must
also be rolled back, and so on.

• This effect is known as cascading rollback and is one of the problems associated with basic TO, since the
schedules produced are not guaranteed to be recoverable.

• An additional protocol must be enforced to ensure that the schedules are recoverable, cascadeless, or strict.
The concurrency control algorithm must check whether conflicting operations violate the timestamp ordering
in the following two cases:

1. Whenever a transaction T issues a write_item(X) operation, the following is checked:

• a. If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then abort and roll back T and reject the operation. This
should be done because some younger transaction with a timestamp greater than TS(T)—and hence after T
in the timestamp ordering—has already read or written the value of item X before T had a chance to write X,
thus violating the timestamp ordering.

• b. If the condition in part (a) does not occur, then execute the write_item(X) operation of T and set
write_TS(X) to TS(T).

2. Whenever a transaction T issues a read_item(X) operation, the following is checked:

• a. If write_TS(X) > TS(T), then abort and roll back T and reject the operation. This should be done because
some younger transaction with timestamp greater than TS(T)—and hence after T in the timestamp
ordering—has already written the value of item X before T had a chance to read X.

• b. If write_TS(X) ≤ TS(T), then execute the read_item(X) operation of T and set read_TS(X) to the larger of
TS(T) and the current read_TS(X).
• Whenever the basic TO algorithm detects two conflicting operations that occur in the
incorrect order, it rejects the later of the two operations by aborting the transaction that
issued it.
• The schedules produced by basic TO are hence guaranteed to be conflict serializable, like
the 2PL protocol.
• However, some schedules are possible under each protocol that are not allowed under the
other. Thus, neither protocol allows all possible serializable schedules. As mentioned
earlier, deadlock does not occur with timestamp ordering.
• However, cyclic restart (and hence starvation) may occur if a transaction is continually
aborted and restarted.
Strict Timestamp Ordering (TO):

• A variation of basic TO called strict TO ensures that the schedules are both strict (for easy
recoverability) and (conflict) serializable.

• In this variation, a transaction T that issues a read_item(X) or write_item(X) such that

TS(T) > write_TS(X) has its read or write operation delayed until the transaction T1 that
wrote the value of X (hence TS(T1) = write_TS(X)) has committed or aborted.

• To implement this algorithm, it is necessary to simulate the locking of an item X that has
been written by transaction T1 until T1 is either committed or aborted. This algorithm does
not cause deadlock, since T waits for T1 only if TS(T) > TS(T1).