Bài giảng Hệ điều hành nâng cao - Chương 5 Thời gian và đồng bộ hoá 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.