LỜI MỞ ĐẦU
Ngày nay Internet cùng với các ứng dụng của nó đã đem lại cho xã hội một cuộc
sống tiện nghi và đầy đủ hơn về thông tin. Mạng Internet đã giúp cho con người bước
vào một kỷ nguyên công nghệ thông tin và tri thức. Để có được thành tựu đó thì lĩnh
vực phân tán trong hệ tin học đã đóng một vai trò hết sức quan trọng.
Mục đích của lập trình mạng phân tán là tận dụng các khả năng tính toán và khai
thác dữ liệu của các hệ thống máy tính ở xa để thực hiện những tính toán nhanh hơn
trên cơ sở sử dụng nhiều bộ xử lý, nhiều bộ nhớ đồng thời hoặc nhiều dữ liệu quý giá
được phân tán khắp nơi. Trên nền hệ thống mạng máy tính được kết nối rộng rãi hiện
nay, việc xử lý phân tán sẽ giải quyết được những bài toán lớn hơn, phức tạp hơn và đa
dạng hơn trong thực tế.
Trong phạm vi của tiểu luận này tôi đề cập đến hai phần:
Phần 1 : Phần lý thuyết:
 Khái quát về hệ tin học phân tán.
 Bài toán về bãi đỗ xe ô tô và vấn đề đồng bộ giữa các tiến trình.
 Lập trình mạng phân tán và RMI
Phần 2 : Phần bài tập:
+
Viết chương trình bài toán bãi đỗ xe để mô phỏng quá trình làm việc
của hệ phân tán.
Tôi xin chân thành cảm ơn: PGS.TS. Lê Văn Sơn và các bạn đồng môn đã
giúp tôi hoàn thành tiểu luận này.

địa lý khác nhau, được liên kết với nhau thông qua phương tiện truyền thông (viễn
thông) dưới quản lý thống nhất của một hệ thống điều khiển.
Qua đó ta có thể xem hệ phân tán như là một tập hợp các bộ xử lý (hoặc bộ vi
xử lý) với bộ nhớ và đồng hồ nhịp độc lập. Điều này đồng nghĩa với việc 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ệ 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.
Hệ tin học phân tán thực hiện hàng loạt các chức năng phức tạp, nhưng cơ bản
nhất là đảm bảo cung cấp cho người sử dụng (NSD) khả năng truy cập có kết quả đến
các loại tài nguyên vốn có và rất đa đạng của hệ thống như là những tài nguyên dùng
chung.
LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 2
HVTH: Lê Quốc Dũng -KHMT K16
Việc định nghĩa các tài nguyên của hệ như là tài nguyên dùng chung sẽ mang
đến cho NSD những tiện ích và đem lại cho hệ những hiệu năng tốt trong khai thác
ứng dụng.
Những ưu điểm căn bản của việc sử dụng chung tài nguyên được phản ảnh
trong bảng I.1 sau đây :
TT Ưu điểm so với hệ tập trung
1 Tăng tốc độ bình quân trong tính toán - xử lý
2 Cải thiện tình trạng sẵn sàng của các loại tài nguyên dùng chung
3 Tăng độ an toàn và an ninh cho dữ liệu
4 Cho phép đa dạng hoá các loại hình dịch vụ tin học nói chung
5 Đảm bảo tính vẹn toàn của thông tin do giải quyết được vấn đề gắn bó dữ
liệu (Coherence).


