Bài giảng Hệ quản trị cơ sở dữ liệu - Chương II: Quản lý truy xuất đồng thời

h biểu sau là khả tuần tự
S={W2(X), R1(X), W1(X), C1, R3(X), W2(X), R3(Y),
R2(Z),C2, R3(Z), C3}
70
Ví dụ
 S1: W2(X),W1(X),R3(X),R1(X),W2(Y),R3(Y),R3(X),R2(X)
 Bất khả tuần tự vì đồ thị có chu trình
71
Ví dụ
 S1:R2(Z),W2(X),W2(Y),W1(X),R1(X),R3(X),R3(Z),R3(Y)
 Khả tuần tự vì đồ thị không có chu trình
72
Bài tập
T2T1
Read(A)
Read(B)
Write(A)
Write(B)
S
T3
Read(A)
Write(A)
Read(B)
Write(B)
 T2 S T3
2 3
 T1 S T2
1 2
73
Lịch có khả tuần tự không?
Bài tập
T2T1
Read(A)
Read(B)
Write(A)
Write(B)
S
T3
Read(A)
Write(A)
Read(B)
Write(B)
Lịch có khả tuần tự không?
74
Bài tập
75
T2T1
Read(A)
Write(A)
S T4
Read(A)
Write(A)
T3
 Vẽ P(S)
 S có conflict-serializable không?
Bài tập
76
T2T1
Read(A)
Read(C)
Write(A)
Write(C)
S
T4
Read(A)
Write(A)
Write(D)
Write(B)
T3
 Vẽ P(S)
 S có conflict-serializable không?
View-Serializability 
77
 Xét lịch S
T2T1
Write(A)
S
Write(A)
T3
Read(A)
Write(A)
1 2
3
 P(S) có chu trình
 S không conflict-serializable
View-Serializability (tt) 
78
 So sánh lịch S và 1 lịch tuần tự S’
 Trong S và S’ đều có T1 thực hiện read(A)
 T2 và T3 không đọc A 
 Kết quả của S và S’ giống nhau
T2T1
Write(A)
S
Write(A)
T3
Read(A)
Write(A)
Không conflict-serializable
T2T1
Write(A)
S’
Write(A)
T3
Read(A)
Write(A)
Serial
Giải thích như thế nào đây?
View-Serializability (tt) 
79
 Ý tưởng
 Xét trường hợp
 Nhận xét
 Sau khi T ghi A xong mà không có giao tác nào đọc giá trị của A 
 Khi đó, hành động wT(A) có thể chuyển đến 1 vị trí khác trong lịch thao 
tác mà ở đó cũng không có giao tác nào đọc A
 Ta nói
 Hành động rU(A) có gốc là giao tác T
T U
Write(A)
Read(A)
View-Serializability (tt) 
80
 Định nghĩa
 S, S’ là những lịch thao tác view-equivalent
 1- Nếu trong S có wj(A)  rj(A) thì trong S’ cũng có wj(A)  rj(A)
 2- Nếu trong S có ri(A) là thao tác đọc giá trị ban đầu của A 
thì trong S’ cũng ri(A) đọc giá trị ban đầu của A
 3- Nếu trong S có wi(A) là thao tác ghi giá trị sau cùng lên A 
thì trong S’ cũng có wi(A) ghi giá trị sau cùng lên A
 Một lịch thao tác S là view-serializable
 Nếu S là view-equivalent với một lịch thao tác tuần tự nào đó
 S view-serializable  S conflict-serializable
 S view-serializable  S conflict-serializable???
View-Serializability (tt) 
81
 S conflict-serializable  S view-serializable
 Chứng minh
 Hoán vị các hành động không xung đột
 Không làm ảnh hưởng đến những thao tác đọc
 Cũng không làm ảnh hưởng đến trạng thái CSDL
View-Serializability (tt) 
82
 S view-serializable  S conflict-serializable
 Trong S có những hành động ghi không có tác dụng (useless)
 S =  w2(A)  w3(A)  
Không có hành động đọc A
T2T1
Write(A)
S
Write(A)
T3
Read(A)
Write(A)
View-Serializability (tt) 
83
View-Serializability (tt) 
84
 Quan sát lịch S thấy các giao dịch T4 và T6 thực hiện 
