0.7 Deadlock  (Page 12/15)

Tuy nhiên, chúng ta cũng thấy rằng, khi hệ thống ở trong trạng thái này, một yêu cầu (3, 3, 0) bởi P4 không thể được gán vì các tài nguyên là không sẳn dùng. Một yêu cầu cho (0, 2, 0) bởi P0 không thể được cấp mặc dù tài nguyên là sẳn dùng vì trạng thái kết quả là không an toàn.

Phát hiện deadlock

Nếu một hệ thống không thực hiện giải thuật ngăn chặn deadlock hay tránh deadlock thì trường hợp deadlock có thể xảy ra. Trong môi trường này, hệ thống phải cung cấp:

• Giải thuật xem xét trạng thái của hệ thống để quyết định deadlock có xảy ra hay không.
• Giải thuật phục hồi từ deadlockTrong thảo luận dưới đây, chúng ta thảo luận chi tiết về hai yêu cầu khi chúng liên quan đến những hệ thống với chỉ một thể hiện của mỗi loại tài nguyên cũng như đối với hệ thống có nhiều thể hiện cho mỗi loại tài nguyên. Tuy nhiên, tại thời điểm này chúng ta chú ý lược đồ phát hiện và phục hồi yêu cầu chi phí bao gồm không chỉ chi phí tại thời điểm thực thi cho việc duy trì thông tin cần thiết và thực thi giải thuật phát hiện mà còn các lãng phí có thể phát sinh trong việc phát hiện từ deadlock.

Một thể hiện của mỗi loại tài nguyên

Hình VI‑7 a) Đồ thị cấp phát tài nguyên. b) Đồ thị chờ tương ứng

Chính xác hơn, một cạnh từ Pi tới Pj trong đồ thị chờ hiển thị rằng quá trình Pi đang chờ một quá trình Pj để giải phóng tài nguyên mà Pi cần. Cạnh Pi  Pj tồn tại trong đồ thị chờ nếu và chỉ nếu đồ thị cấp phát tài nguyên tương ứng chứa hai cạnh Pi  Rq và Rq  Pj đối với một số tài nguyên Rq. Thí dụ, trong hình VI-7 dưới đây, chúng ta trình bày đồ thị cấp phát tài nguyên và đồ thị chờ tương ứng.

Như đã đề cập trước đó, deadlock tồn tại trong hệ thống nếu và chỉ nếu đồ thị chờ chứa chu trình. Để phát hiện deadlock, hệ thống cần duy trì đồ thị chờ và định kỳ gọi giải thuật để tìm kiếm chu trình trong đồ thị.

Một giải thuật phát hiện chu trình trong đồ thị yêu cầu độ phức tạp n2 thao tác, ở đây n là số cạnh của đồ thị.

Nhiều thể hiện của một loại tài nguyên

Lược đồ đồ thị chờ không thể áp dụng đối với hệ thống cấp phát tài nguyên với nhiều thể hiện cho mỗi loại tài nguyên. Giải thuật phát hiện deadlock mà chúng ta mô tả sau đây có thể áp dụng cho hệ thống này. Giải thuật thực hiện nhiều cấu trúc dữ liệu thay đổi theo thời gian mà chúng tương tự như được dùng trong giải thuật Banker.

• Available: một vector có chiều dài m hiển thị số lượng tài nguyên sẳn có của mỗi loại.
• Allocation: ma trận nxm định nghĩa số lượng tài nguyên của mỗi loại hiện được cấp phát tới mỗi quá trình.
• Request: ma trận nxm hiển thị yêu cầu hiện tại của mỗi quá trình. Nếu Request[i,j] = k, thì quá trình Pi đang yêu cầu k thể hiện nữa của loại tài nguyên Rj.

Quan hệ  giữa hai vectors được định nghĩa trong phần VI.7.3. Để ký hiệu đơn giản, chúng ta sẽ xem những hàng trong ma trận Allocation và Request như các vector, và sẽ tham chiếu chúng như Allocationi và Requesti tương ứng. Giải thuật phát hiện được mô tả ở đây đơn giản khảo sát mọi thứ tự cấp phát có thể đối với các quá trình còn lại để được hoàn thành. So sánh giải thuật này với giải thuật Banker.