Bài giảng Hệ điều hành mạng nâng cao - Hoàng Xuân Dậu - Chương 5: Thời gian và đồng bộ hóa thời gian

Hệ điều hành mạng
nâng cao
Giảng viên: Hoàng Xuân Dậu
Email: dauhoang@vnn.vn
Khoa Công nghệ thông tin 1
Học viện Công nghệ BC-VT
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 2
V. Thời gian và
đồng bộ hoá thời gian
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 3
Thời gian và đồng bộ hoá thời gian
• Dịch vụ thời gian (Time Service)
– Yêu cầu và các vấn đề cần giải quyết
– Các nguồn cung cấp thời gian chính xác
• Các giải thuật đồng bộ hoá thời gian
– Đồng hồ lệch và sai giờ
– Giải thuật Cristian
– Giải thuật Berkerly
– Network Time Protocol - NTP
• Thời gian và đồng hồ logic
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 4
Sự cần thiết của dịch vụ thời gian
• Đo độ trễ (delays) giữa các thành phần
phân tán
• Đồng bộ hoá các dòng dữ liệu, như dòng
dữ liệu hình ảnh và âm thanh
• Thiết lập trật tự của các sự kiện
• Cung cấp tem thời gian chính xác cho xác
thực các giao dịch, đồng bộ hoá các
CSDL phân tán, ...
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 5
Cơ chế đồng hồ phần cứng
• Có sẵn trong các thiết bị điện tử
• Đếm số dao động xuất hiện trong tinh thể thạch
anh tại tần số xác định
• Lưu số dao động trong một thanh ghi đếm
• Ngắt được tạo ra định kỳ
• Chương trình xử lý ngắt đọc thanh ghi đếm,
chuyển đổi giá trị đọc được ra đơn vị thời gian
(giây, nanô giây) và cập nhật đồng hồ phần
mềm.
• VD: thời gian tính bằng số giây kể từ 01/01/1970
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 6
Các vấn đề với đồng hồ phần cứng
• Tần số dao động
– Thay đổi theo nhiệt độ
– Không giống nhau trên các máy khác nhau
• Độ chính xác:
– Thường sai 1 giây trong 11.6 ngày.
• Dịch vụ thời gian tập trung
– Không thích hợp vì độ trễ của các thông điệp
là không đồng đều.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 7
Đồng hồ lệch và sai giờ
• Đồng hồ lệch giờ:
– Thời gian tại hai đồng hồ trong hệ thống lệch nhau
• Đồng hồ sai giờ:
– Khoảng lệch thời gian giữa một đồng hồ so với đồng
hồ chuẩn.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 8
Các nguồn cung cấp thời gian
chính xác
• Universal Coordinated Time (UTC, from French)
– Dựa trên thời gian nguyên tử
– Phát quảng bá từng giây thông qua các trạm truyền
thanh và vệ tinh
• Global Positioning System (GPS)
– Phát quảng bá UTC
• Các trạm thu UTC và GPS: sử dụng cho các
mục đích thương mại và đồng bộ qua đồng hồ
cục bộ.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 9
Đồng bộ đồng hồ
• Giả thiết sai số thời gian cho phép là D
• Đồng bộ đồng hồ ngoài (external) với nguồn thời
gian chuẩn:
– Sai số tuyệt đối giữa đồng hồ và nguồn thời gian
chuẩn phải nhỏ hơn D tại mọi thời điểm trong chu kỳ
đồng bộ hoá;
– Độ chính xác phải trong giới hạn D.
• Đồng bộ các đồng hồ nội bộ (internal) với nhau:
– Sai số tuyệt đối giữa các đồng hồ phải nhỏ hơn D tại
mọi thời điểm trong chu kỳ đồng bộ hoá;
– Các đồng hồ phải cho giá trị thời gian với sai khác
trong giới hạn D.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 10
Hiệu chỉnh thời gian
• Giả thiết 2 đồng hồ lệch nhau với tần suất
R mili giây / giây:
– Sai khác lớn nhất giữa 2 đồng hồ này là
2R/giây
– Vì thế chúng cần được đồng bộ hoá theo chu
kỳ D/2R, để đạt được sai số cho phép D.
• Hiệu chỉnh đúng đồng hồ:
– Đọc giá trị UTC và chỉnh lại đồng hồ phần
mềm.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 11
Các phương pháp đồng bộ thời gian
• Các hệ thống đồng bộ
– Đơn giản, thường dựa trên các giới hạn thời
gian biết trước.
• Các hệ thống không đồng bộ
– Mạng Intranet:
• Giải thuật Cristian
• Giải thuật Berkerly
– Mạng Internet:
• Network Time Protocol
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 12
Các hệ thống đồng bộ
• Đồng bộ hoá nội bộ giữa 2 tiến trình
– Biết trước các giới hạn MAX, MIN của độ trễ thông
điệp
– Độ trễ đồng hồ và tần suất thực thi
• Giả thiết tiến trình 1 gửi thông điệp đến tiến trình
2 với thời gian t:
– Tiến trình 2 có thể hiệu chỉnh đồng hồ của mình theo
thời gian t + (MAX + MIN)/2
– Độ lệch lớn nhất giữa đồng hồ của hai tiến trình là
(MAX - MIN)/2
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 13
Giải thuật Cristian
• Ước lượng thời gian truyền thông điệp là p = (T1
- T0 - h)/2 (1/2 của thời gian chu trình request-
reply).
• Hiệu chỉnh đồng hồ đến UTC + p
• Lặp lại chu trình trên và đo khoảng thời gian T1 -
T0. Ghi nhận giá trị T1 - T0 nhỏ nhất là thời điểm
cho thời gian chính xác nhất.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 14
Giải thuật Cristian (tiếp)
• Chỉ đồng bộ hoá được nếu thời gian
round-trip là ngắn so với độ chính xác yêu
cầu
• Chỉ đạt được độ chính xác cao khi thời
gian truyền thông điệp nhỏ nhất.
• Server có thể là nút yếu nhất trong hệ
thống.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 15
Giải thuật Berkerly
Đồng bộ hoá thực hiện tốt trong khoảng 20-25ms cho 15 máy tính, với tần
suất lệch là 2 x 10-5 và thời gian max của chu trình thông điệp là 10ms.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 16
Giải thuật Berkerly
• Lựa chọn một điều phối viên master định
kỳ thăm các slaves
• Master ước lượng thời gian cục bộ tại các
slaves dựa trên round-trip
• Master tính thời gian trung bình cho tất cả
slaves, trừ các giá trị không hợp lệ (sai
quá lớn)
• Master gửi thông điệp hiệu chỉnh thời gian
đến từng slave.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 17
Giải thuật Berkerly
• Độ chính xác:
– Phụ thuộc vào thời gian round-trip
• Sai số trung bình:
– Loại trừ được các ngoại lệ thời gian
– Thời gian hiệu chỉnh là trung bình của giá trị
thời gian đọc được tại các đồng hồ với độ
lệch nằm trong một giới hạn.
• Trường hợp master gặp trục trặc:
– Bầu chọn ra 1 master mới
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 18
Network Time Protocol
• Gồm nhiều máy chủ NTP trên mạng Internet
• Primary servers kết nối trực tiếp với thiết bị tiếp
nhận thông điệp UTC
• Secondary servers đồng bộ hoá thời gian với
primary servers
• Tertiary servers đồng bộ hoá thời gian với
secondary servers,...
• Số lượng servers phụ thuộc vào số lượng
clients.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 19
Tổ chức NTP Servers
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 20
Các chế độ đồng bộ hoá NTP
• Multicast
– Một hoặc một số servers định kỳ multicast đến các servers khác
trên đường truyền LAN tốc độ cao;
– Các servers hiệu chỉnh đồng hồ với giả thiết độ trễ thông điệp rất
nhỏ.
• Chế độ gọi thủ tục (Procedure Call Mode)
– Tương tự giải thuật Cristian: client yêu cầu thời gian từ một vài
máy chủ
– Thường dùng để có độ chính xác cao hơn hoặc nơi không có
multicast
• Giao thức đối xứng (Symetric Protocol)
– Sử dụng bởi các masters trong LAN và các lớp servers gần
masters nhất;
– Cho độ chính xác cao nhất, dựa trên việc đồng bộ hoá từng cặp.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 21
Thời gian logic
• Trong nhiều trường hợp, ta chỉ cần thống
nhất về thời gian trong hệ thống (không
nhất thiết là thời gian UTC).
• Nhờ vậy có thể suy ra trật tự của các sự
kiện có tính nhân - quả:
a → b (a xuất hiện trước b)
• Thời gian logic biểu diễn quan hệ nhân -
quả.
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 22
Ví dụ về trật tự nhân - quả
HĐH mạng nâng cao Thời gian & đồng bộ thời gian 23
Đồng hồ logic
• Đồng hồ logic: sử dụng bộ đếm phần mềm
tăng đều (không phải là thời gian thực)
• Mỗi tiến trình có một bộ đếm làm tem thời
gian.
• a → b ám chỉ T(a) < T(b), trong đó T(a) là
tem thời gian logic của a, T(b) là tem thời
gian logic của b.