Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA CÔNG NGHỆ THÔNG TIN
TIỂU LUẬN LẬP TRÌNH MẠNG
VIẾT CHƯƠNG TRÌNH ÁP DỤNG THUẬT TOÁN
DUY TRÌ GẮN BÓ, TRÁNH BẾ TẮC VÀ THIẾU
THỐN VÔ HẠN HAI PHA TRONG HỆ ĐA SERVER
GVHD: PGS.TS. LÊ VĂN SƠN
SVTH : ĐOÀN CƯỜNG
VÕ LÊ ĐỨC HUY
LỚP : KHOA HỌC MÁY TÍNH
Đà Nẵng tháng 03- 2010
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 1
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
Lời mở đầu
Như chúng ta đã biết, đối với các hệ thống thông tin lớn, cơ sở dữ liệu không chỉ
được lưu trữ và quản lý bởi các Server độc lập mà thường được phân tán trên
nhiều Server và phân bố ở các vị trí địa lý khác nhau. Hệ thống cho phép xử lý
đa truy cập đồng thời và cho phép đăng ký từ xa. Một trong những lợi ích của
Việc phân tán dữ liệu như vậy là nhằm phân chia yêu cầu xử lý dữ liệu cho
nhiều máy nhằm làm tăng năng lực xử lý thông tin của hệ thống và đặc biệt, nó
đảm bảo yêu cầu toàn dữ liệu vì dữ liệu được lưu trữ dự phòng ở nhiều nơi khác
nhau.
Hệ thống trình bày như trên là hệ thống đa server và phức tạp. Một trong các
yêu cầu đặt ra cho hệ thống là phải đảm bảo gắn bó dữ liệu giữa các server
đồng thời không làm ảnh hưởng đến năng lực xử lý của hệ thống.
Nội dung chủ yêu trình bày trong báo cáo này tập trung vào xây dựng chương
trình đảm bảo gắn dữ liệu cho hệ thống đa server. Chương trình này được thiết
kế và xây dựng dựa trên các điều kiện sau:
Về mặt công cụ: Sử dụng ngôn ngữ lập trình mạng JAVA của Sun Micro System

Do vậy, để nghiên cứu, ta cần giả định một số quy tắc nhất định cho Việc hoạt động
của hệ. Các quy tắc này thể hiện trong bảng sau đây :
STT Quy tắc
1 Chỉ có một loại phép toán (hay giao dịch) duy
nhất là chuyển khoản từ tài khoản này sang tài
khoản khác.
2 Hệ có số lượng tài khoản cố định.
3 Không có trao đổi nào khác diễn ra ngoài ngân
hàng.
4 Ngân hàng không được phép tiết lộ bí mật về số
dư của khách.
Xét các quy tắc có tính chất điều kiện như trên, sau khi thực hiện xong hoàn toàn
một giao dịch nào đó, hệ quản lý giao dịch cần phải đảm bảo hai đặc tính sau đây :
STT Ký
hiệu
Đặc tính
1 P1 Tổng tất cả các số dư phải là một hằng
số.
2 P2 Số dư cho một tài khoản là đại lượng ≥
0.
Hai đặc tính này gọi là đặc tính trạng thái tổng quát của CSDL (hay là các ràng
buộc toàn vẹn của hệ). Ta nói rằng trạng thái của hệ được gắn bó, nếu hệ mang hai đặc
tính vừa nêu.
Phép toán chuyển khoản thể hiện bằng cách trừ đi một giá trị P nào đó ở một tài
khoản và cộng chính giá trị đó vào tài khoản khác. Nếu ta ký hiệu A là số dư tài khoản
bị trừ đi và B là số dư tài khoản được cộng vào, thì chương trình thể hiện giao dịch này
có thể Iết như sau :
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 3
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
Nếu A >= P thì

