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

Chia sẻ: Nguyen Le Nhat Nam | Ngày: | Loại File: PPT | Số trang:45

Thêm vào BST

Báo xấu

327
lượt xem 30
download

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

Đồ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.

Chủ đề:

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

Lưu

Nội dung Text: 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 DUYTAN UNIVERSITY
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. DUYTAN UNIVERSITY
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. DUYTAN UNIVERSITY
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, ...)  DUYTAN UNIVERSITY
GIỚI THIỆU Loại trừ tương hỗ đối với hệ thống tập trung • Để xử lý 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 UNIVERSITY
Loạ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ới sự 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 nhau trong hệ thống phân tán: 1. Phương pháp tiếp cận dựa trên Token 2. 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 Quorum
Phươ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 DUYTAN UNIVERSITY
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. DUYTAN UNIVERSITY
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 DUYTAN UNIVERSITY
Thuật toán Central Coordinator DUYTAN UNIVERSITY
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ên mới phải được tạo + Điều phối viên có thể là một trong những tiến trình cạnh tranh để truy cập, một thuật toán bầu cử đã được chạy trong để chọn một và chỉ có một điều phối viên mới được chon.̣ DUYTAN UNIVERSITY
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 và đồ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 DUYTAN UNIVERSITY
Thuật toán Ricart-Agrawala • Tiến trinh yêu cầu đăng nhập vào CS phải : ̀ - Soạn thông điệp có chứa: +Identifier (machine ID, process ID) +Tên tài nguyên +Nhan/dấu thời gian Lamport (dấu thời gian hoàn ̃ toàn phần Lamport) - Gởi thông báo yêu cầu đến tất cả các tiến trình khác cạnh tranh với cùng một tài nguyên - Nó được cho phép nhập vào CS khi tất cả các tiến trình đã trả lời tin nhắn này cho phép - Truy cập vào găng, sử dụng tài nguyên DUYTAN UNIVERSITY
Thuật toán Ricart-Agrawala • Khi các tiến trình nhận yêu cầu: - Nếu tiến trình nhận không quan tâm: gởi OK đến tiến trình gởi - Nếu tiến trình đang ở trong CS : Không trả lời và add yêu cầu vào hàng đợi - Nếu tiến trình vừa nhận/ gởi thông điệp : +So sánh nhãn thời gian  Sớm nhất sẽ chiến thắng +Nếu tiến trình nhận thua cuộc : gởi OK +Nếu tiến trình nhận thắng cuộc, không trả lời và add vào hàng đợi • Khi tiến trình thực hiện xong trên CS - Gởi OK đến tất cả các tiến trình trên hàng đợi DUYTAN UNIVERSITY
Thuật toán Ricart-Agrawala DUYTAN UNIVERSITY
Thuật toán Ricart-Agrawala • Vấn đề xay ra: ̃ - Thuật toán là tốn kém về lưu lượng truy cập tin nhắn, nó đòi hỏi 2(n-1) tin nhắn cho vào một CS: (n- 1) yêu cầu và (n-1) trả lời. - Sự thất bại của bất kỳ tiến trình tham gia ngăn chặn hoạt động tiến trình khác nếu không có biện pháp phục hồi đặc biệt được thực hiện. DUYTAN UNIVERSITY
Thuật toán Lamport • Mỗi tiến trình duy trì yêu cầu hàng đợi Lamport time - Có yêu cầu loại trừ lẫn nhau • Yêu cầu critical section: - Tiến trình Pi gởi request(i, Ti) đến tất các các node - Yêu cầu vị trí trên hàng đợi riêng của nó - Khi 1 tiến trình Pj nhận một yêu cầu, nó trả về một nhãn thời gian ack DUYTAN UNIVERSITY
Thuật toán Lamport Đăng nhập vào CS: - Pi nhận được một tin nhắn (ack hoặc release) từ mỗi tiến trình khác với một dấu thời gian lớn hơn Ti - Yêu cầu của Pi có dấu thời gian sớm nhất trong hàng đợi của nó - Sự khác biệt với Ricart-Agrawala: + Mọi tiến trình đều đáp ứng trở lại + Tiến trình quyết định dựa trên xem yêu cầu của nó là sớm nhất trong hàng đợi của nó DUYTAN UNIVERSITY