DEADLOCK

- Là trạng thái xảy ra trong môi trường đa nhiệm khi hai hoặc nhiều tiến trình đi vào vòng lặp chờ tài nguyên mãi mãi.
- Đồ thị cấp phát tài nguyên (RAG) là đồ thị có hướng, với tập đỉnh V và tập cạnh E.
+ Tập đỉnh V gồm 2 loại:
	* P = {P1, P2, …, Pn}		(Tất cả process trong hệ thống)
	* R = {R1, R2, …, Rn}	(Tất cả các loại tài nguyên trong hệ thống)
+ Tập cạnh E gồm 2 loại:
	* Cạnh yêu cầu: Pj → Rj
	* Cạnh cấp phát: Rj → Pj
=> 	RAG không chứa chu trình thì không có deadlock
	RAG chứa một hay nhiều chu trình:
		* Nếu mỗi loại tài nguyên chỉ có một thực thể => Deadlock
		* Nếu mỗi loại tài nguyên có nhiều thực thể => Có thể xảy ra deadlock
- Điều kiện xảy ra deadlock: (cả 4 đồng thời xảy ra)
+ Loại trừ lẫn nhau: Một tài nguyên không thể sử dụng hơn một tiến trình tại một thời điểm.
+ Giữ và chờ: Các tiến trình giữ tài nguyên và chờ tài nguyên mới.
+ Không có trưng dụng tài nguyên: Các tài nguyên không thể bị đòi lại, chúng chỉ có thể được giải phóng bởi chính tiến trình chiếm giữ chúng.
+ Chờ đợi vòng tròn: Các tiến trình chiếm giữ tài nguyên và chờ tài nguyên bị giữ bởi tiến trình khác, tạo thành một chu trình.
- Đối phó deadlock:
+ Ngăn chặn deadlock: ngăn chặn ít nhất 1 trong 4 điều kiện để xảy ra deadlock nêu trên. VD: cho phép chia sẻ tài nguyên, cho phép trưng dụng,…
+ Phòng tránh deadlock: dự đoán trước deadlock có xảy ra hay không trước khi tiến hành phân phối tài nguyên cho tiến trình. VD: giải thuật nhà băng.
+ Phát hiện và khắc phục deadlock: nếu không thể phòng tránh hay ngăn chặn deadlock, cứ để deadlock xảy ra và ta sẽ phát hiện và khắc phục chúng. Pp này phù hợp với hệ thống ít xảy ra deadlock và hậu quả deadlock ít nghiêm trọng
- Thuật toán nhà bank: (Banker’s Algorithm)
Need = Max – Allocation
Với mỗi Request, kiểm tra xem hệ thống có đang trong trạng thái an toàn không?
RequestP1 < NeedP1 < Available
=> RequestP1 được cấp → Cập nhật AllocationP1, NeedP1, Available
Available ≥ Need thì cho phép và cộng dồn Available += Allocation
Khi có request thì cập nhật Available = Available – Request