Giáo trình Hệ điều hành - Chương 5: Thời gian và đồng bộ hóa thời gian - Hoàng Xuân Dậu

Nội dung text: Giáo trình Hệ điều hành - Chương 5: Thời gian và đồng bộ hóa thời gian - Hoàng Xuân Dậu

1. HHệệ điđiềềuu hhàànhnh mmạạngng nângnâng caocao GiGiảảngng viên:viên: HoHoààngng XuânXuân DDậậuu Email:Email: dauhoang@vnn.vndauhoang@vnn.vn KhoaKhoa CôngCông nghnghệệ thôngthông tintin 11 HHọọcc viviệệnn CôngCông nghnghệệ BCBC VTVT
2. V.V. ThThờờii giangian vvàà đđồồngng bbộộ hohoáá ththờờii giangian HĐH mạng nâng cao Thời gian & đồng bộ thời gian 2
3. ThThờờii giangian vvàà đđồồngng bbộộ hohoáá ththờờii giangian • 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 3
4. SSựự ccầầnn thithiếếtt ccủủaa ddịịchch vvụụ ththờờii giangian • Đ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 4
5. CơCơ chchếế đđồồngng hhồồ phphầầnn ccứứngng • 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 5
6. CCáácc vvấấnn đđềề vvớớii đđồồngng hhồồ phphầầnn ccứứngng • 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 6
7. ĐĐồồngng hhồồ llệệchch vvàà saisai gigiờờ • Đồ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 7
8. CCáácc ngunguồồnn cungcung ccấấpp ththờờii giangian chchíínhnh xxáácc • 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 8
9. ĐĐồồngng bbộộ đđồồngng hhồồ • 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 9
10. HiHiệệuu chchỉỉnhnh ththờờii giangian • 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 10
11. CCáácc phươngphương phpháápp đđồồngng bbộộ ththờờii giangian • 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 11
12. CCáácc hhệệ ththốốngng đđồồngng bbộộ • Đồ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 12
13. GiGiảảii thuthuậậtt CristianCristian • Ướ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 13
14. GiGiảảii thuthuậậtt CristianCristian (ti(tiếếp)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 14
15. GiGiảảii thuthuậậtt BerkerlyBerkerly Đồ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 15
16. GiGiảảii thuthuậậtt BerkerlyBerkerly • 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 16
17. GiGiảảii thuthuậậtt BerkerlyBerkerly • Độ 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 17
18. NetNetworkwork TimeTime ProtocolProtocol • 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 18
19. TTổổ chchứứcc NTPNTP SServerservers HĐH mạng nâng cao Thời gian & đồng bộ thời gian 19
20. CCáácc chchếế đđộộ đđồồngng bbộộ hohoáá NTPNTP • 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 20
21. ThThờờii giangian logiclogic • 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 21
22. VVíí ddụụ vvềề trtrậậtt ttựự nhânnhân ququảả HĐH mạng nâng cao Thời gian & đồng bộ thời gian 22
23. ĐĐồồngng hhồồ logiclogic • Đồ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. HĐH mạng nâng cao Thời gian & đồng bộ thời gian 23