B GIO DC & O TO
I HC NNG
Khoa Cụng Ngh Thụng Tin
Tiểu luận môn
Tiểu luận mônTiểu luận môn
Tiểu luận môn học
học học
học LậP TRìNH MạNG NÂNG CAO
LậP TRìNH MạNG NÂNG CAOLậP TRìNH MạNG NÂNG CAO
LậP TRìNH MạNG NÂNG CAO
Đề tài:
Đề tài:Đề tài:
Đề tài:
LP TRèNH BNG CC PHNG PHP
IU KHIN BI XE
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.

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 1
HVTH: Lê Quốc Dũng -KHMT K16
CHƯƠNG 1 : CƠ SỞ LÝ THUYẾT
Trong chương này, các vấn đề cơ bản sau đây được trình bày :
• Các khái niệm ban đầu như khái niệm hệ phân tán và các đặc điểm chủ
yếu của hệ.
• Tiến trình nhu cầu tài nguyên trong các hệ phân tán.
• Tầm quan trọng của việc đồng bộ hóa các tiến trình trong hệ phân tán.
• Vấn đề tương thích giữa thuật toán điều khiển bải để xe với chiến lược
cung cấp tài nguyên dùng chung trong hệ phân tán.
• Tổng quan về trật tự từng phần và khái niệm ban đầu về ấn phong di
chuyển trên vòng tròn ảo.

đế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).
Bảng I.1 Các ưu điểm căn bản của việc sử dụng chung tài nguyên
2 Các đặc điểm của hệ phân tán
Các đặc điểm và yêu cầu được liệt kê dưới đây (bảng I.2 và I.3) giúp ta nhận
biết những đặc trưng cơ bản và phân biệt hệ tin học phân tán với các hệ tin học khác,
đồng thời cung cấp thông tin cơ bản trong quá trình phân tích, thiết kế, xây dựng và
đánh giá một hệ thống nào đó.