Đặc điểm
1 Thời gian truyền thông tin trong hệ không giống nhau
2 Các thông điệp có thể bị mất trong quá trình truyền thông tin
3 Các thông điệp có thể được truyền kép
4 Việc phát và nhận thông điệp đối với toàn hệ là ngẩu nhiên
5 Việc cập nhật thông tin (chương trình và dữ liệu) dẫn đến hệ rơi vào
trạng thái thiếu gắn bó
6 Hệ có thể rơi vào trạng thái bế tắc, tắt nghẽn đường truyền, chờ vô hạn
và thiếu thốn tài nguyên
7 Một (hay nhiều) máy tính cấu thành của hệ phân tán có thể bị sự cố
Bảng I.3 Đặc điểm cơ bản của hệ phân tán
II. TIẾN TRÌNH TRONG HỆ PHÂN TÁN
Tiến trình (Process) là khái niệm khá quen thuộc và là đối tượng nghiên cứu
của hệ điều hành. Trong hệ phân tán ta chỉ xem xét và bổ sung đặc điểm hoạt động và
truy cập của các tiến trình có nhu cầu cung cấp tài nguyên dùng chung.
Các đặc điểm đó là :
1. Các tiến trình được hình thành và điều khiển bởi hệ điều khiển duy nhất
có nghĩa là nếu trong các thành phần tham gia hệ phân tán như mạng máy tính,
các hệ tập trung, có thể có các hệ điều hành riêng với các tiến trình riêng của
mình, thì chúng cũng bị phái sinh lại trong nội dung của tiến trình mới, phân
tán.
2. Tiến trình là chương trình hay đoạn chương trình đang hoạt động trong
hệ phân tán là đối tượng chủ yếu có nhu cầu tài nguyên phần cứng hay phần
mềm để thực hiện các lệnh của mình. Tiến trình cần tài nguyên để phát triển.
Về nguyên tắc, tất cả các tiến trình và tài nguyên được cung cấp là các đối
tượng ở xa.
3. Các nguyên lý của hệ tập trung có thể nghiên cứu và áp dụng cho các
tiến trình phân tán như dự phòng và chống bế tắc, chống xung đột,
4. Khi tiến trình được cung cấp tài nguyên có thể nó thực hiện ngay, nếu nó

Hợp lực là nguyên nhân chính của sự tác động tương hỗ được lập trình giữa
các tiến trình nhằm cho phép chúng tham gia vào các hành động chung.
Sự tương tranh và hợp lực giữa các tiến trình đòi hỏi phải có trao đổi thông tin
qua lại với nhau. Trong các hệ thống tập trung, điều đó được thực hiện nhờ thuật toán
loại trừ tương hỗ thông qua các biến cùng tác động trong một vùng nhớ chung. Trong
hệ tin học phân tán, các thông tin cần trao đổi thông qua các thông điệp bằng các kênh
viễn thông
IV. BÀI TOÁN ĐỒNG BỘ HOÁ TIẾN TRÌNH NHU CẦU TÀI NGUYÊN
DÙNG CHUNG
. Trong hàng loạt các tài liệu đã nêu lên nhiều mặt khác nhau của bài toán điểu
khiển bãi để xe. Trong phạm vi của tiểu luận này, ta trình bày vấn đề dưới giác độ
đồng bộ hóa đã được xác định trong phần I.3 ở trên. Bãi để xe ô tô được mô tả trong
hình vẽ I.1. Bãi này có m chổ để xe và có thể phân n (n<m, nguyên, dương) khu vực
ứng với n cửa vào/ra ô tô. Tại mỗi cửa vào/ra, ta có người bảo vệ làm nhiệm vụ cung
cấp phiếu cho ô tô vào chổ còn trống và thu hồi lại phiếu khi có một ô tô ra, thông báo
cho các người bảo vệ khác biết để cùng hành động cho chính xác trong việc phân phối
chổ của bãi.
LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 5
HVTH: Lê Quốc Dũng -KHMT K16
VT
VT
VT
VT
VT
VT
VT
VT

3. Chờ khẳng định nhận của tất cả những người bảo vệ khác trong bãi
4. Giải phóng ô phiếu, đưa ô về trạng thái tự do
Xử lý lúc rối loạn như mất điều khiển
1. Khởi động lại nạp lại chính xác số chổ còn trống
2. Trình tự khởi động các người bảo vệ
3. Xác định tính tuần tự
Tình huống sự cố
Không nhận được khẳng định từ người nhận
Hình I.3 : Mô phỏng bãi đậu xe ôtô

LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 6
HVTH: Lê Quốc Dũng -KHMT K16
Sự tương quan giữa các đối tượng trong bãi để xe và các đối tượng trong hệ
phân tán có thể mô tả trong bảng I.4 dưới đây.
TT Bãi để xe Hệ phân tán Thuyết minh
1 Ô tô Tiến trình Ở đây, tiến trình được xem như
là đồng nhất (cùng 1 loại).
Trong hệ phân tán, các tiến
trình đa dạng
2 Người bảo vệ Phần mềm
điều khiển
Ký hiệu là ĐK, hoàn toàn
giống nhau trên
Server/Workstation
3 Cổng vào/ra Server/Workstation

