2. Loại trừ lẫn nhau

Nguyên tắc cơ bản của hệ phân tán là sự đồng thời và cộng tác của những đa tiến trình. Trong nhiều trường hợp , điều này có nghĩa là những tiến trình cần truy cập cùng một lúc cùng một tài nguyên. Để tránh điều này giải pháp là cho phép xử lý truy cập theo kiểu lọai trừ lẫn nhau.

Thuật toán Phân tán loại trừ lẫn nhau có thể được phân lớp thành 2 giải pháp khác nhau: giải pháploại trừ lẫn nhau theo biểu tượng và permission-base solution.

2.1 Phương pháp thứ nhất 

Đạt được bằng cách đưa ra một thông điệp đặc biệt giửa các tiến trình, được gọi là biểu tượng – token. Chỉ có 1 token sẵn sang và ai là người có token này được phép truy cập đến tài nguyên chia sẻ.  Phương pháp này có một số đặc tính quan trọng. 

+ Đầu tiên là nó phụ thuộc vào các làm thế nào để tổ chức các tiến trình, những đặc tính này dễ dàng bảo đảm cho mọi tiến trình có một sự thay đổi trong cách truy cập tài nguyên. Nói cách khác, những đặc tính này tránh sự thiếu tài nguyên

+ Do deadlock ,tiến trình phải đợi những tiến trình khác để được xử lý, có thể tránh deadlock một cách dễ dàng bằng cách đóng góp vào sự đơn giản của các tiến trình. Không may là trở ngại chính của token-base solution lại nghiêm trọng hơn, một chương trình con phức tạp được phân phối cần được chạy để chắc chắn rằng một token mới đựoc tạo ra nhưng cái chính là token đó phải token duy nhất 

2.2 Phương pháp thứ 2: 

Một tiến trình muốn truy cập vào tài nguyên thì phải được sự cho phép của các tiến trình khác. Cónhiều cách để có được sự cho phép và được chỉ ra dưới đây 

2.2.1.Thuật toán tập trung:

Cách dễ hiểu nhất để đạt được sự loại trừ lẫn nhau trong hệ thống phân tán là giả lập cách nó thực hiện trong  hệ thống một  Bộ xử lý. Một tiến trinh được bầu như một bộ điều phối. Bất cứ lúc nào một tiến trình muốn truy cập những tài nguyên chia sẻ,  nó gửi một thông điệp yêu cầu tới bộ điều phối đang thống kê xem loại tài nguyên nào mà tiến trình muốn truy cập và xin phép truy cập. Nếu như không có tiến trình nào đang truy cập tào nguyên, bộ điều phối sẽ gửi lại tiến trình xin phép một thông điệp cho phép truy cập hệ thống.

Ưu điểm và tính chất: Dễ dàng thấy rằng giải thuật đảm bảo sự loại trừ lẫn nhau: bộ điều phối chỉ để một tiến trình truy cập tài nguyên trong 1 thời điểm. Điều này khá tốt nếu các yêu cầu được chấp nhận theo thứ tự mà chúng được nhận. Không có tiến trình nào phải đượi vô thời hạn. Sự xắp xếp này dễ thực thi và chỉ yêu cầu 3 thông điệp cho mỗi lần sử dụng tài nguyên (gồm: yêu cầu truy nhập tài nguyên, sự cho phép và giải phóng tài nguyên). Điều này tạo ra một giải pháp hấp dẫn cho nhiều tình huống thực tế.

Hạn chế: 

-Nếu như bộ điều phối lỗi, hệ thống thực thể có thể sẽ bị down. Nếu các tài nguyên làm trởngại một cách bình thường sau khi tạo yêu cầu thì chúng không thể phân biệt một bộ điều phối đã chết với một từ chối truy cập trong trường hợp không thông điệp nào quay lại.

-Trong một hệ thống lớn, một bộ điều phối đơn có thể trở thành một thắt cổ chai.Sự đơn giản của giải thuật trong nhiều trường hợp mang lại nhiều  trở ngại.

2.2.2 Thuật tóan không tập trung

Thuật tóan được đề cửa sử dụng trong hệ thống dựa trên DHT. Giải pháp là mở rộng những bộ phân phối tập trung theo cách sau: Mỗi tài nguyên được gán một bản sao n lần. Mỗi bản sao có bộ phân phối của nó để điều khiển việc truy nhập bởi những tiến trình thực thi đồng thời

Dù vậy, mỗi khi một tiến trình muốn truy cập tài nguyên nó phải được sự cho phép của m >= n/2 bộ điều phối. Không giống như giải pháp tập trung được đưa ra ở trên(trong trường hợp b của ví dụ), khi một bộ điều phối không đưa ra sự đồng ý để truy cập tài nguyên, nó sẽ cho tiến trình yêu cầu tài nguyên biết 

Khi một bộ điều phối b hỏng, nó nhanh chóng được khôi phục nhưng lại không nhớ được số vote mà nó đã có trứoc đó., hay nói cách khác là bộ điều phối tự khởi động lại ở thời điểm bất kỳ mà lỗi xảy ra.

