Lập trình mạng
Lời mở đầu
Phan Thị Ánh Sao K24-KHMT Trang 1
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.
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 là JDK 1.6, đồng thời khai thác bộ thư Iện hỗ trợ lập trình
phân tán được xây dựng sẳn trong bộ ngôn ngữ này là RMI.
Về mặt thuật toán: Thuật toán sử dụng trong chương trình này là
“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”.
Trong phạm vi của tiểu luận này, chương trình được cài đặt demo
trên 3 server, tuy nhiên chúng ta có thể cài đặt trên hệ thống gồm nhiều
server. Chương trình cũng bao gồm một công cụ gọi là module monitor
nhằm giám sát Việc cập nhật dữ liệu giữa các server, nhằm đánh giá tính
gắn bó dữ liệu giữ liệu giữa các server với nhau.
Cuối cùng, tôi mong muốn nhận được các ý kiến đóng góp, bổ sung
của quý thầy và các bạn. Xin chân thành cảm ơn!
Lập trình mạng
PHẦN I: LÝ THUYẾT
I.1 Đặt vấn đề:
Bây giờ, ta hãy nghiên cứu một ví dụ cụ thể về Việc quản lý các tài khoản của một
ngân hàng. Mỗi một người mở tài khoản tại ngân hàng sẽ được lưu trữ trong 1 bản ghi của
CSDL. Các trường của bản ghi này bao gồm họ và tên, địa chỉ, điện thoại và một khoá
duy nhất (mã số) cho người đó. Mã số đóng vai trò con trỏ đến CSDL khác chứa các lần

Phan Thị Ánh Sao K24-KHMT Trang 2
Lập trình mạng
Nếu A >= P thì
A := A - P (a)
B := B + P (b)
nếu không
<Xử lý theo kiểu séc không có tiền bảo chứng>
{Không cập nhật các tài khoản}
Kết thúc nếu
Theo thuật toán thể hiện bằng đoạn chương trình trên, ta cần lưu ý hai điểm sau
đây :
1. Giả sử rằng ta thực hiện đồng thời hai séc trích từ A hay rót vào B. Việc cập nhật
thông tin trên mỗi tài khoản không thể tiến hành theo kiểu tùy ý mà phải đảm bảo loại trừ
tương hổ ở mức tài khoản. Việc loại trừ đó có thể thực hiện theo các kiểu khác nhau, một
trong các kiểu đơn giản nhất là loại trừ ở mức toàn CSDL và hệ quả là loại bỏ các phép
song song. Có thể áp dụng loại trừ ở mức từng tài khoản riêng biệt.
2. Giả sử rằng bộ xử lý thực hiện giao dịch bị rơi vào trạng thái không làm Việc được
tại thời điểm giữa a và b. Tài khoản A đã được trừ trong khi B còn chưa được cộng. Nói
cách khác, đặc tính P1 không thể đảm bảo được gì hơn, nếu dừng lại ở đây. Ta cần phải
bổ sung thêm cho hệ một đặc tính nữa nhằm vào điều vừa nêu. Đó là sau khi thực hiện
một giao dịch hoặc là tất cả các cập nhật đều được tiến hành hoặc là trạng thái các tài
khoản không thay đổi.
Như vậy, lưu ý thứ 2 cho phép ta đảm bảo được tính gắn bó dữ liệu trong điều kiện
có sự cố. Đó chính là đòi hỏi quan trọng đối với toàn hệ trong Việc truy cập thông tin.
Bây giờ, ta giới thiệu một loại giao dịch mới. Đó là giao dịch kèm theo tỷ lệ lợi
nhuận tiền gửi t có nghĩa là sau một khoản thời gian nào đó số dư này được tính tăng lên
bằng cách cộng số dư với lợi nhuận ngân hàng.
Ta ký hiệu U - giao dịch mới
T - các giao dịch chuyển khoản
và, bây giờ, các ràng buộc toàn vẹn của hệ là :