Mỗi cổng đặt 1 máy (chưa tính

GVHD: PGS.TS. Lê Văn Sơn
Trang 7
HVTH: Lê Quốc Dũng -KHMT K16
Trong thực tế, một NBV nào đó tin rằng không còn ô trống nữa trong khi một
NBV khác lại vừa mới cho ra khỏi bãi một số xe ô tô mà anh ta chưa kịp báo cho các
NBV khác. Cũng có thể diễn ra trường hợp là cùng một lúc các người bảo vệ giải
quyết các xe vào cùng một vị trí trong bãi do vì họ thiếu thông tin.
Như vậy, các người bảo vệ phải hợp lực với nhau để phân phối chính xác các
chỗ trong bãi, đặc biệt là số lượng ô còn trống càng ít, thì vai trò của sự hợp lực càng
quan trọng.
V. GẮN BÓ DỮ LIỆU VÀ TẦM QUAN TRỌNG CỦA NÓ VỚI VẤN ĐỀ
CUNG CẤP TÀI NGUYÊN DÙNG CHUNG TRONG HỆ PHÂN TÁN
Vì lý do ổn định và hiệu quả của hệ trong quá trình cung cấp tài nguyên dùng
chung cho các tiến trình mà ta phải phân tán chức năng cung cấp trên nhiều
Server/Workstation khác nhau. Sự hoạt động gắn bó với nhau giữa các chương trình
cung cấp là rất cần thiết để bảo đảm cho hoạt động cung cấp được hoàn toàn chính
xác.
Tiếp tục nghiên cứu khía cạnh đồng bộ và ý nghĩa của việc gắn bó dữ liệu phân
tán của bài toán điều khiển bải đỗ xe dưới đây, ta có thể rút ra một số kết luận quan
trọng làm cơ sở cho việc giải quyết thích hợp các vấn đề đặt ra của tiểu luận văn này.
Trong các phần trước, ta đã xác định một người bảo vệ có vai trò như là chương
trình điều khiển và cung cấp chổ của bãi để xe ô tô. Ở đây, chổ để xe được xem như là
tài nguyên dùng chung của hệ. Giả sử rằng ở thời diểm cho trước ta có 4 người bảo vệ
và có 100 chổ còn trống. Tất cả các người bảo vệ đều có thông tin đó. Trạng thái của
hệ lúc này là gắn bó. Ba trong số họ phát đi các thông tin như sau :
TT Thông điệp Thông tin phát đi trong thông điệp
1 T1 Thêm 20 chổ trống
2 T2 Đã có 10 chổ bị chiếm
3 T3 Dành 10% chổ trống để quét dọn sân bãi.
Bảng I.5 Nội dung của các thông điệp phát đi

LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 8
HVTH: Lê Quốc Dũng -KHMT K16
2 T3 108 T2 110 T1 110 T3 81
3 T2 98 T3 99 T2 100 T1 101
Bảng I.6 Sự không gắn bó giữa các người bảo vệ
Tại đây, để dễ dàng hình dung vấn đề, ta có thể xem người bảo vệ như là
chương trình cung cấp tài nguyên nêu trên, còn chổ trong bãi là tài nguyên và các ô tô
là các tiến trình của hệ. Dễ dàng nhận thấy rằng các vị trí (chỗ để xe) và các xe là
những thực thể đồng nhất. Vì vậy, tiến trình và tài nguyên được xét trong ví dụ này là
tiến trình và tài nguyên đồng nhất.
Để tìm giải pháp cho bài toán điều khiển bãi để xe, thực chất, là ta phải giải
quyết vấn đề đồng bộ hóa giữa các thực thể tạo ra các sự kiện trong hệ phân tán. Đó
chính là các tiến trình tại các Server/Workstation yêu cầu tài nguyên để phát triển và
tạo nên các thu, phát và là nguyên nhân chính của việc chuyển từ trạng thái này sang
trạng thái khác một cách ngẩu nhiên.
Liên quan đến vấn đề đồng bộ hoá là vấn đề gắn bó dữ liệu và tầm quan trọng
của nó với bài toán điều khiển phân tán, vấn đề trật tự hóa các sự kiện và vai trò của
giải thuật Lamport với giá trị đồng hồ lô gíc mà ta sẽ lần lượt trình bày trong các phần
sau này được đánh giá như là vấn đề ưu tiên hàng đầu cần phải xét đến.
VI.TỔNG QUAN VỀ CHIẾN LƯỢC CUNG CẤP TRONG HỆ PHÂN TÁN
Một sự hoạt động gắn bó của các chương trình cung cấp phân tán quản lý trên
cùng một tập hợp các tài nguyên chỉ đặt được nêu tuân thủ các quy tắc sau, ở đây các
thông điệp được hiểu là các yêu cầu hay khuyến nghị giải phỏng tài nguyên.
TT
Quy tắc
1 Các bộ cung cấp bắt buộc phải thực hiện cùng một giải thuật
2 Các bộ cung cấp đều nhận tất cả các thông điệp phát đi từ các

hàm) có tên là phieu(S). Mỗi một giá trị chỉ phục vụ cho một và chỉ một sự kiện mà
thôi.
Giả sử rằng tất cả các sự kiện được đánh số bởi một bộ tuần tự duy nhất S. Khi
một tiến trình cung cấp cho sự kiện i một số thông qua phieu(S), ta có thể khẵng định
như sau (không có sự cố) :
1. rằng các sự kiện t bao hàm các giá trị nhỏ hơn t đã được diễn ra.
2. rằng số thứ tự sự kiện kề liền sau t phải bằng t+1.
Việc triển khai một bộ tuần tự cần phải mang hai đặc tính sau đây :
TT Ký hiệu Đặc tính
1 P1 Nếu a và b là hai sự kiện thực hiện trên cùng hàm
phieu(S), thì ta có a
→
b hay b
→
a.