các giao tác write (A) mà không thực hiện một lệnh 
Read (A) nào. Các thao tác này gọi là thao tác mù. Các 
thao tác ghi mù xuất hiện trong một lịch biểu view-
serializability nào đó thì lịch biểu không conflict 
serializability
Các kỹ thuật khóa dữ liệu
Giới thiệu
Kỹ thuật khóa đơn giản
Kỹ thuật khóa đọc ghi
Kỹ thuật khóa 2 pha
85
Giới thiệu
 Các giao tác trước khi muốn đọc/viết lên 1 đơn vị dữ 
liệu phải phát ra 1 yêu cầu xin khóa (lock) đơn vị dữ 
liệu đó
Lock(A) hay L(A)
 Yêu cầu này được bộ phận quản lý khóa xử lý
Nếu yêu cầu được chấp thuận thì giao tác mới được 
phép đọc/ghi lên đơn vị dữ liệu
 Sau khi thao tác xong thì giao tác phải phát ra lệnh giải 
phóng đơn vị dữ liệu (unlock)
Unlock(A) hay u(A)
86
Kỹ thuật khóa đơn giản
 Nếu xuất hiện 2 giao tác tương tranh thì áp dụng cơ chế chờ: một
giao tác xử lý hạt dữ liệu A sẽ khóa hạt dữ liệu này cho đến khi
hòan tất. Các giao tác còn lại phải chờ cho đến khi hạt dữ liệu này
được giải phóng
 Trước khi muốn thao tác lên 1 đơn vị dữ liệu A thì phải phát ra 1
yêu cầu xin khóa trên A
 Nếu yêu cầu trên khóa A được chấp thuận thì được thao tác trên A (Lock).
Sau khi thao tác xong thì phải phải phát ra lệnh giải phóng A (Unlock)
 Nếu yêu cầu trên khóa không được chấp thuận thì chờ
 Hai kiểu khóa
 Khóa đọc (Read lock): chỉ cho phép một giao tác đọc
 Khóa ghi (Write lock): cho phép cả hai giao tác đọc và ghi
 Bộ phận cấp phát khóa (lock manager) sẽ chỉ cấp phát trên A nếu
A tự do87
Kỹ thuật khóa đơn giản (tt)
Nguyên tắc khóa
Giao tác chỉ có thể đọc hoặc ghi trên đơn vị dữ
liệu nếu trước đó có yêu cầu lock trên đơn vị dữ
liệu và chưa nhả lock.
Nếu giao tác đã lock trên dvdt thì sau đó phải 
unlock
Tính hợp lệ
Không thể có 2 giao tác đồng thời khóa trên 1 
đvdl
88
Kỹ thuật khóa đơn giản (tt)
89
Ví dụ lịch hợp lệ và giao tác đúng
90
T2T1
Read(A,s)
s:=s*2
t:=t+100
Read(A,t)
t:=t+100
Write(A,t)
Read(B,t)
Write(B,t)
s:=s*2
Write(A,s)
Read(B,s)
Write(B,s)
S
Lock(A)
Unlock(A)
Lock(A)
Unlock(A)
Lock(B)
Unlock(B)
Lock(B)
Unlock(B)
Ví dụ
 Nếu lịch S hợp lệ thì S có khả tuần tự không?
91
Write(B,s); Unlock(B)
T2T1
s:=s*2
t:=t+100
t:=t+100
Write(A,t); Unlock(A)
Write(B,t); Unlock(B)
s:=s*2
Write(A,s); Unlock(A)
S
Lock(A); Read(A,t)
Lock(A); Read(A,s)
Lock(B); Read(B,s)
Lock(B); Read(B,t)
A B
25 25
125
50
250
150
Bài tập
92
 Cho biết lịch nào hợp lệ? Giao tác nào là đúng?
T2T1
Read(B)
Read(A)
Write(B)
Write(B)
Read(B)
S1
Lock(A) 
Unlock(A)
Lock(B)
Unlock(B)
Lock(B)
Unlock(B)
Lock(B) 
Unlock(B)
T3 T2T1
Read(B)
Read(A)
Write(B)
Write(B)
Read(B)
S2
Lock(A) 
Unlock(A)
Lock(B)
Lock(B)
Unlock(B)
Unlock(B)
T3
Bài tập
93
 Cho biết lịch nào hợp lệ? Giao tác nào là đúng?
