Bài giảng Hệ điều hành mạng nâng cao: Chương VI - TS. Hoàng Xuân Dậu

Bài giảng Hệ điều hành mạng nâng cao: Chương VI - Điều độ tiến trình trong hệ thống phân tán có nội dung trình bày vấn đề điều độ trong hệ thống phân tán, loại trừ tương hỗ phân tán (distributed mutual exclusion), bầu chọn lãnh đạo hay người điều phối hệ thống, bài toán loại trừ tương hỗ.
Nội dung trích xuất từ tài liệu:
Bài giảng Hệ điều hành mạng nâng cao: Chương VI - TS. Hoàng Xuân Dậu Hệ điều hành mạng nâng cao Giảng viên: Ho àng Xuân D ậu Email: dauhoang@vnn.vn Khoa Công ngh ệ thông tin 1 Học viện Công ngh ệ BC-VT Điều độ các tiến trình trong hệ thống phân t án HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 2 Điều độ các tiến trình • Vấn đề điều độ (co-ordination) trong các hệ thống phân tán • Loại trừ tương hỗ phân tán (distributed mutual exclusion) • Bầu chọn lãnh đạo hay người điều phối hệ thống HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 3 Tại sao c ần điều độ các tiến trình? • Cập nhật đồng thời các tài nguyên chia sẻ: – các bản ghi trong CSDL (khoá bản ghi) – các files – một bảng tin chia sẻ • Thoả thuận thực hiện các thao tác: – Thực hiện hoặc huỷ bỏ một giao dịch CSDL – Thống nhất việc đọc kết quả từ một nhóm các cảm biến • Gán lại vai trò cho master – Lựa chọn máy chủ thời gian chính sau sự cố – Lựa chọn người điều độ sau khi mạng được cấu hình lại. HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 4 Các khó khăn c ủa v/đ điều độ • Các giải pháp điều độ tập trung không phù hợp với hệ thống phân tán do thành phần tập trung sẽ trở thành điểm nút cổ chai. • Các mô hình master/slave tĩnh cũng không phù hợp do master có thể gặp trục trặc. • Tôpô mạng trong hệ phân tán rất phức tạp • Khả năng chịu lỗi mạng (lỗi đường truyền, tiến trình gặp trục trặc). HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 5 Loại trừ tương h ỗ phân t án • Các giải thuật loại trừ tương hỗ (mutual exclusion) thường được sử dụng trong lập trình song song (concurrent programming) để tránh việc sử dụng đồng thời một tài nguyên dùng chung (như một biến toàn cục) bởi các đoạn mã chương trình (critical sections). • Các giải thuật loại trừ tương hỗ phân tán: – Phương pháp tập trung – Phương pháp phân tán toàn phần – Phương pháp dùng thẻ bài. HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 6 Bài toán loại trừ tương h ỗ • Bài toán: – Có n tiến trình không đồng bộ, để đơn giản hoá, giả thiết không có tiến trình nào trục trặc – Đảm bảo các thông điệp được chuyển đến đích – Để thực thi critical section (CS), m ỗi tiến trình sẽ gọi: • enter() • resourceAccess() • exit() • Yêu cầu: i. Chỉ một tiến trình ở trong CS tại một thời điểm HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 7 Loại trừ tương h ỗ tập trung HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 8 Loại trừ tương h ỗ tập trung (ti ếp) • Một tiến trình trong hệ thống được chọn làm co- ordinator (server) tại điểm vào CS. • Một tiến trình muốn gọi chức năng loại trừ tương hỗ gửi một thông điệp request đến co-ordinator. • Khi co-ordinator nhận được thông điệp request, nó kiểm tra: – Nếu không có tiến trình nào đang ở trong CS, co- ordinator gửi thông điệp reply cho tiến trình gửi request. – Nếu có tiến trình đang ở trong CS, co-ordinator đưa request đó vào hàng đợi HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 9 Loại trừ tương h ỗ tập trung (ti ếp) • Khi nhận được thông điệp reply từ co-ordinator, tiến trình gửi request đi vào CS. • Khi tiến trình này ra khỏi CS, nó gửi thông điệp release cho co-ordinator • Khi co-ordinator nhận được thông điệp release, nó xoá request khỏi hàng đợi. HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 10 Loại trừ tương h ỗ tập trung (ti ếp) • Đặc điểm: – Đảm bảo được loại trừ tương hỗ – Không xảy ra trường hợp tiến trình bị “bỏ đói” nếu trật tự thực hiện trong co-ordinator là công bằng, theo kiểu đến trước được phục vụ trước – Cần 3 thông điệp request, reply và release • Hạn chế: – co-ordinator có thể là điểm nút cổ chai – Hệ thống ngừng hoạt động nếu co-ordinator gặp trục trặc. Lúc đó cần chọn ra một co-ordinator mới. HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 11 Loại trừ tương h ỗ phân tán toàn phần • Tiến trình Pi muốn vào CS: – Tạo ra một tem thời gian TS – Gửi thông điệp request(P i, TS) đến tất cả các tiến trình trong hệ thống • Khi nhận được một thông điệp request, một tiến trình có thể: – Gửi lại ngay thông điệp reply nếu nó không ở trong CS – Hoãn việc gửi thông điệp reply trong một số điều kiện cụ thể • Khi Pi nhận được reply từ tất cả các tiến trình: – Pi vào CS – Hoãn trả lời các thông điệp request từ các tiến trình khác. HĐH mạng nâng cao mạ VI. Điều độ tiến trình phân tán Điề độ tiế trì tá 12 Loại trừ tương h ỗ phân t án toàn phần (tiếp) • Các yếu tố quyết định việc tiến trình Pi có trả lời hay hoãn trả lời thông điệp request(P j, TS): – Nếu Pi đang ở trong CS, nó hoãn gửi reply – Nếu Pi không có nhu cầu vào CS, nó gửi nga ...