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 SERVER
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.79 MB, 27 trang )
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 d ng hoá các lo i hình d ch v tin h c.ạ ạ ị ụ ọ
•
Đ m báo tính toàn v n c a thông tin.ả ẹ ủ
ĐÔ NG BÔ HO A ̀ ̣́
TIÊ N TRI NH́ ̀
Đô ng b hóa các ti n trình trong h đi u ̀ ộ ế ệ ề
hành phân tán
•
Trong hệ phân tán, việc đồng bộ hóa chủ yếu
yêu cầu thiết lập một trật tự giữa các sự kiện.
•
Trật tự đó thể hiện thông qua việc trao đổi các
thông điệp với nhau.
•
Lamport đã đưa ra rằng hai sự kiện từ các trạm
khác nhau chỉ có thể có trật tự nếu chúng được
tách rời với nhau bằng cách gửi và nhận thông
điệp.
Thời gian lôgic và trật tự sự kiện từng
phần [Lamport]
Trật tự giữa các sự kiện có thể được xác lập nhờ
vào quan hệ “có trước” (→), thỏa mãn các điều
kiện sau:
• •
a
b
P
1.
a “có trước” b (a → b)
•
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
P3
Q1
Q2 Q3
P
Q
Trật tự từng phần của các sự
kiện:
P1 → P2 → P3, Q1 → Q2 →
Q3
Thời gian lôgic và trật tự sự kiện từng
phần [Lamport] (t.t)
Nếu P1 là sự kiện phát thông điệp và Q2 là sự
kiện nhận tương ứng thì: P1 → Q2
P
1
P2
P3
Q1
Q2 Q3
P
Q
Thông điệp
Thời gian lôgic và trật tự sự kiện từng
phần [Lamport] (t.t)
Trật tự các sự kiện được định nghĩa như sau:
•
Nếu A và B là hai sự kiện của cùng một trạm
và A xảy ra trước B thì ta có A→B.
•
Nếu A là phát thông điệp từ một trạm nào đó
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
(
b
)
Điều kiện đồng hồ
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
a
Pi
Ci
(
a
) <
Cj
(
b
) và
Cj
(
b
) <
Cj
(
c
)
•
b
Pj
•
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
Tiến trình 2 yêu cầu truy
cập vào
CS.
Điều phối
viên xếp yêu cầu vào
hàng đợi và từ chối
không cho truy cập vì
hàng đợi không trống.
Ti n trình 1 r i kh i ế ờ ỏ
CS.
Điều phối viên loại bỏ 1
khỏi hàng đợi và cấp quyền
truy cập cho tiến trình đầu
tiên trong hàng đợi – đó là
tiến trình 2
1
2 3
C
REL
ACK
2
Thuật toán đóng dấu thời gian của Lamport
•
Thuật toán là sự suy rộng của Hàng đợi tập
trung.
•
Sử dụng cơ chế đóng dấu thời gian cho việc
đồng bộ các đồng hồ lôgic.
•
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:
•
Pi
a
Ci
Ci+1
(m, Tm = Ci (a) )
Thuật toán đóng dấu thời gian của Lamport
Quy luật 3: Khi nhận được thông điệp
m
, tiến
trình
Pj
đặt lại giá trị
Cj
:
Cj
=
max
(
Cj
,
Tm
) + 1
Các qui luật:
•
Pj
Cj
Cj = max (Cj, Tm) + 1
(m, Tm)
a
Các kiểu thông điệp :
•
(
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:
•
Ci
: Đồng hồ cục bộ của
Pi
, khởi tạo từ 0.
•
qi
: Hàng đợi [0 N-1] chứa các thông điệp.
Khi một tiến trình tại trạm Si muốn thi hành đoạn găng,
nó sẽ gửi thông điệp REQ có đánh dấu thời gian cho tất
cả các trạm trong hệ thống kể có trạm Si.
Mỗi trạm, Si, duy trì một hàng đợi chứa các thông điệp
yêu cầu được sắp xếp theo trật tự các dấu thời gian
Khi một trạm nhận được yêu cầu, nó sẽ đưa thông điệp
đó vào hàng đợi yêu cầu của nó theo thứ tự dấ
một tiến trình không thể thi hành đoạn găng của nó cho
đến khi nó nhận được trả lời từ tất cả các trạm khác u
thời gian và gửi một thông điệp trả lời REP
Khi một trạm hoàn thành miền găng của nó, nó sẽ gửi
khuyến nghị giải phóng REL đến tất cả các trạm
Thuật toán
BA I TOA N đ NG B ̀ ́ Ồ Ộ
HÓA TI N TRÌNH Ế
TRÊN H PHÂN TÁN Ệ
V I 4 SERVEŔƠ
