Tiểu Luận Tìm hiểu về thuật toán lamport và các ứng dụng của nó

Mục lục


[TABLE="class: MsoNormalTable"]
[TR]
[TD="width: 613"] I. Loại trừ ràng buộc phân tán
[/TD]
[TD="width: 28"] 2
[/TD]
[/TR]
[TR]
[TD="width: 613"] II. Thuật toán Lamport
[/TD]
[TD="width: 28"] 7
[/TD]
[/TR]
[TR]
[TD="width: 613"] III. Tài liệu tham khảo .
[/TD]
[TD="width: 28"] 10
[/TD]
[/TR]
[/TABLE]





































NỘI DUNG

I. Loại trừ ràng buộc phân tán

Loại trừ ràng buộc đảm bảo rằng các QT đồng thời đưa ra các truy nhập tới tài nguyên hoặc dữ liệu chia xẻ (cập nhật CSDL hoặc gửi tín hiẹu điều khiển tới thiết bị vào-ra). Thuật toán loại trừ ràng buộc trong hệ phân tán hoạt động theo đúng nghĩa loại trừ nhau (với tính chất tiến bộ nào đó) mà chỉ sử dụng phương thức TT ngang hàng. Thông thường, sử dụng hai cách tiếp cận sau để giải bài toán loại trừ ràng buộc là dựa theo cạnh tranh và dựa theo điều khiển (Thông qua tín hiệu điều khiển - dùng thẻ bài).
Tiếp cận dựa theo cạnh tranh được hiểu là mỗi QT cạnh tranh một cách tự do và bình đẳng để lấy quyền có tài nguyên chia xẻ khi dùng yêu cầu về tiêu chuẩn quyết định. Tiêu chuẩn quyết định có thể dựa trên số lần yêu cầu, tính chất các yêu cầu hoặc biểu quyết.
Trong tiếp cận điều khiển, thẻ lôgic biểu diễn quyền truy nhập tới đối tượng chia xẻ được chuyển theo kiểu quy định giữa các QT cộng tác. QT giữ thẻ được phép đi vào khoảng tới hạn.
Các QT cần cạnh tranh thẻ loại trừ ràng buộc trong thuật toán tiếp cận điều khiển. Trong tiếp cận điều khiển tương tranh, thẻ điều khiển được phân bố theo cách có thứ tự, hiệu quả và tốt đẹp. Có nét tương tự giữa loại trừ ràng buộc phân tán của HĐH với điều khiển truy nhập trung gian của LAN.

Loại trừ ràng buộc theo cạnh tranh Cạnh tranh vào khoảng tới hạn được quyết định nhờ bất kỳ tiêu chuẩn nhằm tháo bỏ ràng buộc khi các yêu cầu đồng thời xuất hiện. Hợp lý nhất là cấp cho QT đưa ra câu hỏi sớm nhất (theo thời gian logic) hoặc QT nhận được nhiều phiếu bầu nhất từ các QT khác. Gọi hai phương án khác nhau này là các sơ đồ ưu thế tem thời gian và phiếu bầu. Sơ đồ ưu thế tem thời gian Trong sơ đồ ưu thế tem thời gian, sử dụng khái niệm đồng hồ lôgic làm thứ tự tổng cộng của yêu cầu đi vào khoảng tới hạn.
Thuật toán loại trừ ràng buộc phân tán Lamport hoạt động như sau1) QT yêu cầu vào khoảng tới hạn quảng bá Request tới tất cả các QT khác (kể cả nó). Mỗi QT duy trì một dòng đợi các REQUEST chưa giải quyết vào dòng đợi của mình được