DBMS concurrent Control in 3rd Unit .ppt

Concurrent Control

1. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Concurrency Control I

2. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Concurrency Control
T1 T2 … Tn
DB
(consistency
constraints)

3. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Prevent cycles in precedence graph from occurring

T1 T2 ….. Tn
Scheduler
DB
Enforce Conflict Serializable Schedules

4. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
A locking protocol
For transaction i

Use li to lock an item
Use ui to unlock the lock enforced by transaction i
scheduler
T1 T2
lock
table

5. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Well behaved transactions
Ti: … li(A) … pi(A) … ui(A) ...

6. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Example of a transaction performing locking
T
1: l1(A);
read (A);
u1(A);
l1(B);
read (B);
u1(B);
display(A+B)
Sufficient to guarantee serializability ?

7. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Example:
T2: Read(A) T3: Read(A)
A  A+100 A  A2
Write(A) Write(A)
Read(B) Read(B)
B  B+100 B B2
Write(B) Write(B)
Constraint: A=B

8. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Schedule A
T2 T3 25 25
l1(A);Read(A)
A A+100;Write(A);u1(A) 125
l2(A);Read(A)
A Ax2;Write(A);u2(A) 250
l2(B);Read(B)
B Bx2;Write(B);u2(B) 50
l1(B);Read(B)
B B+100;Write(B);u1(B) 150
250 150
A B

9. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Two-Phase Locking Protocol
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

10. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Ti = ……. li(A) ………... ui(A) ……...
no unlocks no locks

11. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
# locks
held by
Ti
Time
Growing Shrinking
Phase Phase

12. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
What happens to a transaction which tries to lock an item but
failed?

13. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Schedule B
T2 T3
l1(A);Read(A)
A A+100;Write(A)
l1(B); u1(A)
l2(A);Read(A)
A Ax2;Write(A); l2(B)l2(B)
Read(B);B B+100
Write(B); u1(B)
l2(B); u2(A);Read(B)
B Bx2;Write(B);u2(B);
delayed

14. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
2PL  conflict-serializable schedules?
To help in proof:
Definition Shrink(Ti) = SH(Ti) = first unlock action of Ti

15. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
First:
Ti  Tj in S  SH(Ti) <
S SH(Tj)
Proof:
Ti  Tj means that
S = … pi(A) … ui(A) … lj(A) ... qj(A) …

16. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Then:
(1) Assume P(S) has cycle
T1  T2 …. Tn  T1
(2) By lemma: SH(T1) < SH(T2) < ... < SH(T1)
(3) Impossible, so P(S) acyclic
(4)  S is conflict serializable

17. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Deadlock

To handle a deadlock one of T
4 or T
5 must be rolled back
and its locks released.
T4 T5
l3(B)
read(B)
write(B)
l4(A)
read(A)
l4(B)
l3(A)

18. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Starvation
A transaction does not get its turn for a long time
Example:
A transaction may be waiting for a lock on an item, while a
sequence of other transactions request and are granted an
lock on the same item.
The same transaction is repeatedly rolled back due to
deadlocks.
Concurrency control manager can be designed to prevent
starvation.

19. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
2PL and Deadlock
Are schedules from 2PL transactions deadlock free?

20. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
2PL and Possible Schedules
Does 2PL allow all possible conflict serializable schedules?

21. 3/9/2005 Yan Huang - CSCI5330 Database
Implementation – Concurrency Control
Beyond this simple 2PL protocol, it is all a matter of improving
performance and allowing more concurrency….

Shared locks
Multiple granularity

Inserts, deletes and phantoms

Other types of C.C. mechanisms