Bài giảng Cơ sở dữ liệu phân tán - Chương 4: Điều khiển tương tranh

A) 
Unlock (A) 
 Unlock (A) 
b. Thuật toán kiểm tra tính khả tuần tự của lịch S: 
Xây dựng 1 đồ thị có hướng G, mỗi giao tác Ti là một node. 
- T là 1 tập các giao tác T1, T2, …, Tn. Xét các thao tác Oij có dạng Lock(A), Unlock (A) 
(không quan tâm các thao tác khác) 
- Nếu Ti có 1 thao tác có dạng Unlock(A), Tj có thao tác tiếp theo sau đó có dạng Lock(A) 
(cùng đơn vị dữ liệu A) thì vẽ 1 cung có hướng đi từ Ti đến Tj (i.e., Ti phải thực hiện trước Tj). 
- Lịch thao tác khả tuần tự ĩ Đồ thị không có chu trình. 
Ø Ví dụ 1: 
Ng 
Duc
 Thu
an
CSDLPT-Điều khiển tương tranh 12 
T1 T2 
Lock A 
Read A à a1 
Unlock A 
 Lock A 
 Read A à a2 
 a2+1à a2 
 Write a2 à A 
 Unlock A 
A1+1à a1 
Lock A 
Write a1àA 
Unlock A 
T1 T2
Ø Ví dụ 2: 
T1 T2 T3 T4 
 Lock A (1) 
 Lock A (2) 
 Lock B (3) 
 Unlock A (4) 
 Unlock B (5) 
Lock B (6) 
 Unlock A (7) 
 Lock B (8) 
Lock A (9) 
 Unlock B (10) 
Lock C (11) 
Unlock A (12) 
 Lock A (13) 
 Unlock A (14) 
Unlock B (15) 
Unlock C (16) 
Ng 
Duc
 Thu
an
CSDLPT-Điều khiển tương tranh 13 
T1 T2
T4 T3
Những cung liền nét: xác định được từ thuật toán 
Những cung đứt nét: Khi T3 thực hiện lệnh Lock 
A (2) thì T2 đang giữ khóa A nên bắt buộc T3 
phải thực hiện sau T2 
=> Chỉ cần thực hiện theo thuật toán (T2 ® T3 
® T1 ® T4) 
3. Kỹ thuật khóa đọc/ viết (Readlock/Writelock): 
a. Giới thiệu: 
- Nếu không phân biệt khóa cho thao tác đọc hay viết thì rõ ràng sẽ có nhiều giao tác phải 
chờ để được quyền khóa trên một đơn vị dữ liệu. Thưc tế là nhiều khi một giao tác chỉ cần lấy 
giá trị của 1 đơn vị dữ liệu nhưng không thay đổi giá trị đó. Vì vậy để giảm bớt tình huống phải 
chờ khi các giao tác cùng đọc dữ liệu, người ta đề nghị tách yêu cầu khóa thành 2 yêu cầu khóa 
riêng biệt: 
· Khóa để đọc (hay Shared lock): một giao tác T chỉ muốn đọc một đơn vị dữ liệu A sẽ 
thực hiện lệnh RLOCK(A), ngăn không cho bất kỳ giao tác khác ghi giá trị mới của A trong khi 
T đã khóa A. Tuy nhiên các giao tác khác vẫn có thể giữ 1 khóa đọc trên A cùng lúc với T. 
· Khóa để ghi (hay Exclusive lock): một giao tác T muốn thay đổi giá trị của một đơn vị 
dữ liệu A đầu tiên sẽ lấy khóa ghi bằng cách thực hiện lệnh WLOCK(A). Khi 1 giao tác đang 
giữ 1 khóa ghi trên 1 đơn vị dữ liệu, các giao tác khác không thể lấy được khóa đọc hoặc khóa 
ghi trên A cùng lúc với T. 
 Cả hai khóa đọc và khóa ghi đều được loại bỏ bằng lệnh UNLOCK. 
Ø Điều kiện để xin khóa đọc/ viết: 
 + Một yêu cầu xin RLOCK(A) chỉ được chấp thuận nếu A chưa bị khóa bởi 1 WLOCK trước 
đó. 
 + Một yêu cầu xin WLOCK(A) chỉ được chấp thuận nếu A được tự do. 
- Ma trận tương thích các loại khóa: 
 Lock đang được giữ 
 R-lock W-lock 
