Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 1
Chương IV : ĐIỀU KHIỂN TƯƠNG TRANH
I. Giao tác (transaction)
1. Khái niệm:
Giao tác là một tập hợp các thao tác có thứ tự truy xuất dữ liệu trên CSDL thành một đơn vò
công việc logic (xem là một thao tác nguyên tố ), chuyển CSDL từ trạng thái nhất quán này
sang trạng thái nhất quán khác.
Để ghi nhận sự hoàn tất hay không của một giao tác, người ta sử dụng các lệnh sau:

BEGIN TRANSACTION
Bắt đầu một giao tác
COMMIT TRANSACTION
Kết thúc giao tác thành công
ROLLBACK TRANSACTION
Kết thúc giao tác không thành công, những thao tác làm
ảnh hưởng CSDL đã được thực hiện trước đó được
undo, CSDL được trả về tình trạng trước khi thực hiện
giao tác.
END TRANSACTION
Chỉ mang ý nghóa hình thức, thường không sử dụng
Ví dụ: Cho 2 quan hệ
- LOP (Malop, Tenlop, SoSV)
- SV (MaSV, TenSV, Malop)
Quy đònh: khi thêm một sinh viên vào một lớp thì phải cập nhật lại sỉ số của lớp đó.
Ø Giao tác thêm 1 SV vào 1 lớp:
BEGIN TRANSACTION Them_SV
Insert into SV values(v_masv,v_tensv,v_malop)
Update LOP
Set SoSV = SoSV + 1
Where Malop = v_malop

COMMIT TRANSACTION Them_SV
2. Các tính chất của giao tác: ACID
a. Tính nguyên tố (Atomic)
- 1 giao tác là 1 đơn vò xử lý không thể chia nhỏ được nữa; hoặc là tất cả các thao tác trong
giao tác được thực hiện (được ghi nhận chắc chắn), hoặc là không có thao tác nào được ghi nhận
kết quả.(Nếu chia nhỏ giao tác thành các thao tác thì sẽ không đảm bảo tính nhất quán của
CSDL.)
b. Tính nhất quán (Consistency)
- Giao tác chuyển CSDL từ tình trạng nhất quán này sang tình trạng nhất quán khác.
c. Tính cô lập (Isolation)
- Các giao tác xử lý đồng thời phải độc lập với những thay đổi được thực hiện bởi các giao tác
chưa hoàn tất khác (những thay đổi này chưa hình thành nên 1 trạng thái nhất quán của CSDL).
d. Tính lâu dài, bền vững (Durability)
- Tất cả những thay đổi lên CSDL mà giao tác thực hiện cho đến khi được xác nhận hoàn tất
(commit) thì phải được ghi nhận chắc chắn lên CSDL.
Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 2
II. Các vấn đề của việc truy xuất đồng thời:
1. Mất dữ liệu cập nhật (lost update)
Ø Ví dụ: Cho quan hệ HANGHOA (MaHH, TenHH, ĐVT, SLTon)
SLTon = 20
Transaction Giá trò
T1 (bán hàng) T2 (bán hàng) x1 x2 SLTon

Begin Transaction Begin Transaction
20
Read (SLTon) à x1
20
20
Read (SLTon) à x2 20

20
20
x1 – 10 à x1
10
20 20
x2 – 3 à x2 10
17
20
Write x1à SLTon 10 17
10
Write x2à SLTon 10 17
17
Commit T1 Commit T2
17
Ø Lost Update: Thao tác cập nhật của T1 coi như bò mất, không được ghi nhận (do những thay
đổi của các giao tác khác ghi đè lên).
2. Đọc dữ liệu chưa commit (uncommitted data)
Ø Ví dụ: Cho quan hệ HANGHOA (MaHH, TenHH, ĐVT, SLTon)
SLTon = 20
Transaction Giá trò
T1 (nhập hàng) T2 (bán hàng) x1 X2 SLTon

Begin Transaction
20
Read (SLTon) à x1
20
20
x1 + 100 à x1
120
20

Write x1à SLTon 120
120

Begin Transaction
120 120
Read (SLTon) à x2 120
120
120
x2 – 5 à x2 120
115
120
Write x2à SLTon 120 115
115

Commit T2
120 115 115
Rollback T1

