Deadlock là gì? 4 điều kiện cần thiết và các cách phòng tránh?

Deadlock xảy ra khi nhiều process chờ nhau giải phóng resource mà không process nào có thể tiếp tục.

Coffman

1. xác định 4 điều kiện cần thiết đồng thời:
2. Mutual Exclusion: resource chỉ 1 process dùng tại một thời điểm
3. Hold and Wait: process giữ ít nhất 1 resource và chờ thêm resource khác
4. No Preemption: resource không thể bị lấy bắt buộc
5. Circular Wait: tồn tại chuỗi vòng P1→P2→...→Pn→P1 chờ nhau

Phòng tránh bằng cách phá vỡ một điều kiện: Lock Ordering (phá Circular Wait): luôn acquire lock theo thứ tự cố định — ví dụ database luôn lock bảng A trước bảng B. Trylock với timeout (phá Hold and Wait): nếu không lấy được lock sau timeout thì release tất cả và retry. Banker's Algorithm: OS kiểm tra trước khi cấp resource. Thực tế: Java synchronized blocks, Go channel patterns, và database transaction isolation level đều phải xử lý deadlock — PostgreSQL phát hiện deadlock và rollback một transaction.

A deadlock occurs when multiple processes are each waiting for another to release a resource, so none can proceed.

Coffman

1. identified 4 conditions that must all hold simultaneously:
2. Mutual Exclusion: a resource can be held by only one process at a time
3. Hold and Wait: a process holds at least one resource while waiting to acquire additional resources
4. No Preemption: resources cannot be forcibly taken from a process
5. Circular Wait: a circular chain P1→P2→...→Pn→P1 exists where each process waits for a resource held by the next

Prevention involves breaking one condition: Lock Ordering (breaks Circular Wait) — always acquire locks in a fixed global order, e.g., a database always locks table A before table B. Trylock with timeout (breaks Hold and Wait) — if a lock cannot be acquired within the timeout, release all held locks and retry. Banker's Algorithm — the OS checks resource availability before granting a request. In practice, Java synchronized blocks, Go channel patterns, and database transaction isolation levels all must handle deadlocks — PostgreSQL detects deadlocks and rolls back one of the transactions.