Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
ĐẠI HỌC ĐÀ NẴNG

TIỂU LUẬN MÔN HỌC
HỆ PHÂN TÁN
 
ĐIỀU KHIỂN ĐỒNG THỜI BẰNG CƠ CHẾ THEN CÀI &
BÀI TOÁN SỬ DỤNG BỘ QUẢN LÝ KHÓA CƠ BẢN VÀ
NHỮNG ĐIỂM CẦN CẢI TIẾN

 !"#$
%  &'()&$*+,
-./$  '011)'012
-340(5'01'
 Võ Minh Trang – Khoa học máy tính Khóa 24 -1-
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
LỜI MỞ ĐẦU

Ngày nay cùng với sự phát triển nhanh, vượt bậc của nền Khoa học - Công
nghệ. Mạng máy tính ra đời làm cho thế giới của chúng ta dường như nhỏ lại và
mọi người trở nên gần nhau hơn và mọi người có thể trao đổi thông tin với một
khối lượng lớn và khoảng cách xa hơn với thời gian nhanh hơn. Trên thực tế, một
xu hướng kỹ thuật mới ra đời - xu hướng 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. Vì vậy nếu chúng ta ngồi trước máy vi tính có nối mạng (LAN, WAN, Internet,
…) thì hầu như chúng ta 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, chúng ta có thể ở nhà để đă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, … Song
để 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

bao gồm một danh sách các tập tin bị khoá, và từ chối tất cả mọi cố gắng cài then
tập tin mà tập tin đó đã thật sự bị khoá bởi một tiến trình khác. Khoá được sinh ra
và được giải thoát một cách tự động bởi hệ thống các giao tác, không phụ thuộc
vào hành động của lập trình viê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, chúng ta 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.
,8 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.
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.
 Võ Minh Trang – Khoa học máy tính Khóa 24 -3-

+ 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.
 Võ Minh Trang – Khoa học máy tính Khóa 24 -4-
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
ABC 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.
2$D'%$
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ự.
Ngược lại, nếu các giao dịch của một tập hợp không phải là hình thành tốt và

đó cũng đồng nghĩa với việc đảm bảo trong tài khoản của người sủ dụng không
bao giờ có giá trị bằng 0 hay giá trị âm.
Bây giờ chúng ta hãy nghiên cứu vấn đề quản lý truy cập thông tin tài 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)

T
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

2
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).
 Võ Minh Trang – Khoa học máy tính Khóa 24 -6-
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
PHẦN II

Hình 2: Các bộ phận quản lý thực hiện giao dịch phân tá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 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
(c)

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
 Võ Minh Trang – Khoa học máy tính Khóa 24 -9-
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
-EFG+HFGI=CJK8.
Qui tắc 1:
Khi nhận được một thao tác pi[x] từ bộ quản lý giao tác (Transaction

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
 Võ Minh Trang – Khoa học máy tính Khóa 24 -10-
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
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
OpSet: một tập các Dbop
SiteSet: một tập các SiteIde
WAIT(msg: Message)
begin
{đợi cho đến khi có một thông báo đến}
end

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á}
Op ← pm.opn
x ← pm.result
T ← pm.tid
tìm đơn vị khoá lu sao cho x
⊆
lu, giải phóng khoá trên lu do T giữ
if không còn khoá nào trên lu and
có những thao tác đang đợi khoá lu trong hàng đợi then
begin
SOP ← thao tác đầu tiên trong hàng đợi
SOP ← SOP
∪
{O là một thao tác trên hàng đợi có thể khoá
lu ở thể thức khoá tương thích với các thao tác hiên hành trong
L }

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
1
(y), lr
1
(y), Cl}
Ở đây LR
i
(z) biểu thị thao tác giải phóng khoá trên z đang được T
i
giữ.
Chú ý rằng S không khả tuần tự. Bởi vì, nếu trước lúc thực hiện các giao dịch
này, giá trị của x và y lần lượt là 50 và 20. Nếu S khả tuần tự, thì giá trị sau khi

x ← x + 1
Write(x)
Read(y)
y ← y – 1
Write(y)
Commit
T
2
: Read(x)
x ← x * 2
Write(x)
Read(y)
y ← y * 2
Write(y)
Commit
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
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).
Quá trình cấp phát và thu hồi khóa được thể hiện ở biểu đồ khoá 2PL sau:
Hình 3: Biểu đồ Khóa 2PL
Hình trên cho thấy bộ quản lý khóa giải phóng khóa ngay sau khi hoàn tất
việc truy xuất. Điều này cho phép các giao dịch đang đợi khoá tiếp tục tiến
hành và nhận khoá, do vậy, làm tăng hoạt động đồng thời.
Gọi Oper(T,x) là lệnh truy xuất mục dữ liệu x trong giao tác T.
Dựa vào kỹ thuật khóa chốt hai giai đoạn, ta có thể chia giao tác thành hai
giai đoạn, dựa trên 3 nguyên tắc trên:
+ Giai đoạn tăng trưởng (growing phase), trong giai đoạn này nó nhận
các khoá và truy xuất các mục dữ liệu.
Khi bộ lập lịch nhận được lệnh Oper(T,x), nó kiểm tra lệnh này có tranh
chấp với những lệnh truy xuất trên x khác, đã được bộ lập lịch cấp khóa.

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
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
bảo rằng các khoá chỉ được giải phóng nếu thao tác là uỷ thác hoặc huỷ bỏ.
 Võ Minh Trang – Khoa học máy tính Khóa 24 -15-
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
Toàn bộ thuật toán 2PL nghiêm ngặt được trình bày trong Thuật toán 2, thuật toán
quản lý giao dịch để xếp lịch theo 2PL được trình bày trong Thuật toán 3.
Thuật toán 2. Thuật toán quản lý khoá bằng phương pháp khoá chốt hai pha
nghiêm ngặt (S2PL-LM).
declare-var
msg : Message
dop : Dbop
Op : Operaeion
x : Dataltem
T : TransactionId

