DBMS-Database Transactions and Query Processing4.4-Lock-Based Protocols and Timestamp-Based Protocols

 Lock-Based Protocols and Timestamp-Based Protocols

Lock-Based Protocols

 A lock is a mechanism to control concurrent access to a

data item

 Data items can be locked in two modes :

1. exclusive (X) mode. Data item can be both read as well as

written. X-lock is requested using lock-X instruction.

2. shared (S) mode. Data item can only be read. S-lock is

requested using lock-S instruction.

 Lock requests are made to concurrency-control manager.

Transaction can proceed only after request is granted.

Lock-Based Protocols (Cont.)

 Lock-compatibility matrix

 A transaction may be granted a lock on an item if the requested

lock is compatible with locks already held on the item by other

transactions

 Any number of transactions can hold shared locks on an item,

but if any transaction holds an exclusive on the item no other

transaction may hold any lock on the item.

 If a lock cannot be granted, the requesting transaction is made

to wait till all incompatible locks held by other transactions have

been released. The lock is then granted.

4

Lock-Based Protocols (Cont.)

 Lock-compatibility matrix

 A transaction may be granted a lock on an item if the requested

lock is compatible with locks already held on the item by other

transactions

 Any number of transactions can hold shared locks on an item,

but if any transaction holds an exclusive on the item no other

transaction may hold any lock on the item.

 If a lock cannot be granted, the requesting transaction is made

to wait till all incompatible locks held by other transactions have

been released. The lock is then granted.

5

Lock-Based Protocols (Cont.)

 Example of a transaction performing locking:

T2

: lock-S(A);

read (A);

unlock(A);

lock-S(B);

read (B);

unlock(B);

display(A+B)

 Locking as above is not sufficient to guarantee serializability — if A and B

get updated in-between the read of A and B, the displayed sum would be

wrong.

 A locking protocol is a set of rules followed by all transactions while

requesting and releasing locks. Locking protocols restrict the set of

possible schedules.

6

PCCOE, Pune Prof. Rahul Patil 4/28/2022

Pitfalls of Lock-Based Protocols

 Consider the partial schedule

 Neither T3 nor T4 can make progress — executing lock-S(B) causes T4

to wait for T3

to release its lock on B, while executing lock-X(A) causes

T3

to wait for T4

to release its lock on A.

 Such a situation is called a deadlock.

 To handle a deadlock one of T3 or T4 must be rolled back

and its locks released.

Pitfalls of Lock-Based Protocols (Cont.)

 The potential for deadlock exists in most locking protocols.

Deadlocks are a necessary evil.

 Starvation is also possible if concurrency control

manager is badly designed. For example:

 A transaction may be waiting for an X-lock on an item,

while a sequence of other transactions request and

are granted an S-lock on the same item.

 The same transaction is repeatedly rolled back due to

deadlocks.

 Concurrency control manager can be designed to prevent

starvation.

The Two-Phase Locking Protocol

 This is a protocol which ensures conflict-

serializable schedules.

 Phase 1: Growing Phase

 transaction may obtain locks

 transaction may not release locks

 Phase 2: Shrinking Phase

 transaction may release locks

 transaction may not obtain locks

The Two-Phase Locking Protocol (Cont.)

 Two-phase locking does not ensure freedom from

deadlocks

 Cascading roll-back is possible under two-phase locking.

To avoid this, follow a modified protocol called strict two-

phase locking. Here a transaction must hold all its

exclusive locks till it commits/aborts.

 Rigorous two-phase locking is even stricter: here all

locks are held till commit/abort. In this protocol

transactions can be serialized in the order in which they

commit.

10

Timestamp-Based Protocols

 Each transaction is issued a timestamp when it enters the

system. If an old transaction Ti has time-stamp TS(Ti

), a new

transaction Tj

is assigned time-stamp TS(Tj

) such that TS(Ti

)

<TS(Tj

).

 The protocol manages concurrent execution such that the

time-stamps determine the serializability order.

 In order to assure such behavior, the protocol maintains for

each data Q two timestamp values:

 W-timestamp(Q) is the largest time-stamp of any

transaction that executed write(Q) successfully.

 R-timestamp(Q) is the largest time-stamp of any

transaction that executed read(Q) successfully.

Timestamp-Based Protocols (Cont.)

 The timestamp ordering protocol ensures that any conflicting

read and write operations are executed in timestamp order.

 Suppose a transaction Ti

issues a read(Q)

1. If TS(Ti

)  W-timestamp(Q), then Ti needs to read a value of Q

that was already overwritten. Hence, the read operation is

rejected, and Ti

is rolled back.

2. If TS(Ti

) W-timestamp(Q), then the read operation is

executed, and R-timestamp(Q) is set to the maximum of R-

timestamp(Q) and TS(Ti

).

Timestamp-Based Protocols (Cont.)

 Suppose that transaction Ti

issues write(Q).

 If TS(Ti

) < R-timestamp(Q), then the value of Q that Ti

is

producing was needed previously, and the system

assumed that that value would never be produced. Hence,

the write operation is rejected, and Ti

is rolled back.

 If TS(Ti

) < W-timestamp(Q), then Ti

is attempting to write

an obsolete value of Q. Hence, this write operation is

rejected, and Ti

is rolled back.

 Otherwise, the write operation is executed, and W-

timestamp(Q) is set to TS(Ti

).