Deadlock — bốn điều kiện Coffman và cách phá vòng chờ

TL;DR: Deadlock là khi một nhóm luồng bị kẹt vĩnh viễn vì mỗi luồng đang giữ một khoá và chờ một khoá mà luồng khác trong nhóm đang giữ — vòng chờ khép kín, không ai nhả, không ai tiến. Nó chỉ xảy ra khi cả bốn điều kiện Coffman cùng đúng: mutual exclusion, hold-and-wait, no preemption, circular wait. Phá bất kỳ một điều kiện là đủ chống deadlock, và cách thực dụng nhất là phá circular wait bằng lock ordering — luôn lấy các khoá theo cùng một thứ tự toàn cục. Khi đã lỡ deadlock, jstack (thread dump) in thẳng "Found one Java-level deadlock" và chỉ ra vòng chờ. Khác race (kết quả sai), deadlock làm chương trình treo — thường dễ chẩn đoán hơn nhưng vẫn là sự cố nặng.

Ở bài trước, mutex trị được race. Nhưng khoá không miễn phí về rủi ro: dùng nhiều khoá không cẩn thận sinh ra một loại lỗi mới — chương trình không sai kết quả, nó đơn giản đứng im. Một service đang chạy bỗng ngừng xử lý request, CPU về 0%, không log, không exception. Đó thường là deadlock: hai luồng đang lịch sự chờ nhau, mãi mãi.

Bài này mổ đúng cơ chế đó: dựng một deadlock tối thiểu bằng hai khoá, chỉ ra bốn mảnh ghép phải cùng có để nó xảy ra, cách bắt nó tại hiện trường bằng thread dump, và cách thiết kế để nó không thể xảy ra. Học xong, bạn chẩn đoán được một service treo là deadlock qua thread dump, và thiết kế lock ordering để nó không thể xảy ra ngay từ đầu.

1. Analogy — hai người, một cây cầu một làn

Hai người đi xe máy vào một cây cầu hẹp một làn từ hai đầu, gặp nhau ở giữa. Muốn đi tiếp, mỗi người cần phần cầu người kia đang chiếm. Cả hai đều nghĩ: "Tôi tới trước, người kia lùi đi." Không ai lùi. Cả hai kẹt cứng — không phải vì hỏng xe, mà vì mỗi người giữ chỗ của mình và chờ chỗ của người kia.

Đây đúng là deadlock. Không ai làm gì sai theo luật riêng; hệ thống kẹt vì cấu trúc chờ đợi tạo thành vòng kín. Và cách phá cũng lộ ra từ analogy: nếu có luật "xe từ hướng Bắc luôn được ưu tiên" (một thứ tự toàn cục), sẽ không bao giờ có thế kẹt — người hướng Nam biết phải lùi.

2. Dựng một deadlock tối thiểu

Cách chắc chắn nhất để tạo deadlock: hai luồng lấy hai khoá theo hai thứ tự ngược nhau. Ví dụ chuyển tiền giữa hai tài khoản, mỗi tài khoản có một khoá riêng:

public class DeadlockDemo {
    static final Object lockA = new Object();
    static final Object lockB = new Object();

    public static void main(String[] args) {
        // Luong 1: khoa A truoc, roi B
        Thread t1 = new Thread(() -> {
            synchronized (lockA) {
                sleep(50);                 // tao khe thoi gian de chac chan ket
                synchronized (lockB) {     // cho B -- t2 dang giu
                    System.out.println("t1 got both");
                }
            }
        });
        // Luong 2: khoa B truoc, roi A  <-- THU TU NGUOC
        Thread t2 = new Thread(() -> {
            synchronized (lockB) {
                sleep(50);
                synchronized (lockA) {     // cho A -- t1 dang giu
                    System.out.println("t2 got both");
                }
            }
        });
        t1.start(); t2.start();
    }

    static void sleep(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException e) {}
    }
}

Chạy chương trình: nó in... không gì cả, rồi treo. t1 giữ lockA và chờ lockB; t2 giữ lockB và chờ lockA. Không ai nhả khoá đang giữ (vì còn kẹt trong synchronized), không ai lấy được khoá đang chờ. Chương trình đứng im vô hạn — CPU 0%, không crash.

