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

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.
Dĩ nhiên, nạp giải thuật phát hiện deadlock cho mỗi yêu cầu có thể gây ra một
chi phí có thể xem xét trong thời gian tính toán. Một thay đổi ít đắt hơn là nạp giải
thuật tại thời điểm ít thường xuyên hơn- thí dụ, một lần một giờ hay bất cứ khi nào
việc sử dụng CPU rơi xuống thấp hơn 40%. Nếu giải thuật phát hiện deadlock được
nạp trong những thời điểm bất kỳ, thì có nhiều chu trình trong đồ thị tài nguyên.
Chúng ta không thể nói quá trình nào của nhiều quá trình bị deadlock gây ra deadlock.
IX Phục hồi deadlock
Khi giải thuật phát hiện xác định rằng deadlock tồn tại, nhiều thay đổi tồn tại.
Một khả năng là thông báo người điều hành rằng deadlock xảy ra và để người điều
hành giải quyết deadlock bằng thủ công. Một khả năng khác là để hệ thống tự động
phục hồi. Có hai tuỳ chọn cho việc phá vỡ deadlock. Một giải pháp đơn giản là huỷ bỏ
một hay nhiều quá trình để phá vỡ việc tồn tại chu trình trong đồ thị cấp phát tài
nguyên. Tuỳ chọn thứ hai là lấy lại một số tài nguyên từ một hay nhiều quá trình bị
deadlock.
IX.1 Kết thúc quá trình
Để xóa deadlock bằng cách hủy bỏ quá trình, chúng ta dùng một trong hai phương
pháp. Trong cả hai phương pháp, hệ thống lấy lại tài nguyên được cấp phát đối với
quá trình bị kết thúc.
• Huỷ bỏ tất cả quá trình bị deadlock: phương pháp này rõ ràng sẽ phá vỡ chu
trình deadlock, nhưng chi phí cao; các quá trình này có thể đã tính toán trong
thời gian dài, và các kết quả của các tính toán từng phần này phải bị bỏ đi và
có thể phải tính lại sau đó.
• Hủy bỏ một quá trình tại thời điểm cho đến khi chu trình deadlock bị
xóa:phương pháp này chịu chi phí có thể xem xét vì sau khi mỗi quá trình bị
hủy bỏ, một giải thuật phát hiện deadlock phải được nạp lên để xác định có
quá trình nào vẫn đang bị deadlock.
Hủy bỏ quá trình có thể không dễ. Nếu một quá trình đang ở giữa giai đoạn cập
nhật một tập tin, kết thúc nó sẽ để tập tin đó trong trạng thái không phù hợp. Tương
tự, nếu quá trình đang ở giữa giai đoạn in dữ liệu ra máy in, hệ thống phải khởi động
lại trạng thái đúng trước khi in công việc tiếp theo.
Nếu phương pháp kết thúc một phần được dùng thì với một tập hợp các quá
trình deadlock được cho, chúng ta phải xác định quá trình nào (hay các quá trình nào)
nên được kết thúc trong sự cố gắng để phá vỡ deadlock. Việc xác định này là một
quyết định chính sách tương tự như các vấn đề lập thời biểu CPU. Câu hỏi về tính
kinh tế là chúng ta nên hủy bỏ quá trình nào thì sự kết thúc của quá trình đó sẽ chịu
chi phí tối thiểu. Tuy nhiên, thuật ngữ chi phí tối thiểu là không chính xác.