T2T1
Read(B)
Read(A)
Write(B)
Write(B)
Read(B)
S3
Lock(A) 
Unlock(A)
Lock(B)
Unlock(B)
Lock(B)
Unlock(B)
Lock(B) 
Unlock(B)
T3
Kỹ thuật khóa đơn giản (tt)
 Các trường hợp cần tránh
Khóa sống (live lock): khóa nhưng không giải phóng
làm cho các giao tác phải chờ vô tận
 T1 yêu cầu khóa trên B, T2 yêu cầu khóa trên B
 T1 yêu cầu trước nên B được T1 khóa, nhưng T1 không 
giải phóng B nên T2 không thể khóa B mà phải chờ vô tận
Khóa chết (dead lock): trường hợp 2 hay nhiều giao
tác chờ đợi lẫn nhau. Giả sử T1 đang khóa A và chờ
B được giải phóng để khóa; trong khi T2 đang khóa 
B và chờ A được giải phóng để khóa A. Các yêu cầu
khóa A,B như vậy dẫn đến sự chờ trở nên vô hạn.
94
Ví dụ Live-Lock
 Để giải quyết vấn đề này thì lock Manager phải 
tinh tế hơn bằng cách ghi nhận thứ tự xin khóa
95
Ví dụ DeadLock
 Kỹ thuật ngăn ngừa
deadlock
Ép người viết chương
trình viết không bao 
giờ deadLock có thể 
xảy ra  ngăn ngừa 
deadlock
HQT theo dõi nếu có 
deadlock sẽ báo cho 
admin biết để xử lý
96
Giải phát cho DeadLock
97
Giải quyết Deadlock
Hủy tất cả  không phải là cách giải quyết tốt
Hủy giao tác gây ra deadlock. Giao tác nào gây 
ra?
 Dùng thời gian chờ.
 Dùng đồ thị chờ
 Ngăn ngừa Deadlock
 Sắp xếp các đơn vị dữ liệu theo một thứ tự cố 
định và các giao tác yêu cầu lock trên chúng theo 
thứ tự này.
 Các giao tác chờ lần nhau  deadlock. Các transaction 
chờ theo 1 chiều nhất định  ngăn ngừa deadlock.
Đồ thị chờ
98
Khi có trình trạng deadlock xảy ra, hệ 
thống hủy trình trạng deadlock.
Dùng đồ thị chờ để phát hiện deadlock
Cho S là lịch giao tác của các giao tác T1, T2,.., Tn.
Đồ thị có đỉnh là các giao tác.
Cung có hướng Ti  Tj nếu Ti phải chờ Tj
Đồ thị có chu trình  Deadlock
Để giải quyết: hủy đỉnh (ứng với giao tác) có 
nhiều cung vào ra nhất.
Ví dụ
99
T1 T2
L(A); R(A)
L(C); R(C)
1
T3 T4
L(B); R(B)
L(D); R(D)
2
3
4
5
6
7
8
L(A)
L(C)
L(A)
L(B)
 Chờ
 Chờ
 Chờ
 Chờ
T
2
T
1
T
3
T
4
Ví dụ
100
T
2
T
1
T
3
T
4
T1 T2
L(A); R(A)
L(C); R(C)
1
T3 T4
L(B); R(B)
L(D); R(D)
2
3
4
5
6
7
8
L(A)
L(C)
L(A)
L(B)
Kỹ thuật khóa 2 giai đoạn (2PL)
 Qui tắc
 (3) Giao tác 2PL 
t
EOTBOT
Phase lock Phase unlock
Đơn vị
dữ liệu 
giữ
lock 
của Ti
Thực hiện xong hết tất cả 
các yêu cầu lock rồi mới 
tiến hành unlock
S :  li(A)  ui(A) 
không có lockkhông có unlock
101
Kỹ thuật khóa 2 giai đoạn (tt)
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)
Thỏa nghi thức 
khóa 2 giai đoạn
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)
Không thỏa nghi thức 
khóa 2 giai đoạn
102
Ví dụ
T2T1S
Write(B,t); Unlock(B)
Read(B,t); t:=t+100
t:=t+100; Write(A,t)
Lock(A); Read(A,t)
Lock(B); Unlock(A)
Lock(B); Ulock(A) 
Read(B,t); t:=t*2
Write(B,t); 
Unlock(B)
s:=s*2; Write(A,s)
Lock(A); Read(A,s)
Lock(B) 
Chờ
T2T1
Read(A,s)
s:=s*2
t:=t+100
Read(A,t)
t:=t+100
Write(A,t)
Read(B,t)
Write(B,t)
s:=s*2
Write(A,s)
Read(B,s)
Write(B,s)
S
103
Ví dụ
104
T2T1
s:=s*2
S
Lock(B)
Lock(A) 
t:=t+100
Read(A,t)
Lock(B)
Write(A,t)
Write(B,s)
Không xin 
được lock