2

P2
Nếu a thực hiện phép t = phieu(S), thì giá trị gán cho t là
số lượng các phép phieu(S) đã được thực hiện trước a.
Bảng I.8 Đặc tính của bộ tuần tự
Đặc tính P1 thể hiện việc loại trừ tương hổ trên các phép toán phieu(S), còn P2
thể hiện tính liên tục trong khi đánh số có nghĩa là không để lại khoản trống khi đánh
số.
Việc triển khai bộ tuần tự trong các hệ thống một bộ xử lý hay nhiều bộ xử lý
với bộ nhớ chung được tiến hành bằng cách triển khai cơ chế sơ đẳng loại trừ tương hổ
là đủ. Trong các hệ thống phân tán, việc vận dụng nó không hề giản đơn bởi vì có sự
hiện diện của các kênh viễn thông sử dụng theo kiểu loại trừ tương hổ và đặc biệt tồn
tại vòng tròn duy nhất hay một kênh lan truyền duy nhất.

xây dựng lại vòng tròn khi có một trạm nào đó bị sự cố. Phép xử lý này gọi là cấu hình
lại bao gồm cả việc cập nhật các giá trị của suc[i] và pred[i] của các hàng xóm của
trạm bị sự cố. Việc cấu hình lại mạng không khó khăn lắm, nếu trạm bị sự cố không
phá huỷ hoàn toàn liên kết lô gíc. Khi một trạm bị sự cố có thể hoạt động trở lại, thì
phép toán chèn cho phép nó tham gia vào mạng. Tốt nhất là hai phép toán cấu hình lại
và chèn được thể hiện ở tầng giao vận.
2.2. Ấn phong bằng các biến trạng thái
Giải thuật đầu tiên là một giải pháp thích nghi của giải thuật Dijkstra.
2.2.1. Hoạt động không sự cố
Một số nguyên K (K >1) được chọn cho tập hợp của hệ. Trên trạm i (i chiếm
giá trị từ 0 đến N-1), một tiến trình Pi được giao nhiệm vụ di chuyển ấn phong tuân thủ
các quy tắc sau đây :
1. Mỗi tiến trình Pi đều có biến trạng thái S[i] có thể nhận các giá trị nguyên từ
0 đến K-1.
suc[i] = i + 1 modulo N
pred[i] = i-1 modulo N
LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 11
HVTH: Lê Quốc Dũng -KHMT K16
2. Mỗi biến S[i] đều được cập nhật bởi Pi và có thể đọc bởi trạm kế tiếp sau
của Pi.
Thuật toán di chuyển trạng thái ấn phong được thể hiện như sau :
a. Tiến trình Pi có ấn phong chỉ khi :
S[i] ≠ S[i - 1] , cho i ≠ 0
S[0] - S[N - 1] , cho i = 0
b. Khi tiến trình Pi có ấn phong, thì nó phải bỏ ấn phong sau một
khoản thời gian xác định và phải thay đổi trạng thái :
S[i] := S[i-1], nếu i ≠ 0

