Atomic & CAS: đồng bộ lock-free cho thao tác trên một biến

TL;DR: Với thao tác trên đúng một biến, không cần khóa. Compare-and-swap (CAS) — lệnh nguyên tử của CPU — cho phép cập nhật lạc quan theo vòng lặp đọc-tính-thử: thất bại thì đọc lại và làm lại, không thread nào block. Các lớp Atomic* đóng gói vòng lặp đó; AtomicReference ghép với immutable holder để cập nhật nguyên tử cả cụm trường với nhiều writer. Hai góc khuất phải thuộc: ABA (CAS so giá trị, không so lịch sử — cần stamp) và lambda trong updateAndGet phải thuần vì có thể chạy lại nhiều lần. Ranh giới cứng: CAS không gói được invariant trải trên nhiều biến — lúc đó quay về khóa (đường contention nặng và VarHandle để bài kế).

1. Vì sao tăng một bộ đếm lại phải khóa cả object?

Bài trước, để sold của BookingService tăng đúng, ta quây nguyên cả object sau một intrinsic lock: mỗi khách đặt vé thì mọi khách khác xếp hàng, dù việc cần làm chỉ là cộng một vào bộ đếm. Gốc rễ nằm ở bài Atomicity: sold++ là read-modify-write ba bước, hai thread chen vào giữa có thể cùng đọc 9, cùng ghi 10, bốc hơi một lần tăng. volatile chỉ lo visibility, không gói ba bước thành một khối. Còn synchronized là hàng rào loại trừ sinh ra cho cả cụm thao tác phức tạp, nay bị bắt đi canh một biến.

Luận điểm của bài: với thao tác trên đúng một biến, ta đạt atomicity mà không cần khóa. Cơ sở là compare-and-swap (CAS), chỉ thị phần cứng mà mọi CPU hiện đại đều có. CAS nhận ba đối số — vị trí bộ nhớ, giá trị kỳ vọng, giá trị mới — và nguyên tử trong một nhịp: nếu giá trị ở đó còn bằng kỳ vọng thì ghi giá trị mới rồi báo thành công, ngược lại báo thất bại.

Điểm cốt lõi là cách dùng nó. Khóa bi quan: giả định sẽ có xung đột nên chặn trước rồi mới làm. CAS lạc quan: đọc giá trị hiện tại, tính giá trị mới, rồi ghi với điều kiện chưa ai đổi từ lúc ta đọc — thành công thì cả quãng đọc-tính-ghi không ai chen vào, thất bại thì vứt kết quả và thử lại. Nói cho chính xác: một cập nhật lock-free là một vòng lặp quanh chỉ thị CAS, không phải một lệnh duy nhất.

int oldValue, newValue;
do {
    oldValue = readCurrent();        // doc gia tri hien tai
    newValue = oldValue + 1;         // tinh gia tri moi dua tren no
} while (!compareAndSet(oldValue, newValue));  // chi ghi neu chua ai doi; that bai thi lap lai

Một analogy: cuốn sổ ghi chung chỗ đông người. Cách "khóa" là ai muốn viết phải cầm cây bút duy nhất; cách "CAS" là ai cũng có bút riêng, nhưng chỉ được viết nếu dòng cuối vẫn như lúc mình đọc.

Đặc tính ấy quyết định khi nào CAS thắng: contention thấp thì phần lớn lần thử thành công ngay, không block, không context switch; contention cao thì các vòng retry quay không tải, đốt CPU. Khóa biến tranh chấp thành chờ đợi (thread ngủ), CAS biến nó thành làm lại (thread bận) — điểm yếu này đẻ ra LongAdder, chủ đề bài kế tiếp.

Trên JVM, CAS phơi ra qua các method nội tại mà JIT dịch thẳng thành chỉ thị phần cứng: x86 là lock cmpxchg, ARM là cặp load-linked/store-conditional. Một chú thích cho chính xác: với phép cộng dồn trên x86-64, getAndAdd được intrinsify thành lock xadd — fetch-and-add, cộng và trả giá trị cũ trong một lệnh, không cần retry. CAS-loop là đường fallback khi không có lệnh chuyên dụng.

2. Các lớp Atomic*

java.util.concurrent.atomic gói CAS và vòng lặp retry vào những lớp dễ dùng — AtomicInteger, AtomicLong, AtomicBoolean, AtomicReference — mỗi lớp bọc một giá trị duy nhất. Đây là lời giải lock-free cho bộ đếm vé của TicketFlow, biến thể của bước v1 trong capstone.

public class SeatCounter {
    private final AtomicInteger sold = new AtomicInteger(0);

    public int reserve()   { return sold.incrementAndGet(); }   // khong khoa, van nguyen tu
    public int soldCount() { return sold.get(); }               // reader khong can khoa
}

incrementAndGet là getAndIncrement đảo chiều trả về — cả hai nguyên tử, ngữ nghĩa đúng vòng lặp CAS ở mục trên, chỉ là JDK viết hộ (trên x86 chúng intrinsify thành một lệnh lock xadd). So với bản Monitor Pattern, hai khách đặt vé không còn ngủ chờ nhau mà cùng thử CAS.

Bộ method chia ba nhóm. Cộng dồn — getAndIncrement, getAndAdd, addAndGet — cho số nguyên. CAS trần — compareAndSet(expected, new) — trả boolean đúng như chỉ thị phần cứng, là viên gạch để tự xây cập nhật phức tạp hơn. Cập nhật theo hàm — updateAndGet, accumulateAndGet, getAndUpdate — nhận lambda "giá trị mới tính từ giá trị cũ thế nào" rồi tự chạy vòng retry:

private final AtomicInteger sold = new AtomicInteger(0);

// chi giu cho neu chua het ve — compound action van nguyen tu nho retry quanh lambda
public boolean reserveIfAvailable() {
    int prev = sold.getAndUpdate(cur -> cur < capacity ? cur + 1 : cur);
    return prev < capacity;   // prev < capacity nghia la lan nay ta gianh duoc mot cho
}

Cảnh báo gắn liền với nhóm cuối là hệ quả của vòng lặp retry: hàm bạn truyền vào có thể bị gọi nhiều lần khi có contention, vì mỗi lần CAS thất bại nó chạy lại trên giá trị mới. Hàm đó phải thuần — không side effect. Một lambda tưởng vô hại như "cộng một và đồng thời tăng một metric" sẽ tăng metric nhiều hơn số cập nhật thật, và bẫy này không lộ trong test đơn luồng.

AtomicReference mở cơ chế đó cho một tham chiếu object thay vì một số — cầu nối tới bài Immutability: gói nhiều trường vào một holder immutable rồi đặt holder sau một AtomicReference, ta cập nhật nguyên tử cả cụm trường bằng CAS.

public record Availability(int sold, int capacity) {
    Availability soldOne() { return new Availability(sold + 1, capacity); }
}
private final AtomicReference<Availability> state = new AtomicReference<>(new Availability(0, 100));

public boolean reserve() {
    Availability prev, next;
    do {
        prev = state.get();
        if (prev.sold() >= prev.capacity()) return false;   // het ve, khong retry vo ich
        next = prev.soldOne();
    } while (!state.compareAndSet(prev, next));   // ai chen vao thi prev cu → CAS truot → lap lai
    return true;
}

Đây là chỗ atomic vượt qua volatile của bài trước: bản volatile chỉ đúng khi một writer, còn bản AtomicReference đúng với nhiều writer, vì CAS lọc ra đúng một người thắng mỗi vòng. Giới hạn vẫn còn: ta cập nhật nguyên tử một tham chiếu duy nhất. Nếu invariant trải trên hai AtomicReference phải đổi cùng lúc, CAS từng cái một không gói được cả hai vào một thao tác, và ta lại phải về với khóa — ranh giới đó là chủ đề kết bài.

3. ABA problem

CAS hỏi đúng một câu: "giá trị hiện tại có còn bằng giá trị tôi kỳ vọng không?" Lớp lỗi tinh vi nằm ở chỗ nó chỉ so giá trị chứ không so lịch sử. Nếu một biến đi từ A sang B rồi quay lại A trong lúc ta đang tính toán, CAS vẫn thấy A và vẫn thành công — dù thế giới đã thay đổi rồi trở lại. Đây là ABA problem.

Với bộ đếm số nguyên thuần, ABA vô hại: giá trị quay lại đúng số cũ thì phép cộng vẫn đúng. ABA chỉ thành lỗi khi giá trị mang ý nghĩa về danh tính hoặc cấu trúc — kinh điển nhất là CAS trên tham chiếu node trong cấu trúc lock-free như ngăn xếp. Một thread đọc node đỉnh A, định CAS đỉnh sang node kế; xen giữa, thread khác pop A, pop cả node kế, rồi push lại A. CAS của thread đầu thấy đỉnh vẫn là A nên thành công, nhưng "node kế của A" đã bị gỡ khỏi stack — cấu trúc hỏng âm thầm.

Lời giải là gắn vào mỗi giá trị một dấu hiệu đổi-mỗi-lần-ghi. AtomicStampedReference ghép tham chiếu với một con tem số nguyên — stamp — tăng mỗi lần cập nhật; CAS chỉ thành công khi cả tham chiếu lẫn stamp đều khớp, nên chuyến đi A→B→A bị lộ ngay vì stamp đã nhảy.

// stamp tang moi lan ghi → chuyen di A→B→A bi phat hien vi stamp khong con khop
AtomicStampedReference<Node> top = new AtomicStampedReference<>(initial, 0);

int[] stampHolder = new int[1];
Node cur = top.get(stampHolder);   // doc kem stamp hien tai
top.compareAndSet(cur, cur.next, stampHolder[0], stampHolder[0] + 1);   // khop ca ref lan stamp

AtomicMarkableReference là biến thể gọn hơn: thay con tem đếm bằng một bit boolean — cờ "đã bị đánh dấu" — cho thuật toán chỉ cần biết node đã bị logic xóa chưa. Cả hai đắt hơn CAS trần vì phải đóng gói cặp tham-chiếu-và-dấu, nên chỉ rút ra khi ABA thật sự là rủi ro (khi ta tự xây cấu trúc lock-free), chứ không rải mặc định lên mọi AtomicReference.

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

• Bài 04 — Atomicity: định nghĩa read-modify-write và sold++ ba bước — bài toán CAS giải bằng đường lock-free.
• Bài 07 — Immutability: immutable holder là nửa kia của mẫu AtomicReference + CAS — holder lo nhất quán, CAS lo nhiều writer.
• Bài 08 — volatile & synchronized: JVM dùng đúng lệnh CAS này cho thin lock; xem lại mục mark word để thấy CAS ở cả hai tầng.
• Bài 10b — LongAdder & VarHandle: điểm yếu retry-quay-không-tải của CAS dưới contention cao dẫn tới striped counter; VarHandle áp CAS thẳng lên field sẵn có.
• Bài 11 — ReentrantLock và Condition: khi invariant trải trên nhiều biến, CAS bó tay và explicit lock là bước kế tiếp.

5. 📚 Deep Dive Oracle

6. Tóm tắt

• Thao tác trên đúng một biến không cần khóa: CAS cho cập nhật lạc quan — đọc, tính, ghi có điều kiện, trượt thì thử lại. Cập nhật lock-free là vòng lặp quanh chỉ thị CAS (riêng getAndAdd trên x86-64 thành lock xadd, một lệnh).
• Các lớp Atomic* đóng gói vòng lặp đó; AtomicReference ghép holder immutable cho phép cập nhật nguyên tử cả cụm trường với nhiều writer. Lambda của updateAndGet phải thuần, vì nó chạy lại mỗi lần CAS trượt.
• ABA: CAS so giá trị chứ không so lịch sử — dùng AtomicStampedReference hay AtomicMarkableReference khi danh tính quan trọng.
• Contention cao và cách né (LongAdder), cùng VarHandle cho CAS thẳng trên field, ở bài kế tiếp.

Ranh giới cứng, đúng chỗ để sang bài sau: CAS chỉ nguyên tử trên một biến. Khi invariant trải trên nhiều biến phải đổi cùng lúc, ta buộc quay về khóa. Mà synchronized thiếu nhiều thứ hệ thống thật cần: không thử-rồi-thôi, không timeout, không hủy giữa chừng, không tách đọc khỏi ghi — đó là bài explicit locks.

7. Tự kiểm tra

Bài tiếp theo: LongAdder & VarHandle — đếm dưới contention cao và CAS trên field sẵn có