V. Đồng bộ hóa và phối hợp
Hệ phân tán (NW605)
1. Các thuật toán phân tán
2. Thời gian và đồng hồ
3. Trạng thái toàn cục
4. Kiểm soát tương tranh
Middleware 2
Các thuật toán phân tán
Thuật toán phân tán được thiết kế để làm việc trong một môi trường phân tán
•
Dùng để thực hiện các nhiệm vụ như:
–
Liên lạc
–
Truy nhập tài nguyên
–
Cấp phát tài nguyên
–
Đồng thuận
–
v.v
•
Đồng bộ hóa và phối hợp đóng vai trò quan trọng với thuật toán phân tán
–
Một số thuật toán phân tán được dùng để đạt được sự đồng bộ và phối hợp
–
Một số thuật toán phân tán đòi hỏi cơ chế đồng bộ hóa và phối hợp
Middleware 3
Hệ phân tán đồng bộ / không đồng bộ
Mô hình thời gian của một hệ phân tán
Chịu ảnh hưởng của:

–
Thời gian/tốc độ thực thi của các tiến trình
–
Độ trễ liên lạc
–
Clock drift – đồng hồ tại các tiến trình chạy nhanh/chậm khác
nhau do có chu kì khác nhau
–
Thất bại (của một bộ phận)
Hai mô hình thời gian:
–
Mô hình đồng bộ
–
Mô hình không đồng bộ.
Middleware 4
Hệ phân tán đồng bộ
Độ xê dịch thời gian nằm trong giới hạn
Thực thi: thời gian và tốc độ thực thi nằm trong giới hạn
Liên lạc: độ trễ truyền thông tin nằm trong giới hạn
Đồng hồ: chênh lệch về thời gian địa phương và độ lệch của đồng hồ nằm trong giới hạn
Hiệu ứng:
•
Có thể dựa vào timeout (thời gian đợi vượt ngưỡng) để phát hiện thất bại
–
Ưu: dễ dàng hơn cho việc thiết kế các thuật toán phân tán
–
Nhược điểm: đòi hỏi rất chặt chẽ
•
Hạn chế về số tiến trình song song tại mỗi bộ xử lý
•

Hạn chế về việc song song sử dụng mạng
•
Đòi hỏi đồng hồ chính xác và việc đồng bộ hóa đồng hồ
Middleware 5
Hệ phân tán không đồng bộ
Độ xê dịch thời gian không có giới hạn
Thực thi: thời gian chạy các bước không bị giới hạn
Liên lạc: độ trễ truyền thông tin đa dạng
Đồng hồ: chênh lệch về thời gian địa phương là tùy ý
Hiệu ứng:
•
Không có giả thiết gì về các khoảng thời gian
–
Không thể dựa vào timeout để phát hiện thất bại
–
Đa số các bài toán phân tán không đồng bộ đều khó giải quyết
–
Lời giải cho phân tán không đồng bộ cũng dùng được cho phân tán đồng
bộ
•
Đa số các hệ phân tán thực vừa có tính đồng bộ vừa có tính không đồng bộ
Middleware 6
Đồng bộ hóa và phối hợp
Quan trọng:
Doing the right thing at the right time
Hai vấn đề căn bản:
•
Phối hợp (the right thing)
•
Đồng bộ hóa (the right time)

Middleware 7
Đồng bộ hóa
Sắp thứ tự tất cả các hành động
–
Thứ tự toàn phần của các sự kiện
–
Thứ tự toàn phần của các lệnh (instruction)
–
Thứ tự truy nhập tài nguyên
–
Đòi hỏi khái niệm về thời gian
Middleware 8
Phối hợp
Phối hợp hành động và đồng ý về các giá trị
Phối hợp hành động:
–
Sẽ thực hiện những hành động gì
–
Ai sẽ làm
Đồng ý về các giá trị
–
Đồng ý về giá trị toàn cục
–
Đồng ý về môi trường
–
Đồng ý về trạng thái
Middleware 9
Các vấn đề chính
Thời gian và đồng hồ: đồng bộ hóa các đồng hồ khác nhau và sử dụng thời gian trong các thuật toán
phân tán

