[Advanced Java] Deadlock, Livelock trong Java và cách phòng tránh

Một chương trình bị deadlock không crash. Nó không log ra gì, không throw exception, và không có watchdog nào kêu. Hai thread chỉ đơn giản là dừng lại, mỗi bên đang giữ đúng cái lock mà bên kia cần, và request chúng đang phục vụ thì không bao giờ trả về. Nhìn từ bên ngoài, nó giống hệt một hệ thống chạy chậm.

Đó mới là phần khó nhất của loại bug này: phân biệt deadlock với một chương trình chỉ đang bận. Bài viết dựng một deadlock tái hiện được theo yêu cầu, chứng minh nó đúng là deadlock bằng thread dump thật, rồi sửa nó theo bốn cách khác nhau — mỗi cách phá một trong bốn điều kiện mà deadlock cần. Cuối bài là livelock và starvation, hai kiểu hỏng trông giống deadlock trên dashboard monitoring nhưng lại chẳng để lại dấu vết gì trong thread dump.

Mọi chương trình bên dưới đều được compile và chạy thật trên OpenJDK 21.0.6 (arm64), và mọi thread dump đều là bản chụp thật từ một JVM đang treo thật. Output của code concurrent không deterministic: thứ tự dòng, số lần thử và tên thread thay đổi giữa các lần chạy, nên chỗ nào thay đổi được đều được ghi rõ, và bạn có thể phải chạy lại một ví dụ vài lần mới thấy đúng hiện tượng được mô tả.

Deadlock là gì và bốn điều kiện tạo ra nó

Deadlock là một tập thread mà mỗi thread trong đó đang chờ một resource do một thread khác cùng tập đang giữ. Vì không ai đi tiếp được nên cũng không ai nhả thứ mình đang giữ, và cả tập kẹt vĩnh viễn. Không có timeout nào hết hạn, bởi vì synchronized không có timeout.

Deadlock không phải tai nạn của scheduler. Nó cần bốn điều kiện xảy ra đồng thời, kết quả thường được gán cho bài báo năm 1971 của Edward Coffman. Phá đúng một điều kiện là deadlock không thể xảy ra, và đó chính là lý do bốn điều kiện này là khung xương của chiến lược phòng tránh chứ không phải kiến thức thuộc lòng cho vui.

synchronized cho bạn ba điều kiện đầu một cách mặc định. Monitor là độc quyền, synchronized lồng nhau là hold and wait, và không gì tước được monitor khỏi chủ của nó. Vậy chỉ còn circular wait là thứ bạn tấn công được nếu vẫn ở lại với synchronized — đúng là lý do vì sao lời khuyên kinh điển luôn là "luôn lấy lock theo cùng một thứ tự". ReentrantLock mở thêm lựa chọn thứ hai, vì tryLock cho phép một thread rút lui khỏi lần acquire mà nó không hoàn tất được.

Dựng một deadlock tái hiện được mọi lần

Deadlock cần cả hai thread cùng nằm trong khoảng giữa lần acquire thứ nhất và thứ hai tại cùng một thời điểm. Nếu để tự nhiên, khoảng đó rộng vài nanosecond và bug xuất hiện mỗi tháng một lần trên production. Chèn một sleep vào giữa là nó xảy ra ở mọi lần chạy.

public class DeadlockDemo {
 
    static final Object LOCK_A = new Object();
    static final Object LOCK_B = new Object();
 
    static void log(String msg) {
        System.out.println(Thread.currentThread().getName() + ": " + msg);
    }
 
