0.7 Deadlock  (Page 11/15)

Chúng ta có thể xem xét mỗi dòng trong ma trận Allocation và Need như là những vectors và tham chiếu tới chúng như Allocationi và Needi tương ứng. Vector Allocationi xác định tài nguyên hiện được cấp phát tới quá trình Pi; vector Needi xác định các tài nguyên bổ sung mà quá trình Pi có thể vẫn yêu cầu để hoàn thành tác vụ của nó.

Giải thuật an toàn

Giải thuật để xác định hệ thống ở trạng thái an toàn hay không có thể được mô tả như sau:

1. Gọi Work và Finish là các vector có chiều dài m và n tương ứng. Khởi tạo Work:=Available và Finish[i]:=false cho i = 1, 2, …,n.
2. Tìm i thỏa:
   • Finish[i] = false
   • Need i  Work.

Nếu không có i nào thỏa, di chuyển tới bước 4

1. Work:=Work + Allocation i

Finish[i] := true

Di chuyển về bước 2.

1. Nếu Finish[i] = true cho tất cả i, thì hệ thống đang ở trạng thái an toàn.

Giải thuật này có thể yêu cầu độ phức tạp mxn2 thao tác để quyết định trạng thái là an toàn hay không.

Giải thuật yêu cầu tài nguyên

Cho Requesti là vector yêu cầu cho quá trình Pi. Nếu Requesti[j] = k, thì quá trình Pi muốn k thể hiện của loại tài nguyên Rj. Khi một yêu cầu tài nguyên được thực hiện bởi quá trình Pi, thì các hoạt động sau được thực hiện:

1. Nếu Requesti  Needi, di chuyển tới bước 2. Ngược lại, phát sinh một điều kiện lỗi vì quá trình vượt quá yêu cầu tối đa của nó.
2. Nếu Requesti  Available, di chuyển tới bước 3. Ngược lại, Pi phải chờ vì tài nguyên không sẳn có.
3. Giả sử hệ thống cấp phát các tài nguyên được yêu cầu tới quá trình Pi bằng cách thay đổi trạng thái sau:

Available := Available – Requesti;

Allocationi := Allocationi + Requesti;

Needi := Needi – Requesti;

Nếu kết quả trạng thái cấp phát tài nguyên là an toàn, thì giao dịch được hoàn thành và quá trình Pi được cấp phát tài nguyên của nó. Tuy nhiên, nếu trạng thái mới là không an toàn, thì Pi phải chờ Requesti và trạng thái cấp phát tài nguyên cũ được phục hồi.

Thí dụ minh họa

Xét một hệ thống với 5 quá trình từ P0 tới P4, và 3 loại tài nguyên A, B, C. Loại tài nguyên A có 10 thể hiện, loại tài nguyên B có 5 thể hiện và loại tài nguyên C có 7 thể hiện. Giả sử rằng tại thời điểm T0 trạng thái hiện tại của hệ thống như sau:

Nội dung ma trận Need được định nghĩa là Max-Allocation và là

Chúng ta khẳng định rằng hệ thống hiện ở trong trạng thái an toàn. Thật vậy, thứ tự<P­1, P3, P4, P2, P0>thỏa tiêu chuẩn an toàn. Giả sử bây giờ P1 yêu cầu thêm một thể hiện loại A và hai thể hiện loại C, vì thế Request1 = (1, 0, 2). Để quyết định yêu cầu này có thể được cấp tức thì hay không, trước tiên chúng ta phải kiểm tra Request1  Available (nghĩa là, (1, 0, 2))  (3, 3, 2)) là đúng hay không. Sau đó, chúng ta giả sử yêu cầu này đạt được và chúng ta đi đến trạng thái mới sau:

Chúng ta phải xác định trạng thái mới này là an toàn hay không. Để thực hiện điều này, chúng ta thực thi giải thuật an toàn của chúng ta và tìm thứ tự<P1, P3, P4, P0, P2>thỏa yêu cầu an toàn. Do đó, chúng ta có thể cấp lập tức yêu cầu của quá trình P1.