0.7 Deadlock  (Page 13/15)

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. Cho i = 1, 2, …,n, nếu Allocationi ≠ 0, thì Finish[i]:= false; ngược lại Finish[i]:= true.
2. Tìm chỉ số i thỏa:
3. Finish[i] = false
4. Request 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] = false cho một vài i, 1  i  n thì hệ thống đang ở trạng thái deadlock. Ngoài ra, nếu Finish[i]= false thì quá trình Pi bị deadlock.

Giải thuật này yêu cầu độ phức tạp mxn2 để phát hiện hệ thống có ở trong trạng thái deadlock hay không.

Câu hỏi đặt ra là tại sao chúng ta trả lại tài nguyên của quá trình Pi (trong bước 3) ngay sau khi chúng ta xác định rằng Requesti  Work (trong bước 2b). Chúng ta biết rằng Pi hiện tại không liên quan deadlock (vì Requesti  Work). Do đó, chúng ta lạc quan và khẳng định rằng Pi sẽ không yêu cầu thêm tài nguyên nữa để hoàn thành công việc của nó; do đó nó sẽ trả về tất cả tài nguyên hiện được cấp phát tới hệ thống. Nếu giả định của chúng ta không đúng, deadlock có thể xảy ra sao đó. Deadlock sẽ được phát hiện tại thời điểm kế tiếp mà giải thuật phát hiện deadlock được nạp.

Để minh hoạ giải thuật này, chúng ta xét hệ thống với 5 quá trình P0 đến P4 và 3 loại tài nguyên A, B, C. Loại tài nguyên A có 7 thể hiện, loại tài nguyên B có 2 thể hiện và loại tài nguyên C có 6 thể hiện. Giả sử rằng tại thời điểm T0, chúng ta có trạng thái cấp phát tài nguyên sau:

Chúng ta khẳng định rằng hệ thống không ở trong trạng thái deadlock. Thật vậy, nếu chúng ta thực thi giải thuật, chúng ta sẽ tìm ra thứ tự<P0, P2, P3, P1, P4>sẽ dẫn đến trong Finish[i] = true cho tất cả i.

Bây giờ giả sử rằng quá trình P2 thực hiện yêu cầu thêm thể hiện loại C. Ma trận yêu cầu được hiệu chỉnh như sau:

Chúng ta khẳng định rằng hệ thống bây giờ bị deadlock. Mặc dù chúng ta có thể đòi lại tài nguyên được giữ bởi quá trình P0, số lượng tài nguyên sẳn dùng không đủ để hoàn thành các yêu cầu của các quá trình còn lại. Do đó, deadlock tồn tại và bao gồm các quá trình P1, P2, P3, P4.

Sử dụng giải thuật phát hiện deadlock

Khi nào thì chúng ta nên nạp giải thuật phát hiện deadlock? Câu trả lời phụ thuộc vào hai yếu tố:

1. Deadlock có khả năng xảy ra thường xuyên như thế nào?
2. Bao nhiêu quá trình sẽ bị ảnh hưởng bởi deadlock khi nó sẽ ra?

Nếu deadlock xảy ra thường xuyên thì giải thuật phát hiện nên được nạp lên thường xuyên. Những tài nguyên được cấp phát để các quá trình bị deadlock sẽ rảnh cho đến khi deadlock có thể bị phá vỡ. Ngoài ra, số lượng quá trình liên quan trong chu trình deadlock có thể tăng lên.

Deadlock xảy ra chỉ khi một số quá trình thực hiện yêu cầu mà không được cấp tài nguyên tức thì. Yêu cầu này có thể là yêu cầu cuối hoàn thành một chuỗi các quá trình đang yêu cầu. Ngoài ra, chúng ta có thể nạp giải thuật phát hiện mọi khi một yêu cầu cho việc cấp phát không thể được cấp tức thì. Trong trường hợp này, chúng ta không chỉ định nghĩa tập hợp các quá trình bị deadlock, mà còn xác định quá trình đã gây ra deadlock. (Trong thực tế, mỗi quá trình trong suốt quá trình bị deadlock là một liên kết trong chu trình của đồ thị tài nguyên, vì thế tất cả chúng gây ra deadlock). Nếu có nhiều loại tài nguyên khác nhau, một yêu cầu có thể gây chu trình trong đồ thị tài nguyên, mỗi chu trình hoàn thành bởi yêu cầu mới nhất và “được gây ra” bởi một quá trình có thể xác định.