Mô hình đồ thị thể hiện các quá trình và các dịch vụ thời gian

Đồng hồ vật lý

Trong mọi hệ thống máy tính, đồng hồ vật lý (physical clocks) được sử dụng để đồng bộ và lập lịch cho các hoạt động của phần cứng. Mặt khác, theo khía cạnh phần mềm, nó cần thiết để mô phỏng thời gian thực hoặc là đo khoảng thời gian. Bộ đếm thời gian phần mềm dựa vào bộ đếm thời gian phần cứng. Trong hệ phân tán, mỗi đồng hồ chạy theo một nhịp riêng của mình, và vì vậy tồn tại một độ trễ trong việc trình diễn đồng hồ thời gian. Vì thông tin về thời gian không thể chuyền và nhận được một cách tức thời, do đó, một đồng hồ vật lý tuyệt đối theo lý thuyết thì không thể có. Vì vậy, chúng ta phải đặt một cái ổn định xấp xỉ thời gian thực toàn cục. Thách thức đặt ra là làm sao cho mọi máy tính có thể nhận được thời gian đồng nhất. Mong muốn có thể đạt thời gian đồng nhất gần với thời gian thực nhất có thể được. Để giải quyết vấn đê trên đây, cần một thuật toán về đồng bộ đồng hồ. Hình 3.10 thể hiện kỹ thuật dịch vụ thời gian gần giống với dịch vụ thời gian phân tán DTC (distributed time service) có trong DCE. Bộ ghi nhận thời gian (TC) trong mỗi máy khách yêu cầu dịch vụ thời gian tới một hoặc nhiều phục vụ thời gian (TS). Phục vụ thời gian lưu giữ những thông tin thời gian mới nhất và có thể truy cập đến nguồn thời gian thực toàn cầu. Phục vụ thời gian có thể trao đổi thông tin thời gian, vì vậy dịch vụ thời gian cua nó có thể thích hợp với những khách của nó. Tồn tại hai vấn đề cần quan tâm trong thực tế trong thi hành dịch vụ thời gian, đó là độ trễ trong việc ghi nhận thông tin về thời gian phải được bù vào và sự khác nhau giữa các nguồn thời gian phải được định cỡ.

Phần bù độ trễ

Hình 3.10 mô tả ba kiểu của truy cập thời gian: Phục vụ thời gian đến nguồn thời gian toàn cầu, khách đến phục vụ thời gian và phục vụ thời gian lẫn nhau. Nhiều nguồn hệ thống thời gian toàn cầu UTC (Universal Coordination Time) chuẩn có sẵn đối với máy tính và những ứng dụng gắn chặt tới thời gian khác. Viện tiêu chuẩn và Công nghệ quốc gia NIST của Mỹ cung cấp cách truy nhập với độ chính xác lên tới một miligiây.

Dịch vụ thời gian máy tính tự động ACTS (Automated Computer Time Service) cung cấp những dịch vụ modem tới thời gian NIST thông qua đường điện thoại. ACTS được thiết kế cho những ứng dụng chỉ yêu cầu những dịch vụ thời gian không thường xuyên: QT quay số modem là quá chậm đối với việc đồng bộ những hoạt động phần cứng.

Đối với những truy nhập mang tính thường xuyên, NIST thực hiện một trạm phát sóng ngắn WWV thực hiện việc tán phát những tín hiệu UTC. Độ trễ thời gian của TĐ có thể được tính toán một cách chính xác nếu như khoảng cách từ trạm phát sóng và khoảng cách đến điểm truyền thông tin là được biết. Tuy nhiên, điều không may là sóng radio lại rất nhạy cảm với môi trường.

Một phương án khác là sử dụng dịch vụ của hệ thống định vị toàn cầu GPS (Global Positioning System). Tuy nhiên, vệ tinh GPS lại có quỹ đạo chậm và khoảng cách của nó đến trái đất cũng thay đổi theo thời gian. Để tính được chính xác độ trễ (hoặc khoảng cách) có thể thì cần đến sự theo dõi của nhiều vệ tinh GPS. Giá thành cho phần cứng cũng như giá thành liên quan đến việc tính toán sẽ là rất cao. Cũng có thể dựa vào trạm vệ tinh để quảng bá các thông tin UTC. Khoảng cách vệ tinh đến trạm máy tính dưới đất thì hoàn toàn cố định nhưng độ trễ tốc độ truyền thì lại rất lớn, khoảng 125 milli giây. Nhiều kênh truyền hình cáp (Cable TV chanel) cũng mang cả thông tin về thời gian trong tần số. Mọi nguồn thời gian toàn cầu (Universal time source) chứa đựng những lập luận tán thành và phê phán trong đó. Rất may là không phải tất cả các phục vụ thời gian cần truy nhập đến UTC từ những nguồn đó mà một phục vụ thời gian có thể truyền bá thời gian UTC hiện tại được nó nắm giữ đến những phục vụ thời gian khác một cách chính xác và nhanh chóng.

Vấn đề độ trễ trong QT trình diễn hoặc thu nhận thông tin UTC từ phía khách của một phục vụ thời gian lại là một vấn đề khác. Thêm vào độ trễ của QT truyền tín hiệu là độ trễ trên đường truyền thông mạng. Độ trễ trên mạng thay đổi thường xuyên và là một vấn đề đáng quan tâm hơn là độ trễ truyền tín hiệu. Giả sử T_s và T_r là thời gian gửi và nhận được những yêu cầu về dịch vụ thời gian từ khách đến phục vụ thời gian. Giả sử t_p là thời gian gian cần thiết để dịch thời gian thực hiện yêu cầu đó. UTC từ phục vụ thời gian trả về cho khách có thể được điều chỉnh cho đúng bằng cách cộng thêm một nửa của độ trễ T_r - T_s - t_p. Công thức tính sự bù đó dựa trên giả thiết là QT giao thông trên mạng (network trafic) là đối xứng.

Nếu đồng hồ ở máy khách nhanh hơn UTC mới thì nó sẽ được làm chậm lại bằng phần mềm. Đồng hồ thời gian không thể quay lại được vì điều đó phủ nhận thời gian của các sự kiên trước đó. Vấn đề đồng hồ chậm hơn thì không đáng ngại nhưng tốt nhất là tăng tốc độ đồng hồ để nó đạt được cùng với UTC một cách từ từ. Ví dụ một sự tăng đột ngột đồng hồ có thể loại bỏ QT đang đợi hoặc là nguyên nhân làm nảy sinh vấn đề hết thời gian (time - out).

Truy cập UTC từ một khách tới một phục vụ thời gian là một mô hình dịch vụ kéo (một kiểu dịch vụ bị động). Một phục vụ thời gian cần phải đóng vai trò chủ động trong việc TĐ UTC đến những khách của nó. Mô hình dịch vụ đẩy (dịch vụ thời gian tích cực) cho ưu điểm là duy trì được mức độ cao tính nhất quán của đồng hồ. Kiểu đẩy giống như sóng radio hoặc là TĐ vệ tinh những UTC mong đợi, cái mà mọi khách đang chờ đón trả lời. Tuy nhiên, khách lại không có cách nào để xác định được độ trễ của mạng. Điều trở ngại này làm cho giải pháp này chỉ thích hợp với những hệ thống có phần cứng đa tán phát, nơi mà độ trễ CTĐ có thể ngắn hơn và có thể dự đoán được trước. Cả hai chế độ kéo và đẩy có thể cùng áp dụng trong việc truyền thông giữa các phục vụ thời gian.

Vần đề dự đoán độ trễ mạng cần phải đạt độ chính xác, đặc biệt khi giao thông trên mạng trở nên đông và tắc nghẽn sẽ dẫn đến kết quả trái ngược nhau về phục vụ thời gian. Để làm tăng độ nhất quán, các phục vụ thời gian có thể định cỡ UTC của chúng với những phục vụ thời gian khác. Một khách có thể nối với nhiều phục vụ thời gian để xác định tính không nhất quán của các UTC.

Xác định sự không đồng nhất

Hình 3.11. Khoảng UTC trung bình

Sự không đồng nhất giữa các phục vụ thời gian có thể được hạn chế nhờ vào sự cộng tác của các UTC. Phục vụ thời gian có thể trao đổi với các phục vụ thời gian khác theo cách kéo hoặc đẩy. Quyết định UTC dựa theo giá trị lớn nhất, nhỏ nhất, điểm giữa hoặc là trung bình của UTC. Hai thuật toán sau là lựa chọn tốt nhất cho mục đích đồng nhất hoá. Nếu trung bình được sử dụng thì hai giá trị nhỏ nhất và lớn nhất được bỏ đi (theo đúng phương pháp thống kê).

Có một điều không chắc chắn nhỏ nữa về UTC được phục vụ thời gian nắm giữ. Phục vụ thời gian có thể kết xuất một khoảng thời gian, UTC ± Δl, trong đó Δl là một thông tin được thống kê một cách không chính xác hoặc những khoảng thời gian không chắc chắn.

Việc xác định tính không chính xác giúp khách quyết định được UTC có đáp ứng được độ chính xác cho ứng dụng đó hay không. Trung bình của UTC trong khoảng thời gian có thể được sửa lại như như trong hình 3.11. Những khoảng không kế tiếp có thể bị bỏ đi. Những phần giao gồm nhiều UTC nhất thì được xác nhận. Điểm UTC mới được xác định ở chính giữa đoạn giao đó.

Thậm chí ngay khi đã có phục vụ thời gian nhất quán, thì tính toán UTC của khách vẫn không nhất quán do độ trễ truyền thông trên mạng không dự đoán được. Vấn đề không nhất quán của khách có thể được giải quyết nếu khách theo chiến lược như phục vụ thời gian là kết nối tới nhiều phục vụ thời gian và định cỡ UTC.

Đồng hồ vật lý đóng vai trò quan trọng trong việc phát triển phần mềm phân tán bởi vì có rất nhiều giao thức phần mềm dựa vào time-out để nắm giữ loại trừ. Nếu khởi tạo time-out bởi một QT được đặt dưới sự kiểm tra của một QT khác đặt trên một máy khác, hai đồng hồ vật lý phải đồng bộ có thể chấp nhận được đối với cả hai QT. Tem thời gian vật lý được dùng để khử thông điệp bội (ngăn ngừa phát lại) và kiểm tra sự mãn hạn quyền hạn đối với điều khiển truy nhập.

Đồng hồ logic

Đồng hồ vật lý là gần tương đương với đồng hồ thời gian thực toàn cục. Việc đo khoảng thời gian là hữu dụng và nhận được trực tiếp từ đồng hồ vật lý. Nói chung, có thể sử dụng đồng hồ vật lý để chỉ ra được sự kiện nào xảy ra trước sự kiện nào trừ khi chúng xảy ra rất gần nhau. Nếu như độ không chắc chắn của UTC là cao hoặc là khoảng thời gian của các sự kiện là giao nhau thì đồng hồ vật lý không cho khả năng xác định được thứ tự của các sự kiện. Đối với nhiều ứng dụng, các sự kiện không cần lập lịch hoặc đồng bộ với thời gian thực mà chỉ quan tâm đến trình tự thực hiện các sự kiện. Trong trường hợp đó thì đồng hồ lôgic được dùng để xác định thông tin về thứ tự của các sự kiện, đặc biệt trong hệ phân tán, việc duy trì một đồng hồ vật lý chung giữa các QT cộng tác là việc rất khó khăn. Đồng hồ logic Lamport là một khái niệm cơ bản để xếp thứ tự các QT và sự kiện trong hệ thống phân tán.

Mỗi một QT P_i trong hệ thống duy trì một đồng hồ logic Ci, Lamport định nghĩa ký hiệu đại số → như quan hệ xảy ra trước (happens - before) để đồng bộ đồng hồ logic giữa hai sự kiện. a → b có nghĩa là sự kiện a xảy ra trước sự kiện b. Trong cùng một QT, nếu sự kiện a xảy ra trước sự kiện b thì đồng hồ logic Ci(a) và Ci(b) được gán sao cho Ci(a) < Ci(b). Đồng hồ logic trong một QT luôn được tăng một số dương tuỳ ý khi sự kiện trong QT được tăng tiến (nghĩa là thời gian không bao giờ quay trở lại và chỉ đo tương đối đối với đồng hồ logic). Một QT tương tác với một QT khác qua cặp hai phép toán gửi (send) và nhận (receive) từ quá trình P_i đến QT P_j. Việc gửi đi phải được thực hiện trước việc nhận được. Do vậy, giữa sự kiện gửi từ QT P_i và sự kiện nhận tại QT Pj phải đảm bảo tính chất là Ci (gửi) < Cj (nhận) do QT nhận không thể hoàn thành được trước khi sự kiện gửi chưa được thực hiện. Đồng hồ logic C dựa trên quan hệ xảy ra trước được tổng kết theo hai quy tắc sau:

1. Nếu a → b trong cùng một QT thì C(a) < C(b).

2. Nếu a là sự kiện gửi một TĐ của QT P_i và b là sự kiện nhận cũng TĐ đó của QT P_j thì C_i(a) < Cj(b).

Quy tắc 1. rất dễ dàng được thi hành vì trong cùng một QT (chẳng hạn, mỗi khi xuất hiện một sự kiện mới thì bộ đếm đồng hồ lôgic của QT đó tăng lên 1). Quy tắc 2. có thể có hiệu lực nếu như gắn tem thời gian đồng hồ logic của QT gửi vào trong TĐ và QT nhận sẽ cập nhật đồng hồ logic của mình bằng cách sử dụng thời gian của đồng hồ của chính nó và việc tăng tem thời gian theo công thức:

C(b) = C(a) + d và C_j(b) = Max (TSa + d, Cj(b))

trong đó TSa là tem thời gian của sự kiện được gửi và d là một số dương. Mỗi quan hệ xảy ra trước thể hiện kết quả của hai QT có tính bắc cầu:

Nếu a → b và b → c thì a → c.

Hai sự kiện a và b được gọi là hai sự kiện rời nhau và có thể chạy đồng thời nếu như không cả a→ b và b→ c. Biểu đồ không gian thời gian trong hình 3.12 thể hiện mối quan hệ của các sự kiện {(a,e,c) và (d,e,h)} và những sự kiện đồng thời {(b,e), (f,h)}. Đồng hồ logic cho những sự kiện đồng thời không liên quan đến những sự kiện khác.

Thứ tự bộ phận và thứ tự toàn bộ của sự kiện

Sử dụng quan hệ xảy ra-trước và hai quy tắc trên, mọi sự kiến có quan hệ nhân quả sẽ được sắp xếp bởi đồng hồ logic. Kết quả này chỉ cho một thứ tự bộ phận trong đồ thị sự kiện. Với hai sự kiện rời nhau a và b (của hai QT i và QT j), thì C_i(a) < C_j(b) không có nghĩa là a→ b. Hơn nữa, có khả năng là C_i(a) = C_j(b). Thứ tự toàn cục của các sự kiện có thể nhận được bằng cách thêm một quy tắc cho hai sự kiện rời nhau (các sự kiện nhân quả luôn có thứ tự).

3. Với mọi sự kiện a và b thì C(a) ≠ C(b).

Những sự kiện rời rạc cùng với đồng hồ logic định danh có thể được phân biệt theo mốc đồng hồ logic của chúng với một số hiệu QT hoàn toàn khác nhau, điều đó đảm bảo sự duy nhất của một đồng hồ logic toàn cục cho cả hệ thống. Thứ tự của các sự kiện rời nhau không liên quan tới việc thực hiện chính quy của QT. Tập thứ tự toàn cục các sự kiện mô tả một dãy thực hiện đúng đắn mềm dẻo của các sự kiện. Tồn tại nhiều thuật toán điều khiển đồng thời sử dụng tính chất thứ tự toàn cục của sự kiện dựa trên đồng hồ logic.

Đồng hồ logic vector

Thậm chí thứ tự sự kiện toàn cục sử dụng đồng hồ logic được miêu tả ở trên không thể khẳng định được là thực sự có phải sự kiện a xảy ra trước sự kiện b hay không cho dù C(a) < C(b) bởi vì chúng có thể cùng được thực hiện. Trong trường hợp đó, cần sử dụng đồng hồ logic vector, trong đó theo phương thức đồng hồ logic vector, mỗi QT lưu giữ một vertor đồng hồ logic riêng đối với mỗi sự kiện.

Giả sự đồng hồ logic vector của sự kiện a tại bộ xử lý i là VC_i(a) = {TS₁, TS₂, ..., C_i(a), .., TS_n}, trong đó n là số QT đồng thời, C_i(a), còn được ghi là TS_i, là thời gian đồng hồ logic của sự kiện a trong QT P_i và TS_k (k nhận 1, 2, ... , n ngoại trừ i) là ước lượng tốt nhất cho thời gian đồng hồ logic của QT P_k. Ước lượng tốt nhất cho thời gian đồng hồ lôgic của QT khác nhận được thông qua thông tin về tem thời gian được mang trong các TĐ trong hệ thống.

Với mỗi QT thì đồng hồ logic vector được khởi tại bằng 0 tại thời điểm bắt đầu thực hiện QT:

- Đồng hồ logic trong nội tại QT được tăng như quy tắc 1.

- Quy tắc 2 được biến đổi theo cách như sau: Khi QT P_i gửi TĐ m (sự kiện a) đến QT P_j, tem thời gian logic của m (chính là VC_i(m)) cũng được gửi cùng với m. Giả sử b là sự kiện nhận m tại QT P_j. P_j sẽ cập nhật đồng hồ logic vector VCj(b) với TS_k(b) = Max { TS_k(a), TS_k(b)}. P_j sẽ giữ giá trị lớn nhất trong cặp của với k = 1 ... n và tăng đồng hồ logic vector của nó lên theo kết quả tính toán. Bằng cách đó, mọi thông tin về đồng hồ được chuyền đến tất cả các QT bằng cách gửi các tem thời gian TSi trong TĐ.

Rõ ràng rằng, nếu sự kiện a trong QT P_i xảy ra trước sự kiện b trong quá Pj thì VCi(a) < VCj(b), nghĩa là TS_k(a) ≤ TS_k(b) với mọi k và TS_j(a) < TS_j(b). Điều đó xẩy ra do có một đường chuyển nhân quả từ sự kiện a đến sự kiện b và sự kiện b có nhiều thông tin cập nhật hơn sự kiện a, tem thời gian được truyền dọc theo đường đó và quy tắc để cập nhật luôn là chọn cái lớn hơn trong hai cái. Thêm vào nữa, đồng hồ logic của sự kiện kế tiếp sẽ được tăng bởi sự kiện a. Vì vậy, TSj(b) phải lớn hơn TSj(a). Đối với những sự kiện rời rạc thì không thể có VC_i(a) < VC_j(b) trừ khi a → b bởi vì QT P_i (nơi xảy ra sự kiện a) sẽ được cập nhật một cách tốt cho thời gian của mình hơn mọi ước lượng của các QT khác về thời gian hiện tại của QT Pi. Do đó, Ci(a) lớn hơn hoặc bằng với TS_i trong những vector khác. Cũng như vậy, VCj(b) < VC_i(a) nếu như b → a. Nói tóm lại là chúng ta có thể kết luận là hai sự kiện có thể có hay không mối quan hệ trước sau bằng cách so sánh vector thời gian của hai sự kiện đó.

Nếu VCi(a) < VC_j(b), chúng ta có thể kết luận là sự kiện a xảy ra trước sự kiện b. Nếu không thì a và b đồng thời. Hình 3.11 đưa ra một ví dụ của đồng hồ logic vector dùng mô hình không gian thời gian.

Đồng hồ logic ma trận

Khái niệm đồng hồ logic vector có thể được mở rộng thành đồng hồ logic ma trận (Matrix logical clock). Một đồng hồ ma trận MC[k,l] tại quá trình P là một ma trận cấp nxn, nó thể hiện giờ logic bằng vector của đồng hồ logic vector. Dòng i trong ma trận MC[1..n,1..n] là một đồng hồ logic vector của P_i. Dòng thứ j trong ma trận MC[1..n,.1..n] xác định chính tri thức mà quá trình Pj có được về đồng hồ logic vector của QT Pi. Luật cập nhập đồng hồ logic ma trận giống như cập nhật cho đồng hồ logic vector. Mỗi một sự kiện địa phương, QT sẽ tăng đồng hồ của nó bằng cách đặt

MC_i[i,i] = MC_i[i,i] + d.

Khi QT P_i gửi TĐ đến QT Pj, toàn bộ đồng hồ ma trận MCi[k,l] được gán tem thời gian bằng TS_i[k,l] và gửi cùng với TĐ đến QT Pj. Đầu tiên, P_j cập nhật đồng hồ vector bằng luật lấy lớn hơn trong một cặp.

MCj[j,l] = max { MC_j[j,l], TSi[j,l] } l = 1..n

Sau đó, P_i cập nhật toàn bộ ma trận một lần nữa bằng luật lấy phần tử lớn hơn trong một cặp

MCj[k,l] = max { MC_j[k,l] , TSi[k,l] } k = 1..n, l = 1..n

Lần cập nhật đầu tiên bảo quản được thứ tự của các sự kiện. Lần cập nhật thứ hai truyền thông tin cho những QT khác qua cách chuyển các TĐ.