TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
KHOA CÔNG NGHỆ THÔNG TIN

TIỂU LUẬN MÔN HỌC
HỆ TIN HỌC PHÂN TÁN
Đề tài:

CÁC PHƯƠNG PHÁP CUNG CẤP SỬ DỤNG
TRẠNG
THÁI TỪNG PHẦN VÀ PHƯƠNG PHÁP DỰ
PHÒNG BẾ TẮC
HVTH: Nguyễn Văn Hùng Trang i
LỜI MỞ ĐẦU
Hệ tin học phân tán là hệ thống xử lý thông tin bao gồm nhiều bộ xử lý hoặc bộ vi
xử lý nằm tại các vị trí khác nhau và được liên kết với nhau thông qua phương tiện viễn
thông dưới sự điều khiển thống nhất của một hệ điều hành. Hệ tin học phân tán rất đa
dạng, đa diện, phức tạp về mặt cấu trúc, tập hợp bao gồm các bộ xử lý hoặc bộ vi xử lý
với bộ nhớ và đồng hồ nhịp độc lập, các bộ xử lý không sử dụng chung bộ nhớ và đồng
hồ. Như vậy, mỗi một hệ xử lý thông tin thành phần của hệ tin học phân tán bao gồm một
hay nhiều bộ xử lý và bộ nhớ cục bộ. Trong hệ phân tán, hệ xử lý thông tin thành phần
phải được thiết kế sao cho về cấu trúc, số lượng và dung lượng có thể cho phép thực hiện
một cách trọn vẹn các chức năng mà nó phải đảm nhận.
Hiện nay, với sự phát triển nhanh chóng của công nghệ và đặc biệt là số lượng
người sử dụng ngày cang tăng, hệ phân tán ngày càng được ứng dụng rộng rãi hơn và phổ
biến hơn trong các lĩnh vực: hệ kinh doanh từ xa, đăng ký vé máy bay, đăng ký tour du
lịch, … Đố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 tăng năng lực xử lý thông tin của hệ thống và đảm
bảo yêu cầu an toàn dữ liệu. Vấn đề đặt ra là phải đảm bảo tính đồng bộ, gắn bó dữ liệu,

phát hiện và xử lý các bế tắc phát sinh trong quá trình hoạt động của hệ thống.
Để tìm hiểu rõ hơn về vấn đề bế tắc và thuật toán dự phòng bế tắc của Lomet, bản
thân tôi đã được PGS TS Lê Văn Sơn - Hiệu trưởng trường Đại học Sư phạm Đà Nẵng
giao đề tài tiểu luận “Các phương pháp cung cấp sử dụng trạng thái từng phần và
thuật toán dự phòng bế tắc. Xây dựng chương trình giao dịch lồng ghép để thực hiện
việc đăng ký du lịch trên hệ th ống gồm 3 Servers quản lý tài nguyên”. Trong thời
gian thực hiện đề tài, tôi đã nhận được sự giúp đỡ nhiệt tình của Thầy Lê Văn Sơn, cùng
với sự cộng tác của đồng nghiệp và đặc biệt là sự quan tâm giúp đỡ của các học viên trong
lớp cao học Khoa học Máy tính 2008 - 2011.
Đà nẵng, tháng 07 năm 2009
HVTH: Nguyễn Văn Hùng Trang ii
HVTH: Nguyễn Văn Hùng Trang iii
Báo cáo tiểu luận hệ tin học phân tán
A. LÝ THUYẾT
CÁC PHƯƠNG PHÁP CUNG CẤP SỬ DỤNG TRẠNG THÁI
TỪNG PHẦN
I. Một số khái niệm
Trong phần này, sẽ đề cập cách giải quyết các vấn đề đặt ra và trình bày các giải
pháp thể hiện dưới dạng các giải thuật riêng cho hệ phân tán.
Trong hệ phân tán, thông thường người ta hay sử dụng khái niệm giao dịch như là
thực thể sử dụng các tài nguyên chẳng hạn.
Giao dịch là phép toán hợp thành một logic hoàn chỉnh mà việc triển khai nó có
thể dẫn đến thực hiện một tiến trình duy nhất hay nhiều tiến trình được định vị trên các
trạm khác nhau.Trường hợp dẫn đến thực hiện nhiều tiến trình trên các trạm ở xa là đối
tượng mà ta cần phải quan tâm nghiên cứu trong chương này.
Một tiến trình nào đó cần sử dụng tài nguyên để phát triển công việc của mình
phải yêu cầu bộ cung cấp một cách hợp thức bằng cách gửi thông điệp yêu cầu . Như thế,
rõ ràng là một tiến trình có nhu cầu tài nguyên sẽ bị treo chừng nào tài nguyên đó còn
chưa được giải phóng hay chưa được cung cấp cho nó.
Bộ cung cấp có thể áp dụng nhiều kiểu cung cấp khác nhau như tiến trình duy

nhất, tập hợp các tiến trình, tập hợp các thủ tục,…. Các thông điệp yêu cầu sử dụng tài
nguyên cũng có thể có các dạng khác nhau như gọi thủ tục, thông báo, thực hiện các lệnh
đặc biệt,….
Một yêu cầu được thoả mãn bởi bộ cung cấp tài nguyên cho tiến trình đề nghị với
điều kiện là yêu cầu đó phải tuân thủ các quy tắc nhất định.
Có hai điều kiện làm cho tiến trình mất khả năng sử dụng tài nguyên đã được
cung cấp trước đó. Đó là:
STT Tên gọi Điều kiện
1 Giải phóng Tiến trình phát tín hiệu ngừng sử dụng tài nguyên
2 Thu hồi Sự lấy lại tài nguyên đã được cung cấp cho tiến trình. Bộ cung
cấp tài nguyên sẽ tiến hành công việc này
Trong hệ, hoạt động của một tập hợp các tiến trình trên một tập hợp các tài
nguyên dùng chung được xem là tuyệt vời, nếu không để xảy ra bế tắc và thiếu thốn tài
nguyên vĩnh viễn.
Bế tắc hay còn gọi là khoá tương hỗ là sự kẹt chéo lẫn nhau có tính chất sống còn
của các tiến trình. Bế tắc diễn ra khi hai tiến trình đang sử dụng hai tài nguyên lại phát yêu
cầu về nhu cầu sử dụng tài nguyên mà tiến trình kia còn đang sử dụng.
Hình vẽ 1.1 sau đây cho phép chúng ta hình dung vấn đề một cách rõ ràng hơn.
Theo hình vẽ này, ta có 4 tài nguyên T
1
, T
2
, T
3
và T
4
và có 3 nhu cầu tài nguyên là Tr
1
, Tr
2

