Tính khả tuần tự của
lịch thao tác trong cơ
chế Lock.

1. Cơ chế Lock
2. Cơ chế Lock 2 giai đoạn (2 Phases Locking)
3. Bài tập và hướng dẫn:

CHÚ Ý:
Quy ước:
Để thuận lợi cho việc biểu diễn các thao tác theo thời gian, 1 thao tác được viết dưới dạng M
iTj
.
Trong đó:
- M là tên thao tác, có thể là Read, Write, Lock, Unlock, Rlock …
- Với i là thứ tự theo thời gian từ trên xuống.
- Với j là mã số của giao tác, ví dụ T1,T2 … Tj.
TÍNH KHẢ TUẦN TỰ CỦA LỊCH THAO TÁC TRONG CƠ CHẾ LOCK

I. CƠ CHẾ LOCK :
1. Đặc điểm:
Chỉ xét các thao tác Lock và Unlock để xét tính khả tuần tự của lịch.
2. Đồ thị khả tuần tự ( cơ chế lock )
- S là tập các giao tác T1,T2,T3…Tn
- Xét các thao tác Mi có dạng Lock(A) và Unlock(A).
- Nếu Ti có 1 thao tác dạng Unlock(A), Tj có thao tác tiếp theo sau đó có dạng
Lock(A) thì vẽ 1 cung có hướng từ Ti Tj .
- Lịch thao tác khả tuần tự  đồ thị không có chu trình .


11
Write(a1) A
12 Unlock(A)  Hướng dẫn:
- T1 thực hiện Unlock
3T1
(A) sau đó T2 thực hiện Lock
4T2
(A)  ta có : T1  T2
- T2 thực hiện Unlock
8T2
(A) sau đó T1 thực hiện Lock
10T1
(A)  ta có: T2  T1

- Kết luận: Đồ thị có chu trình  Lịch S không khả tuần tự.
3. Cách xây dựng đồ thị khả tuần tự:

- Đánh dấu tất cả lệnh Unlock.
- Xét tuần tự từng lệnh Unlock:
o Giả sử đang xét lệnh Unlock (A) của giao tác Ti.
o Với mỗi lệnh Lock (A) của các giao tác Tj (j <> I ) được thực hiện sau lệnh
này, vẽ 1 cung hướng từ Ti  Tj.
- Nếu đồ thị không có chu trình  Lịch S khả tuần tự.

Ví dụ 2: Cho lịch S như sau. Xét tính khả tuần tự của lịch S.
Time

10

Unlock(B)
11
Lock(C)
12 Unlock(A)13
Lock(A)
14

Unlock(A)

15 Unlock(B)

16 Unlock(C)
 HƯỚNG DẪN:
B1. Đánh dấu ( tô đậm như trên hình vẽ trên)
B2: Lần lượt xét các Unlock ( có dạng Unlock
xTy
(X) với x là thứ tự thời gian và y là thứ tự giao
tác):
 Xét Unlock
4T2
(A) của T2 trên ĐVDL là A:
o Ta có: Lock

(A) của T1 trên ĐVDL là A:
o Ta có: Lock
13T4
(A) thực hiện sau thao tác trên nên ta có cung : T1T4
 Xét các Unlock
14T4
(A), Unlock
15T1
(B) và Unlock
16T1
(C) ta có:
o Sau các thao tác này không có các giao tác khác thực hiện Lock trên ĐVDL tương
ứng nên ta không tìm được thêm cung nào nữa.
B3: Vẽ đồ thị.
Sau bước 2 ta có các cung và đồ thị tương ứng sau:
Cung ĐVDL
T2T1 A,B
T2T4 A,B
T3T1 A
T3T4 A
T1T4 B Nhận xét đồ thị không có chu trình:
 Lịch S khả tuần tự theo thứ tự thực hiện sau:
 T2  T3  T1  T4
hoặc
 T3  T2  T1  T4
II. KHÓA 2 GIAI ĐOẠN (2 PL , Two Phase Lock):
1. Điều kiện thỏa nghi thức khóa 2 giai đoạn (2PL):

Read(A)
Unlock(A)

Lock(B)
Read(B)
B=B+A
Write(B)
Unlock(B)Thỏa nghi thức 2PL Không thỏa nghi thức 2PL

II. BÀI TẬP :
1. Bài tập 1 : Cho lịch S như sau :
Time

T1 T2
1 RL(A)

2
Read(A)
3 UL(A)

4

RL(B)
5
Read(B)
6


a. Xét tính khả tuần tự của S.
- Giao tác T1 thực hiện Rlock
1T1
(A), sau đó T2 thực hiện Wlock
7T2
(A), ta có cung :
T1  T2
- Giao tác T2 thực hiện Rlock
4T2
(B) sau đó T1 thực hiện Wlock
12T1
(B),ta có cung :
T2  T1

- Kết luận: Đồ thị có chu trình  Lịch không khả tuần tự.

b. Xét thỏa tính chất 2PL
- Xét T1: RLock(A)  Read (A)  Unlock(A)  Wlock(B)  Read(B)  B=B+A
 Write(B)  Ulock(B).
o Ta có : Wlock(B) thực hiện sau Unlock (A)  T1 không thỏa 2PL.
- Xét T2: RLock(B)  Read(B)  Unlock(B)  Wlock(A)  Read(A)  A=A+B
 Write(A)  Unlock(A) .
o Ta có: Wlock(A) thực hiện sau Unlock(B)  T2 không thỏa 2PL.
2. Bài tập 2: Cho lịch S như sau.
Time

T1 T2 T3 T4
1

RL(A)


RL(B)
10 RL(A)

11

UL(B)
12 WL(C)13 UL(A)

14

WL(B)

15

UL(B)
16 UL(B)

17 UL(C) a. Xét S có khả tuần tự không
b. Các giao tác T1, T2, T3, T4 có thỏa 2PL không.

 HƯỚNG DẪN:
a. Xét tính khả tuần tự.
Cách 1:

6T2
(B) (xét cung kiểu 2) và:
 T1 thực hiện Rlock
7T1
(B) ngay sau đó mà chưa có bất kì 1 giao tác nào
khác T1 thực hiện Wlock(B) nên T1 phải thực hiện sau T2 . Ta có cung:
T2 T1.
 Tương tự với giao tác T4 với thao tác Rlock
9T4
(B). Ta có cung: T2 T4.
o T1 thực hiện Rlock
7T1
(B):
 T4 thực hiện Wlock
14T4
(B) sau thao tác trên của T1 nên ta có cung:
T1 T4.
o Việc xét các thao tác Rlock
9T4
(B) và Wlock
14T4
(B) không tạo thêm cung nào mới
vì sau các thao tác trên không tồn tại 1 thao tác Wlock(B) và Rlock(B) nào trên
các giao tác khác T4.
 Xét trên ĐVDL C (màu xanh lá cây):
o Dễ dàng thấy được, việc xét các thao tác trên ĐVDL này không thể tạo thêm cung
mới nào vì tất cả các thao tác đều thuộc T1.
Như vậy, sau khi xét lần lượt các thao tác cho từng ĐVDL ta có danh sách các cung và đồ thị
sau:
Cung ĐVDL