R-lock Yes No Giao tác yêu cầu 
lock W-lock No No 
Ø Từ ma trận tương thích, chúng ta thấy rằng: 1 đơn vị dữ liệu tại 1 thời điểm có thể có nhiều 
transaction giữ Rlock nhưng chỉ có tối đa 1 transaction giữ Wlock. 
Ø Việc sử dụng cơ chế lock không đủ để bảo đảm tính khả tuần tự cho lịch thao tác. 
Ví dụ: Lịch thao tác không khả tuần tự nên xảy ra lost update 
Ng 
Duc
 Thu
an
CSDLPT-Điều khiển tương tranh 14 
T1 T2 Ghi chú 
Rlock B 
Read B à a1 a1=B=2 
Unlock B 
 Rlock B 
 Read B à a2 a2=B=2 
 Unlock B 
 a2+1àa2 a2 = 3 
 Wlock B 
 Write a2 à B B = a2 = 3 
 Unlock B 
a1+1àa1 a1 = 3 
Wlock B 
Write a1 à B B = a1 = 3 (Lost Update) 
Unlock B 
b. Thuật toán kiểm tra tính khả tuần tự của lịch S: 
- Input: Một lịch S được lập từ n giao tác T1, T2, …, Tn (Ti tuân thủ kỹ thuật khóa Wlock, 
Rlock). 
- Output: S có khả tuần tự hay không ? 
- Xây dựng một dồ thị có hướng G, mỗi giao tác Ti là một node. 
+ Nếu có 1 giao tác Ti phát ra yêu cầu Rlock(A), “ngay” sau đó có 1 giao tác Tj phát ra yêu cầu 
Wlock(A) thì sẽ có 1 cung đi từ Ti đến Tj. 
+ Nếu có 1 giao tác Ti phát ra yêu cầu Wlock(A), “ngay” sau đó có 1 giao tác Tj phát ra yêu 
cầu Wlock(A) hoặc Rlock (A) thì sẽ có 1 cung đi từ Ti đến Tj. 
Lịch S không khả tuần tự khi đồ thị không có chu trình. 
4. Một số vấn đề trong kỹ thuật khóa: 
a. Livelock: 
- Hệ thống trao và buộc khóa các đơn vị dữ liệu không thể hoạt động một cách thất thường, 
nếu không thì các hệ thống không mong muốn có thể sẽ xảy ra. Giả sử trong ví dụ trên, khi T1 
giải phóng khóa trên A, khóa này được trao lại cho T2. Điều gì sẽ xảy ra nếu như trong khi T2 
đang đợi nhận khóa, một giao tác T3 khác cũng xin một khóa trên A, và T3 lại được trao khóa 
này trước T2. Rồi sau khi T3 được trao khóa trên A thì lại có 1 giao tác T4 xin khóa trên A, v…v… 
Và rất có thể T2 phải đợi mãi và cha úng bao giờ nhận được khóa trong khi luôn có 1 giao tác 
khác giữ khóa trên A, dù rằng có 1 số lần T2 có cơ hội nhận được khóa trên A. 
- Như vậy, Livelock là trường hợp 1 giao tác chờ được cấp quyền lock trên 1 đơn vị dữ liệu nào 
đó mà không xác định được thời điểm được đáp ứng yêu cầu. Nó có thể xảy ra âm thầm trong 1 
môi trường có nhiều tiến trình thực hiện cùng một lúc. Chúng ta có thể sử dụng một chiến lược 
đơn giản để tránh livelock, đó là yêu cầu hệ thống khi trao khóa phải ghi nhận tất cả các thỉnh 
cầu chưa được đáp ứng, và khi đơn vị dữ liệu A được mở khóa thì trao cho các giao tác đã xin 
đầu tiên trong số những giao tác đang đợi khóa A. Và khi đó bộ lập lịch (schedulers) sẽ tiến 
hành thực hiện cơ chế: giao tác nào yêu cầu trước thì được đáp ứng trước (FIFO). 
Ng 
Duc
 Thu
an
CSDLPT-Điều khiển tương tranh 15 
b. Deadlock: 
- Xét ví dụ sau: 
T1 T2 Nhận xét 
Lock A 
 Lock B 
 Lock A 