20
Ø Transaction T1 sửa đổi dòng X nhưng chưa commit, Transaction T2 đọc dòng X.
Transaction T1 rollback những gì đã thay đổi trên dòng X => dữ liệu mà Transaction T2 đang
đọc chưa hề tồn tại.
3. Thao tác đọc không thể lặp lại (unrepeatable data)
Ví dụ: Xét 2 giao tác sau:
T1 T2
Read(A) Read(A)
A=A+10 Print(A)
Write(A) Read(A)
Print(A)
Ng Duc Thuan

CSDLPT-Điều khiển tương tranh 3
Giả sử A=20 và 2 giao tác này thực hiện đồng thời theo thứ tự sau:
Transaction Giá trò
T1 T2 x1 x2 A
Begin Transaction
20
Read (A) à x1 20 20

Begin Transaction


Read (A) à x2 20 20 20
x1+10
à
x1

30
20 20
Print (x2) 30 20 20
Write x1
à
A 30 20 30
Read (A) à x2 30 30 30

Commit T2
30 30 30
Commit T1


Ø Khi giao tác T2 đọc nhiều lần trên cùng một dòng dữ liệu, giữa 2 lần đọc thì có một thao

tác làm thay đổi giá trò dòng đó ở giao tác T1 => trong giao tác T2 mỗi lần đọc dòng đó
sẽ cho ra những kết quả khác nhau.
4. Vấn đề “bóng ma” (phantom)
Ví dụ: T1 thực hiện việc chuyển tiền từ tài khoản A sang tài khoản B. Khi T1 mới chỉ thực
hiện thao tác trừ số tiền ở tài khoản A (chưa cộng số tiền vào tài khoản B) thì T2 muốn xem
tổng số tiền ở hai tài khoản => Tổng số tiền không chính xác.
Transaction
T1 T2
Begin Transaction

Read (A)
A=A-50

Write (A)

Begin Transaction

Read(A)

Read (B)

Print (A+B)
Commit T2
Read (B)

B=B+50

Write (B)

Commit T1

Ø Như vậy, một tiêu chuẩn để lập lòch các giao tác là việc thực hiện đồng thời các giao tác cho
kết quả giống như khi thực hiện tuần tự các giao tác.
III. Đơn vò dữ liệu:
1. Đònh nghóa:
- Đơn vò dữ liệu (item) là đơn vò nhỏ nhất mà hệ quản trò CSDL có thể đọc/ghi một lần, là đơn
vò để giải quyết tranh chấp.
- Đơn vò dữ liệu có thể là database, table, field, record,…
Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 4
+ Nếu đònh nghóa đơn vò dữ liệu lớn thì số giao tác thực hiện giảm nhưng sẽ không có thuận lợi
trong việc giải quyết tranh chấp. Ví dụ nếu đơn vò dữ liệu là bảng -> nhiều người cùng truy xuất
trên bảng thì giao tác sau phải chờ giao tác trước nhả bảng ra.
+ Nếu đònh nghóa đơn vò dữ liệu nhỏ thì nhiều giao tác được thực hiện đồng thời. Ví dụ đơn vò dữ
liệu là bộ thì việc truy xuất của người sử dụng trên các bộ khác nhau có thể chấp nhận được.
- Các thao tác trên đơn vò dữ liệu A:Đọc, Ghi
2. Một số tính chất khi thao tác trên đơn vò dữ liệu:
a. Hai thao tác tương thích:
- Hai thao tác O
i
và O
j
(O
i
Ỵ Ti, O
j
Ỵ Tj) gọi là tương thích nếu và chỉ nếu kết quả của việc
thực hiện đồng thời của O
i
và O
j

giống như kết quả của việc thực hiện tuần tự O
i
rồi đến O
j
hoặc
O
j
rồi đến O
i
.
Ø Ví dụ:

T1 T2
Read A à a1 Read A à a2
a1 + 1 à a1 a2 * 2 à a2
11
O
Print a1 Print a2
21
O
Read A à a1 Read A à a2
a1 + 5 à a1 a2 * 2 à a2
12
O
Write a1 à A Write a2 à A
22
O
Read A à a1 Read A à a2
a1 + 2 à a1 a2 +7 à a2
13

O
Write a1 à A Write a2 à A
23
O

14
O
Read B à b1
b1 + 1 à b1
Write b1 à B