Chờ
Lock(A)
Read(B,s)
Không xin 
được lock

Chờ
Bài tập
105
 S có khả tuần tự không?
 Giao tác nào không thỏa 2PL?
T1 T2
RL(A)
Read(A)
UL(A)
RL(B)
Read(B)
UL(B)
WL(A)
Read(A)
A:=A+B
Write(A)
UL(A)
WL(B)
Read(B)
B:=B+A
Write(B)
UL(B)
S
Bài tập
106
 S có khả tuần tự hay không?
 Giao tác nào không thỏa 2PL?
T1 T3
RL(A)
UL(A)
T2 T4
RL(A)
WL(B)
WL(A)
UL(B)
RL(B)
UL(A)
RL(B)
RL(A)
UL(B)
WL(C)
UL(A)
WL(B)
UL(B)
UL(B)
UL(C)
Kỹ thuật khóa đọc ghi
 Bộ lập lịch có các hành động
 Khóa đọc (Read lock, Shared lock)
 RLock(A) hay rl(A)
 Khóa ghi (Write lock, Exclusive lock)
 WLock(A) hay wl(A)
 Giải phóng khóa
 Unlock(A) hay u(A)
Lock(A)
Unlock(A)
Ti Tj
Read(A)
Lock(A)
Unlock(A)
Read(A)
107
Kỹ thuật khóa đọc ghi (tt)
 Cho 1 đơn vị dữ liệu A bất kỳ
WLock(A)
Hoặc có 1 khóa ghi duy nhất lên A
Hoặc không có khóa ghi nào lên A
RLock(A)
Có thể có nhiều khóa đọc được thiết lập lên A
108
Kỹ thuật khóa đọc ghi (tt)
 Giao tác muốn Write(A)
Yêu cầu WLock(A)
WLock(A) sẽ được chấp thuận nếu A tự do
 Sẽ không có giao tác nào nhận được WLock(A) hay 
RLock(A) 
 Giao tác muốn Read(A)
Yêu cầu RLock(A) hoặc WLock(A) 
RLock(A) sẽ được chấp thuận nếu A không đang 
giữ một WLock nào 
 Không ngăn chặn các thao tác khác cùng xin Rlock(A) 
 Các giao tác không cần phải chờ nhau khi đọc A
 Sau khi thao tác xong thì giao tác phải giải phóng 
khóa trên đơn vi dữ liệu A
ULock(A)
109
Kỹ thuật khóa đọc ghi (tt)
 Qui tắc
 (1) Giao tác đúng đắn
 (2) Lịch thao tác hợp lệ
Ti :  rl(A)  r(A)  u(A) 
Ti :  wl(A)  w(A)  u(A) 
S :  rli(A)  ui(A) 
không có wlj(A)
S :  wli(A)  ui(A) 
không có wlj(A)
không có rlj(A)110
Bài tập
111
 Trong các giao tác trong lịch trên giao tác nào viết đúng 
nghi thức khoá hai giai đoạn?
Kỹ thuật nhãn thời gian (timestamps)
 Giới thiệu
 Nhãn thời gian của giao tác
 Nhãn thời gian của đơn vị dữ liệu
 Nhãn thời gian toàn phần
 Nhãn thời gian riêng phần
 Nhãn thời gian nhiều phiên bản (multiversion)
112
Giới thiệu
 Nguyên lý cơ bản của lịch khả tuần tự
 Sắp xếp thứ tự các thao tác khi chúng được gọi thực 
hiện
Kiểm soát các truy xuất tranh chấp trên dữ liệu; phải 
đảm bảo các truy xuất tôn trọng thứ tự trước sau của 
giao tác
 Chọn một thứ tự thực hiện nào đó cho các giao tác bằng 
cách gán nhãn thời gian (timestamping)
Mỗi giao tác T sẽ có 1 nhãn, ký hiệu TS(T)
 Tại thời điểm giao tác bắt đầu
