›
›

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

Download
Concurrency  
Vu Tuyet Trinh  
[email protected].vn  
Department of Information Systems, Faculty of Information Technology  
Hanoi University of Technology  
Example  
500USD  
Account A  
Account B  
read(A)  
If A > 500 then  
What happen  
???  
B:=B+500  
A:=A-500  
Crash  
2
1
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  
Concurrency  
Control  
Atomicity  
Consistency  
Isolation  
Recovery  
Durability  
3
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);  
crash  
t2:=t2+500;  
Write(B,t2);  
t1:=t1-500;  
Write(A,t1);  
}
4
2
Consistency  
ensures that the DB remains in a consistent  
state before the start of the transaction and after  
the transaction is over  
Example  
A+B = C  
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  
}
5
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;  
T’: A+B  
(= 5000+3500)  
Write(B,t2);  
t1:=t1-500;  
Write(A,t1);  
(A+B = 4500+3500)  
}
6
3
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);  
crash  
}
7
A= 4500, B=3500  
Transaction States  
8
4
Transaction Management Interfaces  
Begin Trans  
Commit ()  
Abort()  
Savepoint Save()  
Rollback (savepoint)  
(savepoint = 0 ==> Abort)  
9
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);  
A := A -50;  
T1: read(A);  
temp := A *0.1;  
write(A);  
read(B);  
A := A -temp;  
write(A);  
B := B + 50;  
write(B);  
read(B);  
B := B + temp;  
write(B);  
10  
5
Scheduling  
11  
(2)  
(3)  
(1)  
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  
6
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  
LS  
LX  
Compatibility  
LS  
LX  
true false  
false false  
3  
Example  
T0: LX(A);  
read(A);  
T1: LX(A);  
read(A);  
A := A -50;  
write(A);  
LX(B);  
temp := A *0.1;  
A := A -temp;  
write(A)  
read(B);  
B := B + 50;  
write(B);  
UN(A);  
LX(B);  
read(B);  
B:=B+temp;  
write(B);  
UN(A);  
UN(B);  
UN(B);  
14  
7
Well-Formed, two-phased transaction  
A transaction is 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 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  
(2PL)  
Phase 1  
locks are acquired and no locks are released  
Phase 2  
locks are released and no locks are acquired  
BOT  
EOT  
t
Phase lock Phase unlock  
8
Example  
T3  
Lock(B)  
Read(B)  
B=B-50  
T1  
Lock(A)  
T2  
T4  
Lock(A)  
Read(A)  
Lock(B)  
Read(B)  
B:=B+A  
Lock(B)  
Read(B)  
Lock(A)  
Read(A)  
Unlock(B)  
A:=A+B  
Read(A)  
Write(B)  
Unlock(B)  
Lock(A)  
Read(A)  
A=A+50  
Write(A)  
Unlock(A)  
Unlock(A)  
Lock(B)  
Write(B)  
Unlock(A)  
Unlock(B)  
Read(B)  
Unlock(B)  
Pritn(A+B)  
Write(A)  
Unlock(A)  
2PL  
Not 2PL  
Deadlock  
T0: LX(B);  
(1) T1: LX(A);  
(4)  
(5)  
temp := A *0.1; (6)  
A := A -temp; (7)  
read(B);  
(2)  
(3)  
read(A);  
B := B +50;  
write(B);  
LX(A);  
read(A);  
A := A - 50;  
write(A);  
UN(A);  
(8)  
(10)  
write(A)  
LX(B);  
(9)  
read(B);  
B:=B+temp;  
write(B);  
UN(A);  
UN(B);  
UN(B);  
18  
9
Resolving Deadlock  
Detecting  
Recovery when deadlock happen  
rollback  
Used waitingaph  
Avoiding  
Resource ordering  
Timeout  
Wait-die  
Wound-wait  
Graph  
Node handling lock or waiting for lock  
Edge TU  
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  
10  
Timeout  
Set a limit time for each transaction  
If time-out do r
11  
pdf 11 trang Thùy Anh 13780 Free
Download
Bạn đang xem tài liệu "Bài giảng Thiết kế và quản trị cơ sở dữ liệu - Concurrency - Vũ Tuyết Trinh", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_thiet_ke_va_quan_tri_co_so_du_lieu_concurrency_vu.pdf