và Tr
3.
Cả ba tiến trình này đang ở trong tình trạng bế tắc. Tiến trình Tr
2
chờ tài nguyên T
3
HVTH: Nguyễn Văn Hùng Trang 1
Báo cáo tiểu luận hệ tin học phân tán
do Tr
3
đang chiếm giữ.Tiến trình Tr
3
chờ tài nguyên T
2
được giải phóng bởi Tr
1
và
Tr
3
.Thêm vào đó, tiến trình chờ tiền trình Tr
2
giải phóng T
1
.
Lúc này, ta thấy có hai chu trình kín trong đồ thị là:
Tr
1
– T
1
– Tr

2
– T
3
– Tr
3
– T
2
– Tr
1
và
Tr
3
– T
2
– Tr
2
– T
3
– Tr
3
Hình 1.1. Đồ thị cung cấp tài nguyên bị bế tắc
Thiếu tài nguyên vĩnh viễn là sự chờ đợi bất tận của một tiến trình mà yêu cầu của
nó trễ đến mức không thể xác định được. Nguyên nhân của hiện tượng vừa nêu có nhiều,
nhưng ta có thể chỉ ra ví dụ thường gặp là do sử dụng luật ưu tiên để cung cấp tài nguyên.
Một chiến lược cung cấp tài nguyên tồi cũng có thể là nguồn gốc huỷ hoại hiệu
năng hoạt động của hệ do các hiện tượng “sốc “ làm tăng các yêu cầu mà không được đáp
ứng của một số tài nguyên. Ví dụ như sự sụp đổ của hệ đa chương trình.
Để tránh các hiện tượng đó, bộ cung cấp tài nguyên cần phải đảm bảo chức năng
điều khiển
Ta có thể phân chia thành hai phương diện để nghiên cứu:

1. Phân tán các yêu cầu giữa các tài nguyên tương đương có khả năng thoả mãn.
Chức năng này gọi là phân phối tải. Trong hệ phân tán, nó cần phải tạo điều kiện để tránh
tình hình mà ở đó các yêu cầu đợi đến lượt được thoả mãn trên một trạm đầy, trong khi đó
các tài nguyên tương đương lại rỗi rãi trên các trạm khác.
2. Giới hạn số lượng các yêu cầu được phép cho một số tài nguyên. Việc đó có
thể thực hiện bằng cách hạn chế (tĩnh hay động) số các tiến trình hay số các giao dịch
được chọn (trúng tuyển) sử dụng toàn bộ hay từng phần tài nguyên.Ta gọi trường hợp này
là điều khiển tải tổng quát.
Tóm lại: Bộ cung cấp cần phải phân phối các tài nguyên trên cơ sở tuân thủ các
quy tắc sử dụng, tránh xảy ra bế tắc và thiếu thốn vô hạn, phân bố tải tương đối đồng đều
giữa các tài nguyên cùng loại(cùng có thể thoả mãn) và giới hạn nhu cầu nhằm duy trì hệ
thống hoạt động đạt mức hiệu quả nhất định.
HVTH: Nguyễn Văn Hùng Trang 2
T1 T3
Tr1 Tr2 Tr3
T2
T4
Báo cáo tiểu luận hệ tin học phân tán
II. Cung cấp tập hợp các tài nguyên. Vấn đề bế tắc
Trước hết, ta tìm hiểu một số thuật ngữ và khái niệm có quan hệ mật thiết với
những vấn đề sẽ sử dụng trong phần này.
Tiến trình p đưa ra yêu cầu cung cấp tài nguyên e để thực hiện phép toán cài then
có tính loại trừ v_loai_tru_th(e). Ngoại trừ một số trường hợp đặc biệt, tất cả các tài
nguyên đều được truy cập theo kiểu loại trừ. Nếu việc cung cấp hoán toàn hợp thức thì tài
nguyên này được trao cho p sử dụng. Ta nói rằng tài nguyên này đã được p cài then, nếu
không thì p bị treo và đương nhiên p không cài then được tài nguyên này.
Trong hệ phân tán, ta sẽ tập trung xem xét các giao dịch T
i
có thể sử dụng các tài
nguyên được định vị trên các trạm. Mỗi một giao dịch được triển khai nhờ một tập hợp