Thứ tự của các nhãn tăng dần
 Giao tác bắt đầu trễ thì sẽ có nhãn thời gian lớn hơn các giao
tác bắt đầu sớm113
Nhãn thời gian của giao tác
114
Nhãn thời gian của đơn vị dữ liệu
115
Nhãn thời gian toàn phần
 Mỗi giao tác T khi phát sinh sẽ được gán 1 nhãn TS(T) 
ghi nhận lại thời điểm phát sinh của T.
 Mỗi đơn vị dữ liệu X cũng có 1 nhãn thời TS(X), nhãn 
này ghi lại TS(T) của giao tác T đã thao tác read/write 
thành công sau cùng lên X.
 Khi đến lượt giao tác T thao tác trên dữ liệu X, so sánh 
TS(T) và TS(X).
116
Nhãn thời gian toàn phần (tt)
Read(T, X)
If TS(X) <= TS(T) 
Read(X); 
//cho phép đọc X
TS(X):= TS(T); 
Else 
Abort {T}; 
//hủy bỏ T 
//khởi tạo lại TS
If TS(X) <= TS(T) 
Write(X); 
//cho phép ghi X
TS(X):= TS(T); 
Else 
Abort {T};
//hủy bỏ T 
//khởi tạo lại TS
Write(T, X)
117
Ví dụ
118
TS(A) <= TS(T1) : T1 đọc được A
TS(B) <= TS(T2) : T2 đọc được B
TS(A) <= TS(T1) : T1 ghi lên A được
TS(B) <= TS(T2) : T2 ghi lên B được
TS(B) > TS(T1) : T1 không đọc được B
Abort
TS(T1)=100
1
2
3
4
5
TS(A)=100
TS(B)=200
TS(A)=100
TS(B)=200
T1
Read(A)
T2
TS(T2)=200
A
TS(A)=0
B
TS(B)=0
Read(B)
A=A*2
Write(A)
B=B+20
Write(B)
Read(B)
Khởi tạo lại TS(T1)  TS(T2)  TS(T1)
Lịch khả tuần tự theo thứ tự {T2, T1}
3
Ví dụ
TS(T1)=100
TS(A)=100
TS(A)=120
T1
Read(A)
T2
TS(T2)=120
A
TS(A)=0
Read(A)
Write(A)
Write(A)
TS(A)=120
T1 bị hủy và bắt đầu thực 
hiện lại với timestamp mới
TS(T1)=100
T1 T2
TS(T2)=120
Read(A)
Read(A)
Read(A)
Read(A)
A
TS(A)=0
TS(A)=100
TS(A)=120
TS(A)=120
T1 bị hủy và bắt đầu thực hiện lại 
với timestamp mới
Không phân biệt tính chất của thao tác là đọc hay viết 
 T1 vẫn bị hủy và làm lại từ đầu với 1 timestamp mới
 Nhận xét
Nhãn thời gian riêng phần
 Nhãn của đơn vị dữ liệu X được tách ra thành 2
 RT(X) - read
 Ghi nhận TS(T) gần nhất đọc X thành công 
 WT(X) - write
 Ghi nhận TS(T) gần nhất ghi X thành công
120
Nhãn thời gian riêng phần (tt)
 Công việc của bộ lập lịch
 Gán nhãn RT(X), WT(X) và C(X)
 Kiểm tra thao tác đọc/ghi xuất hiện vào lúc nào
 Có xãy ra tình huống
 Đọc quá trễ
 Ghi quá trễ
 Đọc dữ liệu rác (dirty read)
 Qui tắc ghi Thomas
121
Nhãn thời gian riêng phần (tt)
 Đọc quá trễ
T bắt đầu U bắt đầu
U ghi X
T đọc X  ST(T)  ST(U)
 U ghi X trước,T đọc X sau
 ST(T) <WT(X)
 T không thể đọc X sau U
 HủyT
122
Nhãn thời gian riêng phần (tt)
 Ghi quá trễ
T bắt đầu U bắt đầu
U đọc X
T ghi X  ST(T)  ST(U)
 U đọc X trước,T ghi X sau
 WT(X) < ST(T) < RT(X)
 U phải đọc được giá trị X được
ghi bởiT
 HủyT
123
Nhãn thời gian riêng phần (tt)
124
 Đọc dữ liệu rác
