ĐỀ TÀI

Hãy viết chương trình mô phỏng quá trình phát
và nhận thông điệp trong hệ phân tán

Xây dựng hệ thống 3 server có khả năng phát
nhận thông điệp
GVHD : PGS.TS Lê Văn Sơn
HVTH : Đặng Ngọc Thắng
LỚP : KHMT
KHÓA : K24

GIỚI THIỆU ĐỀ TÀI


- Phần 1: Phần cơ sở lý thuyết những vấn đề chung nhất của
hệ tin học phân tán làm cơ sở cho các phần 2 của đề tài.
- Phần 2: Lập trình phân tán
- Phần 3: Triển khai chương trình
- Phần 4 : Đánh giá kết quả thực hiện được và hướng phát
triển ứng dụng

LÝ THUYẾT

ĐẶT VẤN ĐỀ

Trong môi trường hệ phân tán, việc các tiến trình
muốn truy cập vào các tài nguyên có số lượng hạn
chế hay thông tin dùng chung cùng một lúc là có
thể xảy ra, trường hợp này được gọi là tương

Tienrut =
400
TÀI KHOẢN
P2
Tienrut =
500
800
IF (tai khoan – tien rut >=0)
THEN tai khoan = tien khoan – tien rut;
ELSE thong bao loi;
IF (tai khoan – tien rut >=0)
THEN tai khoan = tien khoan – tien rut;
ELSE thong bao loi;
Chi nhánh I
Chi nhánh II


Trong hệ thống tin học tập trung, vấn đề đồng bộ
hóa được giải quyết thông qua cơ chế loại trừ
tương hỗ. Tuy nhiên, trong hệ phân tán, việc đồng
bộ hóa chỉ đặt ra yêu cầu 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ự đó có thể thể hiện được thông qua
việc trao đổi các thông điệp với nhau.

TRẬT TỰ TỪNG PHẦN

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 “ở

thông điệp nhằm ghi nhận thời điểm truyền trên cơ
sở tham chiếu đồng hồ logic.

Nội dung cơ bản của phương pháp này là trạm
phát được gắn một giá trị gọi là dấu. Giá trị này là
tính chất thời điểm cho trạm phát thông tin và dựa
vào đồng hồ logic cục bộ của chính trạm. Giải
thuật trình bày ở đây là giải thuật Lamport nhằm
cho phép ghi lại các sự kiện của hệ phân tán.

SẮP XẾP KIỂU ĐÓNG DẤU

Giải thuật Lamport nhằm giải quyết vấn đề trình tự (vấn đề mấu
chốt của hệ phân tán) dựa trên giá trị đồng hồ lo gích để sắp xếp
các thông điệp đến.

Mỗi trạm s đều có trang bị công tơ với các giá trị nguyên gọi là
H
s
. Đó chính là đồng hồ lô gích tăng lên giữa hai sự kiện kế tiếp.
Trạm e phát thông điệp ghi dấu E của mình dựa trên giá trị hiện
hành của H
e
. Khi nhận được thông điệp, trạm r cập nhật đồng hồ
H
r
riêng của mình bằng giải thuật sau đây :
Nếu H
r,
thì


Theo định nghĩa, ta có :
a ⇒ b ⇒ (H
i
(a) < H
i
(b)) hay (H
i
(a) = H
i
(b) và i<j)

SẮP XẾP KIỂU ĐÓNG DẤU
Giả thiết
Giả thiết

Trạm i của mạng có thể gửi cho các trạm khác
thông điệp có dạng (T Hi, i), trong đó Hi là dấu
của thông điệp có nghĩa là đồng hồ lô gích của nó
và T có thể nhận một trong ba giá trị REQ, REL,
và ACQ.

SẮP XẾP KIỂU ĐÓNG DẤU

Ba giá trị này xác định bản chất của ba loại thông
điệp khác nhau
STT
Thông
điệp
Giải thích


Mỗi trạm quản lý một hàng đợi các thông điệp
được sắp xếp hoàn toàn bởi quan hệ ⇒ theo cặp
<thời gian, số> của từng thông điệp.

Thuật toán được mô tả theo sơ đồ sau :

Khởi tạo hàng đợi, mỗi máy tự phát thông điệp
M
i
= (REL, C
init
, i)

SẮP XẾP KIỂU ĐÓNG DẤU

Trên mỗi trạm, khi nhận được một thông điệp dạng (REQ,Hi,i) hay
(REL,Hi,i) thông điệp này thay thế thông điệp Mi bất chấp nó là gì.
Khi nhận thông điệp loại (ACQ, Hi,i), thông điệp này thay thế Mi
ngoại trừ nếu Mi là một yêu cầu mà trong trường hợp đó ACQ bị bỏ
qua. Do vậy, ta có thể tiết kiệm việc gởi đi thông điệp ACQ cho
trạm i khi trạm này đã gởi một thông điệp REQ và không còn thông
điệp REL.

Trạm i được quyền vào đoạn găng khi thông điệp REQ của nó đến
trước theo nghĩa của quan hệ => tất cả các thông điệp khác trong
hàng đợi của nó.

ĐỒNG HỒ LOGIC LAMPORT
Cài đặt đồng hồ Lamport

3
4
5
5
6
7
8
9 10
7
Thời gian vật lý
n
Giá trị đồng hồ.
timestamp
Thông điệp
0
1
2
3
4
6
8
7
Các sự kiện logic đồng thời

THUẬT TOÁN LARMPORT
TỔNG QUÁT
(a) cả hai tiến trình 0 và 2 yêu cầu vào đoạn găng
(b) tiến trình 0 vào đoạn găng vì nó có yêu cầu đầu tiên
(c) tiến trình 0 rời đoạn găng, tiến trình 2 vào đoạn găng.


Gởi thông điệp cho mọi tiến trình khác trong hệ