⚛️ Atomics — Lock-free Programming Basics

std::atomic cho phép thực hiện operations không thể bị ngắt giữa chừng — nền tảng của lock-free programming.

---

Atomic là gì?

Analogy: Nuốt thuốc nguyên viên

┌─────────────────────────────────────────────────────────────────┐
│                    ATOMIC OPERATION                              │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  NON-ATOMIC (counter++):                                        │
│  ─────────────────────────                                      │
│  ┌─────────┐   ┌─────────┐   ┌─────────┐                       │
│  │  READ   │ → │ MODIFY  │ → │  WRITE  │                       │
│  └─────────┘   └─────────┘   └─────────┘                       │
│       ↑             ↑             ↑                             │
│       └─────────────┴─────────────┘                             │
│            ⚠️ Có thể bị interrupt!                              │
│                                                                 │
│  ATOMIC (atomic_counter++):                                     │
│  ───────────────────────────                                    │
│  ┌─────────────────────────────────────┐                       │
│  │     READ + MODIFY + WRITE           │  ← INDIVISIBLE!       │
│  │         (một operation)             │                        │
│  └─────────────────────────────────────┘                       │
│                                                                 │
│  💊 Như nuốt thuốc nguyên viên — không thể nhai giữa chừng!     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Atomic operation = Operation mà không thread nào khác có thể thấy ở trạng thái "đang làm dở".

---

std::atomic Basics

Từ Race Condition đến Thread-safe

#include <iostream>
#include <thread>
#include <atomic>

// ❌ RACE CONDITION
int counter = 0;  

// ✅ THREAD-SAFE
std::atomic<int> atomicCounter{0};

void increment() {
    for (int i = 0; i < 100000; ++i) {
        // counter++;           // ❌ Not atomic
        atomicCounter++;        // ✅ Atomic increment
    }
}

int main() {
    std::thread t1(increment);
    std::thread t2(increment);
    
    t1.join();
    t2.join();
    
    std::cout << "Counter: " << atomicCounter << std::endl;  // ✅ Always 200000
    return 0;
}

Supported Types

// Integral types
std::atomic<int> atomicInt;
std::atomic<long> atomicLong;
std::atomic<unsigned int> atomicUint;

// Pointers
std::atomic<int*> atomicPtr;

// Bool
std::atomic<bool> atomicBool;

// Custom types (must be trivially copyable)
struct Point { int x, y; };
std::atomic<Point> atomicPoint;  // OK if sizeof(Point) ≤ CPU word size

📌 Lock-free Check

std::atomic<int> a;
if (a.is_lock_free()) {
    std::cout << "True lock-free on this platform\n";
}

Một số atomic types có thể không phải lock-free trên hardware cũ — chúng sẽ dùng mutex internally.

---

Core Operations

load() và store()

#include <atomic>
#include <iostream>

std::atomic<int> value{42};

int main() {
    // store() — atomic write
    value.store(100);
    
    // load() — atomic read
    int v = value.load();
    std::cout << v << std::endl;  // 100
    
    // Operator overloads (same as load/store)
    value = 200;     // Same as value.store(200)
    int w = value;   // Same as value.load()
    
    return 0;
}

exchange()

Atomically swap giá trị, trả về giá trị cũ:

std::atomic<int> flag{0};

int main() {
    int old = flag.exchange(1);  // Set to 1, return old value
    std::cout << "Old: " << old << ", New: " << flag << std::endl;
    // Output: Old: 0, New: 1
    
    return 0;
}

Arithmetic Operations

std::atomic<int> counter{10};

counter++;          // Atomic increment (returns void)
counter--;          // Atomic decrement
counter += 5;       // Atomic addition
counter -= 3;       // Atomic subtraction

// fetch_* variants return OLD value
int old = counter.fetch_add(10);  // old = current, then add 10
int old2 = counter.fetch_sub(5);  // old2 = current, then subtract 5

---

Compare-and-Swap (CAS)

CAS là building block fundamental của lock-free algorithms:

bool compare_exchange_strong(T& expected, T desired);
bool compare_exchange_weak(T& expected, T desired);

Logic

┌─────────────────────────────────────────────────────────────────┐
│                 COMPARE-AND-SWAP (CAS)                           │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  compare_exchange_strong(expected, desired):                    │
│                                                                 │
│  if (atomic_value == expected) {                                │
│      atomic_value = desired;  // Swap!                          │
│      return true;                                               │
│  } else {                                                       │
│      expected = atomic_value;  // Update expected               │
│      return false;                                              │
│  }                                                              │
│                                                                 │
│  ⚡ Tất cả điều này xảy ra ATOMICALLY!                          │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Lock-free Increment Example

#include <atomic>
#include <iostream>

std::atomic<int> counter{0};

void lockFreeIncrement() {
    int expected = counter.load();
    
    // Keep trying until CAS succeeds
    while (!counter.compare_exchange_weak(expected, expected + 1)) {
        // If failed, 'expected' is updated to current value
        // Loop retries with new expected value
    }
}

int main() {
    // Equivalent to counter++, but explicit CAS
    lockFreeIncrement();
    std::cout << counter << std::endl;  // 1
    return 0;
}

weak vs strong

Version	Spurious Failure	Use Case
compare_exchange_weak	Có thể fail dù value == expected	Trong loop (performance)
compare_exchange_strong	Không spurious failure	Single attempt

// Dùng weak trong loop (faster on some platforms)
while (!counter.compare_exchange_weak(expected, expected + 1)) {
    // retry
}

// Dùng strong cho single check
if (flag.compare_exchange_strong(expected, newValue)) {
    // Success!
}

---

std::atomic_flag — Simplest Atomic

std::atomic_flag là guaranteed lock-free atomic type:

#include <atomic>
#include <thread>
#include <iostream>

std::atomic_flag lock = ATOMIC_FLAG_INIT;  // Must initialize!

void criticalSection(int id) {
    // Spinlock implementation
    while (lock.test_and_set(std::memory_order_acquire)) {
        // Spin until we get the lock
    }
    
    // Critical section
    std::cout << "Thread " << id << " in critical section\n";
    
    lock.clear(std::memory_order_release);  // Release lock
}

int main() {
    std::thread t1(criticalSection, 1);
    std::thread t2(criticalSection, 2);
    
    t1.join();
    t2.join();
    
    return 0;
}

⚠️ Spinlock Caveats

Spinlock burns CPU trong khi chờ. Chỉ dùng cho rất ngắn critical sections!

---

Memory Ordering (Simplified)

Default: Sequential Consistency

// Default memory order — safest, slowest
std::atomic<int> a{0};
a.store(1);  // Implicitly: std::memory_order_seq_cst
int v = a.load();

Common Memory Orders

┌─────────────────────────────────────────────────────────────────┐
│                    MEMORY ORDERS                                 │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  memory_order_seq_cst (default)                                 │
│  ───────────────────────────────                                │
│  • Total ordering across all threads                            │
│  • Safest, most intuitive                                       │
│  • May have performance cost                                    │
│                                                                 │
│  memory_order_acquire / memory_order_release                    │
│  ───────────────────────────────────────────                    │
│  • Acquire: No reads/writes can move BEFORE this               │
│  • Release: No reads/writes can move AFTER this                │
│  • Common pair for producer-consumer                            │
│                                                                 │
│  memory_order_relaxed                                           │
│  ─────────────────────                                          │
│  • No ordering guarantees                                       │
│  • Only atomicity guaranteed                                    │
│  • Fastest, but dangerous!                                      │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Acquire-Release Example

#include <atomic>
#include <thread>
#include <iostream>

std::atomic<bool> ready{false};
int data = 0;

void producer() {
    data = 42;  // Normal write
    ready.store(true, std::memory_order_release);  // Release: data write visible before this
}

void consumer() {
    while (!ready.load(std::memory_order_acquire)) {
        // Spin
    }
    // Acquire: guaranteed to see data = 42
    std::cout << data << std::endl;  // ✅ Always 42
}

int main() {
    std::thread t1(producer);
    std::thread t2(consumer);
    
    t1.join();
    t2.join();
    
    return 0;
}

💡 Rule of Thumb

Dùng default memory_order_seq_cst trừ khi bạn chắc chắn cần optimize và hiểu rõ memory model.

---

Atomics vs Mutex

Aspect	std::atomic	std::mutex
Overhead	Thấp (hardware instruction)	Cao hơn (OS call)
Blocking	Không (hoặc spinning)	Có (thread sleep)
Complexity	Simple operations only	Any code block
Best for	Counters, flags, simple updates	Complex critical sections

When to Use Atomics?

// ✅ GOOD: Simple counter
std::atomic<int> requestCount{0};
requestCount++;

// ✅ GOOD: Flag/signal
std::atomic<bool> done{false};
done.store(true);

// ❌ BAD: Complex operations (use mutex)
std::atomic<int> balance{1000};
// Can't atomically: check balance, then subtract
// This is still a race condition!
if (balance >= 500) {  // Check
    balance -= 500;    // Act (not atomic together!)
}

---

Practical Examples

Lock-free Counter with Statistics

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>

class AtomicStats {
    std::atomic<long long> sum_{0};
    std::atomic<int> count_{0};
    std::atomic<int> max_{std::numeric_limits<int>::min()};
    
public:
    void record(int value) {
        sum_.fetch_add(value);
        count_.fetch_add(1);
        
        // Lock-free max update
        int currentMax = max_.load();
        while (value > currentMax && 
               !max_.compare_exchange_weak(currentMax, value)) {
            // Retry if someone else updated max
        }
    }
    
    void print() const {
        std::cout << "Count: " << count_ 
                  << ", Sum: " << sum_
                  << ", Max: " << max_
                  << ", Avg: " << (double)sum_ / count_
                  << std::endl;
    }
};

int main() {
    AtomicStats stats;
    
    std::vector<std::thread> threads;
    for (int i = 0; i < 4; ++i) {
        threads.emplace_back([&stats, i]() {
            for (int j = 0; j < 1000; ++j) {
                stats.record(i * 1000 + j);
            }
        });
    }
    
    for (auto& t : threads) t.join();
    
    stats.print();
    return 0;
}

Stop Token Pattern

#include <atomic>
#include <thread>
#include <iostream>
#include <chrono>

std::atomic<bool> stopRequested{false};

void workerThread() {
    while (!stopRequested.load(std::memory_order_relaxed)) {
        std::cout << "Working...\n";
        std::this_thread::sleep_for(std::chrono::milliseconds(500));
    }
    std::cout << "Worker stopped gracefully.\n";
}

int main() {
    std::thread worker(workerThread);
    
    std::this_thread::sleep_for(std::chrono::seconds(2));
    
    stopRequested.store(true, std::memory_order_relaxed);
    
    worker.join();
    return 0;
}

---

📚 Tổng kết

Operation	Method	Returns
Read	load()	Current value
Write	store(val)	void
Read-Modify-Write	exchange(val)	Old value
Conditional swap	compare_exchange_*	bool (success)
Add	fetch_add(val)	Old value
Sub	fetch_sub(val)	Old value

Type	Guaranteed Lock-free
std::atomic_flag	✅ Always
std::atomic<T>	Check is_lock_free()

---

➡️ Tiếp theo

Atomics giúp với simple operations. Nhưng khi cần chờ đợi có điều kiện (e.g., "chờ đến khi có data"), chúng ta cần...

Condition Variables → — Producer-Consumer pattern.

🧠 Quiz

Câu 1: compare_exchange_weak khác compare_exchange_strong ở điểm nào?

• [x] A) weak có thể spurious fail (fail dù giá trị khớp) nhưng nhanh hơn trong loop
• [ ] B) strong nhanh hơn vì chỉ thử một lần
• [ ] C) weak chỉ dùng cho kiểu int, strong cho mọi kiểu
• [ ] D) Không có sự khác biệt về hành vi

💡 Giải thích: compare_exchange_weak có thể fail ngay cả khi expected value khớp (spurious failure) — đây là đặc điểm của LL/SC instruction trên một số CPU (ARM, PowerPC). Vì vậy nó luôn được dùng trong loop. Bù lại, mỗi lần gọi nhanh hơn strong. Dùng weak trong loop (phổ biến nhất), strong khi chỉ gọi một lần.

Câu 2: Memory ordering nào cho performance cao nhất nhưng ít guarantee nhất?

• [ ] A) memory_order_seq_cst
• [ ] B) memory_order_acquire
• [x] C) memory_order_relaxed
• [ ] D) memory_order_release

💡 Giải thích: memory_order_relaxed chỉ đảm bảo atomicity (operation không bị xen ngang) nhưng không đảm bảo thứ tự với các operations khác. Ngược lại, seq_cst (default) đảm bảo total ordering nhưng chậm nhất. acquire/release nằm giữa — dùng cho producer-consumer pattern. Chỉ dùng relaxed khi thực sự hiểu rõ, ví dụ: simple counter.

Câu 3: std::atomic_flag khác std::atomic<bool> ở điểm nào quan trọng nhất?

• [x] A) atomic_flag được guaranteed lock-free trên mọi platform, atomic<bool> thì không
• [ ] B) atomic_flag nhanh hơn nhưng không lock-free
• [ ] C) atomic<bool> không hỗ trợ store/load operations
• [ ] D) Chúng hoàn toàn giống nhau về tính năng

💡 Giải thích: std::atomic_flag là kiểu atomic duy nhất được C++ standard guarantee lock-free trên mọi platform. std::atomic<bool> thường lock-free trên hầu hết CPU hiện đại, nhưng không được guarantee bởi standard. atomic_flag có API hạn chế hơn (chỉ test_and_set/clear), thường dùng làm spinlock.