T bắt đầu U bắt đầu
U đọc XT ghi X
T hủy
 ST(T)  ST(U)
 T ghi X trước, U đọc X sau
 Thao tác bình thường
 NhưngT hủy
 U đọc X sau khiT commit
 U đọc X sau khiT abort
Nhãn thời gian riêng phần (tt)
 Qui tắc ghi Thomas
T bắt đầu U bắt đầu
T ghi X
U ghi X
 ST(T)  ST(U)
 U ghi X trước,T ghi X sau
 ST(T) <WT(X)
 T ghi X xong thì không làm được gì
 Không có giao tác nào đọc được giá trị
X của T (nếu có cũng bị hủy do đọc
quá trễ)
 Các giao tác đọc sau T và U thì mong
muốn đọc giá trị X của U
Bỏ qua thao tác ghi củaT
125
Nhãn thời gian riêng phần (tt)
T bắt đầu U bắt đầu
T ghi X
U ghi X
T kết thúc U hủy
 Nhưng U hủy
 Giá trị của X được ghi bởi U bị mất
 Cần khôi phục lại giá trị X trước đó
 VàT đã kết thúc
 X có thể khôi phục từ thao tác ghi
củaT
 Do qui tắc ghiThomas
 Thao tác ghi đã được bỏ qua
 Quá trễ để khôi phục X
 Qui tắc ghi Thomas
126
Nhãn thời gian riêng phần (tt)
 Qui tắc ghi Thomas
T bắt đầu U bắt đầu
T ghi X
U ghi X
T kết thúc U hủy
 KhiT muốn ghi
 ChoT thử ghi và sẽ gỡ bỏ nếuT hủy
 Sao lưu giá trị cũ của X và nhãn
WT(X) trước đó
127
Nhãn thời gian riêng phần (tt)
Read(T, X)
If WS(X) <= TS(T) 
Read(X);//cho phép đọc X
RT(X):= max(RT(X),TS(T)); 
Else 
Rollback{T}; 
//hủy T và khởi tạo lại TS mới
If RT(X) <= TS(T)
If WT(X) <= TS(T)
Write(X);//cho phép ghi X
WT(X):= TS(T); 
//Else không làm gì cả
Else
Rollback{T};
//hủy T và khởi tạo lại TS mới
Write(T, X)
128
Ví dụ
1
2
3
4
5
T1
Read(A)
T2
TS(T2)=200
A
RT(A)=0
B
RT(B)=0
Read(B)
Write(A)
Write(B)
Read(C)
TS(T1)=100 WT(A)=0 WT(B)=0
RT(A)=100
WT(A)=0
RT(B)=200
WT(B)=0
RT(A)=100
WT(A)=100
RT(B)=200
WT(B)=200
C
RT(C)=0
WT(C)=0
RT(C)=200
WT(C)=0
Read(C) RT(C)=200
WT(C)=0
Write(C)
WT(A) <= TS(T1)
T1 đọc được A
WT(B) < =TS(T2)
T2 đọc được B
RT(A) < =TS(T1) T1 ghi lên 
A đượcWT(A) <= TS(T1)
RT(B) <= TS(T2) T2 ghi 
lên B 
được
WT(B) <= TS(T2)
WT(C) < =TS(T2)
T2 đọc được C
WT(C) < =TS(T1)
T1 đọc được C
6
7 RT(C) >TS(T1)
T1 không ghi lên C 
được
Abort129
Ví dụ
T1
Read(B)
T2
TS=150
A
RT=0
B
RT=0
Read(A)
Write(B)
Write(A)
Write(A)
TS=200 WT=0 WT=0
RT=200
WT=0
RT=150
WT=0
RT=175
WT=0
RT=200
WT=200
C
RT=0
WT=0
RT=150
WT=200
Write(C)
Rollback
T3
TS=175
Read(C)
Giá trị của A đã sao lưu bởi T1 
T3 không bị rollback và không cần ghi A
130
Ví dụ
T1
Read(A)
T2
TS=200
A
RT=0
Read(A)
Write(A)
Write(A)
Read(A)
TS=150 WT=0
RT=150
WT=0
RT=200
WT=200
T3
TS=175
Rollback
T4
TS=255
Read(A)
RT=150
WT=150
RT=200
WT=150
RT=255
WT=200
Nhận xét
•Thao tác read3(A) làm cho 
giao tác T3 bị hủy
•T3 đọc giá trị của A sẽ 
được ghi đè trong tương lai 
bởi T2
•Giả sử nếu T3 đọc được giá
trị của A do T1 ghi thì sẽ 
không bị hủy
131
Bài tập
132
 Dùng kỹ thuật timestamp từng phần để điều khiển truy xuất đồng 
