Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng "Lập trình đồng thời và phân tán - Bài 6: Bài toán truy cập tài nguyên chỉa sẻ" cung cấp cho người học các kiến thức: Bài toán loại trừ lẫn nhau trong hệ thống phân tán, những thuật toán dựa trên timestamp, những thuật toán dựa trên token. . | Bài giảng Lập trình đồng thời và phân tán: Bài 6 - Lê Nguyễn Tuấn Thành LẬP TRÌNH BÀI 6: ĐỒNG BÀI TOÁN TRUY CẬP THỜI TÀI NGUYÊN CHỈA SẺ & 1 PHÂN Giảng viên: Lê Nguyễn Tuấn Thành TÁN Email: thanhlnt@tlu.edu.vn NỘI DUNG ▪Bài toán loại trừ lẫn nhau trong hệ thống phân tán ▪Những thuật toán dựa trên timestamp ▪Những thuật toán dựa trên token Bài giảng có sử dụng hình vẽ trong cuốn sách “Concurrent and Distributed Computing in Java, Vijay K. Garg, 2 University of Texas, John Wiley & Sons, 2005” Bài toán loại trừ lẫn nhau trong hệ thống phân tán ▪ Xét hệ thống phân tán bao gồm một số lượng cố định tiến trình và một tài nguyên chia sẻ ▪ Việc truy cập đến tài nguyên chia sẻ được coi là khu vực quan trọng CS ▪ Yêu cầu: Đưa ra thuật toán để phối hợp truy cập tới tài nguyên chia sẻ thỏa mãn 3 thuộc tính sau: 1. Safety: hai tiến trình không có quyền truy cập đồng thời vào CS 2. Liveness: bất kỳ yêu cầu nào tới CS cuối cùng phải được cấp quyền 3. Fairness: những yêu cầu khác nhau phải được cấp quyền đi vào CS theo thứ tự mà chúng được tạo ra ▪ Giả sử rằng không có lỗi trong hệ thống phân tán, các bộ xử lý và liên kết giao tiếp là tin cậy 3 Giao diện Xử lý thông điệp và Khoá 4 Những thuật 5 toán dựa trên timestamp Thuật toán mutex của Lamport (1) ▪ Trong thuật toán này, mỗi tiến trình sẽ lưu giữ: 1. Một đồng hồ vector V (dùng để lưu dấu thời gian) 2. Một hàng đợi Q (dùng để lưu các yêu cầu đi vào CS của các tiến trình trong hệ thống phân tán) ▪ Thuật toán này đảm bảo: các tiến trình đi vào CS theo thứ tự dấu thời gian của yêu cầu ở phía tiến trình gửi ▪ Chứ không phải thứ tự nhận được của yêu cầu bên phía tiến trình nhận ! ▪ Giả sử các thông điệp truyền đi theo thứ tự FIFO 6 Thuật toán mutex của Lamport (2) ▪ Nếu hai yêu cầu có cùng một dấu thời gian, thì yêu cầu của tiến trình có số hiệu nhỏ hơn được coi là nhỏ hơn ▪ Một cách chính thức, Pi có thể đi vào CS nếu: ▪ q[i], q[j]: dấu thời