Đặc tính
1 P'1
Thực hiện một lượng giao dịch T nào đó
không làm thay đổi tổng của tất cả các
tài khoản.
2 P'2 Trong một tài khoản, số dư bao giờ
cũng ≥ 0.
3 P'3 Thực hiện n giao dịch loại U nâng tổng
của các tài khoản bằng (1 + t)n.
Cần lưu ý rằng nếu ta cho phép các giao dịch loại U và T hoạt động song song, thì
có nguy cơ phá vở đặc tính P'3.
Ví dụ :
Hãy xem xét một hệ bao gồm hai tài khoản A và B, trong đó có hai giao dịch được
thực hiện theo kiểu tương tranh nhau :
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 4
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
Giao dịch T Giao dịch U
A := A - P
B := B + P
A := (1 + t) x A
B := (1 + t) x B
và giả sử rằng đầu tiên ta phải kiểm tra điều kiện A ≥ P.
Nếu trình tự thực hiện của tác động sơ đẳng của hai giao dịch như sau :
A := A – P
A := (1 + t) x A
B := (1 + t) x B
B := B + P
thì điều kiện P'3 không được tôn trọng.
Bây giờ, ta sẽ thực hiện bằng những giá trị số cụ thể. Nếu trước khi thực hiện
hai giao dịch A = 1 000, B = 2 000 và nếu

chi tiết vấn đề này, ta hãy tham khảo tài liệu về
mạng máy tính và các hệ thông mở.
3 Hệ thống Iễn thông và các tiến trình là các đối
tượng có thể xảy ra sự cố kỹ thuật.
Ta sẽ trình bày các thuật ngữ, các khái niệm và diễn giải có liên quan mật thiết đến các
đặc điểm vừa nêu.
I.2.2 Tác động và giao dịch
Các đối tượng khác nhau của hệ không phải là các đối tượng độc lập nhau,
chúng liên hệ với nhau bởi tập hợp các quan hệ gọi là các ràng buộc toàn vẹn. Các ràng
buộc này thể hiện sâu sắc các đặc tính riêng biệt của hệ.
Trạng thái của hệ thỏa mãn một tập các ràng buộc toàn vẹn gọi là trạng thái gắn
bó.
Các nhà thiết kế và vận hành hệ mong muốn rằng Việc thực hiện các tiến trình
phải duy trì cho được hệ trong trạng thái gắn bó. Để chính xác hóa đặc tính này, cần
phải lưu ý là trạng thái của hệ chỉ được xác định ở mức quan sát cho trước.
Ta quan tâm đến hai mức quan sát :
STT Mức Giải thích
1 NSD
Tiến trình là một dãy thực hiện các giao
dịch.
Giao dịch đó là chương trình duy nhất
được thực hiện từ một trạng thái gắn bó
dẫn hệ đến một trạng thái gắn bó khác.
2 Hệ
thống
Mỗi giao dịch được cấu tạo từ một dãy
các tác động được thể hiện như sau. Nếu
2 tác động A và B thuộc 2 giao dịch khác
nhau được thực hiện bởi 2 tiến trình, thì
hiệu ứng tổng quát của chúng sẽ là hoặc