Lock B 
- T1 chờ T2 unlock B 
- T2 chờ T1 unlock A 
=> Deadlock 
T1 yêu cầu và được trao khóa trên A, còn T2 yêu cầu và được trao khóa trên B. Do đó khi 
T1 yêu cầu khóa trên B, nó sẽ phải đợi vì T2 đã khóa B. Tương tự khi T2 yêu cầu khóa trên A, 
nó cũng buộc phải đợi vì T1 đã khóa A. Kết quả là không một giao tác nào tiếp tục hoạt động 
được: mỗi giao tác đều phải đợi cho giao tác kia mở khóa, và chúng đều phải đợi nhưng chẳng 
bao giờ nhận được khóa như yêu cầu. 
- Như vậy, Deadlock là tình trạng trong đó những giao tác có liên quan không thể thực hiện 
tiếp các thao tác của nó mà phải chờ nhau mãi. Chúng ta có thể giải quyết Deadlock bằng cách: 
bỏ qua (hủy, làm lại tất cả); ngăn ngừa Deadlock bằng cách để cho các giao tác chờ theo 1 
chiều nhất định; phát hiện Deadlock bằng cách dùng đồ thị chờ (wai-for graph), nếu có chu 
trình thì hủy đỉnh (giao tác) có nhiều cung vào hay ra. 
5. Bộ lập lịch (schedulers) và nghi thức (protocol): 
- Khi thực hiện đồng thời các transaction phát sinh các vấn đề như livelock, deadlock hay lịch 
thao tác không khả tuần tự. Để giảm bớt những vấn đề này, ta có 2 công cụ: bộ lập lịch và nghi 
thức. 
a. Bộ lập lịch (schedulers): là thành phần của hệ thống CSDL giải quyết các yêu cầu đụng độ. 
Bộ lập lịch loại bỏ Livelock bằng cách ép các transaction phải chờ trong trường hợp không đáp 
ứng được yêu cầu lock, hoặc hủy bỏ các transaction (khi xảy ra deadlock và tính không khả 
tuần tự). 
Lock
Table
Lock
Manager
Scheduler
Các Transaction thực hiện theo protocol Yêu cầu lock
Cho phép hay
từ chối lock
Cho phép truy xuất, chờ
hay rollback giao tác
Yêu cầu lock
b. Nghi thức (protocol): giải quyết vấn đề deadlock và tính không khả tuần tự. Ví dụ như 
chiến lược lock 2 pha, hoặc yêu cầu các giao tác lock các đơn vị dữ liệu theo 1 thứ tự cố định 
nào đó. 
Ng 
Duc
 Thu
an
CSDLPT-Điều khiển tương tranh 16 
6. Nghi thức lock 2 giai đoạn (2 phase): 
phase lock phase unlock
BOT EOT
Số các
đơnvị
dữ liệu
bị giữ
lock
t
Ø Nghi thức khóa 2 giai đoạn (lock 2 phase): 1 giao tác thực hiện cơ chế lock 2 phase là 1 
giao tác không thực hiện 1 lock nào nữa sau khi đã unlock (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). Các giao tác tuân theo nghi thức này được gọi là các giao tác hai 
pha: pha ban đầu là pha khóa, pha sau là pha mở khóa. 
Ví dụ: 
T1 T2 T3 
 Lock (A) 
 Unlock(A) 
 Lock (A) 
 Unlock (A) 
Lock (B) 
Unlock (B) 
 Lock (B) 
Thời gian 
 Unlock (B) 
 Trong ví dụ trên, T1 và T3 là các giao tác 2 pha, còn T2 thì không. 
Ø Phát biểu: Một lịch S được lập từ n giao tác thỏa nghi thức khóa 2 pha thì khả tuần tự. 
Chứng minh: 
- Ví dụ cho 1 tập các giao tác T1, T2, …, Tn. Giả sử dồ thị có chu trình: 
T1 T2 T3 Ti Tn... ...
- T1 thực hiện trước T2: T2 thực hiện lock trên 1 số đvdl nào đó được unlock bởi T1 
- T2 thực hiện trước T3: T3 thực hiện lock trên 1 số đvdl nào đó được unlock bởi T2 
- … 
- Tương tự, T1 thực hiện lock trên 1 số đvdl nào đó được unlock bởi Tn 
=> T1 có dạng Lock … … Unlock … …Lock… 
=> T1 không phải lock 2 pha 
Ø Sử dụng nghi thức lock 2 giai đoạn chỉ có thể đảm bảo tính khả tuần tự cho lịch thao tác 
nhưng không thể bảo đảm không xảy ra vấn đề deadlock 
Ng 
Duc
 Thu
an
CSDLPT-Điều khiển tương tranh 17 
Ø Ví dụ: 
T1 T2 Ghi chú 
Lock A 
 Lock B 
Lock B T1 phải chờ T2 unlock B 
 Lock A T2 phải chờ T1 unlock A => deadlock 
Unlock A 
 Unlock B 
Unlock B 
 Unlock A