các tiến trình thể hiện là các đại diện của chúng trên các trạm khác nhau. Hai tiến trình của
cùng một giao dịch được định vị trên các trạm khác nhau có thể được thực hiện song
song. Nhằm thu hồi lại tài nguyên e trên trạm S
j
, giao dịch T
i
cho thực hiện phép toán
v_loai_tru_th(e) thông qua đại diện p
ij
của mình trên trạm này.
Ngoại trừ một số trường hợp đặc biệt, việc cung cấp diễn ra không có thu hồi.
Một tài nguyên bị khoá bởi một tiến trình không thể rút nó trở về được. Như thế, nó cần
phải được giải phóng bởi tiến trình này một cách tường minh nhờ vào phép toán mở then
cài mo_then(e).
Bế tắc có thể được giải quyết bằng cách dự báo và vòng tránh (gọi chung là dự
phòng) có nghĩa là tài nguyên được cung cấp theo kiểu có đề phòng trường hợp bế tắc.
Một phương pháp khác có liên quan đến vấn đề này là phát hiện và chữa trị có nghiã là
khi có sự cố thì quay trở về trạng thái trước đó.
Các thuật toán dự phòng, phát hiện và chữa trị được nghiên cứu cho trường hợp là
tất cả các tài nguyên đều được quản lý bởi bộ cung cấp duy nhất. Bộ cung cấp này tiếp
nhận tất cả các yêu cầu và biết rõ trạng thái của tất cả các tài nguyên.
Ta bắt đầu việc nghiên cứu trong phần này bằng cách nhắc lại các kết quả chủ yếu
của trường hợp nêu trên, trước khi phát triển các vấn dề về hướng tin học phân tán.
1. Các phương pháp sử dụng trong hệ tập trung
Phương pháp dự phòng
Phương pháp dự phòng đơn giản và thường hay sử dụng là phương pháp các
nhóm sắp xếp Havender.
Tư tưởng cơ bản của phương pháp này là các tài nguyên được sắp xếp theo các
nhóm con C1, C2, …Cn. Một tiến trình nào đó có thể thu hồi tài nguyên của nhóm C
i

với
i>1, nếu trước đó nó đã thu hồi tất cả các tài nguyên của nhóm cần thiết cho nó C
1
, C
2
, …
C
i
-
1
. Như thế, trật tự duy nhất của việc thu hồi các tài nguyên được xác định sẽ tránh được
bế tắc. Phương pháp này dẫn đến các tiến trình cần thu hồi trước (tạm ứng) các tài nguyên
của chúng và do vậy làm giảm khả năng thực hiện song song của hệ.
HVTH: Nguyễn Văn Hùng Trang 3
Báo cáo tiểu luận hệ tin học phân tán
Phương pháp phát hiện và chữa trị
Phương pháp Holt sử dụng một đồ thị trạng thái định hướng mà các nút là các tài
nguyên hay các tiến trình. Các cung tiến trình- tiến trình thể hiện các cung cấp đã được
thực hiện. Nếu có sự hiện diện của vòng lặp khép kín trong đồ thị này thì đó chính là biểu
hiện của tình trạng bế tắc.
Sau khi đã phát hiện bế tắc, vấn đề chữa trị được đặt ra, nhưng các phương pháp
này rất phức tạp, tốn kém. Hiện nay, thuật toán chữa trị đang được các nhà chuyên môn
quan tâm nghiên cứu và phát triển.
2. Phân tán chức năng cung cấp
Bây giờ, ta giả định rằng chức năng cung cấp không thể tin tưởng giao phó hoàn
toàn cho một bộ cung cấp duy nhất, mà được phân tán thành tập hợp các bộ cung cấp trên
các trạm khác nhau, trong đó mỗi bộ cung cấp chỉ quản lý các đối tượng cục bộ của trạm
đó mà thôi.
Tồn tại hai nhóm giải pháp cho vấn đề đặt ra:
Duy trì tính duy nhất của trạng thái tài nguyên

Biểu hiện duy nhất (thể hiện tính duy nhất) của trạng thái tài nguyên được chia sẻ
bởi tập hợp các bộ cung cấp. Biểu hiện này tuần hoàn giữa các trạm khác nhau dưới dạng
một thông điệp. Các trạm luân phiên đóng vai trò của bộ cung cấp các tài nguyên mà
mình đang chịu trách nhiệm quản lý. Giải pháp này loại bỏ tất cả các khả năng song song,
không loại bỏ khả năng mất thông điệp trạng thái, thiếu thốn tài nguyên một cách vô hạn.
Phân tán biểu hiện trạng thái và chức năng cung cấp
Có rất nhiều giải pháp có thể:
STT Giải pháp
1 Ta duy trì mỗi trạm một bản sao trạng thái tài nguyên tổng quát. Trong
trường hợp này, cần phải đảm bảo sự gắn bó hữu cơ giữa các bản sao.
2 Ta phân tán biểu hiện trạng thái trên các trạm, mỗi một trạm chỉ co trạng
thái của các tài nguyên cục bộ của mình.Các quyết định được đưa ra trên
các trạm khác nhau cần phải được phối hợp theo kiểu sao cho dữ liệu của
việc cung cấp phải được gắn bó với nhau.
3 Một phương pháp đầy ấn tượng là nhóm sắp xếp nhằm đảm bảo cho tất cả
các yêu cầu tài nguyên xuất phát từ các tiến trình đến được các bộ cung cấp
khác nhau theo một trật tự duy nhất được cố định từ trước.
Các phương pháp khác nhau mang tính năng động cao cho phép ra các quyết định
cung cấp tài nguyên xuất phát từ quan điểm từng phần (ngược với toàn phần) của trang
thái tài nguyên.
Trong các phần tiếp theo, ta sẽ được giơi thiệu lần lượt các vấn đề sau đây:
1. Nguyên lý được hiện bằng giải thuật dự phòng bế tắc cho trường hợp đầu tiên
vừa nêu theo kiểu sử dụng các bản sao trang thái tổng quát .
HVTH: Nguyễn Văn Hùng Trang 4
Báo cáo tiểu luận hệ tin học phân tán
2. Hai giải thuật toán cho các trường hợp sau; một cho dự phòng và một cho phát
hiện bế tăc được trình bày bằng cách sử dụng quan điểm tưng phần của trạng thái
toàn phần .
3. Các phương pháp cung cấp sử dụng trạng thái từng phần
Hai thuật toán mà ta sẽ giới thiệu sau đây rất thích hợp với môi trường phân tán.