Trạng thái toàn cục: làm thế nào để có được kiến thức về trạng thái toàn cục của hệ thống
Kiểm soát tương tranh: phối hợp các truy nhập tương tranh (đồng thời) tới tài nguyên
Phối hợp: khi nào các tiến trình cần phối hợp và phối hợp như thế nào
Thời gian và đồng hồ
10.2, 10.3, 10.4, Coulouris
Middleware 11
Thời gian
Giờ toàn cầu:
–
Giờ UTC – Coordinated Universal Time
•
Dựa vào dao động nguyên tử Cesium-133
•
Giờ toàn cầu chính xác nhất
•
Coi là thời gian tuyệt đối
Giờ địa phương:
–
Thời gian liên quan đến tiến trình đang chạy trong hệ phân
tán / thuật toán phân tán
–
Đồng hồ vật lý / đồng hồ lôgic
–
Có tính tương đối
Middleware 12
Đồng hồ
Đồng hồ máy tính:
–
Các dao động tinh thể với tần số biết trước
–

Các dao động gây ra các ngắt đồng hồ
–
Ngắt đồng hồ cập nhật đồng hồ
Clock skew – lệch giờ
–
Tại cùng một thời điểm, đồng hồ ở các máy khác nhau báo giờ
khác nhau
Timestampt – nhãn thời gian
–
Dùng để ghi lại thời điểm một sự kiện xảy ra
–
Lôgic / vật lý
Middleware 13
Đồng hồ vật lý
Đồng bộ hóa bằng đồng hồ vật lý
Ví dụ:
–
Thực hiện hành động tại một thời điểm chính xác (tắt/bật đèn, đóng/mở
cổng)
–
Ghi nhật trình các sự kiện (phục vụ bảo mật, tìm lỗi, xây dựng hồ sơ)
–
Theo dõi (các camera khác nhau để theo dõi một vật thể đang di chuyển)
–
make (lập trình tại máy này, dịch tại máy khác)
Dựa vào thời gian thực
–
C
p
(t): giờ hiện hành (tại thời điểm t giờ UTC) tại máy p

•
Lý tưởng: C
p
(t) = t
–
Đồng hồ chạy nhanh/chậm → phải định kì đồng bộ theo UTC
Middleware 14
Đồng bộ hóa đồng hồ vật lý
Đồng bộ ngoài – external synchronization
–
Đồng hồ chỉnh giờ theo một nguồn ngoài
•
Chỉnh giờ theo UTC sau mỗi khoảng thời gian dài δ giây
–
Chính xác trong phạm vi δ
Đồng bộ trong - internal synchronization
–
Các đồng hồ trong một hệ thống chỉnh giờ theo nhau
–
Đồng bộ với nhau nhưng có thể cùng lệch giờ với bên ngoài
Dùng time server
–
Server có giờ đúng
–
Server tính ra giờ đúng
Middleware 15
Thuật toán Cristian
Time server
–
Có thiết bị nhận giờ từ nguồn UTC

–
Bị động
Thuật toán
–
Client định kỳ gửi yêu cầu hỏi giờ
•
t + <thời gian trễ>
–
Không chỉnh lùi đồng hồ
–
Tính đến độ trễ truyền tin và xử lý ngắt
•
(T1 – T0)/2, hoặc
•
Đo một loạt và lấy trung bình độ trễ
Middleware 16
Thuật toán Berkeley
master
slave
Middleware 17
Network Time Protocol (NTP)
Mạng các server cấu trúc thành cây
–
Server sơ cấp có đồng hồ UTC
–
Server cấp 2 nối với server sơ cấp, chỉnh theo server sơ cấp
–
v.v
Các kiểu đồng bộ hóa:
–

Multicast: server định kì gửi giờ cho các server chạy tại các
máy khác trong mạng LAN
•
độ chính xác thấp
–
Procedure call: tương tự thuật toán Cristian,
•
độ chính xác tương đối
–
Symmetric: đồng bộ hóa giữa các cặp server ngang hàng,
•
độ chính xác cao nhất
Middleware 18
Đồng hồ lôgic
Thứ tự của các sự kiện quan trọng hơn thời gian vật lý
–
Các sự kiện (VD: thay đổi trạng thái) trong một tiến trình được sắp thứ tự
–
Các tiến trình cần thống nhất về thứ tự của các sự kiện có quan hệ nhân
quả với nhau (vd: gửi và nhận thông điệp)
Thứ tự địa phương:
–
Hệ thống có N tiến trình pi, i thuộc {1,…,N}
–
Thứ tự sự kiện địa phương →
i
: nếu p
i
thấy e trước e’, ta có e →
i