Nếu như yêu cầu truy cập tài nguyên bị từ chối thì nó sẽ được trả lại một biến thời gian chờ chọn ngẫu nhiên và cố thực hiện lần sau. Vấn đề của thuật tóan này là nếu có nhiều nút muốn truy cập đến cùng một tài nguyên thì hệ thống nhanh chóng lỗi, hay nói cách khác có có rất nhiều nút hoàn thành việc truy câp nhưng không nút nào có đủ n/2 bầu chọn để rời khỏi tài nguyên không sử dụng.

2.3 Thuật tóan phân tán

Khi một tiến trình muốn truy cập vào một tài nguyên chia sẻ, nó tạo một thông điệp bao gồm tên của tài nguyên, số xử lý của nó và thời gian(theo logic) hiện tại. Sau đó nó gửi thông điệp này tới các tiến trình khác và chính nó. Việc gửi các thông điệp đi là đáng tin cậy và thông điệp nào bịmất

Khi tiến trình nhận một thông điệp yêu cầu từ tiến trình khác, ứng xử của nó phụ thuộc vào trạng thái của nó với tài nguyên được đặt tên trong thông điệp. Có 3 trường hợp khác nhau được phân biệt rõ ràng:

1.Nếu bên nhận đang không hoặc không muốn truy nhập vào tài nguyên, nó sẽ gửi lại thông điệp là OK tới bên gửi

2.Nếu bên nhận vừa truy cập tài nguyên, nó đơn giản là không phản hồi lại thông điệp yêu cầu, thay vào đó, nó xếp hàng thông điệp yêu cầu đó.

3.Nếu bên nhận cũng muốn truy cập tài nguyên nhưng chưa được phép, nó sẽ so sánh nhãn thời gian (timestamp) của thông điệp gửi đến với timestamp chứa trong thông điệp mà nó gửi đi cho những tiến trình khác. Nếu thông điệp đến có timestamp thấp hơn, bên nhận sẽ gửi thông điệp OK, nếu không thì nó không gửi gì cả

Sau khi gửi các gói tin yêu cầu cho phép, một tiến trình đợi đến khi các tiến trình khác cho phép và ngay sau khi các tiến trình cho phép, tiến trình này truy cập tài nguyên. Khi nó kết thúc, nó gửi 1 thông điệp OK đến tất cả các tiến trình khác ở trong hàng đợi của nó và xóa nội dung hàng đợi đó

Giải thích ví dụ: Tiến trình 0 gửi 1 yêu cầu với timestamp = 8 đến tất cả các tiến trình. Trong cùng thời điểm đó, tiến trình 2 cũng làm tương tự với timestamp = 12. Tiếng trình 1 không muốn truy cập tài nguyên, vì thế nó gửi OK đến cả 2 bên gửi. Cả tiến trình 0 và 2 nhận ra sự xung đột và cùng so sánh timestamp. Tiến trình 2 thua và nó phải gửi thông điệp OK đi. Tiến trình 0 truy cập vào tài nguyên và xếp tiến trình 2 vào hàng đợi của nó để xử lý và truy cập tài nguyên. Sau khi kết thúc, nó loại bỏ yêu cầu từ tiến trình 2 khỏi queue của nó và gửi thông điệp OK đến tiến trình 2 và cho phép nó thực hiện.

Hạn chế: 

- Khi tổng số lượng tiến trình trong hệ thống là n thì yêu cầu 2(n-1) thông điệp cho mỗi thực thể .

- Nếu bất cứ 1 tiến trình nào lỗi, nó sẽ gây lỗi thông điệp phản hồi yêu cầu và khiến toàn bộ các tiến trình tiến vào vùng giới hạn

- Thuật toán này chậm, phức tạp và chi phí đắt và ít mạnh mẽ như thuật tóan tập trung

2.4 Giải thuật vòng với thẻ bài (TokenRing Algorithm).

Giả thiết tất cả các tiến trình được sắp xếp trên một vòng tròn logic, các tiến trình đều được đánhsố và đều biết đến các tiến trình cạnh nó.

Bắt đầu quá trình truyền, tiến trình 0 sẽ được trao một thẻ bài. Thẻ bài này có thể lưu hành xungquanh vòng tròn logic. Nó được chuyển từ tiến trình k đến tiến trình (k+1) bằng cách truyền thông điệp  điểm – điểm. Khi một tiến trình giành được thể bài từ tiến trình bên cạnh nó sẽ kiểm tra xem có thể vào vùng tới hạn hay không. Nếu không có tiến trình khác trong vùng tới hạn nó sẽ vào vùng tới hạn. 

Sau khi hoàn thành phần việc của mình nó sẽ nhả thẻ bài ra, thẻ bài có thể di chuyển tự do trong vòng tròn. Nếu 1 tiến trình muốn vào vùng tới hạn thì nó sẽ giữ lấy thẻ bài, nếu không nó sẽ để cho thẻ bài truyền qua. 

Hạn chế: Vấn đề lớn nhất trong thuật toán truyền thẻ bài là thẻ bài có thẻ bị mất, khi đó chúng ta phải sinh lại thẻ bài bởi vì việc dò tìm lại thẻ bài là rất khó.