DBMS - Bế tắc
Trong một hệ thống nhiều quy trình, bế tắc là một tình huống không mong muốn phát sinh trong môi trường tài nguyên được chia sẻ, nơi một quy trình chờ đợi vô thời hạn một tài nguyên được nắm giữ bởi một quy trình khác.
Ví dụ, giả sử một tập hợp các giao dịch {T 0 , T 1 , T 2 , ..., T n }. T 0 cần một tài nguyên X để hoàn thành nhiệm vụ của nó. Tài nguyên X do T 1 nắm giữ và T 1 đang chờ tài nguyên Y do T 2 nắm giữ . T 2 đang đợi tài nguyên Z, được giữ bởi T 0 . Vì vậy, tất cả các quá trình chờ đợi lẫn nhau để giải phóng tài nguyên. Trong tình huống này, không có quy trình nào có thể hoàn thành nhiệm vụ của chúng. Tình trạng này được gọi là bế tắc.
Bế tắc không tốt cho một hệ thống. Trong trường hợp hệ thống bị kẹt trong bế tắc, các giao dịch liên quan đến bế tắc sẽ được khôi phục hoặc khởi động lại.
Ngăn chặn bế tắc
Để ngăn chặn bất kỳ tình huống bế tắc nào trong hệ thống, DBMS tích cực kiểm tra tất cả các hoạt động, nơi các giao dịch sắp thực hiện. DBMS kiểm tra các hoạt động và phân tích xem chúng có thể tạo ra tình huống bế tắc hay không. Nếu nó phát hiện ra rằng tình huống bế tắc có thể xảy ra, thì giao dịch đó không bao giờ được phép thực hiện.
Có những kế hoạch ngăn chặn bế tắc sử dụng cơ chế sắp xếp dấu thời gian của các giao dịch để xác định trước tình huống bế tắc.
Chương trình Chờ-Chết
Trong lược đồ này, nếu một giao dịch yêu cầu khóa một tài nguyên (mục dữ liệu), tài nguyên này đã bị khóa xung đột bởi một giao dịch khác, thì một trong hai khả năng có thể xảy ra -
Nếu TS (T i ) <TS (T j ) - tức là T i , đang yêu cầu khóa xung đột, cũ hơn T j - thì T i được phép đợi cho đến khi có sẵn mục dữ liệu.
Nếu TS (T i )> TS (t j ) - tức là T i nhỏ hơn T j - thì T i chết. T i được khởi động lại sau đó với độ trễ ngẫu nhiên nhưng có cùng dấu thời gian.
Lược đồ này cho phép giao dịch cũ hơn đợi nhưng giết giao dịch trẻ hơn.
Kế hoạch chờ đợi vết thương
Trong lược đồ này, nếu một giao dịch yêu cầu khóa một tài nguyên (mục dữ liệu), tài nguyên này đã bị khóa xung đột bởi một số giao dịch khác, một trong hai khả năng có thể xảy ra -
Nếu TS (T i ) <TS (T j ), thì T i buộc T j phải được cuộn lại - tức là T i làm T j . T j được khởi động lại sau đó với độ trễ ngẫu nhiên nhưng có cùng dấu thời gian.
Nếu TS (T i )> TS (T j ), thì T i buộc phải đợi cho đến khi có tài nguyên.
Đề án này, cho phép giao dịch trẻ hơn chờ đợi; nhưng khi một giao dịch cũ hơn yêu cầu một mặt hàng do một giao dịch trẻ tuổi nắm giữ, giao dịch cũ hơn buộc giao dịch trẻ tuổi hơn phải hủy bỏ và giải phóng mặt hàng đó.
Trong cả hai trường hợp, giao dịch đi vào hệ thống ở giai đoạn sau sẽ bị hủy bỏ.
Tránh bế tắc
Hủy bỏ một giao dịch không phải lúc nào cũng là một cách tiếp cận thực tế. Thay vào đó, cơ chế tránh bế tắc có thể được sử dụng để phát hiện trước bất kỳ tình huống bế tắc nào. Các phương pháp như "biểu đồ chờ đợi" có sẵn nhưng chúng chỉ phù hợp với những hệ thống mà các giao dịch nhẹ và có ít phiên bản tài nguyên hơn. Trong một hệ thống cồng kềnh, các kỹ thuật ngăn chặn deadlock có thể hoạt động tốt.
Đồ thị Chờ đợi
Đây là một phương pháp đơn giản có sẵn để theo dõi nếu có bất kỳ tình huống bế tắc nào có thể phát sinh. Đối với mỗi giao dịch vào hệ thống, một nút được tạo. Khi một giao dịch T i yêu cầu khóa một mặt hàng, chẳng hạn X, được nắm giữ bởi một số giao dịch khác T j , một cạnh có hướng được tạo từ T i đến T j . Nếu T j giải phóng mục X, cạnh giữa chúng sẽ bị giảm và T i sẽ khóa mục dữ liệu.
Hệ thống duy trì biểu đồ chờ đợi này cho mọi giao dịch chờ một số mục dữ liệu do người khác nắm giữ. Hệ thống tiếp tục kiểm tra xem có bất kỳ chu trình nào trong biểu đồ hay không.
Ở đây, chúng ta có thể sử dụng bất kỳ phương pháp nào trong hai phương pháp sau:
Đầu tiên, không cho phép bất kỳ yêu cầu nào đối với một mặt hàng đã bị khóa bởi một giao dịch khác. Điều này không phải lúc nào cũng khả thi và có thể gây ra tình trạng chết đói, trong đó một giao dịch chờ đợi một mục dữ liệu vô thời hạn và không bao giờ có thể có được nó.
Tùy chọn thứ hai là khôi phục một trong các giao dịch. Không phải lúc nào cũng khả thi để lùi giao dịch trẻ hơn, vì nó có thể quan trọng hơn giao dịch cũ hơn. Với sự trợ giúp của một số thuật toán tương đối, một giao dịch được chọn sẽ bị hủy bỏ. Giao dịch này được gọi làvictim và quá trình này được gọi là victim selection.