*0

0

0

-

1

0

0

-

1

1

0

-

1

1

S[i]
(b)
0 1 2
i
0
1
S[i]
(c)
0 1 2
i
0
1
S[i]
(d)

LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 12
HVTH: Lê Quốc Dũng -KHMT K16
2.2.2. Đưa trạm bị sự cố vào lại
Để đưa một trạm bị sự cố đã khắc phục xong vào mạng, ta cần phải định lại cấu
hình vòng tròn ảo. Sau đó, tiến trình cần phải khởi động lại S[i]. Miễn là trạm j
=suc[i] không cho phép đọc biến S[j] của mình trong thời gian vào đoạn găng. Chỉ
cần thực hiện như sau là đủ :

Nếu j < i thì S[i] := S[j] - 1 mod K
nếu không S[i] := S[j]
Kết thúc nếu
2.3. Jeton tuần hoàn

HVTH: Lê Quốc Dũng -KHMT K16
một công tơ với các giá trị nguyên mà duy nhất chỉ có trạm có jeton mới có thể tăng và
tham chiếu. Các giá trị xuất phát từ tham chiếu đó được xem như là kết quả của các
phép toán phieu được thực hiện trên trạm.
TT

/Bảng I.9/ Diễn giải
1
Khi có một tiến trình trên một trạm muốn gọi phép toán phieu(S), thì ph
ải có
một yêu cầu đặt vào trong hàng đợi vào của TBTT. Tiến trình yêu cầu đó cần
phải đợi cho đến khi yêu cầu của nó xuất hiện trong hàng đợi ra của TBTT : tại
thời điểm đó, yêu cầu này đã được lan truyền và nó được sắp xếp cùng với các
yêu cầu khác.
2
Trạm i xử lý tất cả các yêu cầu phieu(S) đang có trong hàng đợi ra của TBTT của
nó. Mỗi khi có một yêu cầu đến từ một trong các trạm khác, thì trạm i sẵn sàng
tăng nội dung công tơ cục bộ của mình lên. Khi có một yêu cầu nào đó đến từ
một trong các tiến trình của chính trạm i, thì tiến trình này nhận giá trị hiện hành
của công tơ cục bộ và công tơ này tăng lên một số gia.

Lợi ích hiển nhiên của phương pháp đánh số không lổ hổng này là tránh được
hội thoại giữa các trạm để biết số sự kiện tiếp theo sau một sự kiện đã cho. Nhưng thực
tế, việc hội thoại này lại phải diễn ra để có được số hiện hành. Sự khác nhau của
phương pháp này và phương pháp dấu là ở chổ chịu đựng được các sự cố. Trên thực
tế, các trạm bị sự cố không thể nào phục vụ số được, bộ cung cấp cần phải tìm lại số
lượng và giá trị của các số đó. Để thực hiện điều đó, cần phải hội thoại với các trạm
khác.
3. Bộ tuần tự trên kênh lan truyền
Bây giờ ta hãy xem xét trường hợp liên lạc giữa các trạm được thực hiện bởi

đầu bằng cách lờ đi tất cả các thông điệp đến trước thông điệp đồng bộ. Thông điệp
đồng bộ đến sau cùng. Nó lưu trữ mà không xử lý tất cả các thông điệp theo sau nó và
điều đó được duy trì cho đến khi xuất hiện giá trị hiện hành của công tơ được gửi bởi j.
Sau khi thông điệp đồng bộ đến, trạm xử lý tất cả các thông điệp theo sau thông điệp
đồng bộ.

LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 15
HVTH: Lê Quốc Dũng -KHMT K16