Mỗi trạm chỉ quản lý các tài nguyên cục bộ của mình và các quyết định cung cấp được
đưa ra dựa trên thông tin cục bộ. Ta giới hạn về việc trình bày của mình cho mục đích khá
đơn giản. Đó là tất cả các tài nguyên đều được truy cập theo kiểu loại trừ. Các tài nguyên
chia sẻ sẽ là đối tượng xử lý của bài tập số 2 của chương này.
Thuật toán dự phòng bế tắc
Hai thuật toán mà ta sẽ giới thiệu sau đây là một trong những phiên bản của thuật
toán Lomet. Đây là phiên bản sử dụng trạng thái từng phần.
a) Vị trí của vấn đề:
Đây là một ví dụ minh hoạ các khó khăn trong khi ứng dụng vào hệ phân tán.
Ví dụ 1:
Hãy đánh giá 3 giao dịch T
1
, T
2
và T
3
sử dụng 3 tài nguyên e
1
, e
2
và e
3.
Ta ký hiệu
a_loai_tru_th() là phép toán thông điệp.
Giao dịch T
1
t
11
: a_loai_tru_th(e
1

, e
2
)
…….
t
12
: v_loai_tru_th(e1)
…….
t
13
: v_loai_tru_th(e2)
Giao dịch T
2
t
21
: a_loai_tru_th(e
2
, e
3
)
…….
t
22
: v_loai_tru_th(e2)
…….
t
23
: v_loai_tru_th(e3)
Giao dịch T
3

t
31
: a_loai_tru_th(e
3
, e
1
)
…….
t
32
: v_loai_tru(e3)
…….
t
33
: v_loai_tru_th(e1)
Ta giả sử rằng các tài nguyên e
1
, e
2
và e
3
được bố trí trên các trạm tương ứng S
1
,
S
2
và S
3
. Nếu trạm S
i

chỉ nhận thông cáo tương ứng với tài nguyên mà nó quản lý thì nó
HVTH: Nguyễn Văn Hùng Trang 5
Báo cáo tiểu luận hệ tin học phân tán
chỉ duy trì đồ thị G
i
–hình ảnh thu nhỏ của G cho các giao dịch đã phát thông báo. Như
vậy, sau khi đã thực hiện t
32
, ta có các hình ảnh sau:
Tại trạm S1

ta có đồ thị G1:

Hình 3.1. Đồ thị G1 trên trạm S1
Tại trạm S2 ta có đồ thị G2:
Hình 3.2. Đồ thị G2 trên trạm S2
Tại trạm S3 ta có đồ thị G3:
Hình 3.3. Đồ thị G3 trên trạm S3
Rõ ràng, thông qua ba đồ thị trên đây, ta không phát hiện mạch khép kín dẫn đến
tình trạng bế tắc. Nhưng, nếu ở hệ tập trung hay trạng thái không phải từng phần, ta có đồ
thị sau đây:
Hình 3.4. Phát sinh bế tắc
Trong thực tế, mặc dầu không có đồ thị nào trong số này cho phép phát hiện sự
hình thành một vòng lặp bế tắc, nhưng trên một trạm cho trước nào đó, ta lại không thể dự
phòng bế tắc có kết quả được.
b) Nguyên lý và thuyết minh phương pháp
Ta sẽ thay thế vào điều kiện cung cấp trong đồ thị G không vòng lặp một điều
kiện khác mạnh hơn, nhưng được kiểm tra bằng các thông tin cục bộ trên từng trạm.
Để làm được điều đó, ta thêm vào cho từng đồ thị G
’

i
hình ảnh thu nhỏ cho S
i
của
đồ thị của một quan hệ trật tự toàn bộ chặt chẽ được xác định trên các tập hợp giao dịch.
Quan hệ trật tự này có thể được nhờ phương tiện dấu. Điều kiện cung cấp tài nguyên là
duy trì tình trạng không vòng lặp cho các đồ thị G
i
. Căn cứ theo cấu trúc, điều kiện này
có thể được kiểm tra cục bộ trên từng trạm. Ta sẽ chỉ ra G có được tình trạng không vòng
HVTH: Nguyễn Văn Hùng Trang 6
e2
e3
e1
T1
T3
T2
T1 T3
e1
T2 T1
e2
T3 T2
e3
Báo cáo tiểu luận hệ tin học phân tán
lặp như thế nào. Để làm việc đó, ta bắt đầu chỉ ra sự tồn tại của vòng trong G kéo theo sự
tồn tại của vòng trong ít nhất một G
’
i
.
Ta ký hiệu T

j
>>T
k
là quan hệ trật tự toàn phần chặt chẽ trên các giao dịch. Lúc
này, G
’
i
là hình ảnh thu nhỏ của trạm S
i
của đồ thị của quan hệ >> xác định bởi:
T
j
>>T
k
⇔ T
j
>T
k
hay T
j
>>T
k

Giả sử rằng G có vòng lặp bao gồm một tập hợp của n giao dịch được đánh số từ
0 đến n-1 trong trật tự của vòng lặp của trật tự xác định bởi quan hệ >. Giả sử rằng T
p
là
nguyên tố của tập hợp này đến trước tất cả các cái khác theo chiều của quan hệ >> và giả
sử rằng q = p-1 modulo n. Ta có :
T

p
>>T
q
vì T
p
đến trước các cái khác
T
j
>T
k
trong vòng lặp của đồ thị G
Nếu S là số của trạm chứa tài nguyên bị cài then bởi T
q
và thuộc quyền sở hữu
của thông cáo của T
p
thì G
’
i
chứa vòng lặp.
c) Thuật toán:
Như vậy, thuật toán dự phòng được triển khai như sau:
STT Triển khai
1 Việc cung cấp tài nguyên tại trạm S cho giao dịch T
i
được

tiến hành,
nếu việc cung cấp đó không tạo ra vòng lặp trong đồ thị G
’

