Bài giảng Thiết kế và quản trị cơ sở dữ liệu - Bài 11: Concurrency - Vũ Tuyết Trinh

1 
Concurrency 
Vu Tuyet Trinh 
trinhvt@it-hut.edu.vn 
Department of Information Systems, Faculty of Information Technology 
Hanoi University of Technology 
2 
Example 
read(A) 
If A > 500 then 
B:=B+500 
A:=A-500 
Account A Account B 
Crash What happen 
??? 
500USD 
2 
3 
Transaction 
 A sequence of read and write operations on data items 
that logically functions as one unit of work 
 Assuring data integrity and correction 
 ACID Properties 
 Atomicity 
 Consistency 
 Isolation 
 Durability 
Concurrency 
Control 
Recovery 
4 
Automicity 
 guarantee that either all of the tasks of a transaction are 
performed or none of them are 
 Example 
T: Read(A,t1); 
 If t1 > 500 { 
 Read(B,t2); 
 t2:=t2+500; 
 Write(B,t2); 
 t1:=t1-500; 
 Write(A,t1); 
 } 
crash 
3 
5 
Consistency 
 ensures that the DB remains in a consistent 
state before the start of the transaction and after 
the transaction is over 
 Example 
T: Read(A,t1); 
 If t1 > 500 { 
 Read(B,t2); 
 t2:=t2+500; 
 Write(B,t2); 
 t1:=t1-500; 
 Write(A,t1); 
 } 
A+B = C 
A+B = C 
6 
Isolation 
 ability of the application to make operations in a 
transaction appear isolated from all other operations. 
 Example A= 5000, B= 3000 
 T: Read(A,t1); 
 If t1 > 500 { 
 Read(B,t2); 
 t2:=t2+500; 
 Write(B,t2); 
 t1:=t1-500; 
 Write(A,t1); 
 } 
T’: A+B 
(= 5000+3500) 
(A+B = 4500+3500) 
4 
7 
Durability 
 guarantee that once the user has been notified of 
success, the transaction will persist, and not be undone 
 Ví dụ: A= 5000, B= 3000 
T: Read(A,t1); 
 If t1 > 500 { 
 Read(B,t2); 
 t2:=t2+500; 
 Write(B,t2); 
 t1:=t1-500; 
 Write(A,t1); 
 } 
A= 4500, B=3500 
crash 
8 
Transaction States 
5 
9 
Transaction Management Interfaces 
 Begin Trans 
 Commit () 
 Abort() 
 Savepoint Save() 
 Rollback (savepoint) 
 (savepoint = 0 ==> Abort) 
10 
Concurrency Control 
 Objective: 
 ensures that database transactions are performed concurrently 
without the concurrency violating the data integrity 
 guarantees that no effect of committed transactions is lost, and 
no effect of aborted (rolled back) transactions remains in the 
related database. 
 Example 
T0: read(A); T1: read(A); 
 A := A -50; temp := A *0.1; 
 write(A); A := A -temp; 
 read(B); write(A); 
 B := B + 50; read(B); 
 write(B); B := B + temp; 
 write(B); 
6 
11 
Scheduling 
(1) (2) (3) 
Serializability 
 A schedule of a set of transactions is a linear ordering 
of their actions 
 e.g. for the simultaneous deposits example: 
 R1(X) R2(X) W1(X) W2(X) 
 A serial schedule is one in which all the steps of each 
transaction occur consecutively 
 A serializable schedule is one which is equivalent to 
some serial schedule 
7 
13 
Lock 
 Definition 
 a synchronization mechanism for enforcing limits on 
access to DB in concurrent way. 
 one way of enforcing concurrency control policies 
 Lock types 
 Shared lock (LS) readable but can not write 
 Exclusive lock (LX): read and write 
 UN(D): unlock 
 Compatibility LS LX 
LS true false 
LX false false 
14 
Example 
T0: LX(A); T1: LX(A); 
 read(A); read(A); 
 A := A -50; temp := A *0.1; 
 write(A); A := A -temp; 
 LX(B); write(A) 
 read(B); LX(B); 
 B := B + 50; read(B); 
 write(B); B:=B+temp; 
 UN(A); write(B); 
 UN(B); UN(A); 
 UN(B); 
8 
Well-Formed, two-phased transaction 
 A transaction is well-formed if it acquires at least a 
shared lock on Q before reading Q or an exclusive lock 
on Q before writing Q and doesn’t release the lock until 
the action is performed 
 Locks are also released by the end of the transaction 
 A transaction is two-phased if it never acquires a lock 
after unlocking one 
 i.e., there are two phases: a growing phase in which the 
transaction acquires locks, and a shrinking phase in which 
locks are released 
2Phase Locking (2PL) 
 Phase 1 
 locks are acquired and no locks are released 
 Phase 2 
 locks are released and no locks are acquired 
t 
EOT BOT 
Phase lock Phase unlock 
9 
Example 
T1 
Lock(A) 
Read(A) 
Lock(B) 
Read(B) 
B:=B+A 
Write(B) 
Unlock(A) 
Unlock(B) 
T2 
Lock(B) 
Read(B) 
Lock(A) 
Read(A) 
A:=A+B 
Write(A) 
Unlock(A) 
Unlock(B) 
2PL 
T3 
Lock(B) 
Read(B) 
B=B-50 
Write(B) 
Unlock(B) 
Lock(A) 
Read(A) 
A=A+50 
Write(A) 
Unlock(A) 
T4 
Lock(A) 
Read(A) 
Unlock(A) 
Lock(B) 
Read(B) 
Unlock(B) 
Pritn(A+B) 
Not 2PL 
18 
Deadlock 
T0: LX(B); (1) T1: LX(A); (4) 
 read(B); (2) read(A); (5) 
 B := B +50; (3) temp := A *0.1; (6) 
 write(B); (8) A := A -temp; (7) 
 LX(A); (10) write(A) (9) 
 read(A); LX(B); 
 A := A - 50; read(B); 
 write(A); B:=B+temp; 
 UN(A); write(B); 
 UN(B); UN(A); 
 UN(B); 
10 
 Detecting 
 Recovery when deadlock happen 
 rollback 
 Used waiting-graph 
 Avoiding 
 Resource ordering 
 Timeout 
 Wait-die 
 Wound-wait 
Resolving Deadlock 
 Graph 
 Node handling lock or waiting for lock 
 Edge T U 
 U handle L(A) 
 T wait to lock A 
 T must wait until U unlock A 
 If there exists a cycle in the waiting graph deadlok 
Waiting Graph 
11 
Timeout 
 Set a limit time for each transaction 
 If time-out do rollback