Các trạm khác không được phép can thiệp. Do vậy, chúng lờ đi yêu cầu vào lại ,
thông điệp đồng bộ và giá trị truyền.
Phương pháp cập nhật này cũng có thể được sử dụng tại các trạm để trao đổi giá
trị của các công tơ trong việc kiểm tra định kỳ.
Tóm lại, trạng thái của các thành phần thuộc hệ thống tin học phân tán chỉ được
biết một cách không chắc chắn lắm do vì thời gian truyền thông tin trên đường truyền
không cố định, tăng số lượng các trung tâm ra quyết định và đặc biệt có thể xảy ra sự
cố bất cứ lúc nào.
Chúng ta đã nghiên cứu một số vấn đề về đồng bộ không chắc chắn và một số
vấn đề khác trên cơ sở trật tự toàn bộ mà việc triển khai được đặt trên nền tảng đánh số
sự kiện.
Chúng ta cũng đã giả định rằng việc sự cố một trạm hay một đường truyền nào

GVHD: PGS.TS. Lê Văn Sơn
Trang 17
HVTH: Lê Quốc Dũng -KHMT K16
CHƯƠNG II :
SỰ GẮN BÓ DỮ LIỆU TRONG HỆ QUẢN LÝ
BÃI ĐỖ XE
I. ĐẶT VẤN ĐỀ
Trong tất cả các hệ thống tin học, ta cần phải nghiên cứu các công cụ đủ mạnh
và hiệu quả để đồng bộ hoá các tiến trình. Tính cấp thiết về mặt nguyên lý và kỹ thuật
của vấn đề này thể hiện ở hai nguyên do cơ bản sau :
1. Nhìn chung, các tiến trình kể các tiến trình xuất phát từ các ứng dụng độc lập
muốn truy cập vào các tài nguyên với số lượng vốn rất hạn chế hay truy cập vào thông
tin dùng chung cùng một lúc. Trường hợp này gọi là truy cập tương tranh.
Vì vậy, tương tranh là nguyên nhân chính của các xung đột giữa các tiến trình
muốn truy cập vào tài nguyên dùng chung đây là một trong những nguyên nhân phải
thực hiện cơ chế đồng bộ hoá các tiến trình.
2. Các tiến trình của cùng một hệ ứng dụng hoạt động theo kiểu hợp lực để giải
quyết các bài toán đặt ra và cho kết quả nhanh chóng nhất. Điều này cho phép tăng
hiệu năng sử dụng thiết bị và hiệu quả hoạt động của chương trình đây là một trong
những nguyên nhân phải thực hiện cơ chế đồng bộ hoá các tiến trình.
Sự tương tranh và hợp lực giữa các tiến trình đòi hỏi phải có trao đổi thông tin
qua lại với nhau. Trong các hệ thống tập trung điều đó được thực hiện nhờ thuật toán
loại bỏ tương hỗ thông qua các biến cùng tác động trong một vùng nhớ chung. Trong
hệ thống tin học phân tán, các thông tin cần trao đổi thông qua các kênh thuộc hệ viễn
thông.
II. TRẬT TỰ TỪNG PHẦN
Cần chú ý rằng, trong các hệ thống tin học tập trung, vấn đề đồng bộ hoá được
giải quyết thông qua cơ chế loại trừ tương hỗ. Cơ chế này cho phép sắp đặt (xác lập
trật tự) hoàn toàn các sự kiện. Trong thực tiễn, nói một cách chính xác, có một hệ
thống vấn đề về đồng bộ hoá chỉ đòi hỏi trật tự từng phần. Chính vì vậy trật tự hoá


Hình II.1 : Mô tả trật tự từng phần
Theo hình vẽ trên, ta có thể biểu diễn trật tự như sau :
Trật tự từng phần của các sự kiện
A
1
→ A
2
→ A
3
→ A
4
→ A
5

B
1
→ B
2
→ B
3
→ B
4


→ A
5
A
1
→ A
2
→ B
2
→ B
3
→ A
4
→ A
5

Ví dụ về các sự kiện không so sánh
B
1
và A
1
, A
2
, A
3

A
3
và B
2
, B

