Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
ĐẠI HỌC ĐÀ NẴNG
BÁO CÁO MÔN HỌC
HỆ TIN HỌC PHÂN TÁN

ĐIỀU KHIỂN ĐỒNG THỜI BẰNG CƠ CHẾ THEN CÀI

 !"#$%&
'()#$*+,&-./
(0#12,.31455614578
Quảng Bình, 11/2012
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 1/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
LỜI MỞ ĐẦU

Mạng máy tính ra đời làm cho thế giới như nhỏ lại, mọi người có thể
trao đổi với nhau một khối lượng lớn thông tin trong điều kiện khoảng cách
xa hơn với thời gian nhanh hơn. Trên thực tế, xu hướng kỹ thuật mới - phân
tán các thành phần tạo nên hệ tin học theo hướng tiếp cận nơi sử dụng và sản
xuất thông tin trên cơ sở mạng máy tính cho chúng ta cơ hội ngồi trước máy
vi tính có nối mạng (LAN, WAN, Internet, …) thì có được mọi thứ: Chúng ta có
thể trao đổi thông tin, quản lý toàn bộ nhân sự của một đơn vị với nhiều chi
nhánh trên toàn quốc hoặc ở các quốc gia khác nhau; có thể đăng ký vé máy
bay, vé tàu xe, mua hàng tại siêu thị, thanh toán tiền qua hệ thống E-Banking
của ngân hàng qua hệ thống máy tính…
Tuy nhiên, để khai thác có hiệu quả hệ thống, vấn đề quan trọng là chiến
lược khai thác và sử dụng các tài nguyên dùng chung như thế nào ? Chiến lược
khai thác các tài nguyên dùng chung này là chức năng cũng như đối tượng
nghiên cứu của các hệ tin học phân tán. Trong thực tế, hệ tin học phân tán với
những nguyên lý, phương pháp của nó đã và đang được nhiều người quan tâm
để ứng dụng một cách hữu ích trong công việc. Nhiều nội dung lý thuyết nguyên

Sự sắp xếp cơ bản này là hạn chế quá mức và có thể được cải tiến bằng
cách phân biệt khoá đọc và khoá ghi. Nếu một khoá đọc được cài đặt trên một
tập tin, những khoá đọc khác được chấp nhận. Khoá đọc được cài đặt để làm
chắc chắn rằng tập tin sẽ không thay đổi, nhưng nó không có lý do nào để
ngăn cấm những giao tác khác không được đọc những tập tin này. Ngược lại,
khi một tập tin bị khoá quyền ghi, không có bất kỳ loại khoá nào khác được
chấp nhận. Như vậy, khoá đọc bị chia sẽ, nhưng khoá ghi chỉ là duy nhất.
Để đơn giản, giả sử rằng một đơn vị của then cài là một tập tin hoàn
chỉnh. Trong thực tế, nó có thể là một mục nhỏ, giống như một bản ghi riêng
lẻ hay một trang riêng lẻ, hoặc có thể là một mục lớn, giống như một cơ sở dữ
liệu hoàn chỉnh. Vấn đề về độ quy mô của mục để khoá được gọi là tính chất
của then cài.
+; Bằng cách không cần đánh dấu một tiến trình mà tiến trình đó
muốn dùng phần cuối cùng của tập tin chỉ bởi vì có một vài tiến trình khác
đang sử dụng phần đầu. Nói theo cách khác, một cơ chế cài then tốt đòi hỏi có
nhiều khoá, là nhiều tốn kém và có nhiều khả năng dẫn đến sự bế tắc.
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 3/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
II. Cơ chế then cài
Một giao dịch nào đó đang thực hiện phép then cài trên một đối tượng
muốn dành quyền sử dụng đối tượng này theo một vài kiểu truy cập nhất
định. Cơ chế then cài gán hay không gán quyền truy cập này căn cứ vào qui
tắc tiền định như loại trừ tương hỗ, luật đọc – hiệu chỉnh thông tin…
Nếu quyền được thừa nhận thì đối tượng bị cài then bởi giao dịch. Nếu
không, tiến trình thực hiện giao dịch bị khóa và đối tượng không bị cài then.
Cơ chế then cài cho phép một giao dịch có thể giải phóng đối tượng mà
nó đã cài then.
5<)=%>?
Một trong những giải pháp đơn giản để đạt được trật tự hoá gắn bó thể
hiện ở chổ bắt buộc phải sử dụng trật tự hoá tuần tự. Để làm việc đó, toàn bộ