    static void pause(long ms) {
        try {
            Thread.sleep(ms);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
 
    public static void main(String[] args) {
        Thread t1 = new Thread(() -> {
            synchronized (LOCK_A) {
                log("holds A, wants B");
                pause(300);                 // widens the window so the deadlock is reliable
                synchronized (LOCK_B) {
                    log("holds A and B");
                }
            }
        }, "transfer-1");
 
        Thread t2 = new Thread(() -> {
            synchronized (LOCK_B) {
                log("holds B, wants A");
                pause(300);
                synchronized (LOCK_A) {
                    log("holds B and A");
                }
            }
        }, "transfer-2");
 
        t1.start();
        t2.start();
 
        // watchdog: never leave a wedged JVM behind
        Thread watchdog = new Thread(() -> {
            pause(20_000);
            System.out.println("watchdog: still stuck after 20s, killing the JVM");
            Runtime.getRuntime().halt(2);
        }, "watchdog");
        watchdog.setDaemon(true);
        watchdog.start();
    }
}

transfer-1: holds A, wants B
transfer-2: holds B, wants A

Rồi im lặng, cho tới khi watchdog nổ sau hai mươi giây. Không dòng holds A and B nào, cũng không có holds B and A. Thứ tự hai dòng trên đảo qua đảo lại giữa các lần chạy — có lần transfer-2 in trước — nhưng kết cục thì không đổi.

Luôn gắn watchdog cho những ví dụ kiểu này. Ở đây dùng Runtime.halt chứ không dùng System.exit là có chủ ý: exit sẽ chạy shutdown hook, và một shutdown hook đụng vào một trong hai lock cũng sẽ treo nốt.

Cả bốn điều kiện đều có mặt. Monitor là độc quyền, mỗi thread giữ một cái rồi đi xin cái kia, không monitor nào bị tước, và hai cạnh wait-for khép lại thành chu trình.

Làm sao chứng minh một chương trình đang treo đúng là deadlock?

Đừng đoán, hãy lấy thread dump. Tìm process id bằng jps hoặc jcmd -l, rồi hỏi JVM xem các thread của nó đang làm gì.

jps -l                # liệt kê các JVM đang chạy và main class của chúng
jstack 27395          # in toàn bộ thread dump ra stdout

Phần cuối của dump HotSpot là kết quả phân tích deadlock. Đây là bản chụp nguyên văn từ DeadlockDemo đang treo ở trên:

Found one Java-level deadlock:
=============================
"transfer-1":
  waiting to lock monitor 0x0000000a5d0fd0a0 (object 0x0000000310614370, a java.lang.Object),
  which is held by "transfer-2"
 
"transfer-2":
  waiting to lock monitor 0x0000000a5d0fd180 (object 0x0000000310614360, a java.lang.Object),
  which is held by "transfer-1"
 
Java stack information for the threads listed above:
===================================================
"transfer-1":
	at DeadlockDemo.lambda$main$0(DeadlockDemo.java:24)
	- waiting to lock <0x0000000310614370> (a java.lang.Object)
	- locked <0x0000000310614360> (a java.lang.Object)
	at DeadlockDemo$$Lambda/0x00000070010009f8.run(Unknown Source)
	at java.lang.Thread.runWith(java.base@21.0.6/Thread.java:1596)
	at java.lang.Thread.run(java.base@21.0.6/Thread.java:1583)
"transfer-2":
	at DeadlockDemo.lambda$main$1(DeadlockDemo.java:34)
	- waiting to lock <0x0000000310614360> (a java.lang.Object)
	- locked <0x0000000310614370> (a java.lang.Object)
	at DeadlockDemo$$Lambda/0x0000007001000c08.run(Unknown Source)
	at java.lang.Thread.runWith(java.base@21.0.6/Thread.java:1596)
	at java.lang.Thread.run(java.base@21.0.6/Thread.java:1583)
 
Found 1 deadlock.

Cách đọc là khớp các địa chỉ object với nhau. transfer-1 có locked 0x...360 và đang waiting to lock 0x...370; transfer-2 thì ngược lại đúng y như vậy. Hai dòng bắt chéo nhau, và số dòng trỏ đúng vào synchronized bên trong của từng lambda. Địa chỉ là địa chỉ heap nên khác nhau ở mỗi lần chạy, còn cách chúng bắt cặp thì không.

Chính hai thread đó cũng xuất hiện ở phần trên của dump kèm state, và đó là nửa còn lại của bằng chứng:

"transfer-1" #20 [27395] prio=5 os_prio=31 cpu=3.93ms elapsed=1.94s tid=0x0000000a5d15ea00 nid=27395 waiting for monitor entry  [0x0000000171aaa000]
   java.lang.Thread.State: BLOCKED (on object monitor)
	at DeadlockDemo.lambda$main$0(DeadlockDemo.java:24)
	- waiting to lock <0x0000000310614370> (a java.lang.Object)
	- locked <0x0000000310614360> (a java.lang.Object)

BLOCKED (on object monitor) với cpu=3.93ms so với elapsed=1.94s nghĩa là thread gần như không tiêu tốn CPU nào kể từ lúc bắt đầu. Một thread chạy chậm trông hoàn toàn khác: nó ở trạng thái RUNNABLE và giá trị cpu tăng theo elapsed. Chỉ riêng điểm tương phản đó thường đã đủ để phân loại một ca treo trước khi bạn đọc thêm bất cứ thứ gì.

jcmd in ra dump y hệt và là công cụ Oracle khuyến nghị hiện nay, nên máy có cái nào thì dùng cái đó:

jcmd 27395 Thread.print

Có hai giới hạn đáng nhớ. Bộ phát hiện này hiểu monitor và các ownable synchronizer của java.util.concurrent, nên một chu trình ReentrantLock cũng được báo — với dòng waiting for ownable synchronizer 0x... (a java.util.concurrent.locks.ReentrantLock$NonfairSync), which is held by "rl-2" thay cho waiting to lock monitor. Thứ nó không thấy được là chu trình dựng từ mọi thứ khác: semaphore, latch, queue, hay một task đang chờ một task khác. Về mặt thực tế đó đều là deadlock thật, và dump sẽ không in Found 1 deadlock cho bất kỳ trường hợp nào trong số đó.

Phát hiện deadlock từ bên trong chính JVM

ThreadMXBean phơi ra đúng kết quả phân tích đó dưới dạng API, và đây là cách biến deadlock từ một ticket support thành một cái alert. findDeadlockedThreads() trả về null khi không có gì bất thường, và trả về mảng thread id khi có.

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadInfo;
import java.lang.management.ThreadMXBean;
 
static void startMonitor() {
    ThreadMXBean bean = ManagementFactory.getThreadMXBean();
    Thread monitor = new Thread(() -> {
        while (true) {
            pause(1000);
            long[] ids = bean.findDeadlockedThreads();
            if (ids == null) {
                System.out.println("monitor: no deadlock");
                continue;
            }
            ThreadInfo[] infos = bean.getThreadInfo(ids, true, true);
            System.out.println("monitor: DEADLOCK, " + ids.length + " threads");
            for (ThreadInfo info : infos) {
                System.out.println("  \"" + info.getThreadName() + "\" is " + info.getThreadState()
                        + " on " + info.getLockInfo()
                        + " owned by \"" + info.getLockOwnerName() + "\"");
            }
            Runtime.getRuntime().halt(1);
        }
    }, "deadlock-monitor");
    monitor.setDaemon(true);
    monitor.start();
}

Gắn vào đúng hai thread lúc nãy, nó báo ra chu trình ngay ở lượt quét đầu tiên:

monitor: DEADLOCK, 2 threads
  "transfer-1" is BLOCKED on java.lang.Object@6cd66c18 owned by "transfer-2"
  "transfer-2" is BLOCKED on java.lang.Object@181dfeef owned by "transfer-1"

Bốn lần chạy liên tiếp đều báo deadlock; các identity hash sau dấu @ khác nhau mỗi lần. Chú ý phân biệt findDeadlockedThreads() với findMonitorDeadlockedThreads() — cái thứ hai bỏ qua ReentrantLock và chỉ nhìn monitor, nên cứ dùng cái thứ nhất trừ khi có lý do khác. Trong một service chạy dài, bộ phát hiện kiểu này nên nằm trên một scheduled executor, ghi log và bắn alert thay vì gọi halt.

Phòng tránh deadlock bằng cách phá một trong bốn điều kiện

Ví dụ hai lock ở trên thì dễ nhìn ra. Code thật giấu đúng hình dạng đó sau một method lock bất cứ thứ gì được truyền vào:

// Naive: each call locks the accounts in the order it happens to receive them.
static void transfer(Account from, Account to, long amount) {
    synchronized (from) {
        synchronized (to) {
            if (from.balance >= amount) { from.balance -= amount; to.balance += amount; }
        }
    }
}

Ở đây không có chỗ nào nói tới việc lấy hai lock theo thứ tự ngược nhau — thế mà transfer(a, b) ở một thread và transfer(b, a) ở thread khác lại tạo ra đúng như vậy. Với tám thread chuyển tiền qua lại giữa bốn account và một ThreadMXBean monitor đứng canh, ba lần chạy đều deadlock trong chưa tới một giây:

DEADLOCK after 3 threads got stuck
  "worker-0" waits for "worker-5"
  "worker-5" waits for "worker-4"
  "worker-4" waits for "worker-0"

DEADLOCK after 2 threads got stuck
  "worker-0" waits for "worker-2"
  "worker-2" waits for "worker-0"

Độ dài chu trình và tên thread thay đổi theo từng lần chạy — bản chụp thứ hai là chu trình hai thread, bản đầu là chu trình ba thread. Đó mới là trường hợp tổng quát: chu trình deadlock dài bao nhiêu cũng được, và một chu trình ba thread khó nhìn ra khi review hơn nhiều so với một cặp.

Lock ordering toàn cục, cách sửa thực sự dùng được ở quy mô lớn

Gán cho mỗi lock một vị trí trong một thứ tự toàn phần, rồi bắt mọi thread acquire theo thứ tự đó. Khi ấy chu trình không tồn tại được, vì chu trình cần ít nhất một thread đi xuống trong khi một thread khác đi lên. Cách này phá circular wait và không đụng gì tới ba điều kiện còn lại.

Thứ tự đó phải ổn định và phải lấy được ngay tại chỗ gọi. Khi lock là các domain object có khoá tự nhiên — số tài khoản, primary key, user id — thì dùng luôn khoá đó. Khi không có, System.identityHashCode cho bạn một thứ tự trên object bất kỳ:

/** Used only when two distinct objects report the same identity hash code. */
private static final Object TIE_BREAK = new Object();
 
/** Always takes the two monitors in the same global order, whoever calls it. */
static void transfer(Account from, Account to, long amount) {
    int fromHash = System.identityHashCode(from);
    int toHash = System.identityHashCode(to);
    if (fromHash < toHash) {
        synchronized (from) {
            synchronized (to) { move(from, to, amount); }
        }
    } else if (fromHash > toHash) {
        synchronized (to) {
            synchronized (from) { move(from, to, amount); }
        }
    } else {
        // identity hash collision: one extra lock restores a total order
        synchronized (TIE_BREAK) {
            synchronized (from) {
                synchronized (to) { move(from, to, amount); }
            }
        }
    }
}

Vẫn tám thread đó, vẫn bốn account đó, mỗi thread hai mươi nghìn lần chuyển:

all 160000 transfers finished
total before = 4000, total after = 4000

Lần nào cũng chạy tới hết, và invariant vẫn đúng: tổng tiền được bảo toàn, nghĩa là việc sắp thứ tự không đánh đổi tính đúng đắn.

Nhánh else không phải kiểu phòng thủ thừa thãi. System.identityHashCode trả về int, nên hai object khác nhau vẫn có thể trùng giá trị, và khi trùng thì cả fromHash < toHash lẫn fromHash > toHash đều false, hai caller quay về đúng thứ tự argument của mình — chính là cái bug ban đầu. Tạo ra một va chạm không hề khó:

Map<Integer, Object> seen = new HashMap<>();
for (int i = 0; i < 20_000_000; i++) {
    Object o = new Object();
    int h = System.identityHashCode(o);
    Object prev = seen.putIfAbsent(h, o);
    if (prev != null) {
        System.out.println("collision after " + i + " objects: identityHashCode = " + h);
        System.out.println("same hash, different objects? " + (prev != o));
        return;
    }
}

collision after 105842 objects: identityHashCode = 2134400190
same hash, different objects? true

Khoảng một trăm nghìn object, trên một JVM vừa mới khởi động. Ba lần chạy lại đều rơi vào đúng con số đó trên máy này, vì bộ sinh identity hash mặc định của HotSpot là một chuỗi giả ngẫu nhiên theo từng thread; con số sẽ khác trên platform hoặc JVM khác, nhưng kết luận thì không đổi. Một service giữ sống hàng triệu object chắc chắn sẽ gặp va chạm, và TIE_BREAK chính là thứ giữ cho thứ tự vẫn toàn phần khi điều đó xảy ra.

Đặt timeout cho lock bằng tryLock kèm back-off

Hướng tấn công thực tế còn lại là nhắm vào no preemption. synchronized không interrupt và không timeout được, nhưng ReentrantLock.tryLock(timeout, unit) trả về false thay vì chờ mãi, nhờ đó thread nhả được thứ nó đang giữ và làm lại từ đầu. Không cần thứ tự toàn cục nữa, vì không thread nào chờ vô hạn trong lúc vẫn đang giữ lock.

/** Takes both locks or neither. No global order needed - it never waits while holding. */
static boolean transfer(Account from, Account to, long amount) throws InterruptedException {
    ThreadLocalRandom rnd = ThreadLocalRandom.current();
    for (int attempt = 0; attempt < 100; attempt++) {
        if (from.lock.tryLock(50, TimeUnit.MILLISECONDS)) {
            try {
                if (to.lock.tryLock(50, TimeUnit.MILLISECONDS)) {
                    try {
                        if (from.balance >= amount) {
                            from.balance -= amount;
                            to.balance += amount;
                        }
                        return true;
                    } finally { to.lock.unlock(); }
                }
            } finally { from.lock.unlock(); }
        }
        // randomised back-off: without the random part every loser retries in lockstep
        Thread.sleep(rnd.nextInt(1, 8));
    }
    return false;
}

finished, gave up on 0 transfers
total after = 4000

Có ba điểm khiến đoạn này đúng chứ không chỉ khôn khéo. tryLock bên trong nằm trong try của lock bên ngoài, nên lấy hụt lock thứ hai thì lock thứ nhất vẫn được nhả. Vòng retry có giới hạn và method trả về false khi hết lượt, nên caller có một đường thất bại thật sự thay vì một vòng lặp vô hạn. Và back-off là ngẫu nhiên — back-off cố định khiến mọi kẻ thua cuộc thử lại đúng cùng một thời điểm, và đó chính là nguyên liệu của livelock.

Dùng tryLock khi không thể có thứ tự toàn cục: lock do framework đưa cho bạn, thứ tự lock phụ thuộc dữ liệu lúc runtime, hoặc code buộc phải luôn phản hồi được. Còn lại thì dùng ordering, vì ordering không có đường retry nào để làm sai.

Thu hẹp phạm vi lock và bỏ hẳn lock lồng nhau

Cách sửa rẻ nhất là đừng giữ hai lock cùng lúc. Hai quy tắc sau đã lo được phần lớn.

Tính toán bên ngoài, publish bên trong. Thứ gì không đụng tới shared state thì không thuộc về bên trong khối synchronized. Đưa nó ra ngoài giúp rút ngắn thời gian giữ lock và thường xoá luôn lần acquire thứ hai.

// holds the lock across an I/O call and a second lock
synchronized (cache) {
    Report r = reportService.build(id);   // slow, and takes its own locks
    cache.put(id, r);
}
 
// holds the lock only for the publish
Report r = reportService.build(id);
synchronized (cache) {
    cache.put(id, r);
}

Không bao giờ gọi code lạ khi đang giữ lock. Một listener, một callback, một method bị override, một Comparator, một lambda do caller truyền vào — bất kỳ cái nào cũng có thể acquire một lock mà bạn chưa từng nghe tên, và thế là thứ tự lock của bạn có thêm một cạnh không phải do bạn viết. Hãy copy danh sách listener trong lock, nhả lock ra, rồi mới notify. Đây là quy tắc gỡ được nhiều deadlock bất ngờ nhất khỏi một codebase, vì nó gỡ đúng những cái mà không reviewer nào nhìn ra được.

Và ưu tiên những cấu trúc vốn không cần lock: ConcurrentHashMap cùng họ hàng, AtomicLong và các class Atomic* khác, cùng những value object immutable có thể chia sẻ mà không cần phối hợp gì. Một lock bạn không bao giờ lấy thì không bao giờ deadlock được.

Deadlock trong thread pool: task chờ một task khác trong cùng pool

Không phải deadlock nào cũng là chu trình lock. Một fixed-size pool có số thread cố định, và nếu tất cả thread đó đều đang block để chờ một task mà task ấy lại cần một thread mới chạy được, thì pool kẹt vĩnh viễn.

ExecutorService pool = Executors.newFixedThreadPool(2);
 
Callable<String> outer = () -> {
    System.out.println(Thread.currentThread().getName() + ": outer task started");
    Future<String> inner = pool.submit(() -> "inner done");
    return "outer got: " + inner.get();     // blocks a pool thread on a pool task
};
 
Future<String> f1 = pool.submit(outer);
Future<String> f2 = pool.submit(outer);

pool-1-thread-2: outer task started
pool-1-thread-1: outer task started
TimeoutException: both pool threads are blocked on tasks that need a pool thread to run

Hai task chiếm hai thread, cả hai submit một task con, cả hai gọi get(). Hai task con nằm trong queue phía sau những thread sẽ không bao giờ trả về. Thứ tự hai dòng đầu thay đổi giữa các lần chạy.

Bây giờ hãy lấy thread dump của nó, và chi tiết quan trọng lộ ra: jstack không báo deadlock nào cả. Trong dump có đúng không dòng Found one Java-level deadlock nào. Thứ nó cho thấy là như sau:

"pool-1-thread-1" #20 [26627] prio=5 os_prio=31 cpu=1.67ms elapsed=2.65s tid=0x00000008bf8faa00 nid=26627 waiting on condition  [0x000000016daca000]
   java.lang.Thread.State: WAITING (parking)
	at jdk.internal.misc.Unsafe.park(java.base@21.0.6/Native Method)
	- parking to wait for  <0x00000003107cbd38> (a java.util.concurrent.FutureTask)
	at java.util.concurrent.FutureTask.awaitDone(java.base@21.0.6/FutureTask.java:500)
	at java.util.concurrent.FutureTask.get(java.base@21.0.6/FutureTask.java:190)

Mọi thread của pool đều WAITING (parking) trên một FutureTask trong khi queue vẫn còn việc — đó là dấu hiệu nhận dạng. Không có chu trình lock nào để tìm cả, vì chẳng có lock nào tham gia — thứ đang bị chờ là một thread, và bộ phát hiện deadlock không mô hình hoá nguồn cung thread.

Quy tắc rất ngắn: một task không bao giờ được block để chờ công việc đã submit vào chính pool đó. Hoặc cấp cho phần việc lồng bên trong một pool riêng, hoặc ghép các bước lại mà không block. Một chuỗi ghép bằng thenCompose tránh được chuyện này vì không stage nào block để chờ stage khác, còn executor kiểu virtual-thread-per-task thì né được vì virtual thread đang block sẽ nhả carrier ra và executor đó không bị giới hạn kích thước.

Livelock: chạy hết công suất mà không đi tới đâu

Livelock là phiên bản lịch sự của deadlock. Không ai bị block. Mọi thread vẫn acquire, kiểm tra, nhả rồi thử lại — và vì tất cả cùng đưa ra một quyết định nhường nhịn tại cùng một thời điểm, không ai hoàn thành được việc gì.

Cấu trúc của nó là tryLock kèm nhả-và-thử-lại ngay lập tức. Thread thứ nhất lấy cái lock nó lấy được, không lấy được cái còn lại, bèn trả cái của mình lại để khỏi chắn đường ai, rồi thử lại. Thread thứ hai làm y hệt theo chiều ngược lại. Nếu các lần retry của chúng bị đồng bộ với nhau, cảnh đó lặp lại mãi mãi.

static final long PERIOD = TimeUnit.MILLISECONDS.toNanos(10);
 
static void spinUntil(long deadline) {
    while (System.nanoTime() < deadline) Thread.onSpinWait();
}
 
static void polite(ReentrantLock first, ReentrantLock second) {
    while (!stop) {
        long tick = ((System.nanoTime() / PERIOD) + 1) * PERIOD;  // same value in both threads
        spinUntil(tick);
        attempts.incrementAndGet();
 
        first.lock();                             // succeeds: nobody else wants this one
        try {
            spinUntil(tick + PERIOD / 4);         // by now the other thread holds its own
            boolean got = second.tryLock();       // fails: the other thread is holding it
            spinUntil(tick + PERIOD / 2);
            if (got) {
                try { completed.incrementAndGet(); } finally { second.unlock(); }
                return;
            }
        } finally {
            first.unlock();                       // "after you" - hand it back and retry
        }
    }
}

Một thread chạy polite(A, B), thread kia chạy polite(B, A). Cái tick đồng hồ là thứ làm các lần retry đồng bộ với nhau; trên production, sự đồng bộ đó đến từ một back-off cố định, một timer dùng chung, hoặc một rate limiter thả tất cả ra cùng lúc.

t=1s  attempts=200  completed=0  polite-1=RUNNABLE  polite-2=RUNNABLE
t=2s  attempts=404  completed=0  polite-1=RUNNABLE  polite-2=RUNNABLE
t=3s  attempts=604  completed=0  polite-1=RUNNABLE  polite-2=RUNNABLE
t=4s  attempts=806  completed=0  polite-1=RUNNABLE  polite-2=RUNNABLE
t=5s  attempts=1006  completed=0  polite-1=RUNNABLE  polite-2=RUNNABLE

Bốn lần chạy đều như nhau: khoảng hai trăm lần thử mỗi giây, completed đứng yên ở 0, cả hai thread RUNNABLE suốt. Số lần thử chênh nhau vài đơn vị giữa các lần chạy.

Giờ tới phần chẩn đoán, cũng là lý do khiến livelock khó chịu hơn deadlock. Thread dump của JVM đang livelock có không dòng Found one Java-level deadlock nào, và hai thread trông như sau:

"polite-1" #20 [28419] prio=5 os_prio=31 cpu=2638.25ms elapsed=2.64s tid=0x0000000c3b116a00 nid=28419 runnable  [0x000000016de2a000]
   java.lang.Thread.State: RUNNABLE
	at LivelockDemo.spinUntil(LivelockDemo.java:16)
	at LivelockDemo.polite(LivelockDemo.java:27)

RUNNABLE, và cpu=2638.25ms so với elapsed=2.64s — thread đã dành gần như toàn bộ thời gian sống của nó trên CPU. ps báo process ở mức 197% CPU cho hai thread. Những con số này thay đổi theo tải và chỉ nhằm cho thấy hình dạng của vấn đề: mọi thứ mà hệ thống monitoring nhìn vào đều nói service đang khoẻ mạnh và làm việc chăm chỉ, trong khi nó chưa hoàn thành cái gì. Không có bộ phát hiện tự động nào cho tình huống này. Bạn tìm ra nó bằng cách để ý một counter không nhúc nhích trong khi CPU cao, rồi lấy hai dump cách nhau vài giây và thấy vẫn đúng những thread đó trong đúng vòng retry đó.

Sửa livelock bằng back-off ngẫu nhiên

Livelock sống nhờ tính đối xứng, nên cách sửa là phá vỡ đối xứng. Ngẫu nhiên hoá thời điểm retry là đủ — đúng một dòng:

// randomised back-off: the two threads no longer retry on the same instant
long tick = ((System.nanoTime() / PERIOD) + 1) * PERIOD + rnd.nextLong(PERIOD);

attempts=2  completed=2
both threads finished: true

Năm lần chạy đều cho attempts=2 và completed=2: mỗi thread thành công ngay ở lần thử đầu. Vì độ lệch là ngẫu nhiên nên vẫn có thể có lần chạy mà một thread đụng độ một nhịp rồi thử lại, chuyện đó bình thường — điều quan trọng là đụng độ không còn lặp lại nữa, bởi lần retry kế tiếp rơi vào một chỗ khác.

Back-off ngẫu nhiên là câu trả lời chung cho mọi kiểu retry đối xứng: exponential back-off có jitter ở phía client, một khoảng trễ ngẫu nhiên trước khi acquire lại, hoặc đơn giản là một thành phần ngẫu nhiên riêng cho từng thread trong khoảng retry. Back-off cố định là thứ gây ra vấn đề, không phải thứ giải quyết nó.

Starvation và cái giá thật của fair mode

Starvation là kiểu hỏng thứ ba. Một thread không bao giờ lấy được lock, trong khi các thread khác lấy liên tục và cả chương trình vẫn tiến triển bình thường. Deadlock chặn tất cả, livelock giữ tất cả bận rộn rồi chặn tất cả, còn starvation chỉ chặn đúng một thread và ẩn mình trong một hệ thống trông rất khoẻ.

Nguyên nhân với ReentrantLock mặc định là barging: một thread vừa nhả lock rồi xin lại ngay có thể thắng, vì thread đang nằm trong queue phải được scheduler unpark trước đã, và việc đó lâu hơn một lần acquire lại. new ReentrantLock(true) chuyển sang fair mode, nơi lock đang rảnh được trao cho thread chờ lâu nhất.

static long[] run(boolean fair) throws InterruptedException {
    ReentrantLock lock = new ReentrantLock(fair);   // true = fair mode
    long[] counts = new long[THREADS];
    AtomicLong budget = new AtomicLong(TOTAL);
    // 32 threads share a budget of 800,000 acquisitions; count what each one got
    ...
}

Bốn lần chạy mẫu, mỗi lần 32 thread và 800.000 lượt acquire:

unfair     min=15541   max=34735   max/min=2.2   never acquired=0
fair       min=24996   max=25031   max/min=1.0   never acquired=0
 
unfair     min=5115    max=119294  max/min=23.3  never acquired=0
fair       min=24992   max=25145   max/min=1.0   never acquired=0
 
unfair     min=18289   max=34564   max/min=1.9   never acquired=0
fair       min=24989   max=25190   max/min=1.0   never acquired=0
 
unfair     min=17138   max=37791   max/min=2.2   never acquired=0
fair       min=24985   max=25180   max/min=1.0   never acquired=0

Hai quan sát trung thực. Fair mode chia đều ngân sách gần như hoàn hảo ở mọi lần chạy — đúng 25.000 mỗi thread, chênh lệch chưa tới một phần trăm. Lock mặc định thì không, và độ lệch nó tạo ra cũng khó đoán: khoảng 2 lần ở ba lần chạy và 23 lần ở một lần chạy. Và trên máy này chưa lần nào có thread bị bỏ đói hoàn toàn. Barging cho phép starvation chứ không đảm bảo starvation, và mức độ tệ tới đâu còn tuỳ số core, tải, và thời gian giữ lock. Chính vì vậy loại bug này rất khó tái hiện: lần chạy mà một thread được 5.115 lượt còn thread khác được 119.294 lượt nhìn từ ngoài giống hệt lần chạy trước đó.

Dù vậy fair mode vẫn thường là lựa chọn sai, và tài liệu JDK nói thẳng điều đó. Javadoc của ReentrantLock ghi rằng chương trình dùng fair lock "may display lower overall throughput (i.e., are slower; often much slower) than those using the default setting, but have smaller variances in times to obtain locks and guarantee lack of starvation." Cơ chế thì suy ra được mà chẳng cần đo đạc gì: fair mode cấm luôn đường nhanh. Thread vừa nhả lock không được lấy lại ngay trong lúc dữ liệu vẫn còn nóng trong cache; mỗi lần trao tay đều phải park một thread và unpark một thread khác, tức là đi một vòng qua scheduler cho từng lượt acquire.

Còn hai chi tiết nữa trước khi bạn quyết định bật nó. ReentrantLock.tryLock() — bản không có timeout — không tôn trọng thiết lập fairness; javadoc gọi thẳng đó là "barging" và bảo dùng tryLock(0, TimeUnit.SECONDS) nếu bạn muốn fairness được tôn trọng. Và fairness của lock không phải fairness của scheduler: cũng chính javadoc đó cảnh báo rằng một trong nhiều thread dùng fair lock vẫn có thể lấy được lock vài lần liên tiếp. Chỉ bật fair mode khi việc một thread bị bỏ đói là lỗi về tính đúng đắn hoặc phá SLA độ trễ, còn lại thì để mặc định.

Những quy tắc thực dụng giữ deadlock ra khỏi codebase

Hai thói quen vận hành có giá trị ngang với các quy tắc trên. Hãy đặt tên cho thread, vì pool-1-thread-3 trong dump chẳng nói lên điều gì còn payment-writer-3 thì nói hết. Và chạy một bước kiểm tra findDeadlockedThreads() theo lịch trong mọi service sống lâu, để deadlock trở thành một cái alert kèm stack trace thay vì một báo cáo rằng trang web đang chậm.

FAQ

Deadlock và livelock trong Java khác nhau ở đâu?

Trong deadlock, các thread ở trạng thái BLOCKED và không làm gì cả: state của chúng trong thread dump là BLOCKED (on object monitor), thời gian CPU ngừng tăng, và HotSpot in ra Found one Java-level deadlock. Trong livelock, các thread ở trạng thái RUNNABLE và đốt CPU: chúng vẫn acquire rồi nhả lock liên tục, nhưng mỗi lần thử lại bị thread kia phá, nên không đơn vị công việc nào hoàn thành. Dump của một livelock không báo deadlock nào cả, và đó là lý do nó khó tìm hơn. Cả hai đều cho ra cùng một triệu chứng nhìn từ bên ngoài — một request không bao giờ trả về.

Làm sao tìm deadlock trong một ứng dụng Java đang chạy?

Lấy thread dump bằng jstack <pid> hoặc jcmd <pid> Thread.print rồi đọc phần cuối: HotSpot tự phân tích wait-for graph và in ra một mục Found one Java-level deadlock nêu tên các thread, các monitor và thread nào đang giữ cái gì. Về phía code, ManagementFactory.getThreadMXBean().findDeadlockedThreads() trả về đúng thông tin đó từ bên trong JVM và trả về null khi không có gì kẹt, đây là thứ bạn muốn chạy theo lịch trên production. Nếu dump không báo gì mà thread vẫn kẹt, hãy tìm các frame WAITING (parking) — deadlock kiểu thread pool hoặc Future không bao giờ xuất hiện trong mục deadlock.

Dùng ReentrantLock thay cho synchronized có tránh được deadlock không?

Tự nó thì không. Hai object ReentrantLock lấy theo thứ tự ngược nhau vẫn deadlock y hệt hai monitor, và jstack báo nó dưới dạng waiting for ownable synchronizer ... which is held by. Thứ ReentrantLock cho thêm là một lối thoát: tryLock(timeout, unit) trả về false thay vì chờ mãi, và lockInterruptibly() cho phép một thread khác cắt đứt lần chờ đó. Nhờ vậy bạn có cách tấn công điều kiện no preemption, thứ mà synchronized đơn giản là không cho. Việc phòng tránh vẫn nằm ở cách bạn dùng nó.

Vì sao lock ordering theo System.identityHashCode lại cần thêm một lock tie-break?

Vì System.identityHashCode trả về int và hai object khác nhau vẫn có thể trùng giá trị. Khi trùng, cả nhánh nhỏ hơn lẫn nhánh lớn hơn đều false, nên nếu không có nhánh thứ ba thì mỗi caller quay về đúng thứ tự argument của nó — tái tạo lại đúng cái bug mà ordering sinh ra để dẹp. Trong thử nghiệm ở trên, một va chạm xuất hiện sau khoảng 105.000 object trên một JVM vừa khởi động, nên đây không phải nỗi lo lý thuyết với service có tập object sống lớn. TIE_BREAK là một static object duy nhất mà mọi thread đều lấy trước trong trường hợp va chạm, và nó khôi phục lại thứ tự toàn phần.

Thread pool có deadlock được không khi code của tôi không có lock nào?

Có, và đây là một trong những ca treo phổ biến nhất trên production. Một fixed-size pool có số thread cố định; nếu một task block để chờ kết quả của một task khác đã submit vào chính pool đó, thì thread ấy không còn rảnh để chạy đúng task nó đang chờ. Với hai thread và hai task kiểu đó, pool kẹt vĩnh viễn. Không có monitor nào tham gia nên jstack không in mục deadlock nào — dấu hiệu nhận dạng là mọi thread của pool đều ở WAITING (parking) trên một FutureTask trong khi queue vẫn còn việc. Hãy dùng pool riêng cho phần việc lồng bên trong, hoặc ghép các bước lại mà không block thread của pool.

Có nên dùng fair ReentrantLock để tránh starvation không?

Thường là không. Fair mode bỏ mất đường nhanh của barging, nên mỗi lần trao tay đều phải park một thread và unpark một thread khác thay vì để thread vừa nhả lấy lại cái lock vẫn còn nóng trong cache; chính javadoc của JDK nói fair lock "often much slower". Trong phép đo ở trên, fair mode chia 800.000 lượt acquire gần như đều tuyệt đối cho 32 thread, còn lock mặc định tạo ra độ lệch từ khoảng 2 lần tới 23 lần — nhưng chưa lần nào có thread bị bỏ đói hoàn toàn. Chỉ dùng fairness khi một thread bị bỏ đói là lỗi về tính đúng đắn hoặc phá SLA độ trễ, và nhớ rằng tryLock() không timeout bỏ qua hoàn toàn thiết lập fairness.

Deadlock có tự phục hồi được không, hay tôi có thể kill riêng những thread bị kẹt?

Không, và cũng không. Deadlock là vĩnh viễn theo đúng định nghĩa: mọi thread trong chu trình đang chờ một resource chỉ được nhả bởi một thread khác cũng trong chu trình đó. synchronized không có timeout, và Thread.interrupt() không phá được một thread đang block ở cửa monitor — nó chỉ set cờ, và thread sẽ thấy cờ đó khi lấy được cái lock mà nó không bao giờ lấy được. Thread.stop đã throw UnsupportedOperationException từ Java 20 — trên OpenJDK 21.0.6 nó compile được kèm cảnh báo removal rồi throw lúc runtime — mà nếu còn dùng được thì nó cũng làm hỏng state đang được bảo vệ. Phục hồi nghĩa là restart process; còn cách sửa thì nằm ở thiết kế.

Kết luận

Deadlock là bug concurrency duy nhất có một lý thuyết hoàn chỉnh đứng sau. Bốn điều kiện phải cùng đúng, nên có đúng bốn nhóm cách sửa, và mọi kỹ thuật trong bài này đều là một trong bốn nhóm đó áp lên code thật: thứ tự toàn cục dựa trên identityHashCode để phá circular wait, tryLock với vòng retry có giới hạn để phá no preemption, critical section ngắn hơn để phá hold and wait, và dữ liệu immutable hoặc concurrent collection để xoá hẳn mutual exclusion. Hãy chọn ordering trước tiên — nó không có đường retry nào để làm sai.

Phần chẩn đoán quan trọng ngang phần phòng tránh. Một thread BLOCKED có thời gian CPU ngừng tăng trong khi elapsed vẫn lớn dần là deadlock, và HotSpot sẽ gọi tên nó cho bạn ở cuối thread dump. Một thread RUNNABLE đốt trọn một core trong khi counter đứng yên ở 0 là livelock, và sẽ chẳng có ai gọi tên nó hộ bạn. Một thread đơn giản là không bao giờ được xếp lịch trong khi hệ thống vẫn bận là starvation, thứ mà new ReentrantLock(true) sửa được với một cái giá có thật và thường là không cần thiết. Học cách phân biệt ba thứ đó trong một dump là bạn đã qua được phần lớn một đêm trực sự cố tồi tệ.

Đó là hết Part 4 của khoá này. Part 5 chuyển sang Java I/O nâng cao, bắt đầu từ buffered stream và object serialization.