Chương 5 : Đồng bộ hóa 

5.1 Đồng bộ hóa đồng hồ

Trong HPT,mỗi máy tính là một đồng hồ nên việc đồng bộ các đồng hồ này là rất cần thiết và rất khó khăn.

5.1.1 Đồng hồ vật lý

Để thống nhất thời gian vật l‎ người ta đã đưa ra khái niệm thời gian phối hợp toàn cầu UCT (Universal Coordinate Time). Viện chuẩn quốc gia Mỹ đã lập ra trạm phát radio sóng ngắn W W V để gửi UTC khi cần hoặc định kì.

 5.1.2 Các giải thuật đồng bộ hóa vật lý (Clock synchronization algorithm).

Nếu tất cả các máy tính đều có WWV Receiver thì việc đồng bộ chúng là dễ dàng vì tất cả đều cùng đồng bộ với giờ chuẩn quốc tế UTC.Tuy nhiên khi không có WWV thì việc đồng bộ được thực hiện bằng các giải thuật đồng bộ sau.

a. Giải thuật Cristian

Giả sử trong HPT có một máy có WWV (gọi là Time server ) và  chúng ta sẽ tiến hành đồng bộ các máy khác với máy này.Trong khoảng thời gian δ/2p mỗi máy sẽ gửi một thông điệp đến máy chủ hỏi thời gian hiện tại. Máy chủ nhanh sẽ phản hồi bằng một thông điệp mang giá trị thời gian C(utc).Bên gửi nhận được phản hồi nó sẽ thiết lập lại clock thành C(uct).

Đánh giá: giải thuật này có 2 vấn đề :

- Một là nếu clock bên gửi chạy nhanh  thì lúc này C(uct) sẽ nhỏ hơn thời gian hiên tại C của bên gửi..Có thể giải quyết bằng cách thay đổi nhịp ngắt lại nhanh hơn hoặc chậm hơn cho đến lúc khớp nhau.

- Hai là sự chênh lệch từ lúc C(uct) được gửi cho đến lúc nhận được có thể gây lỗi.Giải quyết bằng cách ghi nhận khoản thời gian giữa lúc gửi và nhận

b. Giải thuật Berkeley.

Tư tưởng của giải thuật:

Server sẽ chủ động cho các máy khác biết thời gian chuẩn của mình CUTC sau đó sẽ yêu cầu thông tin về thời gian của các client.

Client sẽ trả lời khoảng thời gian chênh lệch giữa nó và server.

Server sẽ tính khoảng thời gian mà các client so với thời gian chuẩn của server lúc đó và gửi cho các máy khách cách điều chỉnh thời gian cho phù hợp.

c. Giải thuật trung bình

Giải thuật này thực hiện chia thời gian thành những khoảng đồng bộ cố định. Khoảng thời gian I sẽ bắt đầu từ thời điểm (To + i.R) và chạy đến khi To+(i+1)R với To là thời điểm xác định trước và R là một biến HT .

Vào thời điểm bắt đầu của mỗi lần đồng bộ tất cả các máy của mạng sẽ broadcast thời gian của mình .

Sau khi broadcast nó sẽ bắt đầu thu thập thời gian mà các máy khác gửi đến trong khoảng thời gian S. Sau đó bỏ đi giá trị lớn nhất và nhỏ nhất rồi tính trung bình của các giá trị thời gian còn lại.

5.2 Đồng hồ logic

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.

5.2.1 Nhã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 HPT 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ận bở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)

5.2.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]

5.3 Trạng thái tổng thể (Global sate).

Việc xác định trạng thái tổng thể của HT rất có ích. Một trong những phương pháp được đưa ra là Chụp Nhanh Phân Tán (Distributed Snapshort) cùng khái niệm lát cắt (cut).

5.4 Các giải thuật bầu chọn (Election Algorithm).

Khi tiến trình điều phối gặp lỗi thì sẽ phải có quá trình bầu chọn để chọn ra một tiến trình khác làm điều phối thay cho nó. Có hai giải thuật bầu chọn hay được sử dụng là:

5.4.1 Giải thuật áp đảo (Bully Algorithm)

Với giả thiết:

Mỗi một tiến trình đều có một ID duy nhất.Tất cả các tiến trình khác đều có thể biết được số ID và địa chỉ của mỗi tiến trình trong HT.

Chọn một tiến trình có ID cao nhất làm khóa.Tiến trình sẽ khởi động việc bầu chọn nếu như nó khôi phục lại sau quá trình xảy ra lỗi hoặc tiến trình điều phối bị trục trặc.

Các bước của giải thuật:

1.P gửi thông điệp ELEC đến tất cả các tiến trình có ID cao hơn

2.Nếu không có tiến trình nào phản hồi thì P sẽ trở thành tiến trình điều phối

3.Nếu có một tiến trình có ID cao hơn phản hồi thì nó sẽ đảm nhiệm vai trò điều phối.

5.4.2 Giải thuật vòng (Ring Algorithm)

Với giả thiết :

Các tiến trình có một ID duy nhất và được sắp xếp trên 1 vòng tròn Logic. Mỗi một tiến trình có thể nhận biết được tiến trình bên cạnh mình.

Các bước thuật toán:

Một tiến trình bắt đầu gửi thông điệp ELEC tới các nút còn tồn tại gần nhất, quá trình gửi theo 1 hướng nhất định. Thăm dò liên tiếp trên vòng cho đến khi tìm được 1 nút còn tồn tại.

Mỗi một tiến trình sẽ gắn ID của mình vào thông điệp gửi.

Cuối cùng sẽ chọn ra 1 tiến trình có ID cao nhất trong số các tiến trình còn hoạt động và gửi thông điệp điều phối cho tiến trình đó.

5.5 Loại trừ nhau (Mutual Exclusion).

Tổ chức các “vùng tới hạn” (critial section region).

Có nhiều giải thuật được xây dựng để cài đặt cơ chế loại trừ nhau thông qua các vùng tới hạn. Có ba giải thuật phổ biến là:

5.5.1 Giải thuật tập trung (Centralized Algorithm)

Giả thiết: mỗi tiến trình có một số ID duy nhất. Tiến trình được bầu chọn làm điều phối là tiến trình có số hiệu ID cao nhất.

Nội dung thuật toán: Khi một tiến trình nào đó cần vào vùng giới hạn nó sẽ gửi một thông điệp xin cấp quyền .Nếu không có một tiến trình nào đang trong vùng giới hạn thì tiến trình điều phối sẽ gửi phản hồi cho phép. Còn nếu có một tiến trình khác đang ở trong vùn tới hạn rồi thì tiến trình điều phối sẽ gửi thông điệp từ chối và đưa tiến trình này vào hàng đợi cho đến khi không có tiến trình nào trong vùng tới hạn nữa.

Khi tiến trình một tiến trình rời khỏi vùng giới hạn nó sẽ gửi một thông điệp đến tiến trình điều phối thông báo trả lại quyền truy cập.Lúc này tiến trình điều phối sẽ gửi quyền truy cập cho tiến trình đầu tiên trong hàng đợi truy cập.

Đánh giá : Thuật toán này có đảm bảo sự tồn tại duy nhất một tiến trình trong vùng tới hạn và chỉ cần 3 thông điệp để thiết lập là: Request –Grant – Release .Nhược điểm duy nhất là nếu tiến trình điều phối bị hỏng thì HT sẽ sụp đổ .Vì nếu một tiến trình đang trong trạng thái Block nó sẽ không thể biết được tiến trình điều phối có bị DEAD hay không .Trong một HT lớn nếu chỉ có một tiến trình điều phối sẽ xuất hiện hiện tượng thắt cổ chai

5.5.2 Giải thuật phân tán (Distributed Algorithm)

Khi một tiến trình muốn vào vùng giới hạn, trước hết nó sẽ tạo ra một nhãn thời gian và gửi cùng với một thông điệp đến tất cả các tiến trình khác. Các tiến trình khác sau khi nhận được thông điệp này sẽ xảy ra ba tình huống:

Nếu bên nhận không ở trong vùng giới hạn và cũng không muốn vào vùng giới hạn thì nó sẽ gửi thông điệp OK cho bên gửi

Nếu bên nhận đang ở trong vùng giới hạn thay vì trả lời nó sẽ cho vào hàng đợi yêu cầu này.

Nếu bên nhận cũng muốn vào hàng đợi thì nó sẽ so sánh timestamp ai thấp hơn sẽ thắng.

Sau khi gửi đi thông điệp yêu cầu vào vùng giới hạn tiến trình sẽ đợi cho đến khi có trả lời càng sớm càng tốt .Khi đã vào vùng giới hạn rồi thì nó sẽ gửi thông điệp OK đến tất cả các tiến trình khác và xóa các tiến trình trong hàng đợi đi.

5.5.3 Giải thuật vòng với thẻ bài (TokenRing Algorithm).

Giả thiết tất cả các tiến trình được sắp xếp trên một vòng tròn logic, các tiến trình đều được đánh số và đều biết đến các tiến trình cạnh nó.

Bắt đầu quá trình truyền, tiến trình 0 sẽ được trao một thẻ bài. Thẻ bài này có thể lưu hành xung quanh vòng tròn logic. Nó được chuyển từ tiến trình k đến tiến trình (k+1) bằng cách TT điệp  điểm – điểm. Khi một tiến trình giành được thể bài từ tiến trình bên cạnh nó sẽ kiểm tra xem có thể vào vùng tới hạn hay không. Nếu không có tiến trình khác trong vùng tới hạn nó sẽ vào vùng tới hạn. Sau khi hoàn thành phần việc của mình nó sẽ nhả thẻ bài ra, thẻ bài có thể di chuyển tự do trong vòng tròn. Nếu 1 tiến trình muốn vào vùng tới hạn thì nó sẽ giữ lấy thẻ bài, nếu không nó sẽ để cho thẻ bài truyền qua. Vấn đề lớn nhất trong thuật toán truyền thẻ bài là thẻ bài có thẻ bị mất, khi đó chúng ta phải sinh lại thẻ bài bởi vì việc dò tìm lại thẻ bài là rất khó.

5.6 Các giao tác phân tán (Distributed Transactions).

Bốn tính chất của giao tác đối với thế giới bên ngoài: ACID

Tính nguyên tử (Atomic): mọi giao tác diễn ra không thể phân chia được.

Tính nhất quán (Consistent): giao tác không xâm phạm các bất biến của HT.

Tính cô lập (Isolated): các giao tác đồng thời không gây trở ngại cho nhau.

Tính lâu bền (Durable): khi giao tác đã cam kết thì các thay đổi đối với nó không phải là tạm thời mà là kéo dài.

5.6.1  Phân loại các giao tác

Giao tác được chia thành các loại sau:

-Limition of Flat Transaction.

-Nested Transaction

-Distributed Transaction.

5.6.2 Điều khiển tương tranh:

Là quá trình cho phép nhiều giao tác thực hiện đồng thời mà không sảy ra sự tranh chấp giữa các giao tác. Có hai loại tương tranh:

Tương tranh bi quan.

Tương tranh lạc quan.