Nhóm dịch hệ phân tán –Lớp MTT- K50 - DHBKHN
Chương 6 : Đồng bộ hóa
(Synchronization)
Trong chương này chúng ta sẽ tìm hiểu bằng cách nào các tiến trình đồng bộ hóa được với
nhau. Ví dụ, thay vì nhiều tiến trình đồng thời truy nhập vào một tài nguyên chia sẻ thì chúng cấp
quyền truy nhập tạm thời cho nhau. Một ví dụ khác, nhiều tiến trình đôi khi cần trả lời cho 1 sự
kiện nào đó, nói cách khác, cần xác định thông điệp m1 của tiến trình P được gửi trước hay sau
thông điệp m2 cùa tiến trình Q.
Đồ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
trong cá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.
6.1 Đồng bộ hóa đồng hồ (Clock Synchronization).
Trong một hệ tập trung, thời gian hệ thống là rõ ràng. Khi một tiến trình muốn biết thời
gian hệ thống, nó chỉ cần đưa ra 1 lời gọi hệ thống và đợi kernel trả lời. Nếu tiến trình A hỏi thời
gian, ngay sau đó tiến trình B hỏi thời gian, thì thời gian mà B nhận được sẽ lớn hơn(đôi khi
bằng) so với thời gian mà A nhận được. Chắc chắn không bao giờ có chuyện thời gian B nhận
được nhỏ hơn A. Nhưng trong một hệ thống phân tán, đạt được sự thống nhất về thời gian như
vậy không hề đơn giản.
Hãy lấy 1 ví dụ đơn giản trong chương trình make của Unix. Thông thường thì trong
Unix, các chương trình lớn được chia nhỏ ra nhiều file nguồn, để khi có thay đổi trong 1 file
nguồn thì chỉ có file đó phải được biên dịch lại mà không phải là tất cả chương trình. Nếu 1
chương trình có 100 files, thì không nhất thiết phải biên dịch lại toàn bộ bởi 1 file bất kì thay đổi
với tốc độ cao hơn bất kì 1 người lập trình nào có thể làm việc. Lệnh make làm việc hết sức đơn
giản. Khi lập trình viên thay đổi file nguồn và chạy lệnh make thì thời điểm đó được đánh dấu
cho tất cả các file nguồn đã bị modify. Nếu file input.c có thời gian là 2151 và file đối tượng
tương ứng của nó output.o có thời gian là 2150 thì lệnh make hiểu rằng input.c đã bị thay đổi sau
khi output.o được tạo ra. Như vậy cần phải biên dịch lại input.c để cho ra phiên bản output.o mới.

gian, rồi chuyển đổi thành số nhịp tương ứng tính từ 1 thời điểm xác định lưu trữ trong bộ nhớ.
Hầu hết các máy tính có 1 CMOS RAM chạy pin làm nhiệm vụ back up thời gian để mỗi lần khởi
động sau đó không cần phải nhập nữa. Với mỗi nhịp đồng hồ, thủ tục ngắt cộng thêm 1 vào thời
gian trong bộ nhớ. Bằng cách này, đồng hồ(của phần mềm) được cập nhật.
Với một máy tính đơn lẻ và một đồng hồ đơn lẻ, việc đồng hồ chạy sai hoặc ngừng một
thời gian không phải vấn đề gì lớn lắm. Vì tất cả tiến trình trên máy sử dụng chung một đồng hồ
nên chúng có sự thống nhất.
Khi hệ thống đa xử lý ra đời, mỗi 1 CPU có đồng hồ riêng, tình thế đã thay đổi hoàn toàn.
Mặc dù tần số dao động của các tinh thể thường khá là ổn định, nhưng thật khó để cho các tinh
thể khác nhau dao động cùng 1 tần số. Trong thực tế, khi một hệ thống có n máy tính, tất cả n tinh
thể hầu như dao động với n tần số khác nhau, làm cho đồng hồ(của phần mềm) dần dần cách xa
nhau về mặt thời điểm và cho các giá trị khác nhau. Sự sai khác này gọi là clock skew(sự sai
lệch đồng hồ). Hậu quả của sự sai lệch này là các chương trình dựa vào thời gian được gán cho
Nhóm dịch hệ phân tán –Lớp MTT- K50 - DHBKHN
file, đối tượng, tiến trình hoặc thông điệp độc lập với máy sinh ra chúng có thể bị lỗi, như ví dụ
với lệnh make ở trên.
Trong một số hệ thống(ví dụ như các hệ thống thời gian thực), thời gian hiện tại là rất
quan trọng. Chính vì thế việc sử dụng các đồng hồ vật lý bên ngoài là cần thiết. Vì các lý do hiệu
suất và độ phức tạp, việc phát triển một hệ thống các đồng hồ vật lý như vậy đặt ra 2 vấn đề lớn:
(1) Làm sao để đồng bộ chúng với các đồng hồ thực tế trên thế giới, và (2) làm sao để đồng bộ
chúng với nhau?
Trước khi trả lời các câu hỏi trên, hãy xem xét sơ qua làm sao chúng ta đo được thời gian.
Ban đầu, người ta tính thời gian dựa trên sự dịch chuyển của mặt trời trên bầu trời(vốn dĩ do sự tự
quay quanh trục của trái đất). Theo đó, khoảng thời gian giữa 2 lần mặt trời xuất hiện liên tiếp ở
cùng 1 vị trí được gọi là ngày mặt trời. Mỗi một ngày mặt trời được chia ra làm 86400 giây mặt
trời. Như mô tả của hình dưới đây:
Vào những năm 40 của thế kỉ trước, người ta phát hiện ra rằng sự quay của trái đất là
không ổn định. Theo đó, trái đất đang quay chậm dần đều dưới tác động ma sát của thủy triều và
bầu khí quyển. Dựa vào các mẫu vật san hô cổ đại, các nhà địa chất tin rằng 300 triệu năm trước
một năm có tới 400 ngày(hơ hơ, thế thì 1 ngày chỉ có vỏn vẹn 22 tiếng). Thực tế thì khoảng thời

