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

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ư sau:

(1) 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 sắp xếp theo tem thời gian.

(2) Khi nhận được REQUEST, QT lưu TĐ vào hàng đợi yêu cầu của mình và gửi lại REPLY tới QT phát ra yêu cầu.

(3) Khi hàng đợi của QT yêu cầu (phát ra REQUEST) thu thập được N-1 REPLY (lúc này REQUEST đang ở đỉnh hàng đợi) thì QT này được phép vào khoảng tới hạn.

(4) Khi vào khoảng tới hạn, QT gửi thông báo RELEASE tới tất cả các QT và các QT này giải phóng REQUEST khỏi hàng đợi của nó.

Đánh giá thuật toán:

Tổng số thông điệp hoàn thành một lần vào khoảng tới hạn là 3*(N-1) với N là số lượng các QT đang thực hiện.

Cải tiến thuật toán Lamport

Khi quan sát TĐ REPLY bị xóa có thể kết khối QT đi vào khoảng tới hạn, Ricard và Agrawala đã rút gọn độ phức tạp TĐ của thuật toán Lamport. Một số cải tiến như sau:

(1) Nếu QT nhận REQUEST khi nó đang ở trong khoảng tới hạn của nó, hoặc nó đã gửi một REQUEST mà có tem thời gian nhỏ thua tem thời gian của REQUEST đang tới thì nó làm trễ việc phát REPLY.

(2) Chỉ khi QT thu nhận được mọi (N-1) REPLY thì mới được đi vào khoảng tới hạn. Chú ý rằng QT giành dược mọi REPLY chỉ khi nó trở thành QT có ưu tiên cao nhất.

Bản chất là tích hợp hai thông điệp REPLY và RELEASE, số lượng 2*(N-1) TĐ. Thi hành thuật toán ưu thế tem thời gian là đơn giản. Đồng hồ lôgic trong mỗi QT được tăng trưởng theo sự xuất hiện của TĐ thiết lập thứ tự giữa gửi và nhận của các QT và hệ quả là thứ tự tổng cộng của mọi yêu cầu. Thuật toán đạt được loại từ ràng buộc và phát triển bỏ qua sự trì hoãn mập mờ của bất kỳ QU yêu cầu.

Sơ đồ phiếu bầu

Theo thuật toán Lamport (hoặc Ricard và Agrawalia), chỉ cần một QT không sẵn sàng là khóa cũng không sẵn sàng. Cần đưa ra sơ đồ mà QT không phải cần giấy phép của tất cả các QT khác để vào khoảng tới hạn. Giống như cuộc đua chính trị, người thắng cuộc có thể được xác định trước khi các phiếu bầu cuối cùng được kiểm.

Có thể áp dụng sơ đồ này cho loại trừ ràng buộc phân tán. QT cần vào khoảng tới hạn được coi là ứng viên. Lá phiếu là TĐ REPLY. QT nào nhận được đa số phiếu thì thắng cuộc, có nghĩa là được phép vào khoảng tới hạn.

(1) Khi nhận được REQUEST, QT gửi REPLY trả lời chỉ khi nó chưa gửi (bầu) cho một ứng viên khác. Mỗi khi QT đã bầu cử, không cho phép nó gửi thêm bất kỳ một REPLY mới cho đến khi phiếu bầu quay về (thông điệp RELEASE).

(2) ứng cử viên thắng cuộc để đi vào khoảng tới hạn là QT nhận được đa số phiếu bầu. Do chỉ có một ứng viên nhận được đa số phiếu bầu nên loại trừ ràng buộc được đảm bảo.

Có thể xẩy ra vấn đề bế tắc trong sơ đồ phiếu bầu là có ba ứng viên mà mỗi từ chúng nhận được một phần ba số phiếu bầu. Và mường tượng sơ đồ trong đó ứng viên với hầu hết phiếu sẽ là người thắng cuộc. Tuy nhiên, sơ đồ này trở nên phức tạp hơn và tốn kém truyền thông để loại bỏ ràng buộc.

