⚛️ 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

cpp

#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

cpp

// 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

cpp

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()

cpp

#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ũ:

cpp

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

cpp

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:

cpp

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

cpp

#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

cpp

// 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:

cpp

#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

cpp

// 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

cpp

#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?

cpp

// ✅ 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

cpp

#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

cpp

#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.

⚛️ Atomics — Lock-free Programming Basics ​

Atomic là gì? ​

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

std::atomic Basics ​

Từ Race Condition đến Thread-safe ​

Supported Types ​

Core Operations ​

load() và store() ​

exchange() ​

Arithmetic Operations ​

Compare-and-Swap (CAS) ​

Logic ​

Lock-free Increment Example ​

weak vs strong ​

std::atomic_flag — Simplest Atomic ​

Memory Ordering (Simplified) ​

Default: Sequential Consistency ​

Common Memory Orders ​

Acquire-Release Example ​

Atomics vs Mutex ​

When to Use Atomics? ​

Practical Examples ​

Lock-free Counter with Statistics ​

Stop Token Pattern ​

📚 Tổng kết ​

➡️ Tiếp theo ​