thể. Nếu trước khi thực hiện hai giao dịch A = 1 000, B = 2 000 và nếu
t = 0.01 và P = 500, thì sau khi thực hiện chúng ta có A + B = 3300, trong khi đó ta lại có
A + B = 3250. Ta đã làm sai giá trị vốn cần có của chúng.
Ví dụ trên cho ta thấy một điều quan trọng khi thực hiện nhiều giao dịch song song
có thể dẫn hệ thống đến trạng thái không gắn bó. Do vậy, cần phải có các giải pháp khắc
phục tình hình đó và đây cũng chính là nội dung cốt lõi mà ta sẽ nghiên cứu liền sau đây.
I.2 Sự gắn bó thông tin
I.2.1 Các điều kiện giả định và thực tế
Ta có một tập hợp thông tin nào đó có thể được truy cập bởi một tập hợp các tiến
trình. Số lượng các đối tượng thông tin có thể truy cập được và số lượng các tiến trình có
nhu cầu thông tin là con số cố định. Hệ này phát triển rời rạc theo thời gian; giữa các
điểm quan sát (hay còn gọi là điểm xác định), ta có thể nhận biết được trạng thái thực của
Phan Thị Ánh Sao K24-KHMT Trang 4
Lập trình mạng
chúng, có nghĩa là các giá trị của các đối tượng và ngữ cảnh thực hiện của các tiến trình.
Hệ kiểu như vậy hoạt động với độ ổn định tuyệt vời.
Các điều kiện giả định này so với hệ thực tế có những điểm khác nhau căn bản sau
đây :
STT So sánh
1
Các đối tượng và các tiến trình có thể được tạo
lập và huỷ bỏ có tính chất động trong suốt quá
trình tồn tại của hệ.
2
Các đối tượng và các tiến trình có thể được phân
tán trên các trạm khác nhau liên hệ với nhau qua
hệ thống Iễn thông. Do vậy, ta không thể xác định
trạng thái thời điểm của hệ vì lý do độ trễ đường
truyền giữa các trạm và tính không tương thích
giữa các điểm quan sát trong các trạm đó. Để hiểu

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
hiệu ứng của dãy (A; B) hoặc là (B; A).
Ở mức hệ thống, ta có thể nói rằng các tác động là phần tử nhỏ nhất không thể chia cắt
được nữa.
Ví dụ :
Trong hệ thống quản lý tài khoản ngân hàng, mỗi số dư tài khoản được thể hiện bằng
một bản ghi. Ta cần lưu ý rằng :
1. Phép chuyển giá trị từ tài khoản này sang tài khoản khác được xem như là một tác
động.
2. Đọc và ghi một bản ghi là các tác động, nếu hệ quản lý các tập tin đảm bảo tính
không chia cắt được của chúng.
Cho một tập hợp giao dịch M = {T
1
, T
2
, , T
n
} lần lượt được thực hiện bởi các tiến
trình độc lập p
1
, p
2
, , p
n
. Việc thực hiện tuần tự (có nghĩa là thực hiện tất cả các giao dịch
của M theo kiểu nối đuôi nhau và tuân thủ một trật tự nào đó. Sự gắn bó của hệ được bảo
toàn, theo định nghĩa, bằng Việc thực hiện riêng biệt từng giao dịch. Do vậy, nó cũng
được bảo toàn trong chế độ thực hiện tuần tự của M.
Nếu, vì lý do hiệu quả, nhiều giao dịch được thực hiện song song, thì sự gắn bó

1
= (a
11
, a
12
, a
13
, a
14
) và T
1
= (a
21
, a
22
, a
23
). Một trật tự hóa (T
1
, T
2
) được thể hiện ở
ví dụ sau đây :
S = a
21
, a
11
, a
12
, a

:

và S
3
thể hiện một trật tự hoá như sau :
Phan Thị Ánh Sao K24-KHMT Trang 7
Lập trình mạng

Ta nhận thấy dễ dàng là S
2
có cùng hiệu ứng với trật tự hóa tuần tự S
3
, trong khi đó
S
1
lại khác. Trong S
2
và S
3
các cập nhật lần lượt của A và B đều được thực hiện theo cùng
một trật tự, còn trong S
1
trật tự cập nhật B bị đảo ngược.
Ví dụ này cho ta thấy sự quan trọng của Việc đảm bảo trật tự khi cập nhật thông
tin.
Ví dụ 2 :
Hãy xem xét hai giao dịch sau đây :
T
1
: C := 3 và T

tt
, nếu hai điều kiện sau đây
được triển khai :
Điều kiện 1 :
Để cho mỗi đối tượng e, các cập nhật biểu hiện trong cùng một trật tự trong S và S
tt
.
Điều kiện 2 :
Phan Thị Ánh Sao K24-KHMT Trang 8
Lập trình mạng
Hãy xem xét hai cập nhật kế tiếp nhau của một đối tượng e trong số các trật tự hóa, và
các cập nhật tương ứng của e trong trật tự hóa khác. Giữa hai cập nhật này, ta tham khảo
cùng các đối tượng trong hai trật tự hóa này trong cùng trật tự hay không.
Lưu ý 1 :
Các điều kiện nêu trên là các điều kiện đủ cho Việc đánh giá tương đương.
Lưu ý 2 :
Ta chỉ có thể hoán vị, không thay đổi hiệu ứng của một trật tự hóa, hoặc là các thao tác
đọc đối tượng có tính chất liên tiếp hoặc là các thao tác gán các đối tượng khác nhau một
cách liên tục.
Cả hai điều kiện vừa nêu là rất mạnh trong Việc nghiên cứu tiếp tục sau này.
Để cho trật tự hóa S, ta định nghĩa một quan hệ phụ thuộc giữa các giao dịch.
Cho T
1
và T
2
là hai giao dịch của M, e là đối tượng của hệ. Ta nói rằng T
2
phụ
thuộc T
1

tuần tự, đồ thị này không có vòng lặp (thực tế, nếu (T
1
, e, T
2
), thì T
1
trước T
2
trong trật tự
tuần tự).
Để cho hai trật tự hóa có cùng một hiệu ứng, thì điều kiện đủ là chúng phải có
cùng quan hệ phụ thuộc.
Do vậy, điều kiện đủ cho sự gắn bó của một trật tự hóa có thể phát biểu như sau.
Một trật tự hóa là gắn bó, nếu nó có cùng quan hệ phụ thuộc với một trật tự tuần tự.
Chú ý :
Điều kiện cần này cũng có thể trở thành đủ trong một trường hợp đặc biệt mà trong
thực tế ta thường hay gặp. Đó chính là trường hợp mà toàn bộ đối tượng được cập nhật
bằng cách tham chiếu trước thời điểm đó bởi cùng một giao dịch.
Ví dụ :
Các đồ thị phụ thuộc tương ứng với các trật tự hóa S
1
, S
2
và S
3
của ví dụ 1 là :
Phan Thị Ánh Sao K24-KHMT Trang 9
Lập trình mạng
(S
1

1
)
C
T 2T 1
(S'
2
)
C
T 2T 1
Hình I-6. Đồ thị ứng với hai giao dịch S'
1
và S'
2
.
Bây giờ, ta hãy kiểm tra các phương tiện đảm bảo một tập hợp các giao dịch thực
hiện theo một trật tự hóa gắn bó.
I.3 Triển khai giao dịch tôn trọng sự gắn bó
Cho một tập hợp các giao dịch M = {T
1
, T
2
, , T
n
}. Một trật tự hóa của tập hợp các
tác động thành phần sẽ tương ứng với Việc thực hiện hoàn toàn các giao dịch. Việc thu
được một trật tự hóa gắn bó chỉ có thể thành công khi áp dụng các ràng buộc trên trật tự
thực hiện các tác động. Nguyên lý của phương pháp là ở chổ làm chậm một tác động nào
đó cho đến thời điểm mà sự thực hiện của nó không còn có nguy cơ phá huỷ sự gắn bó
của trật tự hóa (bằng cách chặn tiến trình hiện hành).
Hiệu ứng của bộ làm chậm này (cơ chế then cài) đã được trình bày trong các phần

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 khác
muốn truy cập, ngược lại thì Việc truy cập được tiến hành theo kiểu tương tranh.
Để đảm bảo điều đó luôn luôn được thực hiện, người ta cho phép tiến hành cài
then một đối tượng trước khi Việc sử dụng nó có hiệu lực.
Một giao dịch có thể thực hiện 3 hàm nguyên thuỷ trên đối tượng e :
STT Tên hàm Thuyết minh
1 v_doc(e) Sử dụng khi muốn có được quyền đọc e
theo kiểu chia xẻ.
2 v_viet(e) Sử dụng khi muốn có được quyền đọc và
viết vào e theo kiểu loại trừ.
3 giai_phong(e
)
Giải phóng đối tượng e. Giả sử trước đó
đã được cài then bởi cùng giao dịch này.
Hai hàm nguyên thuỷ sau đã được trình bày trong các chương trước.
Nói một cách chính xác hơn, một giao dịch gọi là phát triển, nếu :
1. Một phép toán chỉ được thực hiện trên một đối tượng sau khi đối tượng đó đã
được cài then bởi giao dịch theo kiểu tương thích với phép toán đó.
2. 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 xẽ.
Phan Thị Ánh Sao K24-KHMT Trang 11
Lập trình mạng
3. 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ự hóa có khả năng được
thực hiện.
Một trật tự hóa được gọi là hợp thức nếu :
1. Đối tượng được một giao dịch cài then theo kiểu chia xẻ 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.
2. 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

Ví dụ 1 :
Hãy truy cập vào tập hợp các đối tượng.
Giả sử rằng ta muốn đọc các giá trị của một tập hợp các đối tượng và quy ước rằng
các giá trị này kiểm tra các ràng buộc toàn vẹn. Lúc này, ta cần phải cài then theo kiểu
chia xẻ cho mỗi một đối tượng trước khi đọc, mở then diễn ra ở cuối của giao dịch này.
Một phép như vậy gọi là đọc gắn bó của tập hợp các đối tượng.
Như thế, giao dịch được thể hiện như sau :
v_doc(a)
v_doc(b)
doc(a)
doc(b)
v_doc(c)
doc(c)
giai_phong(a)
giai_phong(b)
giai_phong(c)
là giao dich đọc gắn bó của tập hợp {a, b, c}.
Ví dụ 2 :
Trở lại với ví dụ trong được mô tả trong ví dụ I.1. Đâ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 T
3
v_viet(A)
A := A - P
1
giai_phong(A)

1
và U và T
2
và U.
S
1
(T
1
,U) S
2
(T
2
,U)
Phan Thị Ánh Sao K24-KHMT Trang 13
Lập trình mạng
T
11
: v_viet(A)
T
12
: A := A - P
1
T
13
: giai_phong(A)
U
1
: v_viet(A)
U
2

T
23
: v_viet(B)
T
24
: giai_phong(A)
U
1
: v_viet(A)
U
2
: A := (1 + t) x A
T
25
: B := B + P
2
T
26
: giai_phong(B)
U
5
: v_viet(B)
U
4
: B := (1 + t) x B
U
5
: giai_phong(B)
U
6

Cơ chế điều khiển các tranh chấp truy cập cục bộ
vào các đối tượng và đảm bảo tôn trọng tính vẹn
toàn của các đối tượng cục bộ này.
3 Cơ chế có khả năng xử lý các bế tắc và thiếu thốn
Phan Thị Ánh Sao K24-KHMT Trang 14
Lập trình mạng
vô hạn, hậu quả của Việc huỷ bỏ các giao dịch.
4 Cơ chế phục hồi các giao dịch đã bị huỷ bỏ hay
xử lý các sự cố.
I.3.3 Xử lý các sự cố
Ta giả sử rằng các bộ xử lý và bộ nhớ cấu tạo nên các trạm là nguyên nhân chính của
các sự cố làm ngắt quảng quá trình thực hiện các tiến trình. Các hệ thống Iễn thông cũng
có thể là nơi diễn ra các sự cố làm mất hẵn hay chồng chéo các thông điệp.
Ta xét sự gắn bó thông tin không chỉ trong các điều kiện thuận lợi như đã nêu trước
đây, mà còn tính đến các yếu tố mới và cũng xét đến các công cụ cho phép đảm bảo cho
sự gắn bó này.
Nếu một tiến trình p bị sự cố trong lúc thực hiện một giao dịch T, thì trạng thái của hệ
xuất phát từ Việc thực hiện từng phần đó chắc chắn sẽ không còn gắn bó.
Một cơ chế cho phép duy trì sự gắn bó trong môi trường phân tán có sự cố phải là :
STT Phải thực hiện
1 Giao dịch T bắt buộc phải được thực hiện một
cách trọn vẹn.
2 Nếu có sự cố diễn ra, thì bắt buộc nó phải quay trở
lại điểm xuất phát.
Muốn thực hiện những điều vừa nêu trong bảng trên, người ta đòi hỏi giao dịch phải
có các đặc tính toàn vẹn như sau :
STT Đặc tính
1
Nếu một tiến trình bị sự cố trước khi kết thúc T
nhưng lại sau các thao tác thay đổi cần thiết của T,

DFS là hệ quản lý các tập tin được thành lập cho hệ điều hành mạng ETHERNET. Các
chức năng truy cập vào các tập tin được tiến hành thông qua các tiến trình server. Các
tiến trình server chịu trách nhiệm trao đổi các thông điệp với các tiến trình NSD. Ta nhận
thấy các nguyên lý toàn vẹn và khẵng định ở đây có nhiều mức khác nhau :
Phan Thị Ánh Sao K24-KHMT Trang 16
Lập trình mạng
STT Tên gọi Thuyết minh
1 Ghi tập tin
Tại mức ghi file, phép toán thực hiện trên "bộ nhớ cứng" có nghĩa
là hoặc là thực hiện trọn vẹn phép toán, hoặc là không thực hiện gì
cả. Bộ nhớ cứng được thực hiện bằng cách ghi liên tục hai bản
thông tin, trong đó một cho dự trữ.
2 Giao dịch
Tại mức giao dịch, các thay đổi thông tin không được thực hiện tức
thì, mà được ghi trong một list đích. Một phép toán cho phép
chuyển tập hợp các thay đổi này sang các đối tượng, như thế là
giao dịch khẵng định. Như vậy, list đích hoặc là toàn bộ hoặc là
không có gì.
3 Server
Cuối cùng, khi giao dịch làm giống nhau cho các server, thì tại mỗi
server đều phải có list đích của mình. Một trong các server phải là
server chỉ huy cho giao dịch này và kiểm tra toàn bộ các list đích
đã được chuẩn bị tốt hay 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ác đối tượng phân tán trên nhiều trạm, ta cần phải xác định một trật tự giữa hai tác động
trên hai trạm khác nhau.
Đặc biệt là kỹ thuật dấu, cho phép áp dụng tại đây.
Vấn đề còn lại là phải giải quyết sao cho không diễn ra tình trạng bế tắc. Có thể áp
dụng phương pháp dự phòng dựa trên cơ sở các thông điệp như trong phần III.3. Một
phương pháp như vậy đòi hỏi phải có sự hiểu biết nhất định về các đối tượng xử lý từ
trước bằng một giao dịch nào đó và không được phép định nghĩa động của các đối tượng
này; trong khi đó, ràng buộc này có thể được chấp nhận.
Trong các trường hợp tổng quát, Việc dự phòng các bế tắc là không thể được. Do
vậy, cần phải chấp nhận các xung đột truy cập diễn ra và xử lý chúng chỉ sau khi phát
hiện được. Cách này đòi hỏi ta phải huỷ bỏ các giao dịch. Việc duy trì trạng thái gắn bó
của hệ trên các đối tượng xử lý chỉ đạt được bằng cách sử dụng có hệ thống các kỹ thuật
thích hợp. Đó chính là phương pháp phát hiện động mà ta sẽ giới thiệu sau đây.
I.3.4.2 Thuật toán duy trì sự gắn bó tránh bế tắc và thiếu thốn
Thuật toán này được mô tả trong các ấn phẩm của Rozenkrantz. Các phép toán then
cài và mở then không được chỉ ra trong các giao dịch. Một bộ điều khiển cục bộ trong
từng trạm phân tích tất cả các truy cập vào đối tượng và thực hiện tự động các phép toán
này khi cần thiết theo nguyên lý hai pha. Các đối tượng xử lý bởi các giao dịch không cần
phải biết từ trước.
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

được thực hiện trên các bản sao đối tượng. Nếu giao dịch bị huỷ, một thông điệp huỷ
được gửi đi cho tất cả các trạm chứa các đối tượng thay đổi và các bản sao bị huỷ bỏ.
Trường hợp ngược lại, giao dịch kết thúc bình thường, thì một thông điệp khẵng định
được gửi cho tất cả các trạm đó và lúc này các bản sao của các đối tượng thay đổi được
phép thay thế các bản gốc.
I.3.4.2.2 Huỷ bỏ bế tắc và thiếu thốn vô hạn
Ngay khi ta chặn các giao dịch tác nghiệp trên các đối tượng chung hoặc bằng then
cài hay ngầm định, ta có thể làm phát sinh các rủi ro về bế tắc.
Một bế tắc được loại bằng cách huỷ bỏ hoàn toàn một trong các giao dịch gây nên
xung đột, nhưng nếu ta chọn theo kiểu ngẫu nhiên để huỷ bỏ, thì ta lại gặp phải một
trường hợp rắc rối về kỹ thuật khác là một hay một số giao dịch nào đó sẽ rơi vào trạng
thái chờ vô hạn.
Nhằm tránh hiện tượng thiếu thốn vô hạn đó, tập hợp các giao dịch được hoàn toàn
sắp xếp theo một trong các phương pháp đã nghiên cứu trong chương IV và chương V
như là các dấu chẳng hạn. Khi có xung đột diễn ra, ta chọn lựa giao dịch thích hợp một
cách có hệ thống theo thuật toán dựa trên trật tự đó.
Trong thiết kế hệ thống phân tán, người ta thường sử dụng hai chiến lược chọn lựa
giao dịch. Sau đây, ta sẽ mô tả một trong các phương pháp ấy gọi là phương pháp wait-
die system.
Giả sử rằng 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

Ta hãy minh họa hoạt động của thuật toán bằng Việc thực hiện hai giao dịch :
Giao dịch T
1
Giao dịch T
2
A := A + 10 A := A + 5
Các giao dịch này có thể được phân tích để phát hiện ra các truy cập sơ đẳng vào
đối tượng chia xẻ A. Giả sử rằng a
1
và a
2
là hai biến cục bộ tương ứng với các tiến trình
thực hiện T
1
và T
2
. Để làm sáng tỏ vấn đề xung đột truy cập, ta cũng phải cho xuất hiện,
bằng cách thuyết minh, các phép toán then cài ngầm định :
Giao dịch T
1
Giao dịch T
2
 {v_doc(A)}
a
1
:= A
a
1
:= a
1

1 T
1
thực hiện dãy 
2 T
2
thực hiện dãy  và không có xung đột
diễn ra.
3
T
1
có ý định thực hiện dãy  và bước vào
xung đột với T
2
. Việc sử dụng thuật toán
kéo theo Việc chặn T
1
.
4
T
2
có ý định thực hiện dãy  và bước vào
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á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
opn: Operation
tid: TransactionId
result: DataVal
Scmsg: một bộ ba gồm
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
{Thuật toán 2.1. Bộ quản lý khoá cơ bản (Basic LM)}

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:
Phan Thị Ánh Sao K24-KHMT Trang 23
Lập trình mạng
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 { 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 }
đặ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

(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
1
(y), lr

khoá sau khi nó đã giải phóng một trong các khoá của nó. Điều đó nói rằng một giao dịch
không được giải phóng khoá cho đến khi nó đảm bảo rằng không yêu cầu thêm khoá nữa.
Các thuật toán 2PL thực hiện các giao dịch qua hai pha. Mỗi giao dịch có một pha tăng
trưởng (growing phase), trong pha này nó nhận các khoá và truy xuất các mục dữ liệu, và
có một pha thu hồi ( shrinking phase), là giai đoạn nó giải phóng các khoá (Hình 2.2).
Điểm khoá (locking point) là thời điểm giao dịch đã nhận được tất cả các khoá nhưng
chưa bắt đầu giải phóng bất kỳ khoá nào. Vì thế điểm khoá xác định cuối pha tăng trưởng
và khởi điểm pha thu hồi của một giao dịch.
Phan Thị Ánh Sao K24-KHMT Trang 25