intTypePromotion=1

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

0
15
lượt xem
1
download

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

Mô tả tài liệu
  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ủ đề:
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

  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 
  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ả  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à  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
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2