Giải thuật phát hiện deadlock

Detection Algorithm - Giải thuật phát hiện deadlock
1. Gọi Work và Finish là vector kích thước m và n:
(a) Work:= Available
(b) Với i=1,2,…,n, nếu Allocation(i) # 0 => Finish[i] = false
Ngược lại => Finish[i] = true
2. Tìm i thỏa mãn:
Finish[i] = false và Request(i) <= Work, Nếu không tồn tại i, đến bước 4.
3. Work = Work + Allocation(i)
Finish[i] = true
Quay về bước 2.
4. Эi, 1<=i<=n: Finish[i] = false => hệ thông đang ở trạng thái deadlock. Hơn thế nữa, Finish[i] = false =>P(i) bị deadlock
Cách sử dụng giải thuật
 Thời điểm và mức thường xuyên cần đến giải thuật phụ thuộc:
• Deadlock có khả năng thường xuyên xảy ra như thế nào?
• Có bao nhiêu process bị tác động khi deadlock xuất hiện
 Nếu giải thuật phát hiện deadlock ít được sử dụng, có thể có nhiều chu trình trong biểu đồ tài nguyên và do đó ta không thể tìm được process nào “gây” ra deadlock
 Nếu phát hiện được deadlock, chúng ta cần phục hồi lại bằng một trong hai cách
• Dừng các process
• Thu hồi tài nguyên
Deadlock Recorery - dừng process
- Phục hồi hệ thống deadlock chủ yếu là bẻ gảy chu kỳ wait-for của các process bị deadlock
+ Hủy bỏ tất cả process bị deadlock
+ Hủy bỏ lần lượt từng process và thu hồi tài nguyên cho đến khi không còn deadlock
- Dựa trên cơ sở nào để hủy bỏ process?
+ Độ ưu tiên của process?
+ Thời gian thực thi của process và thời gian còn lại?
+ Loại tài nguyên mà process đã sử dụng?
+ Tài nguyên mà process cần để hoàn tất công việc
+ Số lượng process cần hủy bỏ?
+ Process là interactive process hay batch process?
+ …………
Deadlock Recorery -Thu hồi tài nguyên
- Đoạt tài nguyên từ một process, cấp phát cho process khác cho đến khi không còn deadlock nữa
- Các vấn đề trong chiến lược thu hồi tài nguyên:
+ Chọn “nạn nhân” – tối thiểu chi phí (có thể dựa trên số tài nguyên sở hữu, thời gian CPU đã tiêu tốn,…)
+ Rollback – quay trở về trạng thái safe, bắt đầu các process từ trạng thái đó. Gồm có total rollback và check-point rollback
Hệ thống cần lưu giữ một số thông tin về trạng thái các process sẽ luôn luôn bị đoạt tài nguyên mỗi khi deadlock xảy ra