HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
Giao dịch T
4
tương ứng với T
2
với tháo chốt bị làm trễ được xác định như sau:
T
4
: Lock-S(A);
Read(A);
Lock-S(B);
Read(B);
Display(A+B);
Unlock(A);
Unlock(B);
figure V- 6
Các lịch trình có thể trên T
3
và T
4
không để cho T
4
hiển thị trạng thái không nhất quán.
Tuy nhiên, sử dụng chốt có thể dẫn đến một tình huống không mong đợi. Ta hãy xét lịch
trình bộ phận schedule-2 trên T
3
và T
4
sau:
T
3
T
4
Lock-X(B)
Read(B)
B:=B-50
Write(B)
Lock-S(A)
Read(A)
Lock-S(B)
Lock-X(A)
Schedule-2
figure V- 7
Do T
3
giữ một chốt phương thức Exclusive trên B, nên yêu cầu một chốt phương thức
shared của T
4
trên B phải chờ đến khi T
3
tháo chốt. Cũng vậy, T
3
yêu cầu một chốt Exclusive trên
A trong khi T
4
đang giữ một chốt shared trên nó và như vậy phải chờ. Ta gặp phải tình huống
trong đó T
3
chờ đợi T
4
đồng thời T
4
chờ đợi T
3
một sự chờ đợi vòng tròn và như vậy không
giao dịch nào có thể tiến triển. Tình huống này được gọi là deadlock (khoá chết). Khi tình huống
khoá chết xảy ra hệ thống buộc phải cuộn lại một trong các giao dịch. Mỗi khi một giao dịch bị
cuộn lại, các hạng mục dữ liệu bị chốt bởi giao dịch phải được tháo chốt và nó trở nên sẵn có cho
giao dịch khác, như vậy các giao dịch này có thể tiếp tục được sự thực hiện của nó.
Nếu ta không sử dụng chốt hoặc tháo chốt hạng mục dữ liệu ngay khi có thể sau đọc hoặc
viết hạng mục, ta có thể rơi vào trạng thái không nhất quán. Mặt khác, nếu ta không tháo chốt một
hạng mục dữ liệu trước khi yêu cầu một chốt trên một hạng mục khác, dealock có thể xảy ra. Có
các phương pháp tránh dealock trong một số tình huống, tuy nhiên nói chung dealock là khó tránh
khi sử dụng chốt nếu ta muốn tránh trạng thái không nhất quán. Dealock được ưa thích hơn trạng
thái không nhất quán vì chúng có thể điều khiển được bằng cách cuộn lại các giao dịch trong khi
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
99
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
đó trạng thái không nhất quán có thể dẫn đến các vấn đề thực tế mà hệ CSDL không thể điều
khiển.
Ta sẽ yêu cầu mỗi giao dịch trong hệ thống tuân theo một tập các quy tắc , được gọi là
giao thức chốt (locking protocol), chỉ định khi một giao dịch có thể chốt và tháo chốt mỗi một
trong các hạng mục dự liệu. Giao thức chốt hạn chế số các lịch trình có thể. Tập các lịch trình như
vậy là một tập con thực sự của tập tất cả các lịch trình khả tuần tự có thể.
Xét { T
0
, T
1
, , T
n
} một tập các giao dịch tham gia vào lịch trình S. Ta nói T
i
đi trước T
j
trong S, và được viết là T
i
→ T
j
, nếu tồn tại một hạng mục dữ liệu Q sao cho T
i
giữ chốt phương
thức A trên Q , T
j
giữ chốt phương thức B trên Q muộn hơn và comp(A,B) = false. Nếu T
i
→ T
j
,
thì T
i
sẽ xuất hiện trước T
j
trong bất kỳ lịch trình tuần tự nào.
Ta nói một lịch trình S là hợp lệ dưới một giao thức chốt nếu S là một lịch trình tuân thủ
các quy tắc của giao thức chốt đó. Ta nói rằng một giao thức chốt đảm bảo tính khả tuần tự xung
đột nếu và chỉ nếu đối với tất cả các lịch trình hợp lệ, quan hệ → kết hợp là phi chu trình.
V.1.2. CẤP CHỐT
Khi một giao dịch yêu cầu một chốt trên một hạng mục dữ liệu ở một phương thức và
không có một giao dịch nào khác giữ một chốt trên cùng hạng mục này ở một phương thức xung
đột, chốt có thể được cấp. Tuy nhiên, phải thận trọng để tránh kịch bản sau: giả sử T
2
giữ một
chốt phương thức shared trên một hạng mục dữ liệu, một giao dịch khác T
1
yêu cầu một chốt
phương thức exclusive cũng trên hạng mục này, rõ ràng T
1
phải chờ T
2
tháo chốt. Trong khi đó
một giao dịch khác T
3
yêu cầu một chốt phương thức shared, do yêu cầu chốt này tương thích với
phương thức chốt được giữ bởi T
1
nên nó được cấp cho T
3
. Tại thời điểm T
2
tháo chốt, T
1
vẫn
phải chờ sự tháo chốt của T
3,
nhưng bây
giờ lại có một giao dịch T
4
yêu cầu một chốt phương thức
shared và nó lại được cấp do tính tương thích và cứ như vậy, có thể T
1
sẽ không bao giờ được cấp
chốt mà nó yêu cầu trên hạng mục dữ liệu. Ta gọi hiện tượng này là bị chết đói (starved).
Để tránh sự chết đói của các giao dịch, việc cấp chốt được tiến hành như sau: Khi một
giao dịch T
i
yêu cầu một chốt trên một hạng mục dữ liệu Q ở phương thức M, chốt sẽ được cấp
nếu các điều kiện sau được thoả mãn:
1. Không có giao dịch khác đang giữ một chốt trên Q ở phương thức xung đột với M
2. Không có một giao dịch nào đang chờ được cấp một chốt trên M và đã đưa ra yêu
cầu về chốt trước T
i
V.1.3. GIAO THỨC CHỐT HAI KỲ (Two-phase locking protocol)
Giao thức chốt hai kỳ là một giao thức đảm bảo tính khả tuần tự. Giao thức này yêu cầu
mỗi một giao dịch phát ra yêu cầu chốt và tháo chốt thành hai kỳ:
1. Kỳ xin chốt (Growing phase). Một giao dịch có thể nhận được các chốt, nhưng có
không thể tháo bất kỳ chốt nào
2. Kỳ tháo chốt (Shrinking phase). Một giao dịch có thể tháo các chốt nhưng không
thể nhận được một chốt mới nào.
Khởi đầu, một giao dịch ở kỳ xin chốt. Giao dịch tậu được nhiều chốt như cần thiết. Mỗi
khi giao dịch tháo một chốt, nó đi vào kỳ tháo chốt và nó không thể phát ra bất kỳ một yêu cầu
chốt nào nữa. Các giao dich T
3
và T
4
là hai kỳ. Các giao dịch T
1
và T
2
không là hai kỳ. Người ta
có thể chứng minh được giao thức chốt hai kỳ đảm bảo tính khả tuần tự xung đột, nhưng không
đảm bảo tránh được dealock và việc cuộn lại hàng loạt. Cuộn lại hàng loạt có thể tránh được bởi
một sự sửa đổi chốt hai kỳ được gọi là giao thức chốt hai kỳ nghiêm ngặt. Chốt hai kỳ nghiêm
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
100
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
ngặt đòi hỏi thêm tất cả các chốt phương thức exclusive phải được giữ đến tận khi giao dịch bàn
giao. Yêu cầu này đảm bảo rằng bất kỳ dữ liệu nào được viết bởi một giao dịch chưa bàn giao bị
chốt trong phương thức exclusive đến tận khi giao dịch bàn giao, điều đó ngăn ngừa bất kỳ giao
dịch khác đọc dữ liệu này.
Một biến thể khác của chốt hai kỳ là giao thức chốt hai kỳ nghiêm khắc. Nó đòi hỏi tất cả
các chốt được giữ đến tận khi giao dịch bàn giao. Hầu hết các hệ CSDL thực hiện chốt hai kỳ
nghiêm ngặt hoặc nghiêm khắc.
Một sự tinh chế giao thức chốt hai kỳ cơ sở dựa trên việc cho phép chuyển đổi chốt: nâng
cấp một chốt shared sang exclusive và hạ cấp một chốt exclusive thành chốt shared. Chuyển đổi
chốt không thể cho phép một cách tuỳ tiện, nâng cấp chỉ được phép diễn ra trong kỳ xin chốt, còn
hạ cấp chỉ được diễn ra trong kỳ tháo chốt. Một giao dịch thử nâng cấp một chốt trên một hạng
mục dữ liệu Q có thể phải chờ. Giao thức chốt hai kỳ với chuyển đổi chốt cho phép chỉ sinh ra các
lịch trình khả tuần tự xung đột. Nếu các chốt exclusive được giữ đến tận khi bàn giao, các lịch
trình sẽ là cascadeless.
Ta xét một ví dụ: Các giao dịch T
8
và T
9
được nêu trong ví dụ chỉ được trình bày bởi các
hoạt động ý nghĩa là Read và Write.
T
8
: Read(A
1
);
Read(A
2
);
Read(A
n
);
Write(A
1
).
T
9
: Read(A
1
);
Read(A
2
);
Display(A
1
+ A
2
).
figure V- 8
Nếu ta sử dụng giao thức chốt hai kỳ, khi đó T
8
phải chốt A
1
ở phương thức exclusive. Bởi
vậy, sự thực hiện cạnh tranh của hai giao dịch rút cuộc trở thành thực hiện tuần tự. Ta thấy rằng
T
8
cần một chốt exclusive trên A
1
chỉ ở cuối sự thực hiện của nó, khi nó write(A
1
). Như vậy, T
8
có thể khởi động chốt A
1
ở phương thức shared, và đổi chốt này sang phương thức exclusive sau
này. Như vậy ta có thể nhận được tính cạnh tranh cao hơn, vì như vậy T
8
và T
9
có thể truy xuất
đến A
1
và A
2
đồng thời.
Ta biểu thị sự chuyển đổi từ phương thức shared sang phương thức exclusive bởi upgrade
và từ phương thức exclusive sang phương thức shared bởi downgrade. Upgrade chỉ được phép
xảy ra trong kỳ xin chốt và downgrade chỉ được phép xảy ra trong kỳ tháo chốt. Lịch trình chưa
hoàn tất dưới đây cho ta một minh hoạ về giao thức chốt hai kỳ với chuyển đổi chốt.
Chú ý rằng một giao dịch thử cập nhật một chốt trên một hạng mục dữ liệu Q có thể buộc
phải chờ. Việc chờ bắt buộc này xảy ra khi Q đang bị chốt bởi giao dịch khác ở phương thức
shared.
Giao thức chốt hai kỳ với chuyển đổi chốt chỉ sinh ra các lịch trình khả tuần tự xung đột,
các giao dịch có thể được tuần tự hoá bởi các điểm chốt của chúng. Hơn nữa, nếu các chốt
exclusive được giữ đến tận khi kết thúc giao dịch, lịch trình sẽ là cascadeless.
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
101
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
T
8
T
9
Lock-S(A
1
)
Lock-S(A
2
)
Lock-S(A
2
)
Lock-S(A
2
)
Lock-S(A
3
)
…
Unlock(A
1
)
Unlock(A
2
)
UpGrade(A
1
)
figure V- 9
Ta mô tả một sơ đồ đơn giản nhưng dược sử dụng rộng rãi để sinh tự động các chỉ thị chốt
và tháo chốt thích hợp cho một giao dịch: Mỗi khi giao dich T xuất ra một chỉ thị Read(Q), hệ
thống sẽ xuất ra một chỉ thị Lock-S(Q) ngay trước chỉ thị Read(Q). Mỗi khi giao dịch T xuất ra
một hoạt động Write(Q), hệ thống sẽ kiểm tra xem T đã giữ một chốt shared nào trên Q hay
chưa, nếu đã, nó xuất ra một chỉ thị Upgrade(Q) ngay trước chỉ thị Write(Q), nếu chưa, nó
xuất ra chỉ thị Lock-X(Q) ngay trước Write(Q). Tất cả các chốt giao dịch nhận được sẽ được
tháo chốt sau khi giao dịch bàn giao hay bỏ dở.
V.1.4. GIAO THỨC DỰA TRÊN ĐỒ THỊ (Graph-Based Protocol)
Ta đã biết, trong trường hợp thiếu vắng các thông tin liên quan đến cách thức các hạng
mục dữ liệu được truy xuất, giao thức chốt hai kỳ là cần và đủ để đảm bảo tính khả tuần tự. Nếu ta
muốn phát triển các giao thức không là hai kỳ, ta cần các thông tin bổ xung trên cách thức mỗi
giao dịch truy xuất CSDL. Có nhiều mô hình khác nhau về lượng thông tin được cung cấp. Mô
hình đơn giản nhất đòi hỏi ta phải biết trước thứ tự trong đó các hạng mục dữ liệu sẽ được truy
xuất. Với các thông tin như vậy, có thể xây dựng các giao thức chốt không là hai kỳ nhưng vẫn
đảm bảo tính khả tuần tự xung đột.
Để có được hiểu biết trước như vậy, ta áp đặt một thứ tự bộ phận, ký hiệu →, trên tập tất
cả các hạng mục dữ liệu D ={ d
1
, d
2
, , d
n
}. Nếu d
i
→ d
j
, bất kỳ giao dịch nào truy xuất cả d
i
và
d
j
phải truy xuất d
i
trước khi truy xuất d
j
. Thứ tự bộ phận này cho phép xem D như một đồ thị
định hướng phi chu trình, được gọi là đồ thị CSDL (DataBase Graph). Trong phần này, để đơn
giản, ta hạn chế chỉ xét các đồ thị là các cây và ta sẽ đưa ra một giao thức đơn giản, được gọi là
giao thức cây (tree protocol), giao thức này hạn chế chỉ dùng các chốt exclusive.
Trong giao thức cây, chỉ cho phép chỉ thị chốt Lock-X, mỗi giao dịch T có thể chốt một
hạng mục dữ liệu nhiều nhất một lần và phải tuân theo các quy tắc sau:
1. Chốt đầu tiên bởi T có thể trên bất kỳ hạng mục dữ liệu nào
2. Sau đó, một hạng mục dữ liệu Q có thể bị chốt bởi T chỉ nếu cha của Q hiện đang
bị chốt bởi T
3. Các hạng mục dữ liệu có thể được tháo chốt bất kỳ lúc nào
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
102
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
4. Một hạng mục dữ liệu đã bị chốt và được tháo chốt bởi T, không thể bị T chốt lại
lần nữa.
Các lịch trình hợp lệ trong giao thức cây là khả tuần tự xung đột.
Ví dụ: Cây CSDL là:
A
B C
F
D E
G H I
J
figure V- 10
Chỉ các chỉ thị chốt và tháo chốt của các giao dịch được trình bày:
T
10
: Lock-X(B); Lock-X(E); Lock-X(D); Unlock(B); Unlock(E); Lock-X(G);
Unlock(D); Unlock(G).
T
11
: Lock-X(D); Lock-X(H); Unlock(D); Unlock(H).
T
12
: Lock-X(B); Lock-X(E); Unlock(B); Unlock(E).
T
13
: Lock-X(D); Lock-X(H); Unlock(D); Unlock(H).
figure V- 11
Một lịch trình tuân theo giao thức cây chứa tất cả bốn giao dịch trên được cho trong hình
bên dưới. Ta nhận thấy, các lịch trình tuân thủ giao thức cây không chỉ là khả tuần tự xung đột mà
còn đảm bảo không có dealock. Giao thức cây có mặt thuận lợi so với giao thức hai kỳ là tháo
chốt có thể xảy ra sớm hơn. Việc tháo chốt sớm có thể dẫn đến rút ngắn thời gian chờ đợi và tăng
tính cạnh tranh. Hơn nữa, do giao thức là không dealock, nên không có cuộn lại. Tuy nhiên giao
thức cây có điểm bất lợi là, trong một vài trường hợp, một giao dịch có thể phải chốt những hạng
mục dữ liệu mà nó không truy xuất. Chẳng hạn, một giao dịch cần truy xuất các hạng mục dữ liệu
A và J trong đồ thị CSDL trên, phải chốt không chỉ A và J mà phải chốt cả các hạng mục B, D, H.
Việc chốt bổ xung này có thể gây ra việc tăng tổng phí chốt, tăng thời gian chờ đợi và giảm tính
cạnh tranh. Hơn nữa, nếu không biết trước các hạng mục dữ liệu nào sẽ cần thiết phải chốt, các
giao dịch sẽ phải chốt gốc của cây mà điều này làm giảm mạnh tính cạnh tranh.
Đối với một tập các giao dịch, có thể có các lịch trình khả tuần tự xung đột không thể nhận
được từ việc tuân theo giao thức cây. Có các lịch trình được sinh ra bởi tuân theo giao thức chốt
hai kỳ nhưng không thể được sinh ra bởi tuân theo giao thức cây và ngược lại.
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
103
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
T
10
T
11
T
12
T
13
Lock-X(B)
Lock-X(D)
Lock-X(H)
Unlock(D)
Lock-X(E)
Lock-X(D)
Unlock(B)
Unlock(E)
Lock-X(B)
Lock-X(E)
Unlock(H)
Lock-X(G)
Unlock(D)
Lock-X(D)
Lock-X(H)
Unlock(D)
Unlock(H)
Unlock(E)
Unlock(B)
Unlock(G)
Lịch trình khả tuần tự dưới giao thức cây
figure V- 12
V.1.5. ĐA HẠT (Multiple Granularity)
Trong các sơ đồ điều khiển cạnh tranh được mô tả trước đây, ta đã sử dụng hạng mục dữ
liệu như đơn vị trên nó sự đồng bộ hoá được thực hiện. Tuy nhiên, có các hoàn cảnh trong đó việc
nhóm một vài hạng mục dữ liệu và xử lý chúng như một đơn vị đồng bộ hoá mang lại nhiều lợi
ích. Nừu một giao dich T
i
phải truy xuất toàn bộ CSDL và giao thức chốt được sử dụng, khi đó T
i
phải chốt mỗi hạng mục dữ liệu trong CSDL. Như vậy việc thực hiện các chốt này sẽ tiêu tốn một
thời gian đáng kể. Sẽ hiệu quả hơn nếu T
i
chỉ cần một yêu cầu chốt để chốt toàn bộ CSDL. Mặt
khác, nếu T
i
cần truy xuất chỉ một vài hạng mục dữ liệu, nó không cần thiết phải chốt toàn bộ
CSDL vì như vậy sẽ giảm tính cạnh tranh. Như vậy, cái mà ta cần là một cơ chế cho phép hệ
thống xác định nhiều mức hạt. Một cơ chế như vậy là cho phép các hạng mục dữ liệu có kích cỡ
khác nhau và xác định một sự phân cấp các hạt dữ liệu, trong đó các hạt nhỏ được ẩn náu bên
trong các hạt lớn. Sự phân cấp như vậy có thể được biểu diễn đồ thị như một cây. Một nút không
là lá của cây đa hạt biểu diễn dữ liệu được kết hợp với con cháu của nó. Như một ví dụ minh hoạ,
ta xét cây sau:
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
104
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
DB
A
1
A
2
F
a
F
b
F
c
F
d
R
a1
R
a2
R
an
R
b1
R
bk
R
c1
R
c2
R
cm
R
d1
… R
dq
Phân cấp hạt
figure V- 13
Nó gồm bốn mức nút. Mức cao nhất là toàn bộ CSDL. Thấp hơn là các nút kiểu vùng:
CSDL bao gồm các vùng này. Mỗi vùng lại có các nút kiểu file như các con của nó, mỗi vùng
chứa đúng các file này và không file nào nằm trong nhiều hơn một vùng. Cuối cùng, mỗi file có
các nút con kiểu mẩu tin, không mẩu tin nào hiện diện trong hơn một file.
Mỗi nút trong cây có thể được chốt một các cá nhân. Như đã làm trong giao thức chốt hai
kỳ, ta sẽ sử dụng các phương thức chốt shared và exclusive . Khi một giao dịch chốt một nút,
trong phương thức shared hoặc exclusive, giao dịch cũng chốt tất cả các nút con cháu của nút này
ở cùng phương thức. Ví dụ T
i
chốt tường minh file F
b
ở phương thức exclusive, nó đã chốt ẩn tất
cả các mẩu tin của F
b
cũng trong phương thức exclusive.
Giả sử giao dịch T
j
muốn chốt mẩu tin R
b6
của file F
b
. vì giao địch T
i
đã chốt tường minh
file F
b
, mẩu tin R
b6
cũng bị chốt ẩn. Song làm thế nào để hệ thống biết được T
j
có thể chốt R
b6
hay
không: T
j
phải duyệt cây từ gốc đến mẩu tin R
b6
, nếu có một nút bất kỳ tren đường dẫn bị chốt ở
phương thức không tương thích, T
j
phải chờ. Bây giờ, nếu T
k
muốn chốt toàn bộ CSDL, nó phải
chốt nút gốc. Tuy nhiên, do T
i
hiện đang giữ một chốt trên F
b
, một bộ phận của cây, nên T
k
sẽ
không thành công. Vậy làm thế nào để hệ có thể chốt được nút gốc: Một khả năng là tìm kiếm
trên toàn bộ cây, giải pháp này phá huỷ hoàn toàn sơ đồ mục đích của sơ đồ chốt đa hạt. Một giải
pháp hiệu quả hơn là đưa vào một lớp mới các phương thức chốt, được gọi là phương thức chốt
tăng cường (intension lock mode). Nếu một nút bị chốt ở phương thức tăng cường, chốt tường
minh được tiến hành ở mức thấp hơn của cây (hạt min hơn). Chốt tăng cường được được đặt trên
tất cả các tổ tiên của một nút trước khi nút đó được chốt tường minh. Như vậy một giao dịch
không cần thiết phải tìm kiếm toàn bộ cây để xác định nó có thể chốt một nút thành công hay
không. Một giao dịch muốn chốt một nút, chẳng hạn Q, phải duyệt một đường dẫn từ gốc đến Q,
trong khi duyệt cây, giao dịch chốt các nút trên đường đi ở phương thức tăng cường.
Có một phương thức tăng cường kết hợp với phương thức shared và một với phương thức
exclusive. Nếu một nút bị chốt ở phương thức tăng cường shared (IS), chốt tường minh được tiến
hành ở mức thấp hơn trong cây, nhưng chỉ là một các chốt phương thức shared. Tương tự, nếu
một nút bị chốt ở phương thức tăng cường exclusive (IX), chốt tường minh được tiến hành ở mức
thấp hơn với các chốt exclusive hoặc shared. Nếu một nút bị chốt ở phương thức shared và
phương thức tăng cường exclusive (SIX), cây con có gốc là nút này bị chốt tường minh ở phương
thức shared và chốt tường minh được tiến hành ở mức thấp hơn với các chốt exclusive. Hàm tính
tương thích đối với các phương thức chốt này được cho bởi ma trận:
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
105
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
IS IX S SIX X
IS True True True True False
IX True True False False False
S True False True False False
SIX True False False False False
X False False False False False
figure V- 14
Giao thức chốt đa hạt dưới đây đảm bảo tính khả tuần tự. Mỗi giao địch T có thể chốt một
nút Q theo các quy tắc sau:
1. Hàm tương thích chốt phải được kiểm chứng
2. Gốc của cây phải được chốt đầu tiên, và có thể được chốt ở bất kỳ phương thức nào
3. Một nút Q có thể được chốt bởi T ở phương thức S hoặc IS chỉ nếu cha của Q hiện
đang bị chốt bởi T ở hoặc phương thức IX hoặc phương thức IS.
4. Một nút Q có thể được chốt bởi T ở phương thức X, SIX hoặc IX chỉ nếu cha của Q
hiện đang bị chốt ở hoặc phương thức IX hoặc phương thức SIX
5. T có thể chốt một nút chỉ nếu trước đó nó chưa tháo chốt một nút nào.
6. T có thể tháo chốt một nút Q chỉ nếu không con nào của Q hiện đang bị chốt bởi T
Ta thấy rằng giao thức đa hạt yêu cầu các chốt được tậu theo thứ tự Top-Down, được
tháo theo thứ tự Bottom-Up.
Ví dụ: Xét cây phân cấp hạt như trên và các giao dịch sau:
○ Giả sử giao dịch T
18
đọc mẩu tin R
a2
của file F
a
. Khi đó T
18
cần phải chốt DB, vùng A
1
và F
a
ở phương thức IS và R
a2
ở phương thức S: Lock-IS(DB); Lock-IS(A
1
);
Lock-IS(F
a
); lock-S(R
a2
)
○ Giả sử giao dịch T
19
sửa đổi mẩu tin R
a9
trong file F
a
, khi đó T
19
cần phải chốt CSDL,
vùng A
1
và file F
a
ở phương thức IX và R
a9
ở phương thức X: Lock-IX(DB);
Lock-IX(A
1
); lock-IX(F
a
); lock-X(R
a9
)
○ Giả sử giao dịch T
20
đọc tất cả các mẩu tin của file F
a
, khi đó T
20
cần phải chốt CSDL,
và vùng A
1
ở phương thức IS và chốt F
a
ở phương thức S: Lock-IS(DB); Lock-
IS(A
1
); Lock-S(F
a
)
○ Giả sử giao dịch T
21
đọc toàn bộ CSDL, nó có thể làm điều đó sau khi chốt CSDL ở
phương thức S: Lock-S(DB)
Chú ý rằng T
18
, T
20
và T
21
có thể truy xuất đồng thời CSDL, giao dịch T
19
có thể thực hiện
cạnh tranh với T
18
nhưng không với T
20
hoặc T
21
V.2. GIAO THỨC DỰA TRÊN TEM THỜI GIAN (Timestamp-
based protocol)
V.2.1. TEM THỜI GIAN (Timestamp)
Ta kết hợp với mỗi giao dịch T
i
trong hệ thống một tem thời gian cố định duy nhất, được
biểu thị bởi TS(T
i
). Tem thời gian này được gán bởi hệ CSDL trước khi giao dịch T
i
bắt đầu thực
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
106
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
hiện. Nếu một giao dịch T
i
đã được gán tem thời gian TS(T
i
) và một giao dịch mới T
j
đi vào hệ
thống, khi đó TS(T
i
) < TS(T
j
). Có hai phương pháp đơn giản để thực hiện sơ đồ này:
1. Sử dụng giá trị của đồng hồ hệ thống như tem thời gian: Một tem thời gian của một
giao dịch bằng giá trị của đồng hồ khi giao dịch đi vào hệ thống.
2. Sử dụng bộ đếm logic: bộ đếm được tăng lên mỗi khi một tem thời gian đã được
gán, tem thời gian của một giao dịch bằng với giá trị của bộ đếm khi giao dich đi
vào hệ thống.
Tem thời gian của các giao dịch xác định thứ tự khả tuần tự. Như vậy, nếu TS(T
i
) < TS(T
j
),
hệ thống phải đảm bảo rằng lịch trình được sinh ra là tương đương với một lịch trình tuần tự
trong đó T
i
xuất hiện trước T
j
.
Để thực hiện sơ đồ này, ta kết hợp với mỗi hạng mục dữ liệu Q hai giá trị tem thời gian:
• W-timestamp(Q) biểu thị tem thời gian lớn nhất của giao dịch bất kỳ đã thực hiện
Write(Q) thành công
• R-timestamp(Q) biểu thị tem thời gian lớn nhất của giao dịch bất kỳ đã thực hiện
Read(Q) thành công
Các tem thời gian này được cập nhật mỗi khi một Write hoặc một Read mới được thực
hiện.
V.2.2. GIAO THỨC THỨ TỰ TEM THỜI GIAN (Timestamp-Ordering
Protocol)
Giao thức thứ tự tem thời gian đảm bảo rằng các Write và Read xung đột bất kỳ được
thực hiện theo thứ tự tem thời gian. Giao thức này hoạt động như sau:
1. Giả sử giao dịch T
i
phát ra Read(Q).
a. Nếu TS(T
i
) < W-Timestamp(Q), T
i
cần đọc một giá trị của Q đã được viết
rồi. Do đó, hoạt động Read bị vứt bỏ và T
i
bị cuộn lại.
b. Nếu TS(T
i
) ≥ W-Timestamp(Q), hoạt động Read được thực hiện và
R-Timestamp được đặt bằng giá trị lớn nhất trong hai giá trị R-Timestamp
và TS(T
i
).
2. Giả sử giao dịch T
i
phát ra Write(Q).
a. Nếu TS(T
i
) < R-Timestamp(Q), Giá trị của Q mà T
i
đang sinh ra được giả
thiết là để được dùng cho các giao dịch đi sau nó (theo trình tự thời gian),
nhưng nay không cần đến nũa. Do vậy, hoạt động Write này bị vứt bỏ và
T
i
bị cuộn lại
b. Nếu TS(T
i
) < W-Timestamp(Q), T
i
đang thử viết một giá trị đã quá hạn
của Q, Từ đó, hoạt động Write bị vứt bỏ và T
i
bị cuộn lại
c. Ngoài ra, hoạt động Write được thực hiện và W-Timestamp(Q) được đặt là
TS(T
i
)
Một giao dịch T
i
bị cuộn lại bởi sơ đồ điều khiển cạnh tranh như kết quả của hoạt động
Read hoặc Write đang được phát ra, được gán với một tem thời gian mới và được tái khởi động
lại (được xem như một giao dịch mới tham gia vào hệ thống)
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
107
HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU
Ta xét các giao dịch T
14
và T
15
được xác định như dưới đây:
T
14
: Read(B);
Read(A);
Display(A+B);.
T
15
: Read(B);
B:=B-50;
Write(B);
Read(A);
A:=A+50;
Write(A);
Display(A+B).
figure V- 15
Ta giả thiết rằng một giao dịch được gán cho một tem thời gian ngay trước chỉ thị đầu tiên
của nó. Như vậy, lịch trình schedule-3 dưới đây có TS(T
14
) < TS(T
15
), và là một lịch trình hợp
lệ dưới giao thức tem thời gian:
T
14
T
15
Read(B)
Read(B)
B:=B-50
Write(B)
Read(A)
Read(A)
Display(A+B)
A:=A+50
Write(A)
Display(A+B)
Schedule-3
figure V- 16
Giao thức thứ tự tem thời gian đảm bảo tính khả tuần tự xung đột và không dealock.
V.2.3. QUY TẮC VIẾT THOMAS (Thomas' Write rule)
Một biến thể của giao thức tem thời gian cho phép tính cạnh tranh cao hơn giao thức thứ
tự tem thời gian. Trước hết ta xét lịch trình schedule-4 sau:
CHƯƠNG V ĐIỀU KHIỂN CẠNH TRANH
Trang
108
Không có nhận xét nào:
Đăng nhận xét