Chương 6 Thuật toán loại trừ tương hỗ và bầu cử

Đồng bộ hóa tiến trình (Process Synchronization) Là kỹ thuật cho phép các tiến trình phối hợp thực hiện một cách đồng bộ (có thứ tự) - Chờ nhau thực hiện - Chia sẻ tài nguyên yêu cầu, truy cập độc quyền trên vùng găng (Critical Section - CS) Vấn đề trên được thực hiện nhờ loại trừ lẫn nhau để độc quyền trên găng tại bất kỳ thời gian nhất định.
Nội dung trích xuất từ tài liệu:
Chương 6 Thuật toán loại trừ tương hỗ và bầu cử NỘI DUNG Giới thiệu Loại trừ tương hỗ không dựa trên Token Loại trừ tương hỗ dựa trên Token Thuật toán bầu cử Kết luận DUYTANUNIVERSITY GIỚI THIỆU Đồng bộ hóa tiến trình (Process Synchronization) • Là kỹ thuật cho phép các tiến trình phối hợp thực hiện một cách đồng bộ (có thứ tự) - Chờ nhau thực hiện - Chia sẻ tài nguyên yêu cầu, truy cập độc quyền trên vùng găng (Critical Section - CS) •Vấn đề trên được thực hiện nhờ loại trừ lẫn nhau để độc quyền trên găng tại bất kỳ thời gian nhất định. DUYTANUNIVERSITY GIỚI THIỆU Loại trừ tương hỗ (Mutual Exclusion) • Loại trừ tương hỗ : là quá trình truy cập đồng thời của các tiến trình với một tài nguyên hoặc dữ liệu được chia sẻ, thực hiện theo cách loại trừ lẫn nhau. • Trong hệ thống phân tán không có các biến chia sẻ có thể sử dụng để thực hiện loại trừ lẫn nhau. DUYTANUNIVERSITY GIỚI THIỆU Loại trừ tương hỗ (Mutual Exclusion) • Đối với tài nguyên được quản lý bởi một máy chủ mà thực hiện với khóa riêng của mình cùng với các cơ chế cần thiết để đồng bộ hóa các truy cập vào các nguồn tài nguyên thì loại trừ tương hỗ và đồng bộ hóa là liên quan trong suốt cho quá trình truy cập vào các tài nguyên này (xay ra cho các hệ thống cơ ̃ sở dữ liệu xử lý giao dịch) • Thường thì có không đồng bộ hóa được xây dựng trong thực hiện bảo vệ các nguồn tài nguyên (file, hiển thị cửa sổ, các thiết bị ngoại vi, ...)  DUYTANUNIVERSITY GIỚI THIỆULoại trừ tương hỗ đối với hệ thống tập trung • Để xử lý nhiêu tiên trình thường sử dụng nhiều vùng ̀ ́ găng - Khi một tiến trình yêu cầu đọc hoặc cập nhật liệu, đầu tiên đi vào một vùng găng để loại trừ lẫn nhau và đảm bảo rằng không có quá trình khác sẽ sử dụng cấu trúc dữ liệu được chia sẻ cùng môt luc ̣́ • Loại trừ tương hỗ thông qua : - Kiểm tra và thiết lập phần cứng - Semaphores - Messages - Condition variables DUYTAN UNIVERSITYLoại trừ tương hỗ đối với hệ thống phân tán• Thuật toán loại trừ tương hỗ phải đối phó vớisự chậm trễ thông điệp và thiếu hoặc khôngđoán trước thông tin về trạng thái của hệ thống•Ba cách tiếp cận cơ bản để loại trừ lẫn nhautrong hệ thống phân tán:1. Phương pháp tiếp cận dựa trên Token2. Phương pháp tiếp cận không dựa trên Token 3. Phương pháp tiếp cận dựa trên QuorumPhương pháp tiếp cận dựa trên Token• Một thẻ bài(token) duy nhất được chia sẻgiữa các site• Một site được phép vào CS của nó nếu nó sởhữu token.• Loại trừ lẫn nhau được đảm bảo bởi vìtoken là duy nhất.• Các thuật toán tiêu biểu : Token Ring,Ricart-Agrawala Second Phương pháp tiếp cận không dựa trên Token • Sử dụng hai hoặc nhiều vòng liên tiếp các thông điệp được trao đổi giữa các site để xác định site đó sẽ nhập vào CS tiếp theo. • Các thuật toán tiêu biểu: Central Coordinator, Ricart- Agrawala DUYTANUNIVERSITY Phương pháp tiếp cận dựa trên Quorum • Mỗi site yêu cầu sự cho phép để thực hiện CS từ một tập hợp con của các site (được gọi là một số đại biểu cần thiết). • Hai Qourum bất kỳ chứa một common site . • Common site này chịu trách nhiệm để đảm bảo rằng chỉ có một yêu cầu được thực hiện ở bất cứ lúc nào. DUYTANUNIVERSITY Thuật toán Central Coordinator • Một tiến trình được bầu chọn làm điều phối viên (coordinator) • Điều phối viên trung tâm cấp quyền để nhập vào CS - Để nhập CS, tiến trình gửi một tin nhắn yêu cầu với điều phối viên và sau đó chờ đợi trả lời (trong thời gian chờ đợi quá trình có thể tiếp tục với các công việc khác). - Trả lời từ điều phối viên cho quyền vào CS. - Sau khi hoàn thành công việc trong CS, tiến trình thông báo cho điều phối viên DUYTANUNIVERSITY Thuật toán Central Coordinator DUYTANUNIVERSITY Thuật toán Central Coordinator• Lược đồ này là đơn giản và dễ thực hiện.• Chiến lược này đòi hỏi có chỉ ba tin nhắn mỗi lân yêu ̀câu sử dụng trên CS. ̀ Vấn đề xãy ra : - Điều phối viên có thể trở thành quá tải  thắt cổchai - Điều phối viên “chết”  thất bại của critical point : + Nếu điều phối viên bị treo, một điều phối viênmới phải được tạo + Điều phối viên có thể là một trong những tiến trìnhcạnh tranh để truy cập, một thuật toán bầu cử đã đượcchạy trong để chọn một và chỉ có một điều phối viênmới được chon.̣ DUYTANUNIVERSITY Thuật toán Ricart-Agrawala• Trong môi trường phân tán, thuật toán này sử dụng multicast và đồng hồ logic (không sử dụng điều phối viên trung tâm).• Giả định các kênh truyền thông thực hiện theo quy tắc FIFO.• Sử dụng hai loại thông điệp: REQUEST và REPLY DUYTANUNIVERSITY ...