0.4 Điều khiển cạnh tranh

Giao thức dựa trên chốt

Một phương pháp để đảm bảo tính khả tuần tự là yêu cầu việc truy xuất đến hạng mục dữ liệu được tiến hành theo kiểu loại trừ tương hỗ; có nghĩa là trong khi một giao dịch đang truy xuất một hạng mục dữ liệu, không một giao dịch nào khác có thể sửa đổi hạng mục này. Phương pháp chung nhất được dùng để thực thi yêu cầu này là cho phép một giao dịch truy xuất một hạng mục dữ liệu chỉ nếu nó đang giữ chốt trên hạng mục dữ liệu này.

Chốt (lock)

Có nhiều phương thức chốt hạng mục dữ liệu. Ta hạn chế việc nghiên cứu trên hai phương thức:

1. Shared. Nếu một giao dịch Ti nhận được một chốt ở phương thức shared (ký hiệu là S) trên hạng mục Q, khi đó Ti có thể đọc, nhưng không được viết Q.
2. Exclusive. Nếu một giao dịch Ti nhận được một chốt ở phương thức Exclusive (ký hiệu là X), khi đó Ti có thể cả đọc lẫn viết Q.

Ta yêu cầu là mỗi giao dịch đòi hỏi một chốt ở một phương thức thích hợp trên hạng mục dữ liệu Q, phụ thuộc vào kiểu hoạt động mà nó sẽ thực hiện trên Q. Giả sử một giao dịch Ti đồi hỏi một chốt phương thức A trên hạng mục Q mà trên nó giao dich Tj (Tj  Ti) hiện đang giữ một chốt phương thức B. Nếu giao dịch Ti có thể được cấp một chốt trên Q ngay, bất chấp sự hiện diện của chốt phương thức B, khi đó ta nói phương thức A tương thích với phương thức B. Một hàm như vậy có thể được biểu diễn bởi một ma trận. Quan hệ tương thích giữa hai phương thức chốt được cho bởi ma trận comp sau:

Các chốt phương thức shared có thể được giữ đồng thời trên một hạng mục dữ liệu. Một chốt exclusive đến sau phải chờ đến tận khi tất cả các chốt phương thức shared đến trước được tháo ra.

Một giao dịch yêu cầu một chốt shared trên hạng mục dữ liệu Q bằng cách thực hiện chỉ thị lock-S(Q), yêu cầu một chốt exclusive thông qua chỉ thị lock-X(Q). Một hạng mục dữ liệu Q có thể được tháo chốt thông qua chỉ thị unlock(Q).

Để truy xuất một hạng mục dữ liệu, giao dịch Ti đầu tiên phải chốt hạng mục này. Nếu hạng mục này đã bị chốt bởi một giao dịch khác ở phương thức không tương thích, bộ điều khiển cạnh tranh sẽ không cấp chốt cho đến tận khi tất cả các chốt không tương thích bị giữ bởi các giao dịch khác được tháo. Như vậy Ti phải chờ đến tận khi tất cả các chốt không tương thích bị giữ bởi các giao dịch khác được giải phóng.