Bài giảng Hệ điều hành: Chương 8 (phần 2) - Đặng Minh Quân

Chia sẻ: Dien_vi02 Dien_vi02 | Ngày: | Loại File: PPT | Số trang:22

Thêm vào BST

Báo xấu

40
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Hệ điều hành - Chương 8: Hệ thống phân tán. Nội dung chính được trình bày trong chương này gồm có: Khái niệm chung, tắc nghẽn, sắp xếp sự kiện, giao dịch nguyên tử. Mời các bạn cùng tham khảo để biết thêm các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Hệ điều hành: Chương 8 (phần 2) - Đặng Minh Quân

Operating System Chapter 8: Hệ thống phân tán Dang Minh Quan: Institute of IT for Economics-NEU, 2011 1
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
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
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
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
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
DME: Phương pháp tập trung Dang Minh Quan: Institute of IT for Economics-NEU, 2011 7
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ả Dang Minh Quan: Institute of IT for Economics-NEU, 2011 8
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
DME: Phương pháp phân tán Dang Minh Quan: Institute of IT for Economics-NEU, 2011 10
Đ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
Đ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
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
Giao dịch nguyên tử phân tán Dang Minh Quan: Institute of IT for Economics-NEU, 2011 14
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
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à Dang Minh Quan: Institute of IT for Economics-NEU, 2011 16
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
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
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
Trạng thái 2PC Dang Minh Quan: Institute of IT for Economics-NEU, 2011 20