i
2 Trong trường hợp bị từ chối, tiến hành được giao dịch trên trạm S
được đưa vào hàng đợi cục bộ tại S
3 Khi tài nguyên được giải phóng, tất cả các tiến trình của hàng đợi
được kiểm tra nếu các yêu cầu của chúng có thể được thoả mãn
Qui trình vận hành thuật toán được minh hoạ bởi ví dụ kề liền sau đây:
Ví dụ 2:
Ta hãy lấy lại ví dụ 1. Khi T
1
thực hiện t
12
: v-loai-tru-th(e1), yêu cầu này vào
xung đột với thông cáo a-loai-tru-th(e1) thực hiện bởi T
3
. Như thế, cung T
1
-T
3
được thành
lập trong G. Lúc này, yêu cầu vẫn được chấp nhận vì T
1
>>T
3.
Sau khi diễn ra việc cung cấp này, các đồ thị G
’
i
trên ba trạm sẽ như sau:
HVTH: Nguyễn Văn Hùng Trang 7
T1
T3

T1
T2
T2
T3
Tram S1 Tram S2 Tram S3
Báo cáo tiểu luận hệ tin học phân tán
Hình 2.9. Trạng thái cung cấp tài nguyên trên 3 trạm
Yêu cầu t
22
:v-loai-tru-th(e2) kéo theo trên trạm S
2
sự tạo nên cung T
2
-T
1
bị loại
bỏ; bởi vì nó sinh ra vòng lặp trên S
2
. Tương tự như vậy, yêu cầu t
32
: v-loai-tru-th(e3) bị
từ chối bởi vì nó tạo ra vòng lặp trên S
3
. Nhưng ta cần lưu ý là nếu trật tự theo dạng T
1
,T
2
,
T
3

thì yêu cầu vừa nêu có thể được chấp nhận.
Thuật toán này đặt ra một nguyên tắc tương tự như các nhóm sắp xếp. Duy chỉ
khác nhau có một điều là nó tránh được sự thiếu thốn vô hạn, bởi vì trật tự tổng quát được
triển khai cho các giao dịch chứ không phải cho các tài nguyên. Một giao dịch trở nên rất
cần thiết là giao dịch có thời gian chờ đợi dài nhất sau một khoảng thời gian xác định, nó
đã trở thành giao dịch được ưu tiên nhất trên tất cả các trạm mà nó đã gởi thông điệp.
Thuật toán phát hiện bế tắc
Khi các tài nguyên được sử dụng bởi giao dịch được xác định theo kiểu động
trong quá trình thi hành giao dịch, các phương pháp dự phòng bế tắc dựa trên nền tảng các
thông điệp không còn phù hợp nữa. Lúc này, ta phải sử dụng các phương pháp phát hiện
và chữa trị.
Phương pháp được mô tả bởi Menasce sẽ được trình bày. Phương pháp này đặt ra
vấn đề sử dụng một đồ thị các tranh chấp mà việc kiểm tra các tranh chấp đó cho phép
phát hiện bế tắc.
Tương tự như thuật toán vừa nêu, mỗi trạm quản lý các đối tượng riêng của mình
và việc phát hiện chỉ dựa vào thông tin cục bộ. Các trạm khởi sự các giao dịch bị treo
được đề phòng phát sinh bế tắc (mà bế tắc này có thể phát hiện tại một trạm nào đó) cần
phải đề ra các biện pháp chữa trị cho mình.
Các định nghĩa:
Ta cần xác định trong mọi thời điểm giữa hai giao dịch Tj và Tk quan hệ chặn
trực tiếp như sau:
T
j
> T
k
⇔ Tồn tại ít nhất một tài nguyên bị cài then bởi T
j
và yêu cầu bởi T
k
nhưng

không được đáp ứng
Quan hệ này được biểu hiện bằng một đồ thị gọi là đồ thị các xung đột hữu
hiệu.Sự tồn tại một vòng lặp trong đồ thị này báo hiệu cho ta biết sẽ có bế tắc diễn ra. Một
giao dịch “không bị chặn” có nghĩa là trong đồ thị biểu hiện bằng một nút mà tại đó
không có cung nào dẫn đến.
Giả sử rằng Tk là một giao dịch bị chặn. Tập hợp tất cả các giao dịch mà có thể
đạt được bằng cách chạy khắp các cung xuất phát từ Tk , theo chiều ngược lại với hướng
của chúng, và gọi là tập hợp các chặn của Tk , ký hiệu E(Tk). Các giao dịch thuộc vào
E(Tk) là các giao dịch có nguồn gốc từ sự chặn của Tk .
HVTH: Nguyễn Văn Hùng Trang 8
Báo cáo tiểu luận hệ tin học phân tán
Tại một thời điểm cho trước, đồ thị các xung đột hữu hiệu sinh ra các quan hệ
chặn tồn tại giữa các giao dịch của hệ. ta kí hiệu B(T
k
) là tập hợp các giao dịch bị chặn do
T
k
, nghĩa là các giao dịch có thể đạt được bằng cách chạy khắp các cung xuất phát từ T
k.
Ví dụ 1
Cho đồ thị xung đột hữu hiệu như sau:
Các giao dịch không bị chặn là T
3
,

T
4
,

T

5
Ta có: E(T
5
) = {T
2,
T
3,
T
4,
T
5
}
B(T
5
) = {T
1,
T
3
}
Đồ thị các xung đột hữu hiệu chứa vòng lặp nếu và chỉ nếu tồn tại giao dịch T
k.
mà tập hợp chặn của nó chứa một giao dịch bị chặn bởi T
k.
:
∃k: B(T
k.
) ∩ E(T
k.
) ≠ 0 {Tồn tại vòng lặp}
Nếu ta không muốn duy trì trên mỗi trạm một bản sao của đồ thị tổng quát thì cần

phải xây dựng một ảnh cục bộ cho phép đánh giá các điều kiện vừa nêu trên.
Đó là điều mà ta thực hiện trong giải thuật sau đây:
e) Thuật toán:
Ta kí hiệu S(T
k.
) là trạm nguồn của giao dịch T
k.
. Để cho mỗi giao dịch T
k.
, trạm
S(T
k.
) duy trì các tập hợp B(T
k.
) và E(T
k.
). Việc cập nhật E(T
k.
) cần phải được biểu hiện
trên tất cả các trạm nguồn của các giao dịch thuộc B(T
k.
). Thực tế, giao dịch bị chặn T
k.
là
phần tử của toàn bộ tập hợp chặn của các giao dịch thuộc B(T
k.
).
Giả sử rằng T
k.
đã yêu cầu một tài nguyên e của trạm S

