XÂY D NG GI I PHÁP Đ NG B HÓA TI N Ự Ả Ồ Ộ Ế
TRÌNH TRÊN H PHÂN TÁN V I 4 SERVEŔỆ Ơ
GVHD : PGS. TS. Lê Văn S nơ
H c ọ
viên : Nguy n Anh Toànễ
Hoàng Xuân Đăng C ngườ
Ngô Minh C ngườ
Đoàn Sinh Công
L pớ : K7MCS
NỘI DUNG
Tông Quan hê phân ta ń̉ ̣
Đô ng bô ho a tiê n tri nh̀ ́ ́ ̣̀
Ca c thuât toa n đô ng bô ho á ́ ̀ ̣́ ̣
Ba i toa n đ ng b hóa ti n trình trên ̀ ́ ồ ộ ế
h phân tán v i 4 serverệ ớ
Hệ tin học phân tán hay nói ngắn gọn là hệ
phân tán (Distributed System) 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 đượ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
h phân tán có các u đi m căn b n so v i ệ ư ể ả ớ
h t p trung:ệ ậ
•
Tăng t c đ bình quân trong tính toán, x lý.ố ộ ử
•
C i thi n tình tr ng luôn s n sàng c a các lo i tài ả ệ ạ ẵ ủ ạ
nguyên.
•
Tăng đ an toàn cho d li u.ộ ữ ệ

•
a
P
2.
a “có trước” b (a
→ b)
•
b
Q
•
Thời gian lôgic và trật tự sự kiện từng
phần [Lamport] (t.t)
3.
a
P
a “xảy ra trước” c (
a
→
c
) - b c c u - ắ ầ
•
b
Q
•
c
•
Xét về trật tự sự kiện:
P
1
P2

và B là nhận thông điệp thì ta có A→B.
•
Nếu A→B và B→C, thì A→C.
•
Nếu hai sự kiện A và B xảy ra ở hai tiến trình
riêng biệt và không trao đổi thông điệp thì
các tiến trình này được gọi là song song (A||
B)
Thời gian lôgic và trật tự sự kiện từng
phần [Lamport] (t.t)
Thời gian lôgic và trật tự sự kiện từng
phần [Lamport] (t.t)
Gắn thời gian lôgic với các sự kiện
•
Các đồng hồ lôgic: gán một số cho mỗi sự kiện
cục bộ nhưng không liên quan đến thời gian
vật lý.
∀ sự kiện
a,b
: nếu
a
→
b
thì
C
(
a
) <
C
(

CÁC THUẬT TOÁN
Thuật toán giả phân tán : Hàng đợi tập trung
- Có một trạm điều khiển việc cung cấp tài
nguyên.
- Trạm điều khiển duy trì một hàng đợi chứa
các yêu cầu và cấp cho mỗi trạm quyền truy
cập vào miền găng theo lần lượt.
1
2 3
C
REQ
ACK
1
Tiến trình 1 yêu cầu truy
cập vào miền găng
CS.

Điều phối viên đưa yêu
cầu vào hàng đợi và cấp
quyền truy cập vì lúc
đầu hàng đợi trống.
Tiến trình trạm điều khiển với Hàng đợi Yêu
cầu
1 2 3
C
REQ
1
Không h i ồ
âm
2

Giả định các tiến trình liên lạc thông qua các
kênh FIFO tin cậy.
Thuật toán đóng dấu thời gian của Lamport
Quy luật 1: Mỗi tiến trình
Pi
gia tăng
Ci
thêm
một trị số giữa hai sự kiện thành công.
Các qui luật:
•
Pi
a
Ci
Ci+1
Thuật toán đóng dấu thời gian của Lamport
Quy luật 2: Mỗi tiến trình
Pi
đóng dấu thời
gian cho các thông điệp
m
gửi đi,
Tm
=
Ci
(
a
)
Các qui luật:
•

•
(
REQ, Ci, i
) : Yêu cầu truy cập vào miền găng
CS
của tiến trình
Pi
.
•
(
REP, Ci, i
) : Hồi âm từ tiến trình Pi cho tiến
trình
Pj
khi
Pi
nhận yêu cầu từ
Pj
.
•
(
REL, Ci, i
) : Thông điệp giải phóng từ
Pi

thông báo cho biết nó đã rời khỏi
CS.
Các biến tiến trình:

•