Bài giảng Hệ điều hành - Chương 8, Phần 2: Hệ thống phân tán - Đặng Minh Quân

Operating System 
Chapter 8: Hệ thống phân tán 
Overview 
Khái niệm chung 
Tắc nghẽn 
Sắp xếp sự kiện 
Giao dịch nguyên tử 
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 . 
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 P i có một đồng hồ logic LC i . Đồ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. 
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 P i 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 P i đ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ó. 
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 
DME: Phương pháp tập trung 
DME: Phương pháp phân tán 
Khi tiến trình P i 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 ( P i , TS ) tới tất cả các tiến trình trong hệ thống. 
Khi tiến trình P j 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 P i 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. 
DME: Phương pháp phân tán 
Tiến trình P j quyết định trả lời ngay lập tức cho thông điệp request ( P i , TS ) hay chưa trả lời dựa vào 3 yếu tố: 
Nếu P j đang ở trong miền găng, nó chưa trả lời P i . 
Nếu P j không muốn vào miền găng, nó gửi reply ngay lập tức cho P i . 
Nếu P j 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 P i ( P i yêu cầu trước). 
Nếu không, nó chưa trả lời. 
DME: Phương pháp phân tán 
Đ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). 
Đ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. 
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 
Giao dịch nguyên tử phân tán 
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. 
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 S i và bộ điều phối giao dịch tại S i là C i . 
Phase 1: Tìm kiếm quyết định 
C i thêm bản ghi vào log. 
C i 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 C i 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 C i . 
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 . 
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. 
Trạng thái 2PC 
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 C i . Nếu C i 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 ). 
Sửa lỗi trong 2PC – bộ điều phối C i 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 C i chưa quyết định hoàn tất T . Thay vì đợi C i 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 S i hồi phục