TT Các yêu cầu cơ bản cần nghiên cứu giải quyết
1 Lập trình và thực hiện cho hệ thống đa truy cập, ngẫu nhiên, số
lượng lớn
2 Định danh định danh cho các đối tượng qua hệ thống viễn thông
3 Cấu trúc lập trình được cho các truy vấn đa chiều và đáp ứng lại
truy vấn
4 Trình tự và đồng bộ các tiến trình hoạt động
5 Gắn bó thông tin (Coherence) và vấn đề nhiều bản sao
6 Cung cấp từ xa các tài nguyên dùng chung (tài nguyên găng)
7 Vấn đề xử lý - tính toán đồng thời trong hệ
8 Vấn đề đa Server và hệ điều khiển - giám sát của người quản trị hệ
thống

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ó
là đối tượng được gửi đến từ trước trên bộ xử lý (máy) cục bộ hoặc phải gửi đối
tượng là tiến trình qua hệ thống đường truyền.
5. Việc cung cấp tài nguyên cho các tiến trình có thể thực hiện theo 2 cách
trong hệ phân tán :
• Thông qua hệ thống cung cấp chung cho toàn hệ như
Controllor/Allocator.
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 4
HVTH: Lê Quốc Dũng -KHMT K16
• Thông qua Allocator cục bộ trên Server/Workstation bằng cách tham
chiếu vào bảng trạng thái, ảnh của thông tin toàn cục.
III. TẦM QUAN TRỌNG CỦA VIỆC ĐỒNG BỘ HOÁ TIẾN TRÌNH
TRONG HỆ PHÂN TÁN
Đồng bộ hoá tiến trình được hiểu như là quá trình điều khiển tạo nên sự ăn
khớp với nhau giữa tất cả các tiến trình khác nhau giúp cho hệ phân tán hoạt động
nhịp nhàng, tin cậy và phòng tránh các sự cố kỹ thuật.
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

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
VT
VT
VT
VT
VT
VT
VT
VT
VT
VTVT
VT
VT
BV
BV
BV
BV
BV
BV


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
đến máy dự phòng) và nối
chúng với nhau thông qua hệ
thống đường truyền
4 Chổ để xe Tài nguyên Tài nguyên đồng nhất. Trong
thực tế của hệ phân tán, tài
nguyên có nhiều loại và có các
đặc điểm rất khác xa nhau
5 Ma trận số vị
trí để xe ô tô
Hệ cơ sở dữ liệu
phân tán
Đòi hỏi phải hoàn toàn giống
nhau ở mọi thời điểm truy cập
(Gắn bó dữ liệu)
Bảng I.4 Sự tương quan giữa các đối tượng bãi để xe và hệ phân tán
Bài toán bãi để xe được phát biểu theo tình huống như sau :
Tình huống thứ 1
Ta giả sử rằng bãi để xe ô tô là bãi có số lượng ô lớn và có duy nhất một cổng
vào dưới sự kiểm soát của một (NBV). NBV chỉ biết được một phần của trạng thái bãi

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
Nếu ta không có ràng buộc nào đối với trình tự xử lý các thông điệp nhận được
của các người bảo vệ, thì các người bảo vệ này sẽ có số lượng chổ trống khác nhau. Để
bảo đảm 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 Server/Workstation.
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

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
tiến trình
3 Các thông điệp phải được xử lý cùng một trật tự như nhau trong
các chương trình cung cấp.
Bảng I.7 Các quy tắc tổng quát của việc đồng bộ hoá các tiến trình
Quy tắc sau cùng nhấn mạnh đến sự thiết yếu phải có một trật tự duy nhất trên
tập hợp các thông điệp của hệ. Trật tự này có thể được thực hiện thông qua việc hợp
lực giữa các tiến trình cung cấp mà ta sẽ gặp trong các chương sau hay giữa các tiến
trình phát thông điệp. Trong các phần sau đây của chương này, ta sẽ kiểm tra hai chiến
lược hợp lực giữa các tiến trình phát nhằm phân phối cho mỗi thông điệp một dấu ( có
tài liệu còn gọi là dấu hiệu ) nhằm dựa vào đó, ta có thể xác lập một trật tự hoàn toàn.
Các chiến lược phản ứng được với các sự cố diễn ra trên một Server/Workstation, nếu
giả sử H
4
của được nghiên cứu và triển khai.
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 9
HVTH: Lê Quốc Dũng -KHMT K16

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.
Việc vận dụng tương đối tổng quát bộ tuần tự S trong hệ phân tán là sự chuyển
động giữa các trạm một đối tượng duy nhất gọi là ấn phong chứa giá trị hiện hành của
bộ tuần tự. Khi một trạm có ấn phong, nó có thể thực hiện hàm phieu(S).
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 10
HVTH: Lê Quốc Dũng -KHMT K16
Trước hết, chúng ta nghiên cứu hai phương pháp cho phép di chuyển ấn phong,
sau đó là giải thuật triển khai phép toán phieu. Cuối cùng, ta quan tâm hai vấn đề là sử
dụng đường lan truyền và việc sao chép bộ tuần tự trên mỗi trạm.
2. Bộ tuần tự di chuyển
2.1 Vòng tròn ảo
Để triển khai một ấn phong có kết quả, đầu tiên ta cần phải xác định hành trình
của nó trong mạng máy tính như thế nào. Phương pháp đơn giản nhất là lắp đặt các
trạm nằm trên một vòng theo một chiều xác định. Mỗi trạm chỉ được liên hệ với hai
trạm gần nhất.
Ta hãy xem xét một mạng được hoàn toàn nối với nhau có nghĩa là một tập hợp
bao gồm N trạm, trong đó một trạm có thể liên lạc với các trạm khác một cách dễ

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
S[0] := S[0] + 1 mod K, nếu i = 0
Đó là trường hợp duy nhất mà tiến trình có thể cập nhật các biến trạng thái của
mình.
Nếu tất cả các tiến trình loại Pi đều sử dụng thuật toán này, thì quyền bình đẳng
giữa các trạm được bảo đảm vì mỗi tiến trình đều được nhận ấn phong khi đến phiên
mình.
Ta lấy ví dụ với các giá trị N =3 và K = 2. Nếu trạng thái ban đầu của ba biến
trạng thái là 000, hệ thống chuyển qua các trạng thái sau đây. Ta ký hiệu dấu * là biến
của tiến trình có ấn phong.
Hình I.2 Trạng thái hệ thống

Hình vẽ I-3 chỉ ra sự phát triển của hệ trong trường hợp này.
Chú ý :
Vì ấn phong là duy nhất cho nên ta cần áp dụng loại trừ tương hổ trong trường
hợp này. Một trạm nhận được ấn phong nhưng lại không vào đoạn găng thì phải lập
tức giải phóng nó.

1

1

0

-

1

1

1

-

0

1

1

-

0

0

1


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
Trong thuật toán thứ hai thuộc Le Lann, ấn phong được cụ thể hóa bằng một
thông điệp đặc biệt và gọi là Jeton tuần hoàn trên vòng tròn. Như thế, việc sự cố trên
trạm có thể dẫn đến mất Jeton. Các biến trạng thái được duy trì trên mỗi trạm cho phép
tái sinh jeton trong trường hợp bị mất.
Thuật toán triển khai ý tưởng này là :
1. Jeton mang giá trị là v tương tự với cao độ của mặt trước trong thuật toán
của. Mỗi một trạm j có một biến trạng thái S[j]. Trước khi phát lại jeton vào mạng, các
tác động như sau được thực hiện :

S[j] := v cho j ≠ 0
v := v +1 mod K ; S[j] := v cho j = 0

2. Mỗi một lần chuyển jeton trên trạm j , một đồng hồ bảo vệ được trang bị.
Nếu nó được phát động trước khi jeton đến, thì j tham chiếu đến biến trạng thái S[i]
của trạm kề liền trước i = pred(i) trên vòng tròn.
Nếu một trong hai điều kiện sau đây được kiểm tra,

j > i và S[j] ( S[i]
hay

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
một kênh duy nhất. Các trạm nối với kênh này bởi thiết bị truyền thông (TBTT). Việc
cạnh tranh truy cập đường truyền, việc xử lý các xung đột và việc nhận các thông điệp
được thực hiện thông qua thiết bị này theo các kỹ thuật và công nghệ đã được trình
bày trong môn học mạng máy tính. Theo thiết kế, một lúc, chỉ có một thông điệp được
truyền.
Ta giả sử rằng mỗi TBTT truyền các thông điệp vào đường truyền theo trình tự
mà trạm liên lạc với nó xác định và dội lại trạm này các thông điệp từ đường truyền,
kể cả các thông điệp của chính nó. Ngoài ra, ta còn giả định là
đường truyền không hề làm mất thông điệp và các TBTT đều sắp xếp các thông
điệp theo một trật tự giống nhau. Trong trường hợp này, ta có một trật tự tổng quát và
nó được thể hiện trong hình vẽ I-4.
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 14
HVTH: Lê Quốc Dũng -KHMT K16
Để thực hiện một bộ tuần tự phân tán S , trạm i nào đó cần phải duy trì công tơ
cục bộ và thực hiện cùng một thuật toán.
Thuật toán đó thể hiện như bảng I.9.

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
đó không là nguyên nhân gián đoạn trao đổi giữa các trạm.
VIII. KẾT LUẬN
Thông qua chương 1 của tiểu luận, những vấn đề có tính chất cơ sở về phân
tích, thiết kế, xây dựng, khảo sát - kiểm nghiệm các chiến lược đồng bộ hoá tiến trình
trong hệ phân tán được trình bày. Hệ phân tán với các đặc điểm quan trọng là :
1. Không sử dụng chung bộ nhớ và đồng hồ vật lý,
2. Được mắc nối với nhau thông qua hệ thống đường truyền (viễn thông),
nhưng về cơ bản hệ hoạt động hoàn toàn độc lập với nhau trên bộ xử lý riêng của
mình,
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 16
HVTH: Lê Quốc Dũng -KHMT K16
3. Các thành phần cơ bản của hệ có thể được bố trí trên một phạm vi địa lý rộng
lớn,
4. Việc ăn khớp giữa các hoạt động này (còn gọi là đồng bộ hóa các hoạt động
thành phần) được tiến hành thông qua trao đổi thông điệp giữa các thực thể của hệ,
5. Truy cập mang tính ngẫu nhiên, từ xa và số lượng truy cập lớn

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á
từng phần giữa các sự kiện mà các tiến trình của nó cần phải đồng bộ là vấn đề cần
phải quan tâm giải quyết.
Trong các hệ thống phân tán, việc đồng bộ hoá chỉ đặt ra duy nhất vấn đề thiết
lập một trật tự giữa các sự kiện. Giữa các trạm khác nhau, trật tự đó chỉ có thể hiện
được thông qua việc trao đổi các thông điệp với nhau.
Giả sử rằng ta có thể xác định một trật tự giữa các sự kiện của hệ phân tán nhờ
vào quan hệ được ký hiệu là → và gọi là “có trước” hay “ở ngay trước”.
Quan hệ này tối thiếu phải thoã mãn được ràng buộc thể hiện trong bảng sau
đây :

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 18
HVTH: Lê Quốc Dũng -KHMT K16


5

B
1
→ B
2
→ B
3
→ B
4

Trao đổi thông tin
A
1
→ B
2
và B
3
→ A
4

Chuyển qua
A
1
→ A
2
→ B
2
→ B
3

1
, A
2
, A
3

A
3
và B
2
, B
3
, B
4

Ràng buộc C
1
thể hiện rằng trật tự có thể được bởi quan hệ có trước là tương
thích với các trật tự cục bộ được định nghĩa trong từng trạm.
Ràng buộc C
2
nói lên nguyên tắt nhân quả.
Quan hệ có trước xác định một trật tự từng phần trên tập hợp các sự kiện của hệ
và trật tự này có thể hiện trong hình vẽ trên
C
1
: Nếu A và B là hai sự kiện của cùng một trạm và nếu A được thực hiện
trước B thì theo trật tự cục bộ của trạm ta có A → B.
C
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
đã nêu lên trong H
4
ở trên. Ngoài ra còn giả sử rằng hiện tượng gây sự cố trên một
trạm chỉ làm cho trạm đó không liên lạc được với mạng mà hoàn toàn không ảnh
hưởng đến sự hoạt động của các trạm còn lại hoặc ít nhất là một nhóm các trạm khác.
IV. CÁCH GIẢI QUYẾT VẤN ĐỀ ĐỒNG BỘ HOÁ
1. Đồng bộ hoá bằng phương pháp trật tự từng phần
Sử dụng các công tơ sự kiện thích hợp với các vấn đề đặt ra, Mỗi công tơ, biến
nguyên không lùi, được kết hợp với một nhóm đặt biệt các sự kiện. Trên một công tơ
sự kiện nào đó có phối hợp với nhau được thực hiện bởi các hàm nguyên thuỷ. Việc
triển khai các công tơ sự kiện có thể được thực hiện bằng cách giao cho một bộ xử lý
duy nhất đảm trách việc điều khiển toàn bộ công việc này.
2. Đồng bộ hoá theo một trật tự tổng quát chặt chẽ
Trong một số trường hợp cần phải sắp xếp toàn bộ theo kiểu chặt chẽ các sự
kiện của hệ liên quan trực tiếp đến việc cung cấp các tài nguyên. Nguyên lý của vấn đề
được khái quát như sau. Một tiến trình nào đó gởi thông điệp để yêu cầu sử dung tài
nguyên; một tiến trình sử dụng xong tài nguyên nào đó truyền một thông tin giải
phóng khi nó ngừng chiếm dụng.
Cung cấp tập trung

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
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VT
VTVT
VT
VT
BV
BV
BV
BV

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
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 lúc này của hệ là gắn bó. Ba trong số họ phát đi các thông tin
sau :

STT Ký hiệu Thông tin phát đi
1 M1 Thêm 20 chỗ trống
2 M2 Đã có 10 chỗ bị chiếm
3 M3 Dành 10% chỗ trống để quét dọn sân 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 22
HVTH: Lê Quốc Dũng -KHMT K16
các người bảo vệ ra các quyết định để ôtô vào và ra khỏi bãi đậu một cách có
trật tự theo hình vẽ II.3

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
3 M3 99 M3 99 M3 99 M3 99
Bảng II.1 : Sự gắn bó giữa bốn người bảo vệ
Sau khoảng thời gian, ta nhận thấy rằng dữ liệu ở các trạm trên bảng II.1 là
giống nhau hoàn toàn. Trường hợp này cho thấy dữ liệu ở hệ quản lý đỗ xe là gắn bó.
Nhưng trong thực tế của bài toán hệ quản lý đổ xe việc phát và nhận các thông tin
không được biết lúc nào truyền và lúc nào là nhận cho nên trường hợp trên là quá lý
tưởng (ít xảy ra) và trong khi giải quyết bài toán quản lý bãi đổ xe chúng ta cố gắng
đưa hệ về tình huống này theo một trình tự cập nhật nhất thiết phải giống nhau trên các
trạm.

+ Tình huống thứ 4 :
Cũng theo giả định của tình huống 3 nhưng lúc này các thông điệp được phát và
nhận không theo một trật tự được sắp xếp. Quá trình truyền và nhận thông tin được thể
hiện ở hình II.3
Bảo vệ 1
Bảo vệ 2 Bảo vệ 3 Bảo vệ 4
t
M
1

Từ hình vẽ trên cho ta thấy, nếu ta không có ràng buộc nào đối với trình tự xử
lý các thông điệp nhận được của các người bảo vệ thì các người bảo vệ này sẽ có số
lượng chỗ trống khác nhau.

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

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
3
M
1

M
2
M
3
M
3
M
1
Hình II.3 : Thời hạn truyền và nhận thông điệp

M
2
M
2