sleep(50) chỉ để chắc chắn trúng deadlock mỗi lần cho mục đích minh hoạ. Trong thực tế, không cần sleep: chỉ cần scheduler xui xẻo cho t1 lấy lockA và t2 lấy lockB trước khi luồng nào kịp lấy khoá thứ hai — và như race, timing đó thỉnh thoảng mới trúng, khiến deadlock production cũng rình rập bất chợt.

flowchart LR
  T1["Luong t1<br/>giu lockA"] -->|"cho lockB"| T2["Luong t2<br/>giu lockB"]
  T2 -->|"cho lockA"| T1

Đồ thị "ai chờ ai" có một vòng kín — đó chính là chữ ký hình học của deadlock.

3. Bốn điều kiện Coffman

Deadlock không xảy ra tuỳ tiện. Coffman, Elphick và Shoshani (1971) chứng minh nó cần đồng thời cả bốn điều kiện. Thiếu một, deadlock không thể hình thành:

1. Mutual exclusion (loại trừ lẫn nhau): tài nguyên chỉ một luồng dùng tại một thời điểm. Khoá theo định nghĩa là vậy — nếu chia sẻ được thì đâu cần khoá.
2. Hold-and-wait (giữ và chờ): một luồng đang giữ ít nhất một tài nguyên và đang chờ xin thêm tài nguyên khác. Trong demo: t1 giữ lockA trong khi chờ lockB.
3. No preemption (không thu hồi): không thể cưỡng đoạt tài nguyên từ luồng đang giữ; nó phải tự nguyện nhả. OS không thể "giật" khoá synchronized khỏi t1.
4. Circular wait (chờ vòng tròn): tồn tại một chuỗi luồng T1 → T2 → ... → Tn → T1, trong đó mỗi luồng chờ tài nguyên do luồng kế trong chuỗi giữ. Demo: t1 → t2 → t1.

flowchart TB
  M["Mutual exclusion<br/>(khoa doc quyen)"] --> D(("DEADLOCK"))
  H["Hold-and-wait<br/>(giu + xin them)"] --> D
  N["No preemption<br/>(khong giat duoc)"] --> D
  C["Circular wait<br/>(cho vong tron)"] --> D

Điểm giải phóng nằm ở chữ cả bốn: vì deadlock cần tất cả bốn, ta chỉ cần phá một là chống được. Bốn điều kiện cho ta bốn hướng tấn công.

4. Phá điều kiện nào — và cách nào thực dụng nhất?

Xét từng điều kiện xem có phá được không:

• Phá mutual exclusion? Gần như không — bản chất khoá là độc quyền. (Ngoại lệ: dùng cấu trúc lock-free/immutable để khỏi cần khoá — chính là "đừng chia sẻ" ở bài 02.)
• Phá hold-and-wait? Yêu cầu luồng lấy tất cả khoá cần một lần ngay từ đầu (all-or-nothing); nếu không đủ thì buông hết, không giữ cái nào mà chờ. Khả thi nhưng khó khi không biết trước cần khoá gì.
• Phá no-preemption? Cho phép "buông" khi chờ quá lâu: dùng tryLock(timeout) — nếu không lấy được khoá thứ hai trong hạn, nhả khoá đang giữ rồi thử lại từ đầu. Đây là cách ReentrantLock hỗ trợ trực tiếp.
• Phá circular wait? Áp một thứ tự toàn cục lên mọi khoá và buộc mọi luồng lấy khoá theo đúng thứ tự tăng dần đó. Không thể có vòng kín nếu mọi người đi cùng một chiều. Đây là cách phổ biến và rẻ nhất.

Lock ordering (phá circular wait). Gán cho mỗi khoá một thứ hạng (ví dụ theo id tài khoản) và luôn khoá cái hạng nhỏ trước. (Khi không có id tự nhiên, có thể dùng System.identityHashCode làm thứ hạng, nhưng nó không duy nhất — hai object có thể trùng hash, khiến thứ tự không toàn phần; đúng lúc trùng, JCiP §10.1.2 phải thêm một "tie-breaker lock" thứ ba để phá thế hoà.) Trước khi xem lời giải, thử tự điền hai chỗ trống dưới đây:

