Bài giảng Cơ sở dữ liệu - Chương 2: Giao tác - Điều khiển đồng thời

ị cuối của X lẽ ra là giá trị do T ghi nhưng đã bị bỏ
qua.
¾ Khi U abort, đặt C(X) = false, chép lại giá trị cũ của X và
WT(X)
U bắt đầu 
T bắt đầu 
U writes X 
T writes X 
T commit U abort 
125
Nguyên tắc 
‰ Khi T yêu cầu Read/Write, bộ lập lịch phản 
hồi:
¾Đáp ứng yêu cầu.
¾Abort T và khởi tạo T với nhãn thời gian mới
(Rollback).
¾ Trì hoãn T và sau đó quyết định Abort T hay đáp 
ứng yêu cầu
126
Thuật toán điều khiển
1. T yêu cầu Read X
¾ Nếu TS(T) >= WT(X)
z Nếu C(X) = TRUE, đáp ứng yêu cầu
– Nếu TS(T) > RT(X)
• RT(X) := TS(T)
– Ngược lại không thay đổi RT(X)
z Nếu C(X) = FALSE, trì hoãn T cho đến khi C(X) trở
thành TRUE hay giao dịch đã ghi X abort.
¾ Nếu TS(T) < WT(X)
z Rollback T (Đọc quá trễ)
127
Thuật toán điều khiển
2. Giao dịch T yêu cầu Write X
¾ Nếu TS(T) >= RT(X) and TS(T) >= WT(X)
z Ghi giá trị mới trên X
z Đặt WT(X) := TS(T).
z Đặt C(X) := FALSE.
¾ Nếu TS(T) >= RT(X) and TS(T) < WT(X)
z Nếu C(X) = TRUE, bỏ qua việc ghi của T.
z Nếu C(X) = FALSE, trì hoãn T cho đến khi C(X) = TRUE hoặc 
các giao tác ghi trên X đã abort.
¾ Nếu TS(T) < RT(X)
z Rollback T (Ghi quá trễ)
3. Nếu T commit, bộ lập lịch đặt tất cả các đvdl X mà
T ghi giá trị C(X):=TRUE. Các GT đang chờ trên X 
có thể tiếp tục.
4. Trường hợp T rollback, các GT khác đang chờ trên 
X yêu cầu đọc/ ghi lại.
128
Ví dụ
T1 T2 T3 T4 A B C
420 400 425 415 tr=tw=0 tr=tw=0 tr=tw=0
ReadA tr=415
ReadA tr =420
WriteB tw=415
WriteA tw=420
ReadB T2 
rollback
ReadB tr=425
ReadA
WriteC
WriteA tw=425
129
Ví dụ
T1 T2 T3 T4 A B C
510 550 575 500 tr=tw=0 tr=tw=0 tr=tw=0
ReadA tr=500
ReadA tr =510
WriteB tw=500
WriteA tw=510
ReadB tr=550
ReadB tr=575
ReadA tr=550
WriteC Tw=550
WriteA tw=575
130
PP nhãn thời gian đa phiên bản
‰ Là một biến thể của pp nhãn thời gian.
‰ Ngoài phiên bản mới nhất của đvdl được lưu 
lại, còn có các phiên bản trước đó.
‰Mục đích: giúp cho thao tác đọc không bao 
giờ làm giao tác rollback.
¾Hỏi: Khi nào thì thao tác đọc làm giao tác 
rollback?
¾ PP nhãn thời gian đa phiên bản sẽ làm giao tác T 
thay vì abort vì lý do trên sẽ tiếp tục đọc phiên 
bản (của đvdl cần đọc) phù hợp với nhãn thời 
gian của T.
131
PP nhãn thời gian đa phiên bản
‰Mỗi đvdl X có nhiều phiên bản X1, X2, ..., Xk.
‰ Đối với mỗi phiên bản, lưu lại:
¾Giá trị của phiên bản Xi,
¾Nhãn thời gian đọc của Xi :rT (Xi), là nhãn thời 
gian lớn nhất trong các GT đã đọc Xi.
¾Nhãn thời gian ghi của Xi wT(Xi), là nhãn thời 
gian của giao tác đã tạo ra phiên bản Xi.
‰ Khi T được phép ghi trên X, một phiên bản 
mới Xk+1 được tạo, và:
¾ rT (Xk+1) = wT(Xk+1) = TS(T).
‰ Khi T được phép đọc trên Xi, thì:
¾ rT (Xi) = max(rT (Xi), TS(T))
132
PP nhãn thời gian đa phiên bản
‰ Để bảo đảm khả tuần tự, có 2 nguyên tắc sau phải 
được đảm bảo:
1. T yêu cầu ghi trên X:
¾ Trong các phiên bản của X có nhãn thời gian ghi <= TS(T), 
chọn phiên bản Xi có wT(Xi) lớn nhất: 
z Nếu rT (Xi) > TS(T) thì cho T rollback.
z Nếu rT (Xi) <= TS(T), thì:
– Nếu TS(T) = wT(Xi) thì giá trị của Xi bị ghi đè.
– Nếu TS(T) > wT(Xi) thì tạo phiên bản mới Xj, rT (Xj) = wT(Xj) 
=TS(T)
2. T yêu cầu đọc trên X:
¾ Trong các phiên bản của X có nhãn thời gian ghi <= TS(T), 
chọn phiên bản Xi có wT(Xi) lớn nhất:
z Trả về giá trị Xi cho giao tác T.
z rT (Xi) = max (rT (Xi), TS(T))
133
PP nhãn thời gian đa phiên bản
‰ Nếu T rollback thì tình trạng rollback dây 
chuyền có thể xảy ra.
‰ Để lịch biểu là phục hồi được, khi các GT ghi 
trên các đvdl mà T đã đọc commit thì T mới 
được phép commit.
134
10. Điều khiển đồng thời dùng phương pháp 
kiểm tra hợp lệ (Validation Technique)
135
Phương pháp kiểm tra hợp lệ
‰ KT khóa và KT nhãn thời gian là các PP 
điều khiển đồng thời bi quan: giả sử các GT 
sẽ đụng độ và tránh sự đụng độ này.
‰ KT khoá vá KT nhãn thời gian điều khiển 
thực hiện đồng thời theo cú pháp, vì phân 
biệt đọc/ghi.
‰ PP kiểm tra hợp lệ là PP điều khiển đồng 
thời lạc quan.
136
Phương pháp kiểm tra hợp lệ
‰ Cứ cho GT thực hiện.
¾Cập nhật của GT chỉ trên biến cục bộ, không cập 
nhật trực tiếp trên CSDL cho đến khi GT kết 
thúc.
¾Khi GT thi hành xong, kỳ xác nhận kiểm tra các 
cập nhật của GT có vi phạm tính khả tuần tự
không.
z Nếu không, GT commit và CSDL được cập nhật thật sự
từ biến cục bộ.
z Nếu vi phạm, GT abort và khởi động lại.
137
Phương pháp kiểm tra hợp lệ
‰ GT trải qua các kỳ:
¾ 1. Kỳ đọc (Read phase):
z Ti đọc các mục dl cần thiết.
z Các cập nhật chỉ thực hiện trên biến cục bộ, không phải 
trên CSDL.
¾ 2. Kỳ Kiểm tra hợp lệ (Validation phase):
z Kiểm tra có vi phạm tính khả tuần tự hay không để cập 
nhật CSDL.
– Nếu vi phạm thì rollback.
– Nếu không thì làm tiếp kỳ 3.
¾ 3. Kỳ ghi (Write phase):
z Ghi từ biến cục bộ xuống CSDL.
138
Phương pháp kiểm tra hợp lệ
‰ Ghi nhận các nhãn thời gian:
¾ START(Ti) – thời điểm Ti start
¾VAL(Ti) – thời điểm Ti thực hiện xong phase 
validate
¾ Finish(Ti) – thời điểm T thực hiện xong phase 
finish.
139
Phương pháp kiểm tra hợp lệ
‰ Bộ lập lịch theo dõi 3 tập hợp:
¾ START = {T, T đã start, nhưng chưa validate 
xong} + START (T)
¾VAL = {T, T validate xong nhưng chưa xong phase 
finish} + START (T) + VAL(T)
z VAL(T) là thời điểm để căn cứ vào đó điều khiển tuần 
tự.
¾ FIN = {T, T thực hiện xong phase finish} + 
START(T), VAL(T), FIN(T)
z Bộ lập lịch không quan tâm đến GT T sao cho FIN(T) < 
START(U), U là giao tác đang ở trạng thái kích hoạt.
ValidateStart Finish
140
Kiểm tra hợp lệ
‰ Giả sử có GT U:
¾ U ∈ VAL hoặc U ∈ FIN
¾ FIN(U) > START (T), nghĩa là U không finish trước khi T start.
¾ RS(T) ∩ WS(U) = {X} ≠ ∅: có thể U write X sau khi T read X. Ta 
không chắc T đã đọc giá trị U ghi trước đó hay không, tốt hơn 
hết cho T rollback để tránh rủi ro T và U không tuân theo thứ
tự tuần tự.
Start
Validate
FinishU
T
141
Kiểm tra hợp lệ
‰ Giả sử có GT U:
¾ U ∈ VAL, nghĩa là đã validate xong
¾ FIN(U) > VAL (T), nghĩa là U không finish trước khi T bắt 
đầu giai đoạn validate.
¾ WS(T) ∩ WS(U) = {X} ≠ ∅: có thể T sẽ ghi X trước khi U ghi 
X. Ta không chắc điều này có xảy ra hay không, tốt hơn 
hết là rollback T để không vi phạm tính tuần tự.
Start
Validate
Finish
U
T
142
Ví dụ
T: RS(T)={A,B}
WS(T)={A,C}
V: RS(V)={B}
WS(V)={D,E}
U: RS(U)={B}
WS(U)={D}
W: RS(W)={A,D}
WS(W)={A,C}
Hãy điều khiển đồng thời dùng phương pháp kiểm tra hợp lệ cho 4 GT trên.
143
Phương pháp kiểm tra hợp lệ
‰ Nói chung, TS(Ti) = Validation (Ti). Kiểm tra 
hợp lệ cho Tj:
¾Với mọi Ti thỏa TS(Ti) < TS(Tj) thì một trong hai 
điều kiện sau phải thỏa:
z Finish(Ti) < Start(Tj): nếu Ti xong trước khi Tj bắt đầu.
z Start(Tj) < Finish(Ti) < Validation(Tj): Việc ghi của Ti và
Tj không ghi đè. Thao tác ghi của Tj không ảnh hưởng 
thao tác đọc của Tj.
‰ Lịch biểu dùng kỹ thuật này là không 
rollback dây chuyền vì thao tác ghi được 
thực hiện sau khi giao tác commit.
144
Nhận xét chung
‰ Lưu trữ:
z PP lock: lock table, không gian lưu trữ tỉ lệ với số lượng đvdl bị lock.
z PP nhãn thời gian: cần không gian lưu trữ cho nhãn thời gian đọc và
ghi của từng đvdl, bất kể có đang được truy cập hay không.
z Validation: cần lưu lại nhãn thời gian và read set, write set cho từng 
giao tác đang được kích hoạt.
¾ Nói chung, không gian lưu trữ gần như tỉ lệ với số lượng đvdl được truy 
cập bởi các giao tác đang ở trạng thái kích hoạt.
‰ Về khả năng giao tác hoàn tất mà không bị trì hoãn:
¾ Hiệu quả của các phương pháp còn tùy thuộc vào sự ảnh hưởng lẫn nhau 
của các giao tác (truy cập cùng đvdl) là nhiều hay ít.
z PP lock: trì hoãn GT nhưng tránh được tình trạng rollback, ngay cả khi sự ảnh 
hưởng lẫn nhau giữa các GT đồng thời là nhiều. PP nhãn thời gian và pp Kiểm 
tra hợp lệ không trì hoãn GT nhưng có thể gây ra tình trạng GT rollback Ỉ lãng 
phí tài nguyên.
z Nếu sự ảnh hưởng lẫn nhau giữa các GT đồng thời là nhỏ thì cả PP nhãn thời 
gian lẫn Kiểm tra hợp lệ đều không gây ra rollback. Khi đó cả hai làm việc tốt 
hơn và tốn ít chi phí hơn PP lock.
z Khi rollback xảy ra, pp Nhãn thời gian bắt vấn đề sớm hơn pp Kiểm tra hợp lệ.
145
Phụ lục
146
TT NHÃN THỜI GIAN
1. T yêu cầu Read X
Nếu TS(T) >= WT(X)
T đọc X
RT(X) := max (RT(X), TS(T))
Nếu TS(T) < WT(X)
Rollback T (Đọc quá trễ)
2. Giao dịch T yêu cầu Write X
Nếu TS(T) >= RT(X) and TS(T) >= WT(X)
T ghi X
Đặt WT(X) := TS(T)
Nếu TS(T) < RT(X) or TS(T) < WT(X)
Rollback T (Ghi quá trễ)
147
Nhãn thời gian đa phiên bản
1. T yêu cầu ghi trên X:
¾ Trong các phiên bản của X có nhãn thời gian ghi 
<= TS(T), chọn phiên bản Xi có wT(Xi) lớn nhất: 
z Nếu rT (Xi) > TS(T) thì cho T rollback.
z Nếu rT (Xi) <= TS(T), thì:
– Nếu TS(T) = wT(Xi) thì giá trị của Xi bị ghi đè.
– Nếu TS(T) > wT(Xi) thì tạo phiên bản mới Xj, rT (Xj) 
= wT(Xj) =TS(T)
2. T yêu cầu đọc trên X:
¾ Trong các phiên bản của X có nhãn thời gian ghi 
<= TS(T), chọn phiên bản Xi có wT(Xi) lớn nhất:
z Trả về giá trị Xi cho giao tác T.
z rT (Xi) = max (rT (Xi), TS(T))
148
Hết chương 2.