tượng đó đã được cài then bởi giao dịch theo kiểu tương thích với phép toán.
+ Không có giao dịch nào cài then được trên đối tượng mà trước đó đã bị
cài then cũng bởi chính giao dịch đó, ngoại trừ theo kiểu loại trừ trong
trường hợp trước đó đã sử dụng kiểu chia sẽ.
+ Sau khi chấm dứt một giao dịch, không có đối tượng nào bị cài then.
Các then cài được sử dụng để hạn chế một lớp các trật tự hoá có khả
năng được thực hiện.
Một trật tự hoá được gọi là hợp thức nếu:
+ Đối tượng được một giao dịch cài then theo kiểu chia sẽ không bị bất
cứ then cài nào theo kiểu loại trừ của các giao dịch khác.
+ Một đối tượng bị cài then theo kiểu loại trừ thì không bị bất kỳ then cài
mới nào nữa.
Do vậy, mọi cố gắng cài then không phù hợp với các điều kiện tương hỗ
nêu trên đều phải chờ (bị làm chậm lại) cho đến khi mở then.
EF Một giao dịch được gọi là tốt, nếu nó sử dụng các then cài phù
hợp với đặc điểm của chúng. Một trật tự hoá được gọi là hợp thức, nếu các
then cài hoạt động phù hợp với các đặc điểm này.
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 6/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
7<#)G1'#
Xem xét một giao dịch hình thành hợp thức bằng cách kiểm tra hai điều kiện:
+ Toàn bộ đối tượng bị cài then vẫn ở trong tình trạng cài then cho đến
cuối giao dịch.
+ Không có then cài nào có thể diễn ra tiếp theo một then cài khác trong
cùng một giao dịch.
Điều kiện này thể hiện ở chổ là dãy các phép toán trên các then cài được
phân tích thành hai pha nối tiếp nhau. Một pha mà trong đó các đối tượng bị
cài then, còn pha kia chúng được mở then.
Toàn bộ trật tự hoá hợp thức của một tập hợp các giao dịch hình thành
tốt hai pha là gắn bó, có nghĩa là cùng hiệu ứng với trật tự hoá tuần tự.

khoản cho phép đảm bảo được tính gắn bó.
Sau đây là hai kiểu mô tả khác nhau của giao dịch T và một kiểu mô tả
có thể của giao dịch U:
Giao dịch T
1
Giao dịch T
2
Giao dịch U
v_viet(A)
A:= A - P
1
giai_phong(A)
v_viet(B)
B:= B + P
1
giai_phong(B)
v_viet(A)
A:= A – P
2
v_viet(B)
giai_phong(A)
B:= B + P
2
giai_phong(B)
v_viet(A)
A:= (1+t)*A
v_viet(B)
B:= (1+t)*B
giai_phong(B)
giai_phong(A)

11
: v_viet(A)
T
12
: A:= A – P
1
T
13
: giai_phong(A)
U
1
: v_viet(A)
U
2
: A:= (1+t)*A
U
3
: v_viet(B)
U
4
: B:= (1+t)*B
U
5
: giai_phong(B)
T
14
: v_viet(B)
T
15
: B:= B + P

T
26
: giai_phong(B)
U
3
: v_viet(B)
U
4
: B:= (1+t)*B
U
5
: giai_phong(B)
U
6
: giai_phong(A)
Như vậy, ta kiểm tra rằng S
1
dẫn đến trạng thái không gắn bó, U thực
hiện trên các giá trị không gắn bó của B và rằng S
2
là tương đương với trật tự
hoá tuần tự S
2
(T
2
,U).
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 9/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
PHẦN II
SỬ DỤNG BỘ QUẢN LÝ KHÓA CƠ BẢN