Như giải pháp chọn lựa, một QT có thể thay đổi phiếu bầu của nó khi nhận được yêu cầu từ ứng viên hấp dẫn hơn. Mỗi QT duy trì tem thời gian Lamport và gắn tem đó vào thông điệp REQUEST.

Nếu QT đã bỏ phiếu mà nhận được REQUEST với tem thời gian nhỏ hơn so với tem thời gian của ứng viên mà nó đã bầu thì QT đó lấy lại phiếu bầu đó bằng cách gửi TĐ INQUIRE tới ứng viên. Nếu ứng cử viên này chưa vào khoảng tới hạn thì nó gửi trả lại lá phiếu của người bầu bằng TĐ REINQUISH (ngược lại, khi QT đo đã ở trong khoảng tới hạn thì gửi TĐ RELEASE). Khi QT nhận lại phiếu bầu, nó bỏ phiếu cho ứng cử viên có tem thời gian nhỏ nhất. Kết quả là ứng cử viên nào đó sẽ vào khoảng tới hạn vì chỉ một trong số các ứng cử viên có tem thời gian ngắn nhất.

Đánh giá

Quy tắc ưu thế trong bầu cử đòi hỏi 0 (N) TĐ cho một thực thể khoảng tới hạn (nhiều hơn nếu xảy ra bế tắc). Cải tiến thuật toán nhằm vào rút gọn tổng phí TĐ bằng cách giảm số phiếu cần thiết để vào khoảng tới hạn. Mỗi QT i có tập yêu cầu Si và mỗi QT cần nhận được phiếu bầu từ mọi thành viên trong tập yêu cầu để vào khoảng tới hạn. Nhằm đảm bảo loại trừ ràng buộc, mọi tập yêu cầu phải rời nhau (SiSj=null với mọi cặp tập yêu cầu khách nhau). Các tập yêu cầu hợp lý cho loại trừ ràng buộc thường được coi là tập quy định (quorum), và tập các tập yêu cầu được coi là phái (coterie). Còn có các điều kiện khác cho tập quy định và phái không quan hệ trực tiếp với tính chính xác song đáng được thi hành. Nếu không có một tập quy định nào là tập con thực sự của một tập quy định khác thì phái là tối thiểu. Nếu các tập quy định cùng kích thước thì phái đòi hỏi sự cố gắng như nhau và trách nhiệm như nhau.

Trong tình huống với tập điều kiện cần có đã cho, bài toán xác định phái đảm bảo các tính chất mỗi tập quy định có cùng kích thước tối thiểu. Hợp lý mỗi tập quy định có cỡ O().

Cấu trúc vòng (Ring structure)

Các QT được nối theo một vòng logic và một thẻ bài di chuyển trên vòng. QT sở hữu thẻ bài nó được phép vào khoảng tới hạn. Khi kết thúc khoảng tới hạn (nếu có), QT chuyển thẻ bài tới QT kế tiếp trong vòng. Cấu trúc vòng đơn giản, dễ thực hiện và tránh được bế tắc. Tuy nhiên, thẻ bài cần lưu chuyển trong vòng thậm chí không có QT nào muốn vào khoảng tới hạn của nó tạo ra giao thông mạng không cần thiết. Hơn nữa, một QT muốn vào khoảng tới hạn buộc phải chờ cho tới khi thẻ bài xuất hiện. Việc chờ đợi này có khi rất lớn, ngay cả khi không có một QT khác muốn vào khoảng tới hạn, vì rằng thẻ bài buộc phải di chuyển theo vùng lớn của vòng mới tới được QT yêu cầu. Khi số lượng yêu cầu vào khoảng tới hạn cao, thuật toán vòng lôgic làm việc tốt vì thẻ bài chỉ phải chuyển rất ít bước trong vòng để QT vào khoảng tới hạn.

Cải tiến đáng ghi nhận của tiếp cận dựa theo thẻ bài so với tiếp cận dựa theo cạnh tranh là thẻ bài được dùng mang theo trạng thái. Ví dụ, một sơ đồ ưu thế có thể thi hành bằng việc gắn thông tin ưu tiên vào thẻ bài. QT xác nhận thẻ bài chỉ khi nó nhận được thẻ bài và độ ưu tiên của nó cao hơn độ ưu tiên gắn trên thẻ bài. Độ ưu tiên có thể được người dùng xác định hoặc dùng tem thời gian.

