Đồng bộ hóa

(Synchronization)

-Tìm hiểu bằng cách nào các tiến trình đồng bộ hóa được với nhau.

-Đồng bộ hóa trong các hệ thống phân tán thường khó hơn rất nhiều so với đồng bộ hóa trongcác hệ đơn hoặc đa xử lý.

-Vấn đề trong chương này hướng tới đồng hộ hóa dựa trên thời gian hoạt động, tức là thời gian có tính tương quan giữa các tiến trình hơn là thời gian tuyệt đối.

-Trong nhiều trường hợp, đồng bộ hóa có thể được giải quyết bằng cách một nhóm các tiến trình có thể sử dụng 1 tiến trình được thực thi bằng cách lấy trung bình một vài thuật toán lựa chọn.

1.Đồng hồ logic (Logical Clock)

Trong nhiều trường hợp, giữa các tiến trình không nhất thiết phải phù hợp theo thời gian thực tế mà chỉ cần khớp với nhau về thời gian. Do đó người ta đưa ra khái niệm đồng hồ logic.

1.1Nhãn thời gian Lamport (Lamport timestamps).

Lamport đã đưa ra mô hình đồng hồ logic đầu tiên cùng với khái niệm nhãn thời gian.

a. Xét định nghĩa mối quan hệ “xảy ra trước” - (-> )

Khi có A-> B : A xảy ra trước B thì tất cả các tiến trình trong hệ phân tán thỏa thuận sự kiện A xảy ra trước rồi đến sự kiện B.

A và B là hai sự kiện của cùng một tiến trình. Nếu A xảy ra trước B thì A->B là đúng.

Nếu A là sự kiện bản tin được gửi bởi một tiến trình nào đó, còn B là sự kiện bản tin đó được nhậnbởi một tiến trình khác thì quan hệ A-> B là đúng.

Quan hệ xảy ra trước có tính bắc cầu: A->B , B->C thì A-> C.

b. Tem thời gian (Time Stamps)

Để đo thời gian tương ứng với 4 sự kiện x thì ta gán một giá trị C(x) cho sự kiện đó và thỏa mãn các điều kiện sau:

Nếu A-> B trong cùng một tiến trình thì C(A) < C(B).

Nếu A và B biểu diễn tương ứng việc gửi và nhận một thông điệp thì ta có C(A)< C(B)

Với mọi sự kiện phân biệt (không có liên quan) thì C(A)<>C(B)

1.2 Vector thời gian (Vector Timestamps)

Giải thuật vector timestamp đưa ra một vetor timestamp VT(a) gán cho sự kiện a có thuộc tính là nếu Vtt(a) < VT(b) thì sự kiện là nguyên nhân của b.

Trong vector thời gian mỗi tiến trình Pi lưu giữ một Vi với giá trị N (các tiến trình khác nhau thì N khác nhau) 

- Vi[i] là số các sự kiện đã xảy ra tại Pi

- Nếu Vi[j] = k nghĩa là Pi biết đã có k sự kiện đã xẩy ra tại Pj

Yêu cầu: mỗi khi có sự kiện mới xảy ra ở tiến trình Pi thì phải tăng Vi[i] và phải đảm bảo vector này được gửi cùng thông điệp suốt trong quá trình.

Nhờ đó bên nhận sẽ biết được đã có bao nhiêu sự kiện xảy ra tại Pi .Quan trọng hơn phía nhận sẽ báo cho biết là đã có bao nhiều sự kiện ở các tiến trình khác đã xảy ra trước khi Pi gửi thông điệp m.Nói cách khác timestamp VT của n nói cho bên nhận biết bao nhiêu sự kiện đã xảy ra trong các tiến trình khác trước m.

Luật cập nhật vector

- Thiết lập Vi[j] =0 với mọi j,i

- Sự kiện xảy ra ở Pi là nguyên nhân tăng Vi[i]

- Pi gắn một timestamp t=V[i] vào mọi thông điệp gửi đi

- Khi Pi nhân được một thông điệp có t nó sẽ thiết lập 

Vi[j]=Max(Vi[j] ,t[j]) và tăng Vi[i]