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

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.
Nội dung trích xuất từ tài liệu:
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  ...