Trước hết, chúng ta xem lại định nghĩa tính khả tuần tự một cách hình
thức: Một lịch biểu S được gọi là khả tuần tự nếu và chỉ nếu nó tương đương
tương tranh với một lịch biểu tuần tự. Tính khả tuần tự được định nghĩa như
thế cũng được gọi là khả tuần tự theo tương tranh bởi vì nó được định nghĩa
theo sự tương đương tương tranh. Từ đó, chúng ta có thể chỉ ra rằng chức
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 11/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
năng cơ bản của bộ phận điều khiển đồng thời là tạo ra một lịch biểu khả
tuần tự để thực hiện các giao dịch đang chờ.
Lịch biểu của một giao dịch là một chuỗi các lệnh được thực hiện trong
hệ thống theo thứ tự thời gian. Một lịch biểu đối với một tập các giao dịch
phải bao gồm tất cả các lệnh của tất cả các giao dịch này, và phải bảo toàn
thứ tự mà các lệnh xuất hiện trong mỗi giao dịch cá thể theo thứ tự đó. Lịch
biểu tạo mối liên hệ ràng buộc giữa các giao dịch với nhau.
Ví dụ về lịch biểu khả tuần tự: Có 3 giao dịch T1, T2, T3 (tương ứng với
(a), (b), (c)
BEGIN_TRANSACTION
x = 0;
x = x + 1;
END_TRANSACTION
(a)
BEGIN_TRANSACTION
x = 0;
x = x + 2;
END_TRANSACTION
(b)
BEGIN_TRANSACTION
x = 0;
x = x + 3;
END_TRANSACTION

Bởi vì chúng ta quan tâm đến việc đồng bộ hóa các thao tác tương tranh
của các giao dịch tương tranh nên có hai loại khóa chốt được kèm với mỗi
đơn vị khóa: Khóa đọc (Read Lock RL), và Khóa Ghi (Write Lock -WL).
+ RLi(x): khoá đọc trên phần tử dữ liệu x của giao tác Ti
+ WLj(x): khoá ghi trên phần tử dữ liệu x của giao tác Tj
Hai khoá pli(x) và qlj(y) đụng độ nếu x=y, i≠j,
Hai khoá đụng độ nhau nếu chúng khoá trên cùng một phần tử dữ liệu,
chúng được phát sinh từ hai giao tác khác nhau và một trong hai thao tác là
ghi.
Một giao dịch T
i
đang muốn đọc một mục dữ liệu được chứa trong đơn vị
khóa x sẽ nhận được một khóa đọc trên x (ký hiệu là rl
i
(x) và cũng tương tự
như vậy với thao tác ghi.
Tính tương thích của các thực thể khóa được mô tả trong bảng sau:
RL
i
(x) WL
i
(x)
RL
i
(x) Tương thích Không tương thích
WL
i
(x) Không tương thích Không tương thích
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 13/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài

Thuật toán khoá chốt cơ bản
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 14/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
{Các định nghĩa chuẩn bị cho các thuật toán được trình bày trong tiểu
luận}
Declare-type
Operation: một trong số Begin-Transaction, Read, Write, Abort, hoặc
Commit
DataItem : một mục dữ liệu trong cơ sở dữ liệu phân tán
TransactionId: một giá trị duy nhất được gán cho mỗi giao dịch
DataVal: một giá trị có kiểu dữ liệu cơ bản (nghĩa là số nguyên, số thực,
…)
SiteId: một đinh danh duy nhất cho vị trí
Dbop: một bộ ba gồm {một phép toán trên cơ sở dữ liệu của ứng
dụng} opn: Operation
data: DataItem
tid: TransactionId
Dpmsg: một bộ ba gồm {một thông báo từ bộ xử lý dữ liệu}
opn: Operation
tid: TransactionId
result: DataVal
Scmsg: một bộ ba gồm {một thông báo từ bộ xếp lịch}
opn: Operation
tid: TransactionId
result: DataVal
Transation ← một bộ hai gồm
tid: TransactionId
body: thân giao dịch
Message ← một chuỗi ký tự cần được truyền đi
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 15/32

begin
gởi dop đến bộ xử lý dữ liệu
end
Read or Write {yêu cầu khoá}
begin
tìm đơn vị khoá lu sao cho x lu
if lu chưa bị khoá or thể thức khoá lu tương thích
với Op then
begin
đặt khoá trên lu ở thể thức thích hợp
gởi dop đến bộ xử lý dữ liệu
end
else đưa dop vào một hàng đợi của lu
end-if
end
Abort or Commit:
begin
gởi dop đến bộ xử lý dữ liệu
end
end-case
Dpmsg: {trả lời của bộ xử lý dữ liệu}
Begin {yêu cầu mở
khoá}
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 17/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
Op ← pm.opn
x ← pm.result
T ← pm.tid
tìm đơn vị khoá lu sao cho x
⊆

S = {wl
1
(x) R
1
(x), W
1
(x), lr
1
(x), wl
2
(x), R
2
(x), W
2
(x), lr
2
(x), wl
2
(y),
R
2
(y), W
2
(y), lr
2
(y), C2, wl
1
(y), R
1
(y), W

nhau, làm mất đi tính biệt lập và tính nguyên tử tổng thể. Đây chính là lập
luận của phương pháp khoá chốt hai pha (Two-Phase Locking, 2PL).
Khóa chốt hai pha - 2PL là một trong những kỹ thuật hiệu quả trong
việc khắc phục một số đụng độ cũng như thời gian chết trong quá trình thực
hiện các lệnh của các giao tác.
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 19/32
T
1
: Read(x)
x ← x + 1
Write(x)
Read(y)
y ← y – 1
T
2
: Read(x)
x ← x * 2
Write(x)
Read(y)
y ← y * 2
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
Nhiệm vụ của bộ xếp lịch 2 giai đoạn (Two phase locking, 2PL) là quản
lý khoá chốt và điều khiển giao tác khi nào lấy và khi nào giải phóng khoá.
2PL nhằm đồng bộ hoá việc đọc và ghi. Trước khi đọc mục dữ liệu x,
phải khóa x (khóa do đọc). Trước khi ghi lên x, giao tác phải khóa mục x
( khóa do ghi).
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 20/32
Giai đoạn tăng trưởng
Giai đoạn thu hồi
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài

các khoá nhưng chưa bắt đầu giải phóng khóa nào. Vì thế điểm khóa xác định
cuối giai đoạn tăng trưởng và đầu giai đoạn thu hồi của một giao tác.
Tuy nhiên việc cài đặt Khóa 2PL gặp nhiều khó khăn vì bộ quản lý khoá
phải biết rằng giao dịch đã nhận đủ tất cả mọi khoá và sẽ không còn cần khoá
một mục nào nữa. Bộ quản lý khoá cũng phải biết rằng giao dịch không còn
cần truy xuất mục dữ liệu đó nữa, vì thế khoá có thể được giải phóng. Cuối
cùng, nếu giao dịch bị huỷ bỏ sau khi giải phóng một khoá, nó có thể làm huỷ
bỏ luôn cả các giao dịch đã truy xuất các mục đã mở khoá. Hiện tượng này
được gọi là huỷ bỏ dây chuyền (cascading abort). Vì những khó khăn đó, phần
lớn các bộ xếp lịch 2PL đều cài đặt một dạng khắc khe hơn có tên là khoá chốt
hai pha nghiêm ngặt (strict two-phase locking), trong đó nó giải phóng toàn
bộ các khoá vào lúc giao dịch kết thúc (uỷ thác hoặc bị huỷ bỏ).
Biểu đồ khóa loại này được trình bày như sau:
Hình 4: Biểu đồ khoá hai pha nghiêm ngặt
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 22/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
Kỹ thuật này cũng gồm 2 giai đoạn:
+ Giai đoạn tăng trưởng: giống với giai đoạn đầu của kỹ thuật khóa 2 pha.
+ Giai đoạn thu hồi khóa:

Tất cả các khóa được giải phóng cùng một lúc sau khi giao tác T kết
thúc hoặc bị hủy bỏ.

Không có thao tác đọc/ghi nào được thực hiện một khi khóa được
giải phóng bởi giao tác.

Nếu giao tác bị hủy bỏ thì việc phục hồi lại những thay đổi dữ liệu
được thực hiện trước khi khóa được giải phóng.
Bộ quản lý khoá 2PL nghiêm ngặt chỉ sửa lại một ít trong Thuật toán 1.
Thực sự chỉ cần sửa đổi phần xử lý các hồi đáp từ bộ xử lý dữ liệu nhằm đảm

end
Read or Write {cần khoá chốt}
begin
tìm đơn vị khoá lu sao cho x
⊆
lu
if lu chưa bị khoá or thể thức khoá lu tương thích
với Op then
begin
đặt khoá trên lu ở thể thức thích hợp
gởi dop đến bộ xử lý dữ liệu
end
else đặt dop vào một hàng đợi cho lu
end-if
end
Abort or Commit:
Lê Nam Trung – Khoa học máy tính K24 Quảng Bình 24/32
Hệ Phân tán – Điều khiển đồng thời bằng cơ chế then cài
begin
gởi dop đến bộ xử lý dữ liệu
end
end-case
Dpmsg:
Begin
Op ← pm.opn
res ← pm.result
T ← pm.tid
If Op = Abort or Op = Commit then
begin
for mỗi đơn vị khoá lu bị khoá bởi T do