thời của 4 giao tác trên, với timestamp của các giao tác T1, T2, 
T3, T4 lần lượt là:
a) 300, 310, 320, 330
b) 250, 200, 210, 275
Bài tập
133
134
1) Lịch S có khả tuần tự không? Nếu có thì tương đương 
với lịch tuần tự nào.
2) Thay Rlock bởi Read, thay Wlock bởi Write, bỏ qua 
các thao tác Unlock. Dùng kỹ thuật timestamp từng 
phần để điều khiển việc truy xuất đồng thời của các 
giao tác biết các timestamp của các giao tác là 
T1=100, T2=300, T3=200, T4=400, T5=500.
Nhãn thời gian nhiều phiên bản
 Mỗi đơn vị dữ liệu có thể có nhiều phiên bản cho từng
giao tác.
 Mỗi phiên bản của 1 đơn vị dữ liệu X có
 RT(X) 
 Ghi nhận lại giao tác sau cùng đọc X thành công 
 WT(X) 
 Ghi nhận lại giao tác sau cùng ghi X thành công
 Khi giao tác T phát ra yêu cầu thao tác lên X
 Tìm 1 phiên bản thích hợp của X
 Đảm bảo tính khả tuần tự
 Một phiên bản mới của X sẽ được tạo khi hành động ghi X 
thành công
135
Thuật tóan
i=“số thứ tự phiên bản sau cùng nhất của A” 
While WT(Xi) > TS(T) 
i:=i-1;//lùi lại
Read(Xi); 
RT(Xi):= max(RT(Xi), TS(T));
Read(T, X)
i=“số thứ tự phiên bản sau cùng nhất của A” 
While WT(Xi) > TS(T) 
i:=i-1;//lùi lại
If RT(Xi) > TS(T)
Rollback T//Hủy và khởi tạo TS mới
Else 
Tạo phiên bản Ai+1;
Write(Xi+1);
RT(Xi+1) = 0;//chưa có ai đọc
WT(Xi+1) = TS(T);
Write(T, X)
136
Ví dụ
RT=150
WT=0
RT=0
WT=200
T1
Read(A)
T2
TS=200
A0
RT=0
Read(A)
Write(A)
Write(A)
Read(A)
TS=150 WT=0
T3
TS=175
T4
TS=255
Read(A)
RT=0
WT=150
RT=200
WT=150
RT=200
WT=150
A1 A2
RT=255
WT=200
137
Ví dụ (tt)
T1
TS=100
T2
TS=200
Read(A)
Write(A)
Write(B)
Read(B)
Write(A)
A0
RT=0
WT=0
RT=100
WT=0
RT=0
WT=200
RT=0
WT=0
B1
RT=0
WT=200
RT=100
WT=0
A1
RT=0
WT=100
A2
RT=0
WT=200
138
Nhãn thời gian nhiều phiên bản (tt)
 Nhận xét
 Thao tác đọc
 Giao tác T chỉ đọc giá trị của phiên bản do T hay những giao tác trước T cập nhật
 T không đọc giá trị của các phiên bản do các giao tác sau T cập nhật
Thao tác đọc không bị rollback
 Thao tác ghi 
 Thực hiện được bằng cách chèn thêm phiên bản mới
 Không thực hiện được thì rollback
 Tốn nhiều chi phí tìm kiếm, tốn bộ nhớ
 Nên giải phóng các phiên bản quá cũ không còn được các giao tác sử
dụng
139
Nhận xét
 Khóa & nhãn thời gian
 Nếu các giao tác chỉ thực hiện đọc không thôi thì kỹ thuật 
nhãn thời gian tốt hơn
 Ít có tình huống các giao tác cố gắng đọc và ghi cùng 1 đơn vị dữ 
liệu
 Nhưng kỹ thuật khóa sẽ tốt hơn trong những tình huống 
xãy ra tranh chấp
 Kỹ thuật khóa thường hay trì hoãn các giao tác để chờ xin được 
khóa
 Dẫn đến deadlock
 Nếu có các giao tác đọc và ghi cùng 1 đơn vị dữ liệu thì việc 
rollback là thường xuyên hơn
140