không còn bảo đảm được nữa; ta cũng đã gặp trong ví dụ I.1.
Một yêu cầu khác rất quan trọng là trong quá trình thực hiện hệ phải đảm bảo
cho các tác động không bị ngắt quảng.
Trong các phần tiếp theo sau đây, ta sẽ nghiên cứu các điều kiện thực hiện các
giao dịch song song mà vẫn tôn trọng các yêu cầu của ràng buộc toàn vẹn.
I.2.3 Trật tự hóa các tác động
Trở lại với tập hợp giao dịch M = {T
1
, T
2
, , T
n
} đã được xác định trong I.2.2.
Mỗi một giao dịch được cấu tạo từ một dãy các tác động. Bằng các tác động không
chia xẻ được này, toàn bộ Việc thực hiện của tập hợp các giao dịch M bởi một tập hợp
các tiến trình tương tranh là tương đương với Việc thực hiện một dãy S các tác động
thuộc các giao dịch này, như S = (a
1
, a
2
, , a
n
) chẳng hạn. Trong trật tự tuân thủ trật tự
nội tại của từng giao dịch, dãy này bao gồm tất cả các tác động cấu tạo nên các giao
dịch M; mỗi một tác động chỉ xuất hiện một và chỉ một lần. Một dãy như vậy gọi là
trật tự hóa của tập hợp các giao dịch M.
Ví dụ :
Cho T
1
= (a

13
, a
23
, a
14
Trong số các trật tự hóa của một tập hợp các giao dịch, điều rất quan trọng là phải
tách ra cho được những cái phục vụ trạng thái gắn bó dữ liệu và chúng được gọi là trật
tự hóa gắn bó.
Đến đây, tuy ta chưa có dịp làm quen với các đặc tính tổng quát của trật tự hóa,
nhưng đã nắm được một đặc tính quan trọng là các trật tự hóa tương ứng với Việc thực
hiện tuần tự của tập hợp các giao dịch hay còn gọi ngắn gọn là trật tự hóa tuần tự.
Nếu ta nắm được các đặc trưng của các trật tự hóa tương đương với một trật tự hóa
tuần tự có nghĩa là cùng có tác dụng như trật tự hóa tuần tự, thì ta đã có được điều kiện
đủ của sự gắn bó.
Đó chính là tiêu chuẩn tương đương mà ngay bây giờ ta sẽ phải thành lập.
Ví dụ 1 :
Trở lại với ví dụ trong phần I.1 và xem xét 3 trật tự hóa có thể là S
1
, S
2
và S
3
.
Trật tự hoá S
1
thể hiện bằng hình vẽ I-1 sau đây :

Hình vẽ I-2 thể hiện trật tự hoá S
2
:

: A := C x B
và hai trật tự hóa T
1
và T
2
sau đây (trong đó T
2
được phân ra thành các tác động sơ
đẳng, còn R chỉ đối tượng cục bộ của T
2
).

S'
1
là tuần tự. S'
2
tuân thủ trật tự của các tác động trong mỗi một giao dịch,
nhưng lại không tương đương với S'
1
. Giá trị của A nói chung không bằng 3 x B sau khi
thực hiện S'
2
.
Sự bảo toàn trật tự cập nhật (ví dụ 1) và sự bảo toàn tập hợp các truy vấn trước
khi cập nhật (ví dụ 2) thể hiện điều kiện tương đương giữa các trật tự hóa.
Cho S
tt
là một trật tự hóa tuần tự của tập hợp các giao dịch M và S là một trật tự
hóa bất kỳ của M. Hiệu ứng của S giống với hiệu ứng của S
tt

1
, e, T
2
), với các điều kiện sau đây được
kiểm tra :
1. Một tác động của T
1
tham chiếu e và một tác động sau T
2
thay đổi e.
2. Một tác động của T
1
thay đổi e và một tác động sau T
2
tham chiếu e. (hệ quả của
điều kiện 2).
3. Một tác động của T
1
thay đổi e và một tác động sau T
2
thay đổi e (hệ quả của điều
kiện 1) mà e không được thay đổi bởi một giao dịch khác giữa hai tác động T
1
và T
2
.
Thuật ngữ "trước" được hiểu theo nghĩa "cái tiếp theo nó trong trật tự hóa S".
Quan hệ này được biểu hiện bằng một đồ thị phụ thuộc mà các nút của nó được
gán nhãn bởi tên của giao dịch và các cung là tên các đối tượng. Để cho một trật tự hóa
tuần tự, đồ thị này không có vòng lặp (thực tế, nếu (T

UT
(S
2
)
A
B
UT
(S
3
)
A
B
UT
Hình I-5. Đồ thị ứng với
các trật tự hoá S
1
, S
2
và S
3
.
Các đồ thị tương ứng với các giao dịch S'
1
và S'
2
của ví dụ 2 là :
(S'
1
)
C

I.3.1 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
già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 quy 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.
Ta sẽ mô tả Việc sử dụng các then cài để đạt được sự gắn bó của giao dịch.
Then cài có thể là nguyên nhân của bế tắc và thiếu thốn vô hạn tài nguyên như đã thấy
trong chương IV và ta cũng sẽ giải quyết vấn đề này trong chương này.
I.3.1.1 Loại trừ tương hổ
Một trong những giải pháp giản đơn để đạt được trật tự hóa gắn bó thể hiện ở
chổ bắt buộc phải sử dụng trật tự hóa tuần tự. Để làm Việc đó, toàn bộ giao dịch được
đặt trong cặp hàm nguyên thuỷ mo_giaodich và dong_giaodich. Đây là sự đảm bảo cho
Việc loại trừ tương hổ giữa các giao dịch. Các hàm này có thể được triển khai dựa trên
các phương pháp đã nghiên cứu trong các chương trước.
Nếu ta biết trước các đối tượng được xử lý bởi một giao dịch nào đó, thì ta có
thể cài then công Việc truy cập đến các đối tượng. Điều đó chỉ cho phép thực hiện song
song đối với các giao dịch truy cập vào các đối tượng rời rạc.
Nếu ta muốn nâng cao hơn nữa khả năng sử dụng song song, thì cần phải thực
hiện cài then ở mức độ thấp hơn mức giao dịch. Đó chính là điểm quan trọng mà ta cần
quan tâm.
I.3.1.2 Then cài chọn lựa các đối tượng
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 10
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
Các quy tắc truy cập đối tượng được chú ý. Đó là tính hợp thức của Việc truy
cập. Nội dung của quy tắc này như sau :
Một giao dịch thay đổi giá trị của 1 đối tượng phải loại trừ tất cả các đối tượng

Chú ý :
Một giao dịch 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ự hóa 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.
Trong phần tiếp theo, ta chỉ xem xét các trật tự hóa hợp thức của các giao dịch được
hình thành hoàn toàn hợp thức. Ta sẽ xem xét các điều kiện của một trật tự hóa gắn bó.
I.3.1.3 Giao dịch hai pha
Bây giờ, ta hãy 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 :
1. 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.
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 11
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
Ta có thể chứng minh trong bài tập 1 của chương này rằng toàn bộ trật tự hóa
hợp thức của các giao dịch như vậy là gắn bó. Nói một cách tổng quát, giả sử rằng toàn
bộ giao dịch là hình thành tốt và ngoài ra hãy kiểm tra bằng cách thay điều kiện 1 nêu
trên bằng điều kiện tổng quát hơn. Đó là điều kiện 2.
2. 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 2 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. Đặc tính này định nghĩa các giao dịch theo hai pha.
Bằng cách sử dụng điều kiện tương đương đã cho trong I.2.3 ta có thể hình thành
nên kết quả sau đây và cũng được phản ảnh trong bài tập 1 của chương.
Toàn bộ trật tự hóa 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ự hóa 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à ở
hai pha, thì có thể xây dựng các trật tự hóa hợp thức của M là không gắn bó.
Ví dụ 1 :
Hãy truy cập vào tập hợp các đối tượng.

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) x A
v_viet(B)
B := (1 + t) x B
giai_phong(B)
giai_phong(A)
Ta kiểm tra rằng tất cả các giao dịch đều là hình thành tốt và T
2
và U đều ở hai
pha và T
1
không có hai pha.
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 12
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
Sau đây là hai trật tự hóa hợp thức S
1
và S
2
xuất phát từ Việc thực hiện song song
của T

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
1
U
6
: giai_phong(A)
T
16
: giai_phong(B)
T
21
: v_viet(A)
T
22
: A := A - P
2
T
23

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ự hóa tuần tự S
2
(T
2
,U).
I.3.2 Hệ quả của tính không chắc chắn trên trạng thái của hệ
Bây giờ, ta hãy tưởng tượng rằng các đối tượng được phân tán trên nhiều trạm
khác nhau và được nối với nhau thông qua hệ thống viễn thông và rằng các tiến trình
diễn ra trên các trạm khác nhau. Hệ thống viễn thông cho phép các tiến trình trên các
trạm khác nhau có thể trao đổi các thông điệp với nhau. Ta cũng giả định rằng các tiến
trình và các phương tiện truyền thông tin là các đối tượng có thể rơi vào tình trạng sự
cố.
Các đối tượng thay đổi hay tham chiếu trong quá trình thực hiện cùng một giao
dịch có thể nằm trên các trạm khác nhau. Nếu ta xét đến ví dụ I.1, thì tài khoản A và tài
khoản B có thể được quản lý bởi hai cơ quan khác nhau. Phép chuyển khoản T trong
trường hợp này bao gồm các tác động thực hiện trên hai trạm khác nhau. Một xử lý
như vậy, trong trường hợp hệ tập trung chỉ cần một giao dịch tuần tự là đủ, nhưng với
các hệ phân tán, thì cần ít nhất hai dãy tác động cục bộ. Tương tự như vậy đối với giao
dịch loại U.
Một hệ quản lý tập hợp thông tin phân tán bao gồm :
STT Cơ chế
1
Cơ chế cho phép sắp xếp một cách tổng quát các
tác động của cùng một giao dịch, ngay cả khi các
tác động này diễn ra trên các trạm khác nhau.
2

trạng thái của hệ là gắn bó.
2 Nếu một tiến trình bị sự cố trước khi diễn ra các
thay đổi của T, trạng thái của hệ là gắn bó.
3 Nếu một tiến trình bị sự cố giữa các thay đổi của
T, trạng thái của hệ là không gắn bó.
Các đặc tính trên có thể mô tả bằng hình vẽ I-7 sau đây :

Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 14
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
Hình I-7. Ba giai đoạn của một giao dịch.
Trong tình huống này, ta có hai giải pháp có thể là :
STT Giải pháp tổng quát
1 Phục hồi trạng thái của hệ như trước khi diễn ra
giao dịch T.
2 Cố gắng tiếp tục thực hiện giao dịch T cho đến kết
thúc.
Không phải lúc nào ta cũng có thể áp dụng được giải pháp 1 vì một số tác động
không thể quay trở lại được. Như thế, ta phải xác định cho được điểm không trở lại của
từng giao dịch. Căn cứ vào điểm này, nếu vượt quá nó, không có hành động nào quay
trở lại được thực hiện và trạng thái trước đó của giao dịch sẽ được phục hồi bởi phép
lập lại (rollback).
Trong hệ thống tập trung, Việc triển khai một kỹ thuật khẵng định (điểm không
trở lại) không có gì khó khăn. Ta thực hiện một cập nhật có tính chất quyết định vào
trạng thái bằng một phép ghi duy nhất.
Trong hệ phân tán, vấn đề triển khai có nhiều tinh tế hơn vì khi một trạm bắt
đầu cập nhật, nó phải gửi cho tất cả các trạm khác và sự cố có thể diễn ra vào đúng thời
điểm đó.
Các kỹ thuật khẵng định hai giai đoạn (Lampson) hay ba giai đoạn (Bernstein)
được phát triển.
Ví dụ :

chưa. Khi mọi Việc đã tốt, nó khẵng
định cho tiến trình NSD biết là giao
dịch đã kết thúc. Các list đích được đảm
bảo chắc chắn nhờ cơ chế bộ nhớ cứng.
I.3.4 Quản lý gắn bó các giao dịch
Bây giờ, ta hãy xem xét một hệ, trong đó các đối tượng được phân tán trên nhiều
trạm, không có các bản sao. Mỗi đối tượng chỉ tồn tại có một bản duy nhất.
Một giao dịch T
J
có thể tham chiếu đến các đối tượng nằm trên các trạm khác
nhau và do vậy bao gồm nhiều tác động thực hiện trên nhiều trạm. Như vậy, ta phải
xác định trên từng trạm S
i
một tiến trình P
ji
với nhiệm vụ thực hiện các tác động của
giao dịch T
j
trên S
i
. Các tác động được thực hiện trên các trạm khác nhau có thể tiến
hành theo kiểu song song.
Bây giờ ta hãy xem xét một tập hợp các giao dịch. Như trong phần I.2 đã chỉ ra,
ta cố gắng thực hiện các giao dịch với độ cực đại về song song giữa các tác động trong
điều kiện duy trì tốt trạng thái gắn bó của hệ. Áp dụng cơ chế then cài như đã trình bày
trong I.3.1 có thể là nguyên nhân dẫn đến bế tắc và thiếu thốn vô hạn. Đó là điều mà ta
cần phải tính đến. Nhưng trong thực tế, khả năng xuất hiện bế tắc là không đáng kể vì
mỗi một giao dịch xử lý một phần rất bé của tập hợp các đối tượng. Đó là điểm khác
nhau giữa hệ phân tán và hệ tập trung.
Ta sẽ được giới thiệu hai phương pháp triển khai các nguyên lý trong I.3.1.

I.3.4.2.1 Duy trì sự gắn bó
Nội dung cơ bản của phương pháp này dựa trên các nguyên lý sau đây :
1. Then cài ngầm định.
Bộ điều khiển cục bộ trên mỗi trạm S
i
áp đặt cho các tác động khác nhau trên trạm
và diễn biến theo một trật tự hóa hợp thức. Để làm Việc đó, cần phải chặn giao dịch T
j
hay nói chính xác là tiến trình P
ji
mà tiến trình này đang thực hiện trên S
i
. Tất cả diễn ra
cứ như mỗi một đối tượng được cài then bởi mỗi một giao dịch sử dụng, theo kiểu chia
xẻ trước khi đọc, theo kiểu loại trừ trước khi ghi; tất cả các mở then chỉ diễn ra sau khi
xong một giao dịch. Như thế, sự gắn bó của tập hợp các đối tượng được đảm bảo bằng
kết quả của I.3.1.3. Đó là trật tự hóa hợp thức của giao dịch hình thành tốt hai pha.
2. Phát hiện động các xung đột.
Hành I xung đột truy cập vào đối tượng diễn ra khi có hai giao dịch cố gắng thực
hiện các tác động không tương thích vào một đối tượng này. Các quy tắc tương thích là
các quy tắc của mô hình "đọc-hiệu chỉnh" trong phần I.3.1.2 đã được trình bày. Một
xung đột được phát hiện khi có ý định truy cập bởi một giao dịch T
2
vào một đối tượng
đã bị khóa ngầm định bởi giao dịch T
1
theo kiểu không tương thích. Vì lý do bế tắc mà
ta sẽ trình bày trong phần 2 sau đây, không nên để T
2
chờ cho đến khi T

1
và T
2
là hai giao dịch đang ở trong trạng thái xung đột để truy cập
vào một đối tượng chung e. T
1
đã thực hiện động tác đầu tiên trên e. Ta gọi các N(T
1
)
và N(T
2
) là các dấu kết hợp lần lượt với từng giao dịch khi khởi sự.
Khi diễn ra xung đột, Việc lựa chọn được thực hiện bằng bộ điều khiển của trạm
e được tiến hành như sau :
Nếu N(T
2
) < N(T
1
) thì < T
2
bị chặn >
nếu không < T
2
bị huỷ rồi được khởi sự
lại>
Chấm dứt nếu
Nói cách khác, nếu giao dịch T
2
là trước hơn, thì nó vẫn trong tình trạng bị chặn
cho đến khi T

 {v_doc(A)}
a
1
:= A
a
1
:= a
1
+ 10
 {v_doc(A)}
a
2
:= A
a
2
:= a
1
+ 5
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 18
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
 {v_viet(A)}
A := a
1
{giai_phong(A)}
 {v_viet(A)}
A := a
2
{giai_phong(A)}
Bây giờ ta hãy xem xét ý định thực hiện T
1

xung đột với T
1
. Việc sử dụng thuật toán
kéo theo sự huỷ bỏ T
2
.
5
T
1
được mở chặn và thực hiện dãy  và
không có xung đột vì Việc huỷ bỏ T
2
đã
huỷ bỏ luôn Việc chặn A bởi T
2
.
6
T
2
được thực hiện lại công Việc của mình
ngay từ đầu và thực hiện liên tục  và .
Hiệu ứng tổng quát của Việc thực hiện này cuối cùng chính là hiệu ứng của Việc
trật tự hóa theo kiểu tuần tự, cho nên có thể coi là hợp thức theo dãy .
I.3.5 Kết luận
Trong hệ phân tán, sự hiểu biết không hoàn toàn đầy đủ và chậm trể các thông
tin không phải cục bộ dẫn đến cần phải quản lý chặt chẽ hơn Việc truy cập đến các đối
tượng. Những vấn đề kỹ thuật này được đặt ra, song nếu không giải quyết triệt để, đôi
khi làm thiệt hại đến hiệu quả hoạt động chung của hệ. Như vậy, nếu ta sử dụng các
giao dịch hai pha, Việc dự phòng bế tắc bằng phương pháp gửi các thông điệp có thể
dẫn đến làm chậm trễ các then cài có lợi (vô hại); điều đó làm hạn chế khả năng song

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
{Thuật toán 2.1. Bộ quản lý khoá cơ bản (Basic LM)}
declare-var
msg : Message
dop : Dbop
Op : Operaeion
x : Dataltem
T : TransactionId
pm : Dpmsg
res : Dataval
SOP : Opset
begin
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 20
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
repeat
WAIT(msg)
case of msg
Dbop:
begin
Op ← dop.opn
x ← dop.da ta

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 { 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 SOP }
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 21
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
đặt các khoá trên lu cho các thao tác trong SOP
for tất cả các phép toán trong SOP do
gởi mỗi thao tác đến bộ xử lý dữ liệu
end-for
end-if
end
end-case
until forever
end. {Basic LM}
II.2 - NHỮNG ĐIỂM CẦN CẢI TIẾN
Thuật toán khoá được cho trong thuật toán 2.1 vừa được trình bày không đồng bộ
hoá chính xác các thực thi giao dịch. Điều này là do khi tạo ra các lịch biểu khả tuần
tự, các thao tác khoá và giải phóng khoá cũng cần phải được điều phối. Chúng ta minh
hoạ nó bằng ví dụ sau:
Ví dụ:
Xét hai giao dịch sau đây:
T
1
: Read(x) T
2
: Read(x)
x ← x + 1 x ← x * 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 thực
hiện tương ứng là 102 và 38 nếu T
1
thực hiện trước T
2
, hoặc là 101 và 39 nêu T
2
thực
hiện trước T
1
. Tuy nhiên, kết quả thực hiện S cho ra giá trị của x và y lần lượt là 102 và
39. Điều đó chứng tỏ S không khả tuần tự.
Vấn đề lịch biểu S trong ví dụ này là, thuật toán khoá chốt đã giải phóng các

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 đồ khoá loại này được trình bày trong hình sau đây.
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 23
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
Hình 2.3. Biểu đồ khoá hai pha nghiêm ngặt.
Bộ quản lý khoá 2PL nghiêm ngặt chỉ sửa lại một ít trong Thuật toán 2.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ỏ. Toàn bộ thuật
toán 2PL nghiêm ngặt được trình bày trong Thuật toán 2.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 2.3.
Thuật toán 2.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
pm : Dpmsg
res : Dataval
SOP : Opset
begin
repeat
WAIT(msg)
case of msg
Dbop:
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 24
Tiểu luận: Lập trình mạng GVHD: PGS.TS. Lê Văn Sơn
begin

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 SOP }
Người thực hiện: Đoàn Cường,Võ Lê Đức Huy KHMT 11 Trang 25