CS3402
1
CS3402 Chapter 11: Concurrency Control
Semester B, 2020/2021
Database Concurrency Control
Purposes of Concurrency Control:
To preserve database consistency
To maximize the system performance (higher concurrency)
A lock is a variable associated with a data item that describes its status with respect to possible operations that can be applied to it.
Generally, there is one lock for each data item.
CS3402 2
Locking Techniques for Concurrency Control
Locking is an operation which secures
(a) permission to read a data item for a transaction
(b) permission to write (update) a data item for a transaction Example:
Lock(X): Data item X is locked on behalf of the requesting transaction
Unlocking is an operation which removes these permissions from the data item
Example:
Unlock(X): Data item X is made available to all other
transactions.
Lock and Unlock are atomic operations
CS3402 3
Type of Locks
Several types of locks are used in concurrency control. Binary locks:
Simple
But too restrictive for database concurrency control purposes
and so are not used much.
Shared/exclusive locks (also known as read/write locks)
CS3402
4
provide more general locking capabilities and are used in database locking schemes.
Binary Lock: States
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.
Locked: If the value of the lock on X is 1, item X cannot be accessed by a database operation that requests the item.
Unlocked: 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.
CS3402 5
Binary Lock: Lock Operation
Two operations, lock_item(X) and unlock_item(X), are used with binary locking.
A transaction requests access to an item X by first issuing a LOCK(X) operation.
▪ If LOCK(X) = 1, the transaction is forced to wait.
▪ If LOCK(X) = 0, it is set to 1 (the transaction locks the item) and
the transaction is allowed to access item X.
CS3402 6
Binary Lock: Unlock Operations
When the transaction finishes accessing the item, it issues an UNLOCK(X) operation, which sets lock of X back to 0 (unlocks the item) so that X may be accessed by other transactions.
Hence, a binary lock enforces mutual exclusion on the data item.
CS3402 7
Read/write locks
Binary locking scheme is too restrictive for database items because at most one transaction can hold a lock on a given item.
We should allow several transactions to access the same item X if they all access X for reading purposes only.
Reason: Read operations on the same item by different transactions are not conflicting
However, if a transaction is to write an item X, it must have exclusive access to X.
Thus, we use read/write locks (also called shared/exclusive locks).
CS3402 8
Read/write locks: States
In read/write locks, a lock associated with an item X, LOCK(X), has three possible states: “read-locked”, “write-locked”, or “unlocked”.
CS3402
9
A read-locked item is also called share-locked because other transactions are allowed to read the item.
A write-locked item is called exclusive-locked because a single transaction exclusively holds the lock on the item.
Read/write locks: Operations
Three locking operations: read_lock(X), write_lock(X), and unlock(X).
Locking is an operation which secures permission to read or write a data item for a transaction
CS3402
10
read_lock(X): More than one transaction can apply shared lock on X for reading its value but no write lock can be applied on X by any other transaction.
write_lock(X): Only one write lock on X can exist at any time and no shared lock can be applied by any other transaction on X.
Unlocking is an operation which removes these permissions from the data item
unlock(X): Data item X is made available to all other transactions.
Implementation of read_lock(X)
The following code performs the read lock operation, read_lock(X):
B: if LOCK(X) = “unlocked” then begin LOCK(X) ← “read-locked”;
CS3402
11
no_of_reads (X) ← 1; end
else if LOCK(X) = “read-locked” then no_of_reads (X) ← no_of_reads (X) +1
else begin wait (until LOCK(X) = “unlocked” and the lock manager wakes up the transaction); go to B
end;
Implementation of write_lock(X):
The following code performs the write lock operation, write_lock(X):
B: if LOCK(X) = “unlocked” then LOCK(X) ← “write-locked”;
CS3402
12
else begin
wait (until LOCK(X)=“unlocked”
and the lock manager wakes up the transaction); go to B
end;
Implementation of unlock(X)
The following code performs the unlock operation, unlock(X):
CS3402
13
if LOCK(X) = “write-locked” then begin LOCK(X) ← “unlocked”;
wakes up one of the transactions, if any end
else if LOCK(X) = “read-locked” then begin
no_of_reads (X) ← no_of_reads (X) -1 if no_of_reads (X) = 0 then
begin
end end;
LOCK(X) = “unlocked”;
wake up one of the transactions, if any
Read/write locks: Rules
When we use the read/write 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 an unlock(X) operation unless it already holds a read lock or a write lock on item X.
CS3402 14
Read/write locks: Rules (cont’d)
5. A transaction T will not issue a read_lock(X) operation if it already holds a read lock or a write lock on item X.
6. A transaction T will not issue a write_lock(X) operation if it already holds a read lock or write lock on item X.
It is desirable to relax conditions 5 and 6 in the preceding list to allow lock conversion:
CS3402
15
A transaction T can issue a write_lock(X) and then later to downgrade the lock by issuing a read_lock(X) operation.
If T is the only transaction holding a read lock on X at the time it issues the write_lock(X) operation, the lock can be upgraded.
Lock conversion
CS3402
16
Lock upgrade: existing read lock to write lock
if Ti has a read-lock (X) and Tj has no read-lock (X) (i ≠ j) then
convert read-lock (X) to write-lock (X) else
force Ti to wait until Tj unlocks X
Lock down grade: existing write lock to read lock
if Ti has a write-lock (X) (*no transaction can have any lock on
X*)
convert write-lock (X) to read-lock (X)
Deadlock
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 T′ 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.
CS3402
17
17
Example of Deadlock
CS3402
18
T1
T2
read_lock (Y); read_item (Y);
write_lock (X);
(waits for X)
write_lock (Y);
read_lock (X); read_item (X);
(waits for Y)
Guaranteeing Serializability by Two-Phase Locking Protocols
CS3402 19
Basic Two Phase Locking (B2PL)
Two rules:
1. If a transaction wants to read (respectively, write) an object, it first
requests a shared (respectively, exclusive) lock on the object.
2. A transaction cannot request additional locks once it releases any lock.
Such a transaction can be divided into two phases:
Expanding phase: New locks on items can be acquired but none can be released. Shrinking phase: Existing locks can be released but no new locks can be acquired.
CS3402
20
20
Basic Two Phase Locking (B2PL)
If lock conversion is allowed:
upgrading of locks (from read-locked to write-locked) must be done
during the expanding phase
downgrading of locks (from write-locked to read-locked) must be done in the shrinking phase.
CS3402
21
21
Basic Two Phase Locking (B2PL)
CS3402
22
Q. Do they follow B2PL? Why?
22
B2PL properties
Theorem: If every transaction in a schedule follows the two-phase locking protocol, then the schedule is guaranteed to be conflict- serializable
Obviate the need to test for serializability of schedules. B2PL enforce serializability but may produce deadlock.
CS3402
23
23
Deadlock
T1
T2
read_lock (Y); read_item (Y);
write_lock (X); (waits for X)
write_lock (Y); (waits for Y)
T1 and T2 follow two-phase policy but deadlock occurs
read_lock (X); read_item (X);
CS3402 24
Conservative Two Phase Locking (C2PL)
C2PL requires a transaction to lock all the items it accesses before the transaction begins execution, by predeclaring read-set & write-set:
Read-set: The set of all items that the transaction reads Write-set: The set of all items that it writes.
If any of the predeclared items needed cannot be locked, the transaction does not lock any item; instead, it waits until all the items are available for locking.
It sets lock of a transaction in one step in the beginning of transaction and releases lock in another step at the end of the transaction.
CS3402 25
Conservative Two Phase Locking (C2PL)
CS3402
26
T1 T2 T1 T2
Write(a) Write(a)
WriteLock(a,b)
Write(b) Commit
Write (b) Commit ReleaseLock(a,b)
Write (b) Commit
WriteLock(a,b) => blocked
WriteLock(a,b)
Write(a) Write(b) Commit ReleaseLock(a,b)
Write(a)
Conservative Two Phase Locking (C2PL)
Conservative 2PL is a deadlock-free protocol. Reason:
If a transaction Ti is waiting for a lock held by Tj, Ti is holding no locks
That is, no hold and wait situation => no deadlock.
However, it is difficult to use in practice because of the need to predeclare
the read-set and write-set, which is not possible in some situations.
CS3402
27
27
Strict Two Phase Locking (S2PL)
Two rules:
1. If a transaction wants to read (respectively, write) an object, it first
requests a shared (respectively, exclusive) lock on the object.
2. All locks held by a transaction are released when the transaction is completed.
CS3402 28
Strict Two Phase Locking (S2PL)
CS3402
29
T1
T2 Write(a)
Write(a)
Write(a)
Write (b)
WriteLock(a) => blocked
Commit Write(b)
Write (b) Commit ReleaseLock(a,b)
Commit
WriteLock(a)
T1
T2
Write(a)
WriteLock(b)
Write(b) Commit ReleaseLock(a,b)
WriteLock(a)
WriteLock(b)
Strict Two Phase Locking (S2PL)
In practice, the most popular variation of 2PL is strict 2PL. S2PL guarantees strict schedule.
A transaction T does not release any of its 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.
It may have the problem of deadlock.
CS3402 30
Performance Issues
Basic 2PL only defines the earliest time when the schedule may release a lock for a transaction.
In Strict 2PL, it requires the scheduler to release all of a transaction’s locks altogether.
In Conservative 2PL, it requires the scheduler to both obtain and release all of a transaction’s locks altogether.
CS3402 31
Performance Issues
Compared with B2PL, S2PL’s lock holding time may be longer and the concurrency may be lower
Compared with C2PL, S2PL’s lock holding time may be shorter and the concurrency may be higher
S2PL is better than C2PL when the transaction workload is not heavy since the lock holding time is shorter in S2PL.
When the transaction is heavy, C2PL is better than S2PL since deadlock may occur in S2PL.
CS3402 32
Resolving Deadlock Problem
CS3402 33
Deadlock Prevention by C2PL
C2PL: A transaction locks all data items it refers to before it begins execution.
This way of locking prevents deadlock since a transaction never hold and wait.
But the concurrency is low.
CS3402 34
Deadlock Prevention using TS
Some of these techniques use the concept of transaction timestamp TS(T′), which is a unique identifier assigned to each transaction T’, e.g., its start time.
Notice that the older transaction (which starts first) has the smaller timestamp value.
E.g., If transaction T1 starts before transaction T2, then TS(T1) < TS(T2).
Two schemes using TS to prevent deadlock: wait-die
wound-wait
CS3402 35
Deadlock Prevention using TS (Wait-die)
Setting:
Transaction Ti tries to lock item X.
But it cannot because some other transaction Tj has locked item X.
Wait-die rule :
If TS(Ti ) < TS(Tj), then Ti is allowed to wait;
Otherwise, abort Ti and restart it later with the same timestamp.
Interpretation:
(Wait) An older transaction is allowed to wait for a younger
transaction;
(Die) A younger transaction requesting an item held by an older
transaction is aborted and restarted.
CS3402 36
Deadlock Example (Without deadlock prevention)
Assumption: TS(U) < TS(T)
Transaction U:
Transaction T:
ReadLock (A); Read (A) WriteLock(B); Write (B)
WriteLock(C) (blocked) (Deadlock formed!)
CS3402
37
ReadLock(C); Read (C) WriteLock(A); (blocked)
Deadlock Example (wait-die)
Assumption: TS(U) < TS(T)
Transaction U:
Transaction T:
ReadLock (A); Read (A) WriteLock(B); Write (B)
WriteLock(C); Write (C) ReleaseLock(A,B,C)
CS3402
38
ReadLock(C); Read (C)
WriteLock (A) (restarts / “dies”)
*** T is restarted since it is younger
than U
*** T releases its read lock on C before restart
ReadLock(C); Read(C) ....
38
Deadlock Prevention using TS (Wound- Wait)
Setting:
Transaction Ti tries to lock item X.
But it cannot because some other transaction Tj has locked item X.
Wound-Wait rule:
If TS(Ti ) < TS(Tj ), then abort Tj and restart it later with the same
timestamp;
Otherwise Ti is allowed to wait
Interpretation:
(Wound) An older transaction requesting an item held by a
younger transaction aborts the younger transaction;
(Wait) A younger transaction is allowed to wait for an older one.
CS3402 39
Deadlock Example (wound-wait)
Assumption: TS(U) < TS(T)
Transaction U:
Transaction T:
ReadLock (A); Read (A) WriteLock(B); Write (B)
WriteLock(C); Write (C)
*** T is restarted (“wounded”) by U
WriteLock(A) (blocked/“wait”) *** since T is younger than U
since T is younger than U
*** The write lock on C is granted to U after T has released its read lock on C
ReleaseLock(A,B,C)
CS3402
ReadLock(C); Read(C) ....
40
ReadLock(C); Read (C)
Deadlock Avoidance using TS (comparison)
(Wait-die) If TS(Ti) < TS(Tj), Ti waits, else Ti dies
(Wound-wait) If TS(Ti) < TS(Tj), Ti wounds Tj, else Ti waits Note both methods restart the younger transaction
CS3402 41
Deadlock detection by wait-for graph
Wait-for graph:
CS3402
42
Nodes: One node is created for each transaction.
Directed edges:
(Add edges) 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.
(Remove edges) When Tj releases the lock(s) on the items that Ti was waiting for, the directed edge is dropped from the wait-for graph.
Checking: We have a state of deadlock if and only if the wait-for graph has a cycle.
Another example of wait-for graph
CS3402 43
Starvation
CS3402
44
In a deadlock resolution it is possible that the same transaction may consistently be selected as victim and aborted.
Starvation occurs when a particular transaction consistently waits or restarts and never gets a chance to proceed further.
The algorithm can use higher priorities for transactions that have been aborted multiple times to avoid this problem.
Wait-die and wound-wait schemes avoid starvation:
Reason: 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.
References
7e
Chapter 21
CS3402 45