Deadlock

Deadlock (Khóa chết) là trạng thái xảy ra trong môi trường đa nhiệm (muti-threading) 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.

Ví dụ

Thread 1	Thread 2
Muốn lấy tài nguyên A và B	Muốn lấy tài nguyên A và B
Chiếm tài nguyên A, chờ Thread 2 bắt đầu chạy cho tới khi Thread 2 đợi tài nguyên A giải phóng
	Chiếm tài nguyên B
	Đợi tài nguyên A giải phóng
Đợi tài nguyên B giải phóng
Deadlock

Đối phó với Deadlock

Điều kiện xảy ra Deadlock

Có bốn điều kiện cần thiết để deadlock có thể xảy ra.

1. Điều kiện loại trừ lẫn nhau: Một tài nguyên không thể sử dụng bởi nhiều hơn một tiến trình tại một thời điểm
2. Điều kiện giữ và chờ: Các tiến trình giữ tài nguyên và chờ tài nguyên mới
3. Điều kiện không thể chiếm: 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
4. Điều kiện chu trình chờ: Các tiến trình giữ tài nguyên và chờ các tài nguyên bị giữ bởi tiến trình khác, tạo thành một chu trình. Ví dụ: Tiến trình 1, chiếm A1, chờ A2. Tiến trình 2 chiếm A2, chờ A3,... Tiến trình N chiếm An, chờ A1.

Liên kết ngoài

Bài viết

• "Distributed Deadlock Detection" by JoAnne L. Holliday and Amr El Abbadi
• "Deadlock detection in distributed databases" by Edgar Knapp
• "Advanced Synchronization in Java Threads" by Scott Oaks and Henry Wong

Bản in

• "Deadlock Detection in Distributed Object Systems" by Nima Kaveh and Wolfgang Emmerich
• "Confirmation of Deadlock Potentials Detected by Runtime Analysis" by Saddek Bensalem, Jean-Claude Fernandez, Klaus Havelund and Laurent Mounier
• Coffman, E.G., M.J. Elphick, and A. Shoshani, System Deadlocks, ACM Computing Surveys, 3, 2, 67-78 (1971).
• Eliminating Receive Livelock in an Interrupt-driven Kernel by Jeffrey C. Mogul, K. K. Ramakrishnan
• Havender, J. W., "Avoiding deadlock in multitasking systems", IBM Systems Journal, Volume 7, Number 2, Page 74 (1968)

Chung

• Deadlock Detection Agents
• Etymology of "Deadlock"
• ARCS - A Web Service approach to alleviating deadlock