Bài giảng Hệ điều hành - Chương 8: Hệ thống phân tán - Trường Đại học Kinh tế quốc dân

Nội dung text: Bài giảng Hệ điều hành - Chương 8: Hệ thống phân tán - Trường Đại học Kinh tế quốc dân

1. Operating System Chapter 8: Hệ thống phân tán Dang Minh Quan: Institute of IT for Economics-NEU, 2011 1
2. Overview • Basic concept • I/O model • I/O-System implementation • Access I/O-System Dang Minh Quan: Institute of IT for Economics-NEU, 2011 2
3. A Distributed System Dang Minh Quan: Institute of IT for Economics-NEU, 2011 3
4. Tại sao cần hệ thống phân tán • Chia sẻ tài nguyên – Chia sẻ và in các file từ xa – Xử lý thông tin trên các cơ sở dữ liệu phân tán – Sử dụng các thiết bị đặc biệt từ xa • Tăng tốc độ tính toán – chia sẻ tải • Tăng độ tin cậy – phát hiện và hồi phục các vùng bị lỗi, chuyển chức năng sang vùng khác, tích hợp lại vùng đã bị lỗi • Thông tin liên lạc – truyền thông điệp Dang Minh Quan: Institute of IT for Economics-NEU, 2011 4
5. Hệ điều hành hướng mạng • Người dùng biết về sự hiện diện của rất nhiều các máy tính khác nhau. Truy cập tới tài nguyên của các máy tính được thực hiện bằng cách: – Đăng nhập từ xa vào máy phù hợp. – Chuyển dữ liệu từ các máy ở xa về máy địa phương thông qua các giao thức như FTP, HTTP. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 5
6. Hệ điều hành phân tán • Người dùng không cần biết về sự hiện diện của các máy tính khác. Truy cập tới tài nguyên ở xa cũng tương tự như truy cập tới tài nguyên địa phương. • Di cư dữ liệu – chuyển dữ liệu bằng cách chuyển toàn bộ hay một phần của file cần thiết cho tác vụ tức thời. • Di cư tính toán – chuyển việc tính toán, chứ không phải là dữ liệu, dọc ngang hệ thống. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 6
7. Hệ điều hành phân tán • Di cư tiến trình – chạy toàn bộ tiến trình hay một phần của nó tại các địa điểm khác nhau. – Cân bằng tải – phân tán các tiến trình trên toàn hệ thống để cân bằng tải. – Tăng tốc độ tính toán – các tiến trình con có thể được chạy đồng thời tại các địa điểm khác nhau. – Yêu cầu đặc biệt về phần cứng – chạy tiến trình có thể yêu cầu một bô VXL dặc biệt. – Yêu cầu đặc biệt về phần mềm – phần mềm cần thiết chỉ có ở một địa điểm nhất định. – Truy cập dữ liệu – chay các tiến trình từ xa thay vì truyền dữ liệu từ xa về. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 7
8. Các dịch vụ từ xa • Các yêu cầu truy cập file từ xa được chuyển đến server. Các yêu cầu truy cập được phiên dịch thành các thông điệp cho server và phản hồi từ server cũng được đóng gói thành các thông điệp và chuyển về cho người dùng. • Cách phổ biến để thực hiện như trên là dùng Remote Procedure Call (RPC). • Các thông điệp được gửi tới một tiến trình RPC đang nghe ở một cổng trên máy ở xa có chứa tên tiến trình cần chạy và các tham số. Tiến trình được chạy theo yêu cầu và kết quả được gửi lại cho người yêu cầu trong một thông điệp riêng biệt. • Một cổng là một số được thêm vào ở phần đầu của goi thông điệp. Một hệ thống có thể có nhiều cổng với cùng một địa chỉ mạng để phân biệt các dịch vụ mạng khác nhau. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 8
9. Hệ thống file phân tán • Một hệ thống file phân tán (DFS) có thể được xây dựng như là một tập các tiến trình RPC server và clients. – Thông điệp có địa chỉ tới cổng DFS trên một máy chủ mà tác vụ về file sẽ được thực hiện. – Thông điệp chứa các tác vụ đĩa cần được thực hiện (i.e., read, write, rename, delete or status). – Thông điệp trả lại sẽ chứa các dữ liệu kết quả của lời gọi đó. Tiến trình DFS thực hiện lời gọi thay mặt cho client. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 9
10. Các luồng • Các luồng có thể gửi và nhận thông điệp trong khi các tác vụ khác có thể được thực hiện một cách không đồng bộ. • Luồng Pop-up – được tạo ra khi có RPC mới. – Tạo mới thuận tiện hơn là khôi phục cái sẵn có. – Không cần phải khóa luồng để đợi công việc mới; không cần ghi lại hay khôi phục hoàn cảnh. – Incoming RPCs do not have to copied to a buffer within a server thread. • RPCs tới các tiến trình trên cùng một máy có thể được làm hiệu quả hơn nữa thông qua liên lạc giữa các luồng bằng chia sẻ bộ nhớ. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 10
11. Sự khỏe mạnh của hệ thống Để đảm bảo hệ thống là khỏe mạnh, chúng ta phải: • Phát hiện lỗi. – Đường truyền – Vị trí • Thiết đặt lại hệ thống để việc tính toán có thể tiếp tục. • Khôi phục khi một vị trí hay một đường truyền đã được sửa chữa. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 11
12. Phát hiện lỗi - Thủ tục bắt tay • Trong khoảng thời gian cố định, các vị trí A và B gửi cho nhau một thông báo I-am-up. Nếu vị trí A không nhận được thông báo này trong một khoảng thời gian định trước, nó có thể giả định rằng vị trí B đã bị lỗi, rằng sự liên kết giữa A và B đã bị lỗi hoặc các tin nhắn từ B đã bị mất. • Tại thời điểm vị trí A gửi thông điệp Are-you-up?, nó xác định một khoảng thời gian mà nó sẵn sàng chờ đợi câu trả lời từ B. Nếu A không nhận được tin nhắn trả lời từ B trong khoảng thời gian, A có thể kết luận rằng một hoặc nhiều tình huống sau đã xảy ra: - Vị trí B bị lỗi - Liên kết trực tiếp (nếu có) từ A đến B bị lỗi - Các con đường thay thế từ A đến B bị lỗi. - Thông điệp này đã bị mất. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 12
13. Thiết đặt lại • Thủ tục cho phép hệ thống cấu hình lại và tiếp tục chế độ hoạt động bình thường của nó. • Nếu một liên kết trực tiếp từ A đến B đã bị lỗi, thông tin này phải được báo cho mọi vị trí trong hệ thống, do đó, các bảng định tuyến khác nhau có thể được cập nhật cho phù hợp. • Nếu ta tin rằng một vị trí đã bị lỗi, tất cả các vị trí trong hệ thống phải được thông báo, do đó chúng sẽ không còn cố gắng sử dụng các dịch vụ của các vị trí bị lỗi. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 13
14. Khôi phục từ lỗi • Khi một liên kết hoặc một vị trí đã được sửa chữa, nó phải được tích hợp vào hệ thống một cách thuận lợi. • Giả sử rằng một liên kết giữa A và B đã bị lỗi. Khi nó được sửa chữa, cả A và B phải được thông báo. Chúng ta có thể thực hiện thông báo này bằng cách liên tục lặp đi lặp lại các thủ tục bắt tay. • Giả sử vị trí B đã bị lỗi. Khi nó phục hồi, nó phải thông báo cho tất cả các vị trí khác là nó hoạt động trở lại. Vị trí B sau đó có thể phải nhận từ các vị trí khác các thông tin khác nhau để cập nhật bảng địa phương. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 14
15. Các vấn đề về thiết kế • Tính trong suốt và địa phương - hệ thống phân tán phải trông giống như hệ thống tập trung thông thường và không phân biệt giữa các tài nguyên địa phương và từ xa. • Người sử dụng di động - mang lại môi trường của người sử dụng (ví dụ, thư mục) ở bất cứ nơi nào • Khả năng chịu lỗi - hệ thống cần phải tiếp tục hoạt động khi phải đối mặt với nhiều loại hình lỗi. • Khả năng mở rộng - hệ thống nên thích ứng với tăng tải dịch vụ. • Cấu trúc tiến trình máy chủ - máy chủ nên hoạt động hiệu quả trong thời gian cao điểm, sử dụng các tiến trình nhẹ hoặc luồng. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 15
16. Xử lý tắc nghẽn trong hệ thống phân tán • Giới thiệu về tắc nghẽn • Phát hiện tắc nghẽn • Ngăn chặn tắc nghẽn Dang Minh Quan: Institute of IT for Economics-NEU, 2011 16
17. Giới thiệu về tắc nghẽn Dang Minh Quan: Institute of IT for Economics-NEU, 2011 17
18. Giới thiệu về tắc nghẽn Dang Minh Quan: Institute of IT for Economics-NEU, 2011 18
19. Giới thiệu về tắc nghẽn X1 muốn đi hướng H2 X1 sở hữu hướng H1 Dang Minh Quan: Institute of IT for Economics-NEU, 2011 19
20. Giới thiệu về tắc nghẽn • Điều kiện để xảy ra tắc nghẽn: – Một tài nguyên chỉ có thể bị nắm giữ bởi một đối tượng – Đối tượng đang giữ tài nguyên có thể đợi để có một tài nguyên khác – Một tài nguyên khi đã bị nắm giữ thì không thể lấy ra khỏi đối tượng nắm giữ – Tài nguyên được chờ đợi theo chu trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 20
21. Tắc nghẽn trong hệ thống phân tán • Điều kiện để xảy ra tắc nghẽn: Tiến trình p1 muốn độc quyền sử – Một tài nguyên chỉ có thể dụng tài nguyên r2 bị nắm giữ bởi một tiến trình – Tiến trình đang giữ tài Tiến trình p1sở hữu tài nguyên r1 nguyên có thể đợi để có một tài nguyên khác – Một tài nguyên khi đã bị nắm giữ thì không thể lấy ra khỏi tiến trình nắm giữ – Tài nguyên được chờ đợi theo chu trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 21
22. Hãy chỉ ra hệ thống có tắc nghẽn Hệ thống 1 Hệ thống 2 Dang Minh Quan: Institute of IT for Economics-NEU, 2011 22
23. Phương pháp chung xử lý tắc nghẽn • Bỏ qua • Phát hiện tắc nghẽn • Ngăn ngừa tắc nghẽn • Phòng tránh tắc nghẽn • Chủ yếu áp dụng cho hệ thống phân tán mà – Mỗi tiến trình là một giao dịch có tính nguyên tử Dang Minh Quan: Institute of IT for Economics-NEU, 2011 23
24. Phát hiện tắc nghẽn tập trung • Mỗi máy tính duy trì một đồ thị sử dụng tài nguyên của các tiến trình địa phương • Một bộ điều phối trung tâm duy trì đồ thị sử dụng tài nguyên của toàn bộ hệ thống – Thông điệp sẽ được gửi tới bộ điều phối khi một cạnh của đồ thị được thêm vào hay xóa đi Dang Minh Quan: Institute of IT for Economics-NEU, 2011 24
25. Phát hiện tắc nghẽn tập trung Đồ thị tài nguyên Đồ thị tài nguyên tại A tại B Đồ thị tài nguyên toàn cục tại bộ điều phối Dang Minh Quan: Institute of IT for Economics-NEU, 2011 25
26. Phát hiện tắc nghẽn tập trung • Nếu tiến trình P1 đòi hỏi tài nguyên T của máy B • B sẽ gửi thông điệp đợi T cho bộ điều phối • Bộ điều phối phát hiện chu trình và quyết định máy sẽ gửi thông báo đến để kết thúc tiến trình Dang Minh Quan: Institute of IT for Economics-NEU, 2011 26
27. Phát hiện tắc nghẽn tập trung • Tiến trình P1 giải phóng tài nguyên R • Tiến trình P1 đòi hỏi tài nguyên T của máy B • 2 thông điệp được gửi tới bộ điều phối – 1 (từ A) giải phóng R – 2 (từ B) đợi T • Nếu thông điệp 2 đến trước -> tắc nghẽn sai • Bộ điều phối hỏi các máy có thông điệp giải phóng tài nguyên Dang Minhnào Quan: Institute không of IT for Economics-NEU, 2011 27
28. Phát hiện tắc nghẽn tập trung • Đồ thị tài nguyên của các máy trong 1 hệ thống phân tán được biểu diễn như hình sau. Hệ thống sau có tắc nghẽn hay không Máy 1 Máy 2 Máy 3 Dang Minh Quan: Institute of IT for Economics-NEU, 2011 28
29. Ngăn chặn tắc nghẽn • Thiết kế hệ thống để tắc nghẽn không thể xảy ra • Với giả sử rằng mỗi tiến trình tương ứng với một giao dịch nguyên tử – Mỗi tiến trình sẽ có một nhãn thời gian toàn cục khi nó được khởi tạo Dang Minh Quan: Institute of IT for Economics-NEU, 2011 29
30. Ngăn chặn tắc nghẽn • Thuật toán đợi - chết – Nếu tiến trình già muốn có tài nguyên nắm giữ bởi tiến trình trẻ: Tiến trình già được phép đợi – Nếu tiến trình trẻ muốn có tài nguyên nắm giữ bởi tiến trình già: Tiến trình trẻ tự chết Dang Minh Quan: Institute of IT for Economics-NEU, 2011 30
31. Ngăn chặn tắc nghẽn • Hãy chỉ ra các tiến trình bị kết thúc theo thuật toán đợi - chết Dang Minh Quan: Institute of IT for Economics-NEU, 2011 31
32. Ngăn chặn tắc nghẽn • Thuật toán bị thương - đợi – Nếu tiến trình già muốn có tài nguyên nắm giữ bởi tiến trình trẻ: Tiến trình già kết thúc tiến trình trẻ – Nếu tiến trình trẻ muốn có tài nguyên nắm giữ bởi tiến trình già: Tiến trình trẻ được phép đợi Dang Minh Quan: Institute of IT for Economics-NEU, 2011 32
33. Ngăn chặn tắc nghẽn • Hãy chỉ ra các tiến trình bị kết thúc theo thuật toán bị thương - đợi Dang Minh Quan: Institute of IT for Economics-NEU, 2011 33