2021/4/28 Lock-based Concurrency Control
Lock-based Concurrency Control
Lock-based Concurrency Control Two-Phase Locking
Problems with Locking
Deadlock
>>
COMP9315 21T1 ♢ Locking ♢ [0/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 1/12
2021/4/28 Lock-based Concurrency Control
∧ >> ❖ Lock-based Concurrency Control
Requires read/write lock operations which act on database objects.
Synchronise access to shared DB objects via these rules:
before reading X, get read (shared) lock on X
before writing X, get write (exclusive) lock on X
a tx attempting to get a read lock on X is blocked
if another tx already has write lock on X
a tx attempting to get a write lock on X is blocked
if another tx has any kind of lock on X
These rules alone do not guarantee serializability.
COMP9315 21T1 ♢ Locking ♢ [1/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 2/12
2021/4/28 Lock-based Concurrency Control
<< ∧ >> ❖ Lock-based Concurrency Control
(cont)
Locks introduce additional mechanisms in DBMS:
The Lock Manager manages the locks requested by the scheduler
COMP9315 21T1 ♢ Locking ♢ [2/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 3/12
2021/4/28 Lock-based Concurrency Control
<< ∧ >> ❖ Lock-based Concurrency Control
(cont)
Lock table entries contain:
objectbeinglocked (DB,table,tuple, eld)
type of lock: read/shared, write/exclusive
FIFO queue of tx’s requesting this lock
countoftx’scurrentlyholdinglock (max1for write locks)
Lock and unlock operations must be atomic. Lock upgrade:
ifatxholdsareadlock,anditistheonlytx holding that lock
then the lock can be converted into a write lock
COMP9315 21T1 ♢ Locking ♢ [3/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 4/12
2021/4/28 Lock-based Concurrency Control
<< ∧ >> ❖ Lock-based Concurrency Control
(cont)
Consider the following schedule, using locks:
T1(a): Lr(Y) T2(a):
Lr(X)
R(Y) continued R(X) U(X) continued
T1(b): U(Y)
T2(b): Lw(Y)….W(Y) U(Y)
Lw(X) W(X) U(X)
(where Lr = read-lock, Lw = write-lock, U = unlock)
Locks correctly ensure controlled access to X and
Y.
Despite this, the schedule is not serializable. (Ex:
prove this)
COMP9315 21T1 ♢ Locking ♢ [4/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 5/12
2021/4/28 Lock-based Concurrency Control
<< ∧ >>
❖ Two-Phase Locking
To guarantee serializability, we require an
additional constraint:
in every tx, all lock requests precede all unlock requests
Each transaction is then structured as: growing phase where locks are acquired action phase where “real work” is done shrinking phase where locks are released
Clearly, this reduces potential concurrency …
COMP9315 21T1 ♢ Locking ♢ [5/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 6/12
2021/4/28 Lock-based Concurrency Control
❖ Problems with Locking Appropriate locking can guarantee
serializability..
However, it also introduces potential undesirable effects:
Deadlock
No transactions can proceed; each waiting on lock held by another.
Starvation
One transaction is permanently “frozen out” of access to data.
Reduced performance
Locking introduces delays while waiting for locks to be released.
COMP9315 21T1 ♢ Locking ♢ [6/10]
<< ∧ >>
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 7/12
2021/4/28 Lock-based Concurrency Control
<< ∧ >>
❖ Deadlock
Deadlock occurs when two tx’s wait for a lock on
an item held by the other. Example:
T1: Lw(A) R(A) Lw(B) ……
T2: Lw(B) R(B) Lw(A) …..
How to deal with deadlock?
prevent it happening in the rst place let it happen, detect it, recover from it
COMP9315 21T1 ♢ Locking ♢ [7/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 8/12
2021/4/28 Lock-based Concurrency Control
<< ∧ >>
❖ Deadlock (cont)
Handling deadlock involves forcing a transaction
to “back off”
select process to roll back
choose on basis of how far tx has progressed, # locks held, …
roll back the selected process
how far does this it need to be rolled back?
worst-case scenario: abort one transaction, then retry
prevent starvation
need methods to ensure that same tx isn’t always chosen
COMP9315 21T1 ♢ Locking ♢ [8/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 9/12
2021/4/28 Lock-based Concurrency Control
❖ Deadlock (cont)
Methods for managing deadlock
timeout : set max time limit for each tx waits-forgraph:recordsTj waitingonlock
held by Tk
prevent deadlock by checking for new cycle ⇒ abort Ti
detect deadlock by periodic check for cycles ⇒ abort Ti
timestamps : use tx start times as basis for priority
scenario:Tj triestogetlockheldbyTk …
wait-die:ifTj
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 10/12
2021/4/28 Lock-based Concurrency Control
<< ∧
❖ Deadlock (cont)
Properties of deadlock handling methods:
both wait-die and wound-wait are fair
wait-die tends to
roll back tx's that have done little work but rolls back tx's more often
wound-wait tends to
roll back tx's that may have done signi cant work but rolls back tx's less often
timestamps easier to implement than waits- for graph
waits-for minimises roll backs because of deadlock
COMP9315 21T1 ♢ Locking ♢ [10/10]
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 11/12
2021/4/28 Lock-based Concurrency Control
Produced: 14 Apr 2021
https://cgi.cse.unsw.edu.au/~cs9315/21T1/lectures/tx-locking/slides.html 12/12