- Thao tác
11
O và
21
O là tương thích
- Thao tác
12
O và
22
O không tương thích
- Thao tác
13
O và
23
O không tương thích
- Thao tác
14
O tương thích với các thao tác còn lại.
Như vậy, có thể rút ra kết luận: hai thao tác trên hai đơn vò dữ liệu là tương thích với nhau; 2

thao tác đọc trên cùng một đơn vò dữ liệu là tương thích.
b. Hai thao tác khả hoán vò:
- Hai thao tác
i
O ,
j
O (O
i
Ỵ Ti, O
j
Ỵ Tj) là khả hoán vò nếu kết quả của việc thực hiện
i
O ,
j
O
hay
j
O ,
i
O là như nhau.
Ø Ví dụ: Xét ví dụ trên.
- Thao tác
11
O và
21
O là khả hoán vò.
- Thao tác
12
O và
22

O không khả hoán vò.
- Thao tác
13
O và
23
O là khả hoán vò vì cuối cùng giá trò A ß A +9
Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 5
- Thao tác
14
O khả hoán vò với các thao tác còn lại.
v Nhận xét:
Ø Các thao tác truy xuất các đơn vò dữ liệu khác nhau thì tương thích và khả hoán vò.
Ø Các thao tác truy xuất trên cùng đơn vò dữ liệu:
- Nếu có liên quan đến phép cộng hay trừ thì khả hoán vò.
- Read – Read ==> Khả hoán vò
- Read – Write ==> Không có tính khả hoán vò
- Write – Read ==> Không có tính khả hoán vò
- Write – Write ==> Không có tính khả hoán vò
IV. Lòch tuần tự – Lòch khả tuần tự:
1. Lòch tuần tự (serial schedule):
- Một lòch S được lập từ n giao tác T
1
, T
2
,…, T
n
xử lí đồng thời được gọi là lòch tuần tự nếu các
thao tác của từng giao tác được thực hiện liên tiếp nhau.
2. Lòch khả tuần tự (serializable schedule):

- Một lòch S được lập từ n giao tác T
1
, T
2
,…, T
n
xử lí đồng thời được gọi là lòch khả tuần tự nếu
nó cho cùng kết quả với một lòch tuần tự được lập từ n giao tác trên.
Ø Ví dụ: 2 giao tác T1 và T2 có các thao tác sau:
T1 T2
Read A à a1 Read A à a2
a1 + 1 à a1 a2 * 2 à a2
Write a1 à A Write a2 à A
Read B à b1 Read B à b2
b1 + 1 à b1 b2 * 2 à b2
Write b1 à B Write b2 à B

Lòch 1 (A=1, B=2) Lòch 2 (A=1, B=2)
T1 T2 T1 T2
Read A à a1 Read A à a2
a1 + 1 à a1 a2 * 2 à a2
Write a1 à A (2) Read A à a1
Read A à a2 a1 + 1 à a1
a2 * 2 à a2 Write a2 à A (2)
Write a2 à A (4) Read B à b2
Read B à b1 b2 * 2 à b2
b1 + 1 à b1 Write a1 à A (2)
Write b1 à B (3) Read B à b1
Read B à b2 b1 + 1 à b1
b2 * 2 à b2 Write b1 à B (3)

Write b2 à B (6) Write b2 à B (4)
Ø Theo lòch 1, kết quả nhận được hoàn toàn tương tự như khi thực hiện tuần tự T1<T2
+ Lòch 1 có tính khả tuần tự; lòch 2 không có tính khả tuần tự.
Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 6
- Tính khả tuần tự của các giao tác là điều kiện đủ để tránh đụng độ trong việc truy xuất đồng
thời (nếu khả tuần tự thì không đụng độ, nhưng nếu không khả tuần tự thì chưa chắc có đụng
độ).
- Bộ lập lòch (Scheduler): là một bộ phận của DBMS chòu trách nhiệm lập lòch khả tuần tự từ n
giao tác xử lí đồng thời, sẽ tiến hành lập lòch các thao tác (thao tác sẽ được thực hiện trước, thao
tác nào sẽ được thực hiện sau).
3. Thuật toán kiểm tra tính khả tuần tự của một lòch S:
Input: Lòch S bất kỳ được hình thành từ n giao tác T
1
, T
2
,…, T
n
.
Output: Xác đònh xem S có khả tuần tự hay không bằng cách xây dựng một đồ 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 Read(X) và sau đó có một giao tác Tj (j ¹ i) phát ra
yêu cầu Write (X) thì hình thành cung đi từ Ti đến Tj.
- Nếu có 1 giao tác Ti phát ra yêu cầu Write(X) và sau đó có một giao tác Tj (j ¹ i) phát ra
yêu cầu Write (X) / Read (X) thì hình thành cung đi từ Ti đến Tj.
- Nếu đồ thò G có chu trình thì S không khả tuần tự.
Ví dụ: Xét tính khả tuần tự của lòch thao tác sau:

