Các bế tắc trong DBMS

Bế tắc xảy ra khi hai hoặc nhiều quy trình cần một số tài nguyên để hoàn thành việc thực thi của chúng được quy trình kia nắm giữ.

Trong sơ đồ trên, quy trình 1 có tài nguyên 1 và cần tài nguyên 2. Tương tự quy trình 2 có tài nguyên 2 và cần tài nguyên 1. Mỗi quy trình này cần tài nguyên của người kia để hoàn thành nhưng không ai trong số họ sẵn sàng từ bỏ tài nguyên của mình. Vì vậy, quy trình 1 và quy trình 2 đang gặp bế tắc.

Điều kiện của Coffman

Bế tắc sẽ chỉ xảy ra nếu bốn điều kiện Coffman đúng. Những điều kiện này không nhất thiết phải loại trừ lẫn nhau. Đó là:

Loại trừ lẫn nhau

Cần có một nguồn tài nguyên chỉ có thể được nắm giữ bởi một quy trình tại một thời điểm. Trong sơ đồ bên dưới, có một phiên bản duy nhất của tài nguyên R1 và nó chỉ được nắm giữ bởi quy trình P1.

Giữ và đợi

Một quy trình có thể chứa nhiều tài nguyên và vẫn yêu cầu thêm tài nguyên từ các quy trình khác đang giữ chúng. Trong sơ đồ dưới đây, quy trình P1 giữ tài nguyên R1 và R2 và đang yêu cầu tài nguyên R3 được quy trình P2 nắm giữ.

Không ưu đãi

Một tài nguyên không thể được sử dụng trước một quy trình bằng vũ lực. Một quy trình chỉ có thể giải phóng một tài nguyên một cách tự nguyện. Trong sơ đồ bên dưới, quy trình P1 không thể chặn trước tài nguyên R3 khỏi Quy trình P2. Nó sẽ chỉ được phát hành khi P2 tự nguyện từ bỏ nó sau khi quá trình thực thi hoàn tất.

Chờ theo vòng tròn

Một quy trình đang chờ tài nguyên do quy trình thứ hai nắm giữ, quy trình này đang đợi tài nguyên do quy trình thứ ba nắm giữ, v.v., cho đến quy trình cuối cùng đang chờ tài nguyên do quy trình đầu tiên nắm giữ. Điều này tạo thành một chuỗi tròn. Ví dụ:Quy trình P1 được cấp phát tài nguyên R1 và nó đang yêu cầu tài nguyên R2. Tương tự, quá trình P2 được cấp phát tài nguyên R2 và nó đang yêu cầu tài nguyên R1. Điều này tạo thành một vòng chờ vòng tròn.

Một quy trình đang chờ tài nguyên do quy trình thứ hai nắm giữ, quy trình này đang đợi tài nguyên do quy trình thứ ba nắm giữ, v.v., cho đến quy trình cuối cùng đang chờ tài nguyên do quy trình đầu tiên nắm giữ. Điều này tạo thành một chuỗi tròn. Ví dụ:Quy trình P1 được cấp phát tài nguyên R1 và nó đang yêu cầu tài nguyên R2. Tương tự, quá trình P2 được cấp phát tài nguyên R2 và nó đang yêu cầu tài nguyên R1. Điều này tạo thành một vòng chờ vòng tròn.

Phát hiện bế tắc

Bộ lập lịch tài nguyên có thể phát hiện ra một bế tắc vì nó theo dõi tất cả các tài nguyên được phân bổ cho các quy trình khác nhau. Sau khi phát hiện thấy một bế tắc, nó có thể được giải quyết bằng các phương pháp sau:

• Tất cả các quy trình liên quan đến bế tắc đều bị chấm dứt. Đây không phải là một cách tiếp cận tốt vì tất cả tiến trình đạt được của các quy trình đều bị phá hủy.
• Tài nguyên có thể được sử dụng trước từ một số quy trình và được cấp cho những người khác cho đến khi sự cố được giải quyết.

Ngăn chặn bế tắc

Nhất thiết phải ngăn chặn sự bế tắc trước khi nó có thể xảy ra. Vì vậy, hệ thống kiểm tra chặt chẽ từng giao dịch trước khi nó được thực hiện để đảm bảo rằng nó không dẫn đến bế tắc. Nếu thậm chí có khả năng một giao dịch có thể dẫn đến bế tắc, thì giao dịch đó không bao giờ được phép thực hiện.

Có một số chương trình ngăn chặn bế tắc sử dụng dấu thời gian để đảm bảo rằng bế tắc không xảy ra. Đây là -

• Lược đồ Chờ - Chết

  Trong sơ đồ chờ - chết, nếu giao dịch T1 yêu cầu tài nguyên được giữ bởi giao dịch T2, một trong hai khả năng sau có thể xảy ra:

  • TS (T1)

  • TS (T1)> TS (T2) - Nếu T1 nhỏ hơn T2 tức là T1 đến trong hệ thống sau T2, thì T1 bị giết. Nó được khởi động lại sau với cùng một dấu thời gian.

• Vết thương - Sơ đồ chờ đợi

  Trong sơ đồ chờ đợi, nếu giao dịch T1 yêu cầu tài nguyên được giữ bởi giao dịch T2, một trong hai khả năng sau có thể xảy ra:

  • TS (T1)

  • TS (T1)> TS (T2) - Nếu T1 nhỏ hơn T2, tức là T1 xuất hiện trong hệ thống sau T2, thì nó được phép đợi tài nguyên miễn phí khi T2 đã hoàn thành quá trình thực thi.

Tránh bế tắc

Tốt hơn là tránh một bế tắc hơn là thực hiện các biện pháp sau khi bế tắc đã xảy ra. Biểu đồ chờ đợi có thể được sử dụng để tránh bế tắc. Tuy nhiên, điều này chỉ hữu ích cho các cơ sở dữ liệu nhỏ hơn vì nó có thể khá phức tạp trong các cơ sở dữ liệu lớn hơn.

Chờ đồ thị

Biểu đồ chờ đợi cho thấy mối quan hệ giữa các tài nguyên và các giao dịch. Nếu một giao dịch yêu cầu một tài nguyên hoặc nếu nó đã giữ một tài nguyên, nó sẽ hiển thị dưới dạng một cạnh trên đồ thị chờ đợi. Nếu biểu đồ chờ đợi chứa một chu trình, thì có thể có một bế tắc trong hệ thống, nếu không thì không.

Bỏ qua bế tắc - Thuật toán đà điểu

Thuật toán đà điểu có nghĩa là deadlock đơn giản được bỏ qua và người ta cho rằng nó sẽ không bao giờ xảy ra. Điều này được thực hiện bởi vì trong một số hệ thống, chi phí xử lý bế tắc cao hơn nhiều so với việc đơn giản là bỏ qua nó vì nó rất hiếm khi xảy ra. Vì vậy, đơn giản là giả định rằng deadlock sẽ không bao giờ xảy ra và hệ thống sẽ được khởi động lại nếu nó xảy ra bất kỳ cơ hội nào.