Mini-challenge — săn race và deadlock

TL;DR: Bạn nhận một mini "ngân hàng" đa luồng có hai bug cùng lúc: một race condition ở bộ đếm số giao dịch (transferCount++ không nguyên tử — bài 01), và một deadlock ở hàm chuyển tiền (hai luồng khoá hai tài khoản theo thứ tự ngược nhau — bài 03). Nhiệm vụ: chạy để thấy cả hai triệu chứng (con số đếm sai và chương trình treo), chỉ ra đúng interleaving gây mỗi lỗi, rồi sửa bằng đúng công cụ — atomic cho bộ đếm, lock ordering cho deadlock. Đây là bài tổng hợp cả module: bạn phải nhận diện loại lỗi trước khi chọn cách trị.

🎯 Đề bài

Một hệ thanh toán nhỏ quản lý các tài khoản và cho nhiều luồng chuyển tiền song song. Nó cũng đếm tổng số giao dịch đã thực hiện để báo cáo. Code chạy được nhưng có hai bug đồng thời:

1. Bộ đếm sai: sau khi chạy, transferCount báo ít hơn số giao dịch thật.
2. Treo: thỉnh thoảng (hoặc thường xuyên) chương trình đứng im, không in kết quả, CPU về 0%.

Nhiệm vụ của bạn:

1. Chạy chương trình, quan sát cả hai triệu chứng.
2. Chỉ ra đâu là race, đâu là deadlock — và đúng interleaving gây ra mỗi cái.
3. Sửa cả hai bằng đúng công cụ đã học, giữ hành vi nghiệp vụ (tổng tiền toàn hệ thống không đổi).
4. Chạy lại, xác nhận bộ đếm đúng và chương trình không còn treo.

🔍 Phân tích I-P-O

Điều kiện đúng (invariant):

• Bảo toàn tiền: tổng số dư mọi tài khoản sau khi chạy = tổng ban đầu (không tạo/mất tiền).
• Đếm đúng: transferCount = tổng số lần transfer được gọi thành công.
• Không treo: chương trình luôn kết thúc, in kết quả.

📦 Concept mapping

Bài này gọi lại trực tiếp cả ba bài concept của module:

Điểm mấu chốt: hai bug cần hai cách trị khác nhau. Đừng dùng một synchronized to đùng bọc tất cả — vừa giết hiệu năng vừa không dạy bạn phân biệt. Bộ đếm là thao tác đơn trên một biến → atomic. Chuyển tiền là chuỗi nhiều biến + lồng khoá → mutex + lock ordering.

▶️ Starter code (có bug)

import java.util.concurrent.ThreadLocalRandom;

public class BuggyBank {

    static class Account {
        final int id;
        long balance;
        final Object lock = new Object();
        Account(int id, long balance) { this.id = id; this.balance = balance; }
    }

    static Account[] accounts;
    static long transferCount = 0;          // BUG 1: shared, khong bao ve
    static long[] callCounts;               // dem that: moi luong ghi 1 o rieng -> khong race

    // BUG 2: khoa 'from' truoc roi 'to' -> hai huong nguoc nhau = deadlock
    static void transfer(Account from, Account to, long amount) {
        synchronized (from.lock) {
            synchronized (to.lock) {
                if (from.balance >= amount) {
                    from.balance -= amount;
                    to.balance   += amount;
                }
            }
        }
        transferCount++;                    // BUG 1: race o day
    }

    public static void main(String[] args) throws InterruptedException {
        int N = 4;
        accounts = new Account[N];
        for (int i = 0; i < N; i++) accounts[i] = new Account(i, 1000);
        long expectedTotal = N * 1000L;

        int THREADS = 8, PER_THREAD = 100_000;
        callCounts = new long[THREADS];
        Thread[] ts = new Thread[THREADS];
        for (int t = 0; t < THREADS; t++) {
            final int tid = t;
            ts[t] = new Thread(() -> {
                long local = 0;                 // dem cuc bo -> khong chia se, khong race
                for (int i = 0; i < PER_THREAD; i++) {
                    int a = ThreadLocalRandom.current().nextInt(N);
                    int b = ThreadLocalRandom.current().nextInt(N);
                    if (a != b) { transfer(accounts[a], accounts[b], 1); local++; }
                }
                callCounts[tid] = local;        // moi luong ghi o RIENG cua no -> an toan
            });
        }
        for (Thread t : ts) t.start();
        for (Thread t : ts) t.join();

        long total = 0, actualCalls = 0;
        for (Account a : accounts) total += a.balance;
        for (long c : callCounts) actualCalls += c;   // dem that (khong race)
        System.out.println("Total balance: " + total + " (expected " + expectedTotal + ")");
        System.out.println("transferCount: " + transferCount + " (thuc su goi transfer " + actualCalls + " lan)");
    }
}

Chạy và quan sát. Nếu chương trình treo (thường xảy ra vì 8 luồng chuyển ngẫu nhiên giữa 4 tài khoản rất dễ tạo hai hướng khoá ngược nhau), lấy thread dump để xác nhận:

jps                      # tim pid cua BuggyBank
jstack <pid> | head -30  # doc "Found one Java-level deadlock"

Nếu may mắn không treo, bạn sẽ thấy Total balance: 4000 (đúng — vì transfer được khoá). Nhưng để ý số lời gọi transfer không phải 800.000: với 4 tài khoản, khoảng 25% vòng lặp trúng a == b và bị bỏ qua, nên kỳ vọng chỉ khoảng 600.000 lời gọi (75% × 800.000) kể cả khi không có bug nào. Đó là lý do ta thêm mảng callCounts — mỗi luồng cộng dồn số lời gọi vào ô riêng của nó (không chia sẻ nên không race), rồi main cộng lại thành actualCalls: đây là con số đúng để đối chiếu.

Bằng chứng race nằm ở chỗ transferCount in ra nhỏ hơn actualCalls — mỗi lần hai luồng cùng chạy transferCount++ trên một giá trị cũ, một lần đếm bị nuốt (lost update, bài 01). So transferCount với 800000 là sai lầm: 800000 không phải số lời gọi thực; phải so với actualCalls.

💡 Gợi ý

Gợi ý 1 — Tách hai bug, đừng gộp. Có hai lỗi độc lập. Sửa riêng từng cái bằng đúng công cụ; đừng bọc một khoá khổng lồ quanh cả transfer lẫn transferCount.

Gợi ý 2 — Bộ đếm là thao tác đơn một biến. transferCount++ là read-modify-write trên một biến. Công cụ nhẹ nhất đủ việc là gì? (Bài 02: không cần mutex cho một biến — dùng atomic.)

Gợi ý 3 — Deadlock đến từ thứ tự khoá ngược nhau. transfer(A, B) khoá A rồi B; transfer(B, A) khoá B rồi A. Phá điều kiện nào trong 4 điều kiện Coffman là rẻ nhất? (Bài 03: circular wait — bằng lock ordering.) Bạn có sẵn account.id để làm thứ tự toàn cục.

Gợi ý 4 — Giữ invariant. Sau khi sửa, tổng số dư vẫn phải là 4000. Việc trừ nguồn và cộng đích vẫn phải nằm trong cùng một khối được cả hai khoá bảo vệ — chỉ đổi thứ tự lấy khoá, không đổi phạm vi khoá.

✅ Lời giải

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.atomic.AtomicLong;

public class FixedBank {

    static class Account {
        final int id;
        long balance;
        final Object lock = new Object();
        Account(int id, long balance) { this.id = id; this.balance = balance; }
    }

    static Account[] accounts;
    static final AtomicLong transferCount = new AtomicLong(0);   // FIX 1: atomic
    static long[] callCounts;               // dem that (khong race) de doi chieu

    static void transfer(Account from, Account to, long amount) {
        // FIX 2: lock ordering theo id -> luon khoa id nho truoc -> khong circular wait
        Account first  = from.id < to.id ? from : to;
        Account second = from.id < to.id ? to : from;
        synchronized (first.lock) {
            synchronized (second.lock) {
                if (from.balance >= amount) {
                    from.balance -= amount;
                    to.balance   += amount;
                }
            }
        }
        transferCount.incrementAndGet();     // FIX 1: nguyen tu, khong mat update
    }

    public static void main(String[] args) throws InterruptedException {
        int N = 4;
        accounts = new Account[N];
        for (int i = 0; i < N; i++) accounts[i] = new Account(i, 1000);
        long expectedTotal = N * 1000L;

        int THREADS = 8, PER_THREAD = 100_000;
        callCounts = new long[THREADS];
        Thread[] ts = new Thread[THREADS];
        for (int t = 0; t < THREADS; t++) {
            final int tid = t;
            ts[t] = new Thread(() -> {
                long local = 0;
                for (int i = 0; i < PER_THREAD; i++) {
                    int a = ThreadLocalRandom.current().nextInt(N);
                    int b = ThreadLocalRandom.current().nextInt(N);
                    if (a != b) { transfer(accounts[a], accounts[b], 1); local++; }
                }
                callCounts[tid] = local;
            });
        }
        for (Thread t : ts) t.start();
        for (Thread t : ts) t.join();

        long total = 0, actualCalls = 0;
        for (Account a : accounts) total += a.balance;
        for (long c : callCounts) actualCalls += c;
        System.out.println("Total balance: " + total + " (expected " + expectedTotal + ")");
        System.out.println("transferCount: " + transferCount.get() + " (thuc su goi transfer " + actualCalls + " lan)");
    }
}

Chạy FixedBank: Total balance: 4000 mọi lần, transferCount giờ khớp đúng actualCalls (số lần transfer thực sự chạy — khoảng 600.000, số cặp a != b), không còn lost update, và chương trình không bao giờ treo.

Vì sao mỗi fix đúng

Fix 1 — bộ đếm. transferCount++ là read-modify-write ba bước load/add/store (bài 01), nên hai luồng có thể cùng đọc giá trị cũ và ghi đè — lost update. AtomicLong.incrementAndGet() gói việc tăng vào một vòng lặp CAS nguyên tử (bài 02): không luồng nào chen được vào giữa, không mất update. Đây là thao tác đơn trên một biến nên atomic là công cụ nhẹ nhất đủ việc — không cần mutex.

Fix 2 — deadlock. Bug gốc: transfer khoá from trước to, nên transfer(A,B) và transfer(B,A) chạy song song tạo hai thứ tự khoá ngược nhau → circular wait → deadlock (bài 03). Fix áp lock ordering: sắp hai tài khoản theo id và luôn khoá id nhỏ trước, bất kể ai là nguồn/đích. Giờ mọi lời gọi đều khoá cùng một tài khoản trước → không thể có vòng kín → deadlock bị loại về mặt cấu trúc. Chú ý phạm vi khoá không đổi (vẫn giữ cả hai khoá suốt lúc trừ/cộng để bảo toàn tiền); chỉ thứ tự lấy khoá đổi.

🎓 Mở rộng

Ép deadlock lộ ra để chắc chắn đã bắt đúng

Nếu bản buggy không treo ngay trên máy bạn (timing may), ép nó lộ bằng cách chèn khe thời gian giữa hai lần khoá — đúng thủ thuật ở bài 03:

synchronized (from.lock) {
    try { Thread.sleep(1); } catch (InterruptedException e) {}  // mo rong khe
    synchronized (to.lock) { /* ... */ }
}

Với khe này, gần như chắc chắn treo trong vài lần chạy. Đây là kỹ thuật "khuếch đại" bug timing-dependent để xác nhận chẩn đoán trước khi sửa.

Nếu không có thứ tự toàn cục thì sao?

Ở đây account.id cho sẵn một thứ tự tự nhiên. Khi khoá đến từ nhiều nguồn không so sánh được, dùng tryLock(timeout) (bài 03) để phá no-preemption thay cho lock ordering — nhớ thêm backoff ngẫu nhiên để tránh livelock.

Kiểm tra kỹ hơn: có còn race ẩn nào không?

Sau fix, thử nghĩ: phần if (from.balance >= amount) và from.balance -= amount có an toàn không? Có — vì cả khối nằm trong hai khoá bảo vệ đúng hai tài khoản đang đụng tới. Nhưng nếu bạn quên khoá một trong hai (ví dụ chỉ khoá from), thì to.balance += amount lại thành race. Bài học: khoá phải phủ đúng mọi biến chia sẻ mà critical section chạm tới.

✨ Điều bạn vừa làm được

Bạn vừa chẩn đoán và sửa một chương trình có hai loại bug concurrency cùng lúc — kỹ năng thực chiến quan trọng nhất của module. Nhìn lại những gì bạn đã kết nối:

• Phân loại trước khi sửa: nhận ra bộ đếm là race (thao tác đơn) còn chuyển tiền là deadlock (lồng khoá) — hai lỗi khác loại, hai cách trị.
• Chọn công cụ nhẹ nhất đủ việc: atomic cho một biến, mutex + lock ordering cho chuỗi nhiều biến — không bọc một khoá khổng lồ.
• Đọc thread dump: dùng jstack xác nhận deadlock thay vì đoán.
• Giữ invariant: sửa bug mà không phá bảo toàn tiền — đổi thứ tự khoá, không đổi phạm vi khoá.
• Khuếch đại bug timing-dependent: chèn sleep để ép race/deadlock lộ ra khi cần xác nhận.

Kỹ năng này — nhận đúng loại lỗi concurrency và trị bằng đúng công cụ — là thứ phân biệt người hiểu cơ chế với người chỉ rải synchronized cho tới khi hết crash.

Bài tiếp theo: Tổng kết module — Đồng bộ & Phối hợp