B5
t
LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 19
HVTH: Lê Quốc Dũng -KHMT K16
III. GIẢ ĐỊNH CÁC ĐIỀU KIỆN CHUNG
Các hệ phân tán được xây dựng trên cơ sở các trạm làm việc được mắc nối với
nhau (nối mạng). Mỗi một trạm có bộ nhớ riêng của mình và tuyệt đối không có bộ
nhớ chung.
Ta áp dụng các ký hiệu trong bảng sau :
STT Ký hiệu Thuyết minh
1 H
1
Một trạm trong các trạm đều có thể liên lạc với các trạm còn lại
trong hệ
2 H
2
Không có lỗi truyền thông tin và không mất thông điệp
3 H
3
Trật tự nhận trên trạm j của dãy các thông điệp cũng giống như
chính tại trạm I là giống với trật tự của nơi phát
4 H
4
Sự cố hay gián đoạn vật lý tại một trạm nào đó được phát hiện sẽ
lập tức thông báo đến tất cả các trạm có ý định liên lạc với nó.
Trước hết, trong đề tài này nghiên cứu sự hoạt động của hệ không có sự cố, rồi
sau đó sẽ chỉ ra hiệu ứng của sự cố hay việc phục hồi lại một trạm. Đó là trường hợp

Trang 20
HVTH: Lê Quốc Dũng -KHMT K16
kênh của hệ thống viễn thông. Chính vì vậy nhu cầu sắp xếp các yêu cầu này theo một
trật tự nhất định nào đó luôn được đặt ra.
Nếu chỉ có một thông điệp đến chương trình cung cấp thì trật tự đến thể hiện
một trật tự chặt chẽ. Ngược lại, nếu có nhiều thông điệp đến cùng một lúc thì việc sắp
xếp chúng phải theo kiểu loại trừ tương hỗ trong hàng đợi cục bộ của trạm có chứa
chương trình cung cấp. Điều đó cũng cho phép ta có một trật tự chặt chẽ.
Trật tự có được tại trạm cung cấp có thể không giống như trật tự phát, nếu thời
gian truyền không được cố định. Đây là trường hợp khá phổ biến trong mạng máy
tính. Nhưng nếu ta muốn xử lý các thông điệp theo trình tự không tính tới thời gian
truyền, thì cần phải tính đến một trật tự tổng quát của các lần truyền thông điệp từ các
trạm khác nhau.
Cung cấp phân tán
Vì lý do ổn định và hiệu quả mà ta phải phân tán chức năng cung cấp trên nhiều
trạm khác nhau. Sự hoạt động gắn bó với nhau giữa các chương trình cung cấp là rất
cần thiết để đảm bảo cho hoạt động cung cấp được hoàn toàn chính xác. Bài toán sau
đây sẽ chỉ ra vấn đề sự không gắn bó dữ liệu trong hệ quản lý bãi đỗ xe
V. BÀI TOÁN HỆ QUẢN LÝ BÃI ĐỖ XE
Bài toán bãi để xe được phát biểu như sau : cho một bãi đậu xe ô tô N chỗ và có
ít nhất là 2 lối vào. Hành vi của ô tô là vào bãi, đậu và ra khỏi bãi. Việc quản lý bằng
cách ghi lại số lượng xe vào và số lượng xe ra. Người bảo vệ phát một phiếu cho ô tô
vào và nhận lại phiếu đó khi ô tô ra. Mỗi người bảo vệ cầm giữ một số phiếu cho việc
quản lý cục bộ của mình và chuyển cho người khác những cái dư. Bài toán được mô
phỏng theo hình vẽ II.2.
VT
VT
VT
VT
VT