static void transfer(Account from, Account to, long amount) {
    // Muc tieu: luon khoa tai khoan id NHO hon truoc, bat ke ai la nguon/dich
    Account first  = /* TODO: chon tai khoan nao khoa truoc? */;
    Account second = /* TODO: chon tai khoan nao khoa sau? */;
    synchronized (first.lock()) {
        synchronized (second.lock()) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

Đáp án — sắp hai tài khoản theo id tăng dần, luôn khoá cái nhỏ trước:

static void transfer(Account from, Account to, long amount) {
    // Luon khoa theo thu tu id tang dan -> khong bao gio tao vong kin
    Account first  = from.id() < to.id() ? from : to;
    Account second = from.id() < to.id() ? to : from;
    synchronized (first.lock()) {
        synchronized (second.lock()) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

Giờ dù transfer(A, B) và transfer(B, A) chạy song song, cả hai đều khoá tài khoản id nhỏ trước — không còn hai thứ tự ngược nhau, không còn vòng kín. Deadlock bị loại về mặt cấu trúc.

tryLock (phá no-preemption). Khi không áp được thứ tự toàn cục (khoá đến từ nhiều thư viện, không so sánh được), dùng chờ-có-hạn rồi rút lui:

// tryLock(timeout) va Thread.sleep deu nem InterruptedException -> khai bao throws
void transfer() throws InterruptedException {
    while (true) {
        if (lockA.tryLock(100, TimeUnit.MILLISECONDS)) {
            try {
                if (lockB.tryLock(100, TimeUnit.MILLISECONDS)) {
                    try { /* critical section */ return; }
                    finally { lockB.unlock(); }
                }
            } finally { lockA.unlock(); }   // lay B that bai -> nha A, thu lai
        }
        // backoff ngau nhien de tranh hai luong cu retry dong bo
        Thread.sleep(ThreadLocalRandom.current().nextInt(50));
    }
}

Cách này không kẹt vĩnh viễn (luôn có đường buông ra), nhưng phức tạp hơn và có thể livelock nếu các luồng cứ retry đồng bộ — nên thêm backoff ngẫu nhiên. Ưu tiên lock ordering; dùng tryLock khi không còn cách.

5. Chẩn đoán — đọc thread dump

Khi một service Java treo, công cụ đầu tiên là thread dump — ảnh chụp mọi luồng và khoá chúng đang giữ/chờ. Lấy bằng jstack <pid> (hoặc gửi tín hiệu SIGQUIT/Ctrl-\). JVM tự phát hiện deadlock chu trình khoá synchronized/ReentrantLock và in thẳng ra đầu dump:

Found one Java-level deadlock:
=============================
"Thread-0":
  waiting to lock monitor 0x00007f... (object 0x000000..., a java.lang.Object),
  which is held by "Thread-1"
"Thread-1":
  waiting to lock monitor 0x00007f... (object 0x000000..., a java.lang.Object),
  which is held by "Thread-0"

Java stack information for the threads listed above:
===================================================
"Thread-0":
        at DeadlockDemo.lambda$main$0(DeadlockDemo.java:11)
        - waiting to lock <0x...> (a java.lang.Object)
        - locked <0x...> (a java.lang.Object)
"Thread-1":
        at DeadlockDemo.lambda$main$1(DeadlockDemo.java:19)
        - waiting to lock <0x...> (a java.lang.Object)
        - locked <0x...> (a java.lang.Object)

Đọc dump: dòng Found one Java-level deadlock là kết luận sẵn của JVM. Với mỗi luồng, locked <...> là khoá nó đang giữ, waiting to lock <...> là khoá nó đang chờ. Ghép lại thấy Thread-0 chờ khoá Thread-1 giữ và ngược lại — đúng vòng kín. Số dòng (DeadlockDemo.java:11) chỉ thẳng chỗ code kẹt để bạn sửa.

6. Áp dụng vào code của bạn

• Đếm số khoá một luồng giữ đồng thời. Deadlock cần giữ ≥2 khoá cùng lúc (hold-and-wait). Nếu mỗi luồng chỉ bao giờ giữ một khoá tại một thời điểm, deadlock không thể xảy ra. Cách rẻ nhất chống deadlock là không lồng khoá.
• Khi buộc lồng khoá, áp lock ordering. Định một thứ tự toàn cục (theo id, tên, hay hằng số) và luôn lấy theo thứ tự đó ở mọi nơi trong codebase. Chỉ một chỗ lấy ngược là đủ mở lại cửa deadlock.
• Đừng gọi code lạ trong khi giữ khoá. Gọi callback, listener, hay method của lớp con khi đang giữ khoá là nguy hiểm: code đó có thể lấy khoá khác và tạo vòng bạn không lường trước. Nhả khoá trước khi gọi ra ngoài.
• Ưu tiên không chia sẻ (bài 02). Message passing và immutable không cần khoá → không có deadlock. Deadlock là cái giá của việc chia sẻ dữ liệu bằng khoá; tránh chia sẻ thì tránh luôn cái giá đó.

7. Pitfall tổng hợp

❌ Nhầm 1 — hai method khoá cùng hai object theo thứ tự khác nhau:

void moveLeftToRight() { synchronized (a) { synchronized (b) { ... } } }
void moveRightToLeft() { synchronized (b) { synchronized (a) { ... } } }  // NGUOC

✅ Hai method này chạy song song là deadlock chờ sẵn. Sửa: cả hai lấy khoá theo cùng thứ tự toàn cục (luôn a trước b, bất kể hướng di chuyển). Thứ tự khoá phải nhất quán toàn codebase, không theo ngữ nghĩa lời gọi.

❌ Nhầm 2 — "thêm sleep/retry cho đỡ đụng" mà không phá điều kiện nào:

✅ Chèn sleep chỉ đổi timing, làm deadlock hiếm hơn chứ không hết — y như thêm log không sửa được race. Deadlock chỉ biến mất khi bạn phá một trong bốn điều kiện Coffman một cách có chủ đích (thường là lock ordering). Đừng nhầm "hiếm hơn" với "đã sửa".

❌ Nhầm 3 — giữ khoá rồi gọi ra ngoài (callback/lock lồng ẩn):

synchronized (lock) {
    listener.onChange(this);   // listener co the lay khoa khac -> vong an
}

✅ Bạn không kiểm soát listener làm gì; nó có thể lấy một khoá tạo vòng chờ với lock. Thu thập dữ liệu cần trong khoá, nhả khoá, rồi mới gọi callback ngoài.

8. 📚 Deep Dive — deadlock trong lý thuyết OS

9. Liên hệ các bài khác

• Bài 02 — Mutex & atomic: deadlock là mặt trái của mutex; tryLock (giới thiệu ở bài 02) chính là công cụ phá no-preemption ở đây.
• Bài 01 — Race condition: cặp song sinh — race là kết quả sai, deadlock là chương trình treo; cả hai đều timing-dependent và đến từ chia sẻ dữ liệu.
• Bài 04 — IPC: message passing tránh chia sẻ khoá nên tránh được deadlock do tranh khoá — dù hai bên vẫn có thể kẹt nếu cùng block chờ nhận của nhau (communication deadlock); một lý do nữa để cân nhắc kiến trúc không-chia-sẻ.
• Bài 05 — Mini-challenge: bạn sẽ chẩn đoán và phá một deadlock thật bằng lock ordering.

10. Tóm tắt

• Deadlock: mỗi luồng giữ một khoá và chờ khoá luồng khác giữ, tạo vòng chờ khép kín → treo vĩnh viễn (CPU 0%, không crash).
• Cần cả bốn điều kiện Coffman cùng đúng: mutual exclusion, hold-and-wait, no preemption, circular wait.
• Vì cần cả bốn, phá một là đủ. Thực dụng nhất: phá circular wait bằng lock ordering — luôn lấy khoá theo cùng thứ tự toàn cục.
• tryLock(timeout) phá no-preemption: chờ có hạn rồi nhả hết và thử lại (kèm backoff ngẫu nhiên để tránh livelock).
• jstack in "Found one Java-level deadlock" và chỉ ra locked/waiting to lock của từng luồng — bằng chứng vòng chờ nằm sẵn trong thread dump.
• Deadlock dễ chẩn đoán hơn race (treo quan sát được, JVM tự chỉ) nhưng chỉ thấy được deadlock qua khoá JVM biết.
• Chống rẻ nhất: không lồng khoá (mỗi luồng giữ tối đa một khoá); tốt hơn nữa: không chia sẻ (message passing, immutable) → không cần khoá → không deadlock.

11. Tự kiểm tra

Bài tiếp theo: IPC — pipe, shared memory, socket