end
Abort or Commit:
begin
gởi dop đến bộ xử lý dữ liệu
 Võ Minh Trang – Khoa học máy tính Khóa 24 -16-
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
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
begin
giải phóng khoá trên lu do T giữ
if không còn khoá nào trên lu and
có các thao tác đang đợi khoá lu trong hàng đợi then
begin
SOP ← thao tác đầu tiên trong hàng đợi
SOP ← SOP
∪
{ là một thao tác trên hàng đợi có thể khoá
lu ở một thể thức khoá tương thích với các thao tác hiên hành
trong L }
đặt các khoá trên lu cho các thao tác trong SOP
for tất cả các thao tác trong SOP do
gởi mỗi thao tác đến bộ xử lý dữ liệu

Op ← sm.opn
res ← sm.result
T ← sm.tid
Case of Op
Read:
begin
trả res về cho ứng dụng của người sử dụng (nghĩa là giao dịch)
end
Write:
begin
thông tin cho ứng dụng về việc hoàn tất hành động ghi
trả res về cho ứng dụng
end
Commit:
begin
huỷ vùng làm việc của T
thông tin cho ứng dụng biết về việc hoàn tất thành công giao dịch T
end
Abort:
begin
thông tin cho ứng dụng biết về việc hoàn tất huỷ bỏ giao dịch T
end
end-case
end
end-case
until forever
end. {2PL-LM}
Chúng ta cần chú ý rằng mặc dù thuật toán 2PL cưỡng chế tính khả tuần tự
tương tranh, nó không cho phép tất cả mọi lịch biểu có tính khả tuần tự tương
tranh.

1
: lock (x); lock(y); read (x); write (y);
T
2
: lock (y); lock(x); read (y); write (x);
T
1
chiếm giữ khóa x và cố gắng khóa y, T
2
chiếm giữ khóa y và cố gắng
khóa x. Hiện tượng bế tắc sẽ xảy ra.
M.H%8N#9+
+ Thiết lập thời gian Timeout, nếu thời gian thực hiện giao tác vượt quá
thời gian Timeout thì hủy bỏ giao tác hoặc thực hiện thuật toán kiểm tra bế tắc.
+ Sắp xếp các mục dữ liệu và truy xuất chúng theo một thứ tự nhất
định.
+ Giảm bớt việc đồng hành các giao tác.
 Võ Minh Trang – Khoa học máy tính Khóa 24 -19-
Tiểu luận Hệ Phân Tán – Điều khiển đồng thời bằng cơ chế then cài
KẾT LUẬN

Tất cả các thông tin được trình bày ở trên với mục tiêu tìm hiểu vấn đề điều
khiển đồng bộ bằng cơ chế then cài và bài toán sử dụng bộ quản lý khoá cơ bản
chỉ dừng lại ở phương diện nghiên cứu nguyên lý, phương pháp kỹ thuật giải quyết
các vấn đề đó. Qua đó đã giúp cho tôi nắm bắt cơ bản được việc truy cập thông tin
chung, trong đó đặc biệt lưu tâm là việc truy cập không thể tiến hành theo một
trình tự ngẫu nhiên được. Nguyên do cơ bản của vấn đề này, không phải là cái gì
khác, mà chính là vấn đề bế tắc và gắn bó dữ liệu.
Và cũng từ đó giúp tôi nắm bắt được phương pháp quản lý việc truy cập
thông tin cho phép đảm bảo được tính gắn bó dữ liệu. Và hiểu được rằng, mặc dù

Phần I: Điều khiển đồng thời bằng cơ chế then cài ………………. Trang 3
I. Tổng quan về cơ chế then cài …………………………………… Trang 3
II. Cơ chế then cài …………………………………………………. Trang 3
1. Loại trừ tương hỗ …………………………………………… Trang 4
2. Then cài chọn lựa các đối tượng ……………………………. Trang 4
3. Giao dịch 2 pha …………………………………………… Trang 5
Phần II: Sử dụng bộ quản lý khóa cơ bản Trang 7
I. Tổng quan Trang 7
II. Sử dụng bộ quản lý khóa cơ bản Trang 9
III. Những điểm cần cải tiến Trang 13
Kết luận Trang 20
Tài liệu tham khảo Trang 21
 Võ Minh Trang – Khoa học máy tính Khóa 24 -22-