Các chuẩn IEEE 802.4 (Token Bus) và IEEE 802.5 (Token Ring) đối với LAN sử dụng phương pháp này. Các giao thức LAN chuẩn này đặc tả các thủ tục để cấu hình vòng, kiểm soát độ ưu tiên và lỗi hệ thống. Sự khác nhau cơ bản là là giả thiết về kiến trúc mạng. Token Bus và Token Ring dùng kiến trúc kiến trúc tuyến và vòng phần cứng, trong khi quan tâm loại trừ ràng buộc ở dây là bài toán mức ứng dụng và không có một giả thiết nào về mạng hạ tầng. Chức năng giao thức đòi hỏi năng lực chẳng hạn giám sát tuyến trong Token Bus không thể được thi hành trong mức ứng dụng. Tuy nhiên, dùng thẻ mang thông tin giữa các nút cộng tác có thể tạo thuận lợi cho cộng tác phân tán.

Cấu trúc cây (Tree Structure)

Vấn đề nảy sinh trong cấu trúc vòng là thẻ bài rỗi (Thẻ bài không được sử dụng) cứ di chuyển mãi trên vòng khi không có QT nào cần đến nó. Một lựa chọn khác là QT cần khẳng định rõ yêu cầu thẻ bài và chỉ di chuyển thẻ bài khi biết có yêu cầu chưa quyết định. Do yêu cầu buộc phải tìm được thẻ bài, có thể dẫn tới tình huống trì hoãn và bế tắc không rõ ràng. Có thể thấy rằng cấu trúc vòng không là tốt nhất để đạt được thẻ bài vì đường đi dài (cho yêu cầu hoặc cho thẻ bài), mà trường hợp tồi nhất cần n-1 đoạn (n là số nút trong vòng). Để giải quyết vấn đề này, thuật toán Raymond sử dụng cấu trúc cây lôgic (Hình 4.20).

Trong cây logic, thẻ bài luôn thường trực tại gốc cây. Chú ý là mũi tên về gốc cây, là ngược với quy ước thông thường. Mỗi nút cây thể hiện vị trí logic hiện tại của một QT. Khi một QT yêu cầu thẻ bài, nó gửi yêu cầu theo đường đi tới gốc. Nếu thành công, thẻ bài sẽ chuyển tới nút đó và tạo thành một cây logic mới với gốc là nút nhận thẻ bài. ở đây chỉ trình bày những nội dung cơ bản nhất của thuật toán Raymond.

Mỗi QT duy trình một dòng đợi FIFO các yêu cầu và hướng tới QT tiền nhiệm trực tiếp (đích của cung xuất phát từ QT đang xét). Khi một QT nhận được một yêu cầu, nó bổ sung yêu cầu đó vào cuối của dòng đợi FIFO. Nếu dòng đợi rỗng và nó không có thẻ bài thì QT cần thực hiện thao tác chiếm giữ thẻ bài thông qua việc nó yêu cầu thẻ bài từ QT tiền nhiệm. Ngược lại, QT hoặc đã có thẻ bài hoặc sẽ sớm nhận được thẻ bài, nó không đưa ra một thao tác nào. QT yêu cầu thẻ bài được sinh ra theo yêu cầu cục bộ mà biểu diễn như tiến trình trên.

Khi QT có thẻ bài mà không sử dụng nó và có dòng đợi FIFO khác rỗng, nó tháo bỏ thực thể QT đầu tiên từ dòng đợi FIFO và gửi thẻ bài tới QT này. Điều kiện khởi động xuất hiện khi một yêu cầu đi tới, khi thẻ bài đi tới hoặc QT giải phóng thẻ bài. Do QT không giữ thẻ bài lâu nên nó thay đổi con trỏ tới QT mà nó sẽ gửi thẻ bài tới. Nếu dòng đợi FIFO khác rỗng, QT cần giành lại thẻ bài, vì vậy nó gửi yêu cầu tới QT mới nắm giữ thẻ bài. Một loại bỏ xuất hiện nếu QT là thực thể đầu tiên trong dòng đợi FIFO. Trong trường hợp này, QT đang trong khoảng tới hạn.