i
nào đó. Trên trạm này, ta
thực hiện các phép toán sau đây:
STT Phép toán
1 Nếu e là có sẵn để dùng, yêu cầu được thoả mãn và ta ghi nhận là
T
k.
đang có tài nguyên.
2 Nếu e đã được cung cấp cho giao dịch T
j
thì thông điệp “T
j
chặn
T
k.
” được truyền cho trạm S(T
j.
) và S(T
k.
). Sau này (j, k) chỉ một
thông điệp như vậy.
Khi nhận một thông điệp (j, k) trên một trạm S nào đó, ta thực hiện các tác động
sau đây:
1. Trên trạm S(T
j.
) nguồn của giao dịch chặn T
k.
, ta thêm T
k.
vào tập hợp B(T

j.
) và
kiểm tra rằng ta không làm phát sinh bế tắc, có nghĩa là: B(T
j.
) ∩ E(T
j.
) = 0.
Ta gửi tiếp tục thông điệp (l, k) về phía các trạm nguồn của các giao dịch T
l
chặn
T
j
nhằm cho phép các trạm S(T
k.
) cập nhật các tập hợp BB(T
l.
) của các giao dịch bị chặn
bởi T
l
. Song song với tác động trên, các thông điệp (l, k) được gửi về trạm nguồn của các
giao dịch T
k.
để cập nhật tập hợp E(T
k.
) của các giao dịch bị chặn T
k.
.
2. Trên trạm S(T
k.
) nguồn của giao dịch bị chặn T

k.
, Ta thêm T
j
cho tập hợp E(T
k.
)
và kiểm tra không có bế tắc, có nghĩa là: B(T
j.
) ∩ E(T
k.
) = 0.
HVTH: Nguyễn Văn Hùng Trang 9
Báo cáo tiểu luận hệ tin học phân tán
Ta gửi tiếp tục (j,m) về phía các trạm nguồn của các giao dịch T
m
bị chặn bởi T
k.
nhằm cho phép các trạm S(T
m.
) cập nhật các tập hợp E(T
m.
) của các giao dịch chặn T
m
.
Các khuyến nghị giải phóng dẫn đến thuật toán đối xứng mà ta không có điều
kiện giới thiệu ở đây.
Ví dụ 2
Hãy xét 3 trạm S
1
, S

2
và S
3.
Mỗi trạm S
i
chứa đối tượng e
i
và là nguồn giao dịch
của T
i
:
T
1
T
2
T
3
v-loai-tru-th(e1)
…………
v-loai-tru-th(e2)
v-loai-tru-th(e2)
…………
v-loai-tru-th(e3)
v-loai-tru-th(e3)
…………
v-loai-tru-th(e1)
Ta hãy tưởng tượng rằng tại thời điểm mà tất cả các giao dịch đã được thực hiện
có kết quả phép toán đầu tiên của then cài. Khi đó chuyển sang thời điểm của phép toán
thứ hai, Các giao dịch đều bị chặn. Điều đó kéo theo các sự kiện sau đây:
T

1
trên S
2
đề nghị cung cấp e
2
có trên T
2
;
S
2
gửi (2,1) cho S
1
và S
2
, từ đó ta có:
E(T
1.
)={T
2
} B(T
1.
)= 0
B(T
2.
)={T
1
} E(T
2.
)= 0
T

2
trên S
3
đề nghị cung cấp e
3
có trên T
3
;
S
3
gửi (3,2) cho S
2
và S
3
, từ đó ta có:
B(T
3.
)={T
2
} B(T
3.
)= 0
E(T
2.
)={T
3
} E(T
2.
)={T
1

}
S
2
gửi(3,1) cho S
1
và từ đó sinh ra:
E(T
1.
)={T
2
,T
3
} B(T
1.
)= 0
T
3
trên S
3
đề nghị cung cấp e
1
có trên T
1
;
S
1
sinh ra T
3
trong B(T
1.

) và ta ghi nhận là:
E(T
1.
) ∩ B(T
1.
) =
{
T
3
}
Như vậy, bế tắc được phát hiện trên S
1
.
Kết luận
Hai thuật toán vừa được giới thiệu ở trên xuất phát từ cơ sở cùng một nguyên lý
tương tự. Đó là sự thiếu chắc chắn của trạng thái các trạm xa phát sinh vấn đề lưu trữ một
“giới hạn an toàn” nhất định.
Nhưng bản thân hai thuật toán này, khi triển khai lại cho phép sử dụng các kỹ
thuật khác nhau. Trong thuật toán dự phòng, ta kiểm tra trên trạng thái từng phần một điều
kiện mạnh hơn điều kiện tối thiểu. Trong thuật toán phát hiện, ta có trong một trạm trạng
thái của các trạm khác. Thông thường, mỗi trạm đều nhận các thông tin dư thừa.
HVTH: Nguyễn Văn Hùng Trang 10
Báo cáo tiểu luận hệ tin học phân tán
B. BÀI TẬP
I. Phát biểu bài toán
Trong hệ thống có 3 Server phục vụ việc đăng ký du lịch bao gồm: Tour du lịch,
Xe vận chuyển, Khách sạn. Anh/ chị hãy xây dựng chương trình giao dịch lồng ghép để
thực hiện đăng ký tài nguyên nêu trên.
II. Thiết kế hệ thống
Trước tiên, ta giả sử rằng hệ thống viễn thông với đường truyền mà thông qua đó

các thông điệp được gửi và nhận có độ ổn định ở mức chấp nhận được và khả năng hoạt
động của các bộ vi xử lý với độ tin cậy cao.
Các đối tượng khác nhau của hệ được 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. 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ó.
Xây dựng ứng dụng bằng Java RMI:
Một ứng dụng RMI gồm các nội dung như sau:
HVTH: Nguyễn Văn Hùng Trang 11
Báo cáo tiểu luận hệ tin học phân tán
• Xác định đối tượng ở xa. RMI cho phép xác định tham chiếu đến đối tượng ở
xa bằng cách cho phép chương trình Server đăng ký các đối tượng của nó vào
rmiregistry.
• Giao tiếp với các đối tượng ở xa. Chi tiết về giao tiếp giữa các đối tượng
hoàn toàn do Java xử lý, đối với người lập trình, việc gọi các đối tượng ở xa
cũng tương tự như việc gọi các đối tượng cục bộ.
• Tải mã bytecode động. RMI cho phép tải mã bytecode của đối tượng về máy
cục bộ và truyền dữ liệu đến đối tượng ở xa.
Hình vẽ dưới đây minh hoạ một ứng dụng phân tán RMI sử dụng registry để xác
định tham chiếu đến các đối tượng ở xa. Hình vẽ này cũng cho thấy RMI sử dụng
Webserver để tại mã bytecode của đối tượng ở xa khi cần thiết.
Hệ thống gồm 3 Server chứa chương trình và cơ sở dữ liệu tại các Server như sau:
- Server 1: Lưu trữ database về Tour, giả sử file database là Tour gồm các bảng
TOUR, DANGKY, DANGKY_DICHVU
HVTH: Nguyễn Văn Hùng Trang 12
Báo cáo tiểu luận hệ tin học phân tán
- Server 2: Lưu trữ database về Hotel, giả sử file database là KhachSan gồm các bảng
KHACHSAN, TOUR_KHACHSAN, KHACHSAN_DICHVU, DICHVU
- Server 3: Lưu trữ database về Transport, giả sử file database là PhuongTien gồm hai
bảng PHUONGTIEN, TOUR_PHUONGTIEN
Cơ sở dữ liệu tại các Server phải đảm bảo gắn bó, công việc này được thực hiện

tự động mỗi khi Client cập nhật dữ liệu vào một Server nào đó. Trên mỗi server chứa hai
module xử lý chính:
• Module giao tiếp với Client. Module này có tên là ClientHandle, nó có chức
năng nhận dữ liệu từ các chương trình Client để lưu vào cơ sở dữ liệu.
• Module xử lý danh sách di chuyển. Module này có tên MobListHandle, nó có
chức năng nhận dữ liệu từ module ClientHandle và cập nhật vào tất cả các
server theo giải thuật danh sách di chuyển mà chúng ta sẽ trình bày ở phần
sau.
Giải thuật danh sách di chuyển được trình bày như sau:
HVTH: Nguyễn Văn Hùng Trang 13
Báo cáo tiểu luận hệ tin học phân tán
1. Khởi động các module trên server, gồm module MobListHandle,
ClientHandle. Hệ thống cho phép User cập nhật dữ liệu từ các chương trình
Client.
2. Module ClientHandle nhận dữ liệu từ Client và thành lập danh sách di
chuyển, sau đó chuyển danh sách cho module MobListHandle.
3. MobListHandle mở ra một giao dịch, thực hiện truy vấn dữ liệu ngay trên cơ
sở dữ liệu cục bộ của mình. Sau khi kết thúc truy vấn, MobListHandle gửi
danh sách di chuyển đến Server kế tiếp trong hệ thống đa server.
4. Nếu Server cuối cùng trong danh sách di chuyển - nếu việc thực thi các câu
lệnh truy vấn trên CSDL cục bộ thành công thì chuyển sang trạng thái uỷ thác
(CommitTransaction) và trả danh sách kết quả khác null về cho Server liền
trước nó. Ngược lại trả về null và chuyển sang trạng thái khôi phục
(RollbackTransaction).
5. Server nhận được danh sách kết quả từ Server sau nó trong danh sách di
chuyển - nếu kết quả khác null thì chuyển sang trạng thái uỷ thác
(CommitTransaction) và gán kết quả truy vấn cục bộ vào danh sách kết quả và
trả về Server liền trước nó. Ngược lại, chuyển sang trạng thái khôi phục
(Rollback transaction) trả kết quả về null cho Server liền trước.
6. Khi Server đầu tiên nhận được danh sách kết quả - nếu danh sách kết quả

khác null thì chuyển sang trạng thái uỷ thác (CommitTransaction) và trả danh
sách kết quả cho ClientHandle. Ngược lại, chuyển sang trạng thái khôi phục
(Rollback transaction) và trả kết quả về null cho ClientHandle.
7. ClientHandle nhận được danh sách kết quả và xử lý dựa trên danh sách kết
quả.
HVTH: Nguyễn Văn Hùng Trang 14
Báo cáo tiểu luận hệ tin học phân tán
III. Một số hình ảnh chạy chương trình
Module Client: phần giao diện của module client là hiển thị form nhập dữ liệu.
Module client sau đó sẽ triệu gọi đối tượng từ xa trên hệ thống đa server để cập nhật dữ
liệu vào cơ sở dữ liệu.
Module Interface: thực hiện chức năng giao tiếp giữa module client và module
server, cấu trúc của module interface như sau:
public interface DSDCInt extends java.rmi.Remote
{public void insertDb1(String Madk,String MaPtien,String MaTuyen, String
MaKS,String Hoten, String Diachi, String Dienthoai, String Sender,String
sophong,String soghe) throws java.rmi.RemoteException;
public void welcomeMessage (String message) throws
java.rmi.RemoteException;}
Module Server: Module này đảm nhận toàn bộ các chức năng chính của giải thuật
danh sách di chuyển trình bày ở trên. Module này được cài trên các server khác nhau
được đánh thứ tự từ 1 đến n. Mỗi server thực hiện chức năng lắng nghe các yêu cầu từ
HVTH: Nguyễn Văn Hùng Trang 15
Báo cáo tiểu luận hệ tin học phân tán
module client cũng như từ các module server khác nhằm triển khai giải thuật gắn bó dữ
liệu là giải thuật danh sách di chuyển trình bày ở trên.
Hình ảnh khi chạy chương trình server như sau:
HVTH: Nguyễn Văn Hùng Trang 16
Báo cáo tiểu luận hệ tin học phân tán
Thông tin đăng ký được thêm vào bảng Dangky:

Một số đoạn chương trình chính:
/***************
DSDCImpl.java
***************/
import java.net.*;
import java.io.*;
import java.lang.Thread;
import java.util.*;
import java.sql.*;
import java.rmi.dgc.*;
public class DSDCServerImpl extends java.rmi.server.UnicastRemoteObject
implements DSDCServerInt {
static int[] serverArray;
public DSDCServerImpl() throws java.rmi.RemoteException {
super();
HVTH: Nguyễn Văn Hùng Trang 17
Báo cáo tiểu luận hệ tin học phân tán
serverArray = new int[10];
for (int i = 0; i < serverArray.length; i++){
serverArray[i]=-1;
} }
public void welcomeMessage(String message) throws
java.rmi.RemoteException {
try { System.out.println("\n"+ message);
} catch(Exception e) { e.printStackTrace();
} }
public void insertList1(String Madk,String MaPtien, String MaTuyen,
String MaKS, String Hoten, String Diachi, String Dienthoai, String Sender, String
sophong, String soghe) throws java.rmi.RemoteException {
try { Class.forName("sun.jdbc.odbc.JdbcOdbcDriver").newInstance();

String urlb= "jdbc:odbc:Tour2";
java.sql.Connection dbcnb =
DriverManager.getConnection(urlb,"Admin","");
java.sql.Statement dbstb = dbcnb.createStatement();
System.out.println("ket noi duoc");
int rsb = dbstb.executeUpdate("INSERT INTO
Dangky(madangky,maphuongtien,matuyen,maks,tenkhachhang,diachi,dienthoai,soluong
phong,soluongghe)
VALUES('"+Madk+"','"+MaPtien+"','"+MaTuyen+"','"+MaKS+"','"+Hoten+"','"+Diachi
+"','"+Dienthoai+"','"+sophong+"','"+soghe+"');");
dbcnb.commit();
dbcnb.close();
System.out.println(Sender + " Inserted successfully!");
} catch(Exception e) { e.printStackTrace();
} }
public String select1(String tenTuyen) throws java.rmi.RemoteException
{
String maTuyen="";
try {
Class.forName("sun.jdbc.odbc.JdbcOdbcDriver").newInstance();
String urls1 = "jdbc:odbc:Tour";
java.sql.Connection dbcns1 =
DriverManager.getConnection(urls1,"Admin","");
HVTH: Nguyễn Văn Hùng Trang 18
Báo cáo tiểu luận hệ tin học phân tán
java.sql.Statement dbsts1 = dbcns1.createStatement();
ResultSet rss1 = dbsts1.executeQuery("Select * from Tour");
while (rss1.next())
{ String tamT=rss1.getString(2);
if(tamT.equals(tenTuyen))

{ maTuyen=rss1.getString(1);
} }
dbcns1.commit();
dbcns1.close();
System.out.println( " Select successfully!");
} catch(Exception e) { e.printStackTrace();
}
return maTuyen;
} }
/******************
DSDCServer.java
******************/
import java.rmi.Naming;
public class DSDCServer {
public DSDCServer() {
try { DSDCInt dsdc=new DSDCImpl();
Naming.rebind("rmi://localhost:2001/DSDCForm1",dsdc);
System.out.println("Server1 Running for Client!");
} catch (Exception e) { System.out.println("DSDC Error:"+e);
}
try { DSDCServerInt dsdcThread=new DSDCServerImpl();
Naming.rebind("rmi://localhost:2001/DSDCAlm1",dsdcThread);
System.out.println("Server1 Running for MultiServer");
} catch (Exception e) { System.out.println("DSDC Error:"+e);
} }
public static void main(String args[]) {
System.out.println("SERVER 1 ONLINE !");
new DSDCServer();
} }
HVTH: Nguyễn Văn Hùng Trang 19

Báo cáo tiểu luận hệ tin học phân tán
TÀI LIỆU THAM KHẢO

[1.] Hệ tin học phân tán
PGS TS Lê Văn Sơn – Nhà xuất bản ĐHQG TP.Hồ chí minh, 2002.
[2.] Nguyên lý hệ điều hành
Nguyễn Gia Định, Nguyễn Kim Tuấn – Nhà xuất bản Khoa học và Kỹ
thuật Hà Nội, 2005.
[3] Distributed Deadlock Detection Algorithm
HVTH: Nguyễn Văn Hùng Trang 20
Báo cáo tiểu luận hệ tin học phân tán
R. Obermarck – ACM Transactions on Database Systems, vol.7, no.2, p
187 (June 1992).
[4] Coping with Deadlock in Distributed Systems
David B.Lomet – IBM Thomas J.Watson Research Center Yorktown
Heights, New York 10598.
[5] Distributed Deadlock Detection
K. Mani Chandy, J. Misra and L.M. Haas – ACM transactions on
Computer Systems, vol.1, no.2, p 144 (May 1983).

HVTH: Nguyễn Văn Hùng Trang 21
Báo cáo tiểu luận hệ tin học phân tán
MỤC LỤC
i
LỜI MỞ ĐẦU II
III
A. LÝ THUYẾT 1
CÁC PHƯƠNG PHÁP CUNG CẤP SỬ DỤNG TRẠNG THÁI TỪNG PHẦN 1
I.Một số khái niệm 1
II.Cung cấp tập hợp các tài nguyên. Vấn đề bế tắc 3

B. BÀI TẬP 11
I.Phát biểu bài toán 11
II.Thiết kế hệ thống 11
III.Một số hình ảnh chạy chương trình 15
TÀI LIỆU THAM KHẢO 20
MỤC LỤC 22
HVTH: Nguyễn Văn Hùng Trang 22