Trong đó, BV - người bảo vệ có nhiệm vụ phân phối chổ cho các xe ô tô.
VT - Vị trí cho từng xe ô tô cụ thể.
Các mũi tên hai chiều được sử dụng để mô tả dòng ra vào của ô tô.
Trong bài toán này chúng ta nhận thấy :
- Bãi đậu xe chính là tài nguyên
- Xe chính là các tiến trình
- Nếu một cửa là tập trung còn nhiều của sẽ diến ra tranh chấp
+ Tình huống thứ 1 :
Ta giả sử rằng bãi để xe ô tô là loại bãi lớn có một cổng vào dưới sự
kiểm soát của một người bảo vệ (NBV) duy nhất. NBV chỉ biết được một phần của
trạng thái bãi để xe. Trong khi anh ta nghĩ rằng bãi để xe đã bị đầy, khi đó lại có nhiều
lái xe đang cho xe chạy ra cổng. Vì suy nghĩ như vây, trong trường hợp này, anh ta
không giải quyết được cho các xe khác tiếp tục được vào bãi nữa, mặc dù lúc này
trong bãi đang có chổ trống, như vậy, NBV không nắm được trạng thái hiện hành của
bãi.
+ Tình huống thứ 2 :
Nếu ta có bãi để xe có nhiều cổng vào và tại mỗi cổng có một người bảo
vệ thì mỗi người bảo vệ chỉ có thể biết được trạng thái với độ trễ nhất định và điều đó
đãn đến tình huống thứ 2. Đó là tình huống có nhiều trung tâm ra quyết định như trong
hình vẽ II.2
Trên thực tế một người bảo vệ nào đó tin rằng không còn chỗ trống nữa, trong
khi một người bảo vệ khác lại vừa mới cho ra khỏi bãi một số xe mà anh ta chưa kịp
báo cho các người bảo vệ khác. Cũng có thể diễn ra trường hợp là cùng một lúc các
người bảo vệ giải quyết các xe vào cùng một vị trí trong bãi do vì họ thiếu thông tin.
Như vậy các người bảo vệ phải hợp lực với nhau để phân phối chính xác các
chổ trong bãi, đặc biệt là số lượng chổ còn trống càng ít thì vai trò của hợp lực còn
quan trọng. Đây chính là sự không gắn bó dữ liệu ở bãi đậu xe ô tô
+ Tính huống thứ 3 :
Một người bảo vệ có vai trò như là chương trình cung cấp chổ của bãi để xe ô
tô. Ở đây, chỗ để xe được xem như là tài nguyên của hệ. Giả sử rằng ở thời điểm cho

Theo cách truyền và nhận các thông điệp giữa các trạm bảo vệ trên thấy rằng
việc phát và nhận các thông điệp xảy ra theo một trật tự nhất định về thời gian, như là :
người bảo vệ thứ phát thông điệp m1 sau khi 3 người bảo vệ còn lại đã nhận được
xong thông điệp m1 thì mới đến người bảo vệ thứ 2 phát thông điệp m2.

Bảo vệ 1 Bảo vệ 2 Bảo vệ 3 Bảo vệ 4 Trật
tự
xử lý
Thông
điệp
Giá
Trị
Thông
điệp
Giá
Trị
Thông
điệp
Giá
Trị
Thông
điệp
Giá
Trị
100 100 100 100
1 M1 120 M1 120 M1 120 M1 120
2 M2 110 M2 110 M2 110 M2 110

2

M
2

M
3
M
3
M
3
Hình II.3 : Thời hạn truyền và nhận thông điệp có trật tự

LT Mạng nâng cao Lập tình bằng các phương pháp phân tán để điều khiển bãi đỗ xe

GVHD: PGS.TS. Lê Văn Sơn
Trang 23
HVTH: Lê Quốc Dũng -KHMT K16

100 100 100 100
1 M1 120 M2 90 M3 90 M1 120
2 M3 108 M3 81 M1 110 M2 110
3 M2
118
M1
101
M2
100
M3
99
Bảng II.2 : Sự không gắn bó giữa bốn người bảo vệ
Tại đây, để dễ dàng hình dung vấn đề, ta có thể xem người bảo vệ như là
chương trình cung cấp, còn chỗ trong bãi là tài nguyên và các ô tô là các tiến trình của
hệ.
Trong bảng trên thì chúng ta thấy sau một khoảng thời gian thông tin về dữ liệu
của 4 người bảo vệ ở các trạm khác nhau sẽ có số lượng chỗ con trống là hoàn toàn sai
khác (người thứ 1 số lượng chỗ còn trống 118, người thứ 2 số lượng chỗ còn trống
101, người thứ 3 số lượng chỗ còn trống 100, người thứ 4 số lượng chỗ còn trống 99),
sự sai khác này chính là vấn đề không gắn bó dữ liệu ở bài toán hệ quản lý bãi đậu
xe.bởi vì trong cùng một mốc thời gian thông tin về số lượng chỗ trống trên các trạm
là không hoàn toàn giống nhau. Để đảm bảo các bản cập nhật giống nhau thì trình tự
cập nhật nhất thiết phải giống nhau trên tất cả các trạm.
Bảo vệ 1
Bảo vệ 2 Bảo vệ 3 Bảo vệ 4
t
M
1

M

trên các hệ phân tán cần phải có cách giải quyết thích hợp. Phương pháp giải quyết vấn
đề này được nêu lên ở phần tiếp theo.