Hình 4.20 chỉ dẫn cách cấu trúc cây thay đổi động. Thẻ bài được khởi động tại nút 1. Nút 4 muốn chiếm thẻ bài sớm nhất, đưa ra thao tác yêu cầu thẻ bài tới nút 3. Theo đó, nút 3 chuyển tiếp yêu cầu từ nút 4 tới nút 2. Thẻ bài di chú từ nút 1 tới nút 4 thông qua các nút 2 và 3. Nút 3 chuyển thẻ bài và gửi yêu cầu tới nút 4 do dòng dợi tại nút 3 khác rỗng (nút 3 yêu cầu thẻ bài sau nút 4). Đường vẽ trong hình là các thay đổi chỉ dẫn di chú thẻ bài và số trong các hộp cho biết nội dung của các yêu cầu theo các bước.

Thuật toán là thi hành phân tán dòng đợi FIFO toàn cục. Dòng đợi FIFO cục bộ liên kết với FIFO toàn cục sử dụng kiến trúc cây lôgic. Tính phi chu trình của cấu trúc cây làm cho nó đạt được cái không thể đạt được từ danh sách đợi vòng, loại bỏ khả năng bế tắc. Mỗi nút biểu diễn cây con gứi yêu cầu đơn tới nút tiền nhiệm, đưa yêu cầu thẻ bài đối với thực thể cây con. Dòng yêu cầu tại mỗi nút cho thứ tự ưu tiên các yêu cầu từ cây con người thắng cuộc theo thứ tự FIFO đảm bảo tính tốt và tính tự do khỏi sự trì hoãn mập mờ. Cây lôgic có thể thay đổi kiến trúc lôgic của nó nhằm làm tăng hêịu lực bản chất. Một số giải pháp cải tiến đã được đề xuất.

Cấu trúc quảng bá

Sử dụng kiến trúc lôgic làm tăng tính hiệu quả song việc thi hành thuật toán lại phức tạp hơn do phải khởi tạo và duy trì kiến trúc đó. Trong suốt hơn và là điều mong muốn cho truyền thông nhóm là không cần nhận thức về kiến trúc. Các thuật toán loại trừ ràng buộc dựa theo cạnh tranh trước đây dùng quảng bá và giải quyết cạnh tranh bằng tem thời gian hoặc phiếu bầu. Nếu sử dụng cách quảng bá để cạnh tranh thẻ bài, thì bản chất vẫn là thuật toán dựa theo cạnh tranh. Tuy nhiên, đây là một cải tiến đáng kể dùng thẻ bài. Thẻ bài có thể mang thông tin toàn cục hữu dụng cho cộng tác QT. Thẻ bài điều khiển cho loại trừ ràng buộc được tập trung hóa và được dùng để xếp hàng các yêu cầu tới khoảng tới hạn. Đó là những nội dung cơ bản nhất của thuật toán quảng bá Suzuki/Kasami.

Thẻ bài điều khiển tương ứng với một cấu trúc dữ liệu chứa một vector thẻ bài T và một dòng xếp hàng các yêu cầu Q. Thực thể trong T được chỉ số hóa bằng số hiệu QT và trình bày số tích luỹ việc hoàn thành khoảng tới hạn của QT tương ứng. Mỗi QT giữ một số hiệu dãy cục bộ, chính là số lần QT đã đòi hỏi vào khoảng tới hạn. Số hiệu dãy này được gắn vào mọi TĐ REQUEST mà QT này quảng bá. Mọi QT p còn duy trì một vector dãy Sp, chứa chỉ số dãy cao nhất của mọi QT mà p chấp nhận. Dòng đợi yêu cầu trong thẻ bài là danh sách các yêu cầu theo thứ tự FIFO.