Bài giảng Hệ điều hành - Chương 8: Hệ thống phân tán (Tiếp theo) - 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 (Tiếp theo) - 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 • Khái niệm chung • Tắc nghẽn • Sắp xếp sự kiện • Giao dịch nguyên tử Dang Minh Quan: Institute of IT for Economics-NEU, 2011 2
3. Sắp xếp sự kiện • Nhiều ứng dụng có thể yêu cầu chúng ta xác định trật tự. Ví dụ, trong một kế hoạch phân bổ tài nguyên, chúng ta xác định rằng một tài nguyên có thể được sử dụng chỉ sau khi tài nguyên đã được cấp. • Quan hệ xảy ra trước (được ký hiệu ). – Nếu A và B là các sự kiện trong cùng một tiến trình, và A được chạy trước B, ta có A B. – Nếu A là sự kiện gửi thông điệp của một tiến trình và B là sự kiện nhận thông điệp đó của một tiến trình khác, ta có A B. – Nếu A B và B C thì A C. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 3
4. Cách thực hiện • Dùng một nhãn thời gian cho mỗi sự kiện hệ thống. Với mỗi cặp sự kiện A và B, nếu A B, thì nhãn thời gian của A nhỏ hơn nhãn thời gian của B. • Mỗi tiến trình Pi có một đồng hồ logic LCi. Đồng hồ logic có thể được thực hiện như một bộ đếm đơn giản, nó được tăng lên khi có hai sự kiện liên tiếp được thực hiện trong một tiến trình. • Một tiến trình tăng đồng hồ logic của nó khi nó nhận một thông điệp có nhãn thời gian lớn hơn giá trị hiện tại của đồng hồ logic. • Nếu nhãn thời gian của 2 sự kiện A và B là giống nhau, 2 sự kiện là đồng thời. Chúng ta có thể dùng độ ưu tiên của tiến trình để tạo ra thứ tự. A < B : tiến trình A có độ ưu tiên cao hơn B. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 4
5. Loại trừ phân tán - Distributed Mutual Exclusion (DME) • Giả sử – Hệ thống bao gồm n tiến trình; mỗi tiến trình Pi chạy ở một bộ xử lý khác nhau. – Mỗi tiến trình có một miền găng yêu cầu truy cập mutual exclusion. • Yêu cầu – Nếu Pi đang xử lý trong miền găng, thì không một tiến trình nào khác được vào miền găng của nó. • Chúng ta sẽ xem xét 2 thuật toán để đảm bảo các tiến trình chạy mutual exclusion trong miền găng của nó. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 5
6. DME: Phương pháp tập trung • Một trong số các tiến trình của hệ thống được chọn để điều hành việc truy cập vào miền găng. • Một tiến trình muốn vào miền găng gửi thông điệp request tới bộ điều phối. • Bộ điều phối quyết định tiến trình nào được vào miền găng và nó gửi cho tiến trình đó thông điệp reply. • Khi tiến trình nhận được thông điệp reply từ bộ điều phối, nó vào miền găng. • Sau khi ra khỏi miền găng, tiến trình gửi thông điệp release tới bộ điều phối và tiếp tục dòng xử lý của nó. • Phương pháp này cần 3 thông cho một lần vào miền găng: – request – reply – release Dang Minh Quan: Institute of IT for Economics-NEU, 2011 6
7. DME: Phương pháp tập trung Dang Minh Quan: Institute of IT for Economics-NEU, 2011 7
8. DME: Phương pháp phân tán • Khi tiến trình Pi muốn vào miền găng, nó tạo một nhãn thời gian mới, TS, và gửi thông điệp request (Pi, TS) tới tất cả các tiến trình trong hệ thống. • Khi tiến trình Pj nhận một thông điệp request, nó có thể trả lời ngay lập tức với thông điệp reply hoặc chưa trả lời. • Khi tiến trình Pi nhận thông điệp reply từ tất cả các tiến trình trong hệ thống, nó có thể vào miền găng. • Sau khi ra khỏi miền găng, tiến trình gửi thông điệp reply tới tất cả các tiến trình mà nó chưa trả lời. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 8
9. DME: Phương pháp phân tán • Tiến trình Pj quyết định trả lời ngay lập tức cho thông điệp request(Pi, TS) hay chưa trả lời dựa vào 3 yếu tố: – Nếu Pj đang ở trong miền găng, nó chưa trả lời Pi. – Nếu Pj không muốn vào miền găng, nó gửi reply ngay lập tức cho Pi. – Nếu Pj muốn vào miền găng nhưng chưa vào, nó so sánh nhãn thời gian yêu cầu của nó với nhãn thời gian TS. • Nếu nhãn thời gian yêu cầu của nó lớn hơn TS, nó gửi reply ngay lập tức tới Pi (Pi yêu cầu trước). • Nếu không, nó chưa trả lời. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 9
10. DME: Phương pháp phân tán Dang Minh Quan: Institute of IT for Economics-NEU, 2011 10
11. Điểm thuận tiện của phương pháp phân tán • Không bị tắc nghẽn. • Không xảy ra tình trạng chết đói do việc vào miền găng được dựa trên thứ tự nhãn thời gian. Thứ tự nhãn thời gian đảm bảo việc phân phối tài nguyên theo đến trước – phục vụ trước. • Số lượng thông điệp cho một lần vào miền găng là 2 x (n – 1). Dang Minh Quan: Institute of IT for Economics-NEU, 2011 11
12. Điểm bất tiện của phương pháp phân tán • Các tiến trình phải biết định danh của tất cả các tiến trình khác trong hệ thống. Điều này làm cho việc thêm hay loại bỏ tiến trình trở nên phức tạp. • Nếu 1 trong số các tiến trình bị lỗi, toàn bộ quá trình sẽ bị đổ vỡ. Ta có thể xử lý vấn đề này bằng cách theo dõi trạng thái của tất cả các tiến trình trong hệ thống. • Các tiến trình chưa được vào miền găng sẽ phải thường xuyên đợi. Do đó giao thức này chỉ phù hợp tập các tiến trình ổn định và có số lượng không lớn. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 12
13. Giao dịch nguyên tử • Hoặc tất cả các tao tác của một giao dịch được xử lý hoặc không có thao tác nào được thực hiện. – Rút tiền từ máy ATM: Máy ATM phải trả tiền và trừ vào tài khoản – Đặt vé máy bay: Giảm số ghế còn dư, chuyển tiền từ thẻ tín dụng, tăng số suất ăn Dang Minh Quan: Institute of IT for Economics-NEU, 2011 13
14. Giao dịch nguyên tử phân tán Dang Minh Quan: Institute of IT for Economics-NEU, 2011 14
15. Giao dịch nguyên tử phân tán • Đảm bảo tính nguyên tử trong hệ thống phân tán yêu cầu có bộ điều phối giao dịch transaction coordinator, phụ trách các việc sau: – Bắt đầu việc thực hiện giao dịch. – Chia giao dịch thành các giao dịch con và phân tán chúng tới các địa điểm thích hợp để xử lý. – Điều phối việc kết thúc giao dịch. Giao dịch được thực hiện hoàn tất ở tất cả các địa điểm hoặc bị hủy bỏ ở tất cả các địa điểm. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 15
16. Giao thức hoàn tất 2 pha (2PC) • Giao thức được bắt đầu bởi bộ điều phối sau khi bước cuối cùng của giao dịch được thực hiện. • Khi giao thức được khởi tạo, giao dịch có thể vẫn đang được xử lý tại một số địa điểm. • Giao thức bao gồm tất cả các địa điểm mà giao dịch được thực hiện. • Ví dụ: T là giao dịch được bắt đầu tại địa điểm Si và bộ điều phối giao dịch tại Si là Ci. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 16
17. Phase 1: Tìm kiếm quyết định • Ci thêm bản ghi vào log. • Ci gửi thông điệp tới tất cả các địa điểm. • Khi một địa điểm nhận thông điệp , bộ quản lý giao dịch xác định liệu nó có thể hoàn tất giao dịch. – Nếu không: thêm bản ghi vào log và trả lời cho Ci với thông điệp . – Nếu có: • Thêm bản ghi vào log. • Ghi tất cả các bản ghi trong log có liên quan đến T vào đĩa cứng. • Bộ quản lý giao dịch gửi thông điệp tới Ci. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 17
18. Phase 1 (Cont.) • Bộ điều phối thu thập các thông điệp trả lời – Nếu tất cả các trả lời là “ready”, quyết định là hoàn tất - commit. – Nếu ít nhất 1 câu trả lời là “abort”, quyết định là hủy bỏ - abort. – Nếu ít nhất 1 địa điểm không trả lời đúng hạn, quyết định là hủy bỏ - abort. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 18
19. Phase 2: Lưu quyết định vào cơ sở dữ liệu • Bộ điều phối thêm một bản ghi quyết định hoặc vào log và ghi vào đĩa cứng. • Khi một bản ghi đã được ghi vào đĩa cứng nó không được xem xét lại nữa (kể cả khi có lỗi xảy ra). • Bộ điều phối gửi thông điệp quyết định tới tất cả các địa điểm. • Các địa điểm có các hành động phù hợp với quyết định. Dang Minh Quan: Institute of IT for Economics-NEU, 2011 19
20. Trạng thái 2PC Dang Minh Quan: Institute of IT for Economics-NEU, 2011 20
21. Sửa lỗi trong 2PC – 1 địa điểm bị lỗi • Log chứa bản ghi . Trong trường hợp này, địa điểm thực hiện redo(T). • Log chứa bản ghi . Trong trường hợp này, địa điểm thực hiện undo(T). • Log chứa bản ghi ; địa điểm hỏi Ci. Nếu Ci bị lỗi, địa điểm gửi thông điệp query- status T tới các địa điểm khác. • Log không chứa bản ghi điều khiển nào liên quan đến T. Trong trường hợp này, địa điểm thực hiện undo(T). Dang Minh Quan: Institute of IT for Economics-NEU, 2011 21
22. Sửa lỗi trong 2PC – bộ điều phối Ci bị lỗi • Nếu một địa điểm còn hoạt động chứa bản ghi trong log, T phải được hoàn tất. • Nếu một địa điểm còn hoạt động chứa bản ghi trong log, T phải bị hủy bỏ. • Nếu một số địa điểm còn hoạt động không chứa bản ghi trong log, bộ điều phối bị lỗi Ci chưa quyết định hoàn tất T. Thay vì đợi Ci hồi phục, tôt nhất là hủy bỏ T. • Nếu tất cả các địa điểm còn hoạt động có bản ghi trong log, nhưng không có thêm bản ghi điều khiển nào khác. Trong trường hợp này chúng ta phải đợi cho bộ điều phối hồi phục. – Vấn đề bị chặn – T bị chặn để đợi cho địa điểm Si hồi phục Dang Minh Quan: Institute of IT for Economics-NEU, 2011 22