T1 T2 T3 T4

(1) Read A
(2) Read A
(3) Write B
(4) Write A
(5) Read B
(6) Read B
(7) Read A
(8) Write B
(9) Write A
Đồ thò có chu trình T
1
® T
4
® T
1
nên không khả tuần tự

T
1
T
2
T
4
T
3


Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 7
V. Kỹ thuật sắp xếp các giao tác bằng nhãn thời gian:

Ø Chỉ sắp xếp thứ tự các giao tác (thời gian bắt đầu), không nhằm sắp xếp trình tự thực hiện các
thao tác trong mỗi giao tác.
1. Khái niệm nhãn thời gian (timestamp)
- Là 1 con số được phát sinh bởi bộ lập lòch, được gán cho mỗi giao tác để chỉ đònh thời điểm
bắt đầu thực hiện giao tác. Nhãn thời gian có tính chất duy nhất và tăng dần.
(
ji
TjiTji
ttTT <Û< )
- Nhãn thời gian của đơn vò dữ liệu: Nhãn thời gian của đơn vò dữ liệu chính là nhãn thời gian
của giao tác cuối cùng có truy cập đến đơn vò dữ liệu đó thành công hoặc là nhãn thời gian cao
nhất trong số các giao tác có truy cập thành công đến đơn vò dữ liệu đó.
Ø Ví dụ: T1< T2<T3
T1 T2 T3
A
t
Read A
1TA
tt=
Read A
2TA
tt=
Read A
3TA
tt =
2. Thuật toán sắp xếp toàn phần
Procedure Read (
i
T, A)
Begin

If
i
TiA
tt £ then
- Thực hiện thao tác đọc g
- t
A
:=
Ti
t
Else
Rollback
i
T và bắt đầu lại với nhãn thời gian mới
End Proc
Procedure Write (
i
T, A)
Begin
If
i
TiA
tt £ then
- Thực hiện thao tác ghi g
- t
A
:=
iT
i
t

Else
Rollback
i
T và bắt đầu lại với nhãn thời gian mới
End Proc
Ø Ghi chú:
- t
A
: nhãn thời gian của đơn vò dữ liệu A
-
iT
i
t : nhãn thời gian của giao tác
i
T
- Ban đầu 0=
A
t khi chưa có giao tác nào truy cập.
Ø Ví dụ 1: 0,120,100
21
===
ATT
ttt


Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 8
T1 T2
A
t

Read A
A
t=100
Read A
A
t =120
A = A+1
A = A+1
Write A
A
t =120
Write A
A
t>
1T
t nên T1 phải rollback và
bắt đầu lại với timestamp mới

Ø Ví dụ 2: 0,120,100
21
===
ATT
ttt , Trong trường hợp này, rõ ràng không xảy ra đụng độ,
T1 không cần phải rollback và bắt đầu lại với timestamp mới. Tuy nhiên, thuật toán sắp
xếp toàn phần không phân biệt tính chất của thao tác dữ liệu là read hay write nên T1
vẫn bò rollback và phải bắt đầu lại.
T1 T2
A
t
Read A

A
t=100
Read A
A
t =120
Read A
A
t =120
Read A
A
t>
1T
t nên T1 phải rollback và
bắt đầu lại với timestamp mới
Ø Ví dụ 3:
T1 T2 T3
A
t
B
t
C
t
1T
t =200
2T
t =150
3T
t =175 0 0 0
Read A 150
Read C 175

Read B 200
Write B 200
Write A 200
Write C T
2
rollback


Write A T
3
rollback


v Như vậy:Thuật toán sắp xếp toàn phần: không quan tâm đến tính chất của thao tác dữ liệu
(Read/Write) nên chỉ có 1 nhãn thời gian duy nhất cho 1 đơn vò dữ liệu. Nếu quan tâm đến tính
chất của thao tác dữ liệu thì cần 2 nhãn thời gian cho 1 đơn vò dữ liệu tương ứng với thao tác đọc
và ghi trên đơn vò dữ liệu đó.
3. Thuật toán sắp xếp từng phần
- Mỗi đơn vò dữ liệu A có 2 nhãn thời gian RTS và WTS. Ban đầu, RTS (A)= WTS(A) = 0
- RTS(A) chính là nhãn thời gian của giao tác có timestamp lớn nhất truy cập (read) thành
công lên A.
- WTS(A) chính là nhãn thời gian của giao tác có timestamp lớn nhất truy cập (write) thành
công lên A.
Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 9
Procedure Read (
i
T, A)
Begin
If WTS (A) <= t

Ti
then
- Thực hiện thao tác đọc g
- RTS(A) :=
(
)
Ti
tARTSMax ),(
Else
Rollback
i
T và bắt đầu lại với nhãn thời gian mới
End Proc

Procedure Write (
i
T,
g
)
Begin
If (RTS(A) <= t
Ti
) and ( WTS(A) <= t
Ti
) then
- Thực hiện thao tác ghi g
- WTS(A) := t
Ti

Else

Rollback
i
T và bắt đầu lại với nhãn thời gian mới
End Proc
Ø Ví dụ:
T1 (
1T
t =100) T2 (
2T
t =100)
A
t
B
t
Read A
A
t = 100

Read A
A
t = 120

A = A+1
A = A+1
Write A
A
t = 120
Write A T
1
rollback


v Nhận xét: Trong thuật toán sắp xếp từng phần, số lượng giao tác bò rollback ít hơn trong
thuật toán sắp xếp toàn phần (do nếu 2 giao tác chỉ thực hiện thao tác “Đọc” thì không gây
ra đụng độ)
T1 T2 Nhận xét
(1) Read A
(2) Read A
(3) Read A
Thuật toán sắp xếp toàn phần: T1 bò rollback ở (3)
Thuật toán sắp xếp từng phần: không có rollback

T1 T2 Nhận xét
(1) Read A
(2) Write A
(3) Read A
Thuật toán sắp xếp toàn phần: T1 bò rollback ở (3)
Thuật toán sắp xếp từng phần: T1 bò rollback ở (3)


Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 10
VI. Điều khiển tương tranh bằng cơ chế khóa (lock):
1. Khái niệm khóa:
- Để thấy được nhu cầu phải sử dụng khóa khi các giao tác thực hiện song song, ta xét ví dụ
sau:
Xét 2 giao tác T
1
và T
2
. Mỗi giao tác truy xuất 1 đơn vò dữ liệu A được giả sử là mang giá trò

số nguyên, rồi cộng thêm 1 vào A. Hai giao tác này là các thực hiện của chương trình P dưới
đây:
P: Read (A)
A= A+1
Write (A)
Giá trò của A tồn tại trong CSDL, P đọc A vào vùng làm việc của nó, cộng 1 vào giá trò này
tại đó rồi ghi kết quả vào trong CSDL. Trong hình sau, chúng ta thấy 2 giao tác đang thực hiện
theo kiểu xen kẽ, và chúng ta ghi nhận giá trò của A trong CSDL tại mỗi bước:
A trong CSDL
5 5 5 5 6 6
T
1

Read (A) A=A+1 Write (A)
T
2

Read (A) A=A+1 Write (A)
A trong vùng làm
việc T
1

5 5 6 6 6 6
A trong vùng làm
việc T
2

5 5 6 6
Chúng ta nhận ra rằng mặc dù hai giao tác đều đã cộng thêm 1 vào A, giá trò của A chỉ tăng
1. Vấn đề sẽ nghiêm trọng nếu A biểu thò số ghế đã bán của một chuyến bay.

- Phương pháp thông dụng nhất để điều khiển việc truy xuất các đơn vò dữ liệu là sử dụng
khóa (lock). Bộ quản lý khóa (Lock manager) là thành phần của DBMS chòu trách nhiệm theo
dõi xem một đơn vò dữ liệu hiện có giao tác T nào đang đọc hay ghi vào các phần của A hay
không. Nếu có thì bộ quản lý khóa sẽ ngăn cản không cho các giao tác khác truy xuất A trong
trường hợp truy xuất (đọc hay ghi) có thể gây ra xung đột.
- Như vậy: Lock là 1 đặc quyền truy xuất (access priveleg) lên các đơn vò dữ liệu của các giao
tác mà bộ quản lý khóa có thể trao cho một giao tác hay thu hồi lại. Khi 1 giao tác đã khoá
(lock) trên 1 đơn vò dữ liệu nào đó thì các giao tác khác không được phép truy cập đến đơn vò dữ
liệu đó cho đến khi nó nhả khóa (unlock).
- Khi 1 giao tác T thực hiện được việc lock đơn vò dữ liệu A, ta nói, T đang giữ lock A.
- Thông thường, tại mỗi thời điểm, chỉ có 1 tập con các đơn vò dữ liệu bò khóa, vì vậy bộ quản
lý khóa có thể lưu các khoá hiện hành trong một bảng khóa (lock table) với các mẫu tin có dạng
sau: (A, L, T) (giao tác T có một khóa kiểu L trên đơn vò dữ liệu A)
2. Kỹ thuật khóa đơn giản:
a. Giới thiệu:
- Một giao tác khi có yêu cầu truy xuất đến đơn vò dữ liệu thì phải phát ra yêu cầu xin khóa
(lock) trên đơn vò dữ liệu đó, nếu yêu cầu này được chấp thuận thì được quyền thao tác, và như
vậy các giao tác khác sẽ không được phép truy cập đến đơn vò dữ liệu đó cho đến khi giao tác
giữ khóa được unlock.
Ø Ví dụ: Xét lại ví dụ trên được viết với các khóa như sau:
Ng Duc Thuan
CSDLPT-Điều khiển tương tranh 11
P: Lock (A)
Read (A)
A= A+1
Write (A)
Unlock (A)
Nếu T
1
bắt đầu trước, nó yêu cầu khóa trên A. Giả sử rằng không có giao tác nào đang khóa

A, bộ quản lý khóa sẽ cho nó khóa này. Bây giờ chỉ có T
1
mới có thể truy xuất A. Nếu T
2
bắt
đầu trước khi T
1
chấm dứt thì T
2
thực hiện lệnh Lock (A), hệ thống buộc T
2
phải đợi. Chỉ khi T
1

thực hiện lệnh unlock(A), hệ thống mới cho phép T
2
tiến hành. Kết quả là, T
1
hoặc T
2
sẽ hoàn
tất trước khi giao tác kia bắt đầu, và tác dụng là cộng 2 vào A.

T1 T2 Nhận xét
Lock A
Read (A)
Lock (A) T
2
không thực hiện được lệnh Lock (A) vì T
1

đang giữ
lock => T
2
phải chờ T
1
unlock
Read (A)
A=A+1
A=A+1
Write (A)
Write (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 T
1
, T
2
, …, T
n
. 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 Thuan
CSDLPT-Ñieàu khieå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í duï 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 Thuan
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 (T
2
® T
3

® T
1
® T
4
)
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 Thuan
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 T

1
, T
2
, …, T
n
(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 T
1

giải phóng khóa trên A, khóa này được trao lại cho T
2
. Điều gì sẽ xảy ra nếu như trong khi T
2

đang đợi nhận khóa, một giao tác T
3
khác cũng xin một khóa trên A, và T
3
lại được trao khóa

này trước T
2
. Rồi sau khi T
3
được trao khóa trên A thì lại có 1 giao tác T
4
xin khóa trên A, v…v…
Và rất có thể T
2
phải đợi mãi và chẳ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 T
2
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 Thuan
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 Transactionthựchiệntheo protocol
Yêucầu lock
Chophép hay
từchối lock
Chophéptruyxuất,chờ

hay rollbackgiaotác
Yêucầ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 Thuan
CSDLPT-Điều khiển tương tranh 16
6. Nghi thức lock 2 giai đoạn (2 phase):
phase lockphase unlock
BOTEOT
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, T
1
và T
3
là các giao tác 2 pha, còn T
2
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 T
1
, T
2
, …, T
n
. Giả sử dồ thò có chu trình:
T1
T2 T3 Ti Tn


- T
1
thực hiện trước T
2
: T

2
thực hiện lock trên 1 số đvdl nào đó được unlock bởi T
1

- T
2
thực hiện trước T
3
: T
3
thực hiện lock trên 1 số đvdl nào đó được unlock bởi T
2

- …
- Tương tự, T
1
thực hiện lock trên 1 số đvdl nào đó được unlock bởi T
n

=> T
1
có dạng Lock … … Unlock … …Lock…
=> T
1
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 Thuan
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