e’
Thứ tự toàn cục:
–
Quan hệ xảy-ra-trước (kí hiệu →) của Leslie Lamport
1. Nếu tồn tại p
i
thấy e →
i
e’, thì ta có e →

e’
2. Với mỗi thông điệp m, send(m) → receive(m)
3. Tính bắc cầu: e → e’ và e’ →

e” kéo theo e →

e”
Middleware 19
Đồng hồ lôgic (2)
Quan hệ → là một thứ tự bộ phận:
–
Nếu a → b thì a dẫn đến b về mặt nhân quả
–
các sự kiện không được sắp thứ tự được coi là các sự kiện đồng
thời
Ví dụ:
Middleware 20
Đồng hồ Lamport
Đồng hồ lôgic Lamport:
–

Con đếm phần mềm tính quan hệ xảy-ra-trước →
–
Mỗi tiến trình p
i
giữ một đồng hồ lôgic L
i
Lamport timestampt:
–
L
i
(e): nhãn thời gian của sự kiện e tại p
i

–
L(e): nhãn thời gian của e tại tiến trình mà nó xảy ra
Thuật toán:
1. Trước khi gắn nhãn một sự kiện tại chỗ, p
i
chạy L
i
:= L
i
+ 1
2. Mỗi khi một thông điệp m được gửi từ p
i
đến p
j
:
•
p

i
chạy L
i
:= L
i
+ 1 và gửi L
i
cùng m
•
p
j
nhận L
i
cùng m và chạy L
j
:= max( L
i
,L
i
) + 1, receive(m) được gắn với L
j
Tính chất:
–
a → b kéo theo L(a) < L(b)
–
L(a) < L(b) chưa chắc có nghĩa a → b
Middleware 21
Đồng hồ lôgic sắp thứ tự toàn bộ
Ví dụ:
Thứ tự toàn bộ:

–
Hoàn chỉnh thứ tự bộ phận thành thứ tự toàn bộ bằng cách gắn thêm định
danh tiến trình
–
Cho trước các timestampt địa phương L
i
của e và L
i
của e’, ta định nghĩa
timestampt toàn cục (L
i
, i) và (L
i
, j)
–
Thứ tự từ điển: (L
i
, i) < (L
i
, j) khi và chỉ khi
•
L
i
< L
i
, hoặc
•
L
i
= L

i
và i<j
Middleware 22
Đồng hồ Lamport
Nhược điểm chính của đồng hồ Lamport:
–
L(a) < L(b) chưa chắc có nghĩa a → b
–
không thể rút ra
quan hệ phụ thuộc
nhân quả
từ các nhãn thời gian
–
L
1
(E
11
) < L
3
(E
33
), nhưng không có E
11
→ E
33

–
Tại sao?
•
Đồng hồ tăng một cách độc lập hoặc qua các thông điệp

•
Lí do tăng con đếm đồng hồ không được lưu lại
Middleware 23
Đồng hồ vector
Tại mỗi tiến trình: 01 đồng hồ cho mỗi tiến trình khác
–
mỗi đồng hồ V
i
là một vector kích thước N
–
V
i
[j] chứa kiến thức của i về đồng hồ của j
Thuật toán:
1.
Khởi tạo: Vi[j] := 0 với i,j thuộc {1,…, N}
2.
Trước khi pi gắn timestampt một sự kiện, Vi[i] := Vi[i] + 1
3.
Mỗi khi một thông điệp m được gửi từ pi đến pj:
–
p
i
chạy V
i
[j] := V
i
[j] + 1 và gửi V
i
với m.

–
p
j
nhận V
i
với m và trộn với đồng hồ vector của mình:
Kết quả: a → b khi và chỉ khi V(a) < V(b)
Trạng thái toàn cục
10.5, Coulouris
Middleware 25
Trạng thái toàn cục
Xác định tính chất toàn cục
Ví dụ:
–
Distributed garbage collection
•
Còn tồn tại tham chiếu đến một đối tượng cho trước?
–
Distributed deadlock detection
•
Các tiến trình có đợi nhau theo vòng tròn không?
–
Distributed termination detection
•
Các tiến trình đã ngừng mọi hoạt động chưa?