hành của nó cần duy trì sự chính xác của thời gian qua hàng năm trời. Để làm được điều này, hđh
cần có 1 phần mềm đặc biệt chuyên tính toán số giây phải nhảy.
Viện thời gian chuẩn quốc gia NIST của Mỹ đã lập ra một trạm phát sóng ngắn, tạm gọi là
WWV tại Fort Collins, Colorado để cung cấp thời gian UTC chính xác. WWV phát ra một xung
ngắn ứng với mỗi giây UTC. Sai số của xung này tại nguồn là vào khoảng 1 mili giây, nhưng
dưới điều kiện bầu khí quyển thì sai số thực tế của nó là 10 mili giây. Một vài quốc gia khác cũng
có các trạm phát sóng như vậy.
GEOS là một hệ thống vệ tinh địa tĩnh cũng cung cấp dịch vụ tương tự.
6.1.2 Hệ thống định vị toàn cầu GPS:
Hãy xem xét một ví dụ cụ thể: hệ thống định vị toàn cầu GPS.
GPS sử dụng 29 vệ tinh địa tĩnh ở độ cao xấp xỉ 20 000km trên mỗi vòng quỹ đạo trái đất
nhằm xác định chính xác vị trí của một đối tượng. Mỗi vệ tinh có khoảng 4 đồng hồ nguyên tử
tường xuyên cập nhật với các trạm mặt đất. Một vệ tinh tiếp tục thông báo vị trí của chúng và gán
nhãn thông điệp với thời gian hiện tại(giờ địa phương mà đồng hồ trên vệ tinh thông báo). Điều
này cho phép máy nhận thông điệp có thể tính toán chính xác vị trí của nó chỉ với 3 vệ tinh “trên
đầu”.
Ý tưởng của hệ thống như sau: các vệ tinh địa tĩnh được bố trí trên quỹ đạo 20,000km so
với mặt đất; mỗi vệ tinh có từ 1 đến 4 đồng hồ nguyên tử nhằm đảm bảo giờ địa phương của nó
Nhóm dịch hệ phân tán –Lớp MTT- K50 - DHBKHN
luôn chính xác, các đồng hồ này còn luôn được đồng bộ với các trạm đặc biệt trên mặt đất, tóm
lại giờ của nó là giờ UTC; một thiết bị GPS khi yêu cầu xác định vị trí sẽ nhận được các thông
điệp từ vệ tinh có chứa nhãn thời gian thông báo giờ hiện tại trên vệ tinh và tọa độ của vệ tinh với
hệ kinh vĩ tuyến trái đất. Giờ của mỗi vệ tinh giúp thiết bị tính được khoảng cách giữa nó và vệ
tinh bằng cách trừ đi giờ hiện tại trên thiết bị và nhân với vận tốc sóng truyền tới(vận tốc ánh
sáng). Tọa độ của thiết bị là 1 bộ 3 số có thể được tính dựa vào thông tin nhận về từ ít nhất 3 vệ
tinh, theo lý thuyết.
6.1.3 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.

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.
6.2 Đồ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.
6.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 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ậ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)