Lock-Free 동시성 프로그래밍 완전 가이드 2025: Atomics, 메모리 모델, CAS, 무잠금 자료구조

// Thread 1
x = 1;
y = 2;

// Thread 2
print(y);
print(x);

#include <atomic>

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

// 가장 강함 (Sequential Consistency, 기본값)
x.store(1, std::memory_order_seq_cst);

// Release: 이 store 이전의 모든 메모리 작업이 완료된 후 수행
x.store(1, std::memory_order_release);

// Acquire: 이 load 이후의 모든 메모리 작업이 이 load 이후에 수행
int v = x.load(std::memory_order_acquire);

// Relaxed: 원자성만 보장, 순서 X (가장 빠름)
x.store(1, std::memory_order_relaxed);

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

// Thread 1 (Producer)
data = 42;
ready.store(true, std::memory_order_release);

// Thread 2 (Consumer)
while (!ready.load(std::memory_order_acquire)) {}
assert(data == 42);  // 보장됨!

bool compare_and_swap(int* ptr, int expected, int new_value) {
    if (*ptr == expected) {
        *ptr = new_value;
        return true;
    }
    return false;
}

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

void increment() {
    int old_value, new_value;
    do {
        old_value = counter.load();
        new_value = old_value + 1;
    } while (!counter.compare_exchange_weak(old_value, new_value));
}

counter.fetch_add(1, std::memory_order_relaxed);

use std::sync::atomic::{AtomicUsize, Ordering};

let counter = AtomicUsize::new(0);

// 원자적 증가
counter.fetch_add(1, Ordering::Relaxed);

// CAS
let result = counter.compare_exchange(
    0,                     // expected
    1,                     // new
    Ordering::Acquire,     // success ordering
    Ordering::Relaxed      // failure ordering
);

template<typename T>
class LockFreeStack {
    struct Node {
        T value;
        Node* next;
    };
    std::atomic<Node*> head{nullptr};

public:
    void push(T value) {
        Node* new_node = new Node{value, nullptr};
        Node* old_head;
        do {
            old_head = head.load();
            new_node->next = old_head;
        } while (!head.compare_exchange_weak(old_head, new_node));
    }

    bool pop(T& value) {
        Node* old_head;
        Node* new_head;
        do {
            old_head = head.load();
            if (!old_head) return false;
            new_head = old_head->next;
        } while (!head.compare_exchange_weak(old_head, new_head));
        value = old_head->value;
        delete old_head;  // 위험! 다른 스레드가 읽고 있을 수 있음
        return true;
    }
};

초기: head → A → B → C

Thread 1:                    Thread 2:
old_head = A
new_head = B
                              pop A → delete A
                              pop B → delete B
                              push A (재할당된 메모리)
                              head → A → C

CAS(old_head=A, new_head=B)  ← 성공! 하지만 잘못됨
head → B (이미 free된 메모리)

struct TaggedPtr {
    Node* ptr;
    uint64_t tag;  // 매번 증가
};
std::atomic<TaggedPtr> head;

struct Node {
    T value;
    std::atomic<Node*> next{nullptr};
};

std::atomic<Node*> head;
std::atomic<Node*> tail;

void enqueue(T value) {
    Node* new_node = new Node{value};
    Node* old_tail;
    Node* old_next;
    while (true) {
        old_tail = tail.load();
        old_next = old_tail->next.load();
        if (old_tail == tail.load()) {  // 일관성 체크
            if (old_next == nullptr) {
                // CAS로 next 설정 시도
                if (old_tail->next.compare_exchange_weak(old_next, new_node)) {
                    break;
                }
            } else {
                // tail이 뒤처짐, 도와주기 (helping)
                tail.compare_exchange_weak(old_tail, old_next);
            }
        }
    }
    // tail 갱신 (실패해도 OK, 다른 스레드가 도와줌)
    tail.compare_exchange_weak(old_tail, new_node);
}

// 의사 코드
struct config* config = rcu_dereference(global_config);
int value = config->some_value;  // 락 없이 읽기

// 업데이트
struct config* new_config = malloc(sizeof(*new_config));
memcpy(new_config, old_config, sizeof(*new_config));
new_config->some_value = 42;
rcu_assign_pointer(global_config, new_config);
synchronize_rcu();  // 모든 readers 완료 대기
free(old_config);

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

// 단순 카운터 (낮은 컨텐션)
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet();

// 높은 컨텐션 카운터 (Java 8+)
LongAdder adder = new LongAdder();
adder.increment();  // 분할 셀로 컨텐션 분산
long value = adder.sum();  // 집계

#include <atomic>

std::atomic<int> counter{0};
counter.fetch_add(1, std::memory_order_relaxed);

// 메모리 순서를 정확히 지정해야 함
std::atomic<bool> flag{false};
flag.store(true, std::memory_order_release);
bool v = flag.load(std::memory_order_acquire);

use std::sync::atomic::{AtomicUsize, AtomicBool, Ordering};

static COUNTER: AtomicUsize = AtomicUsize::new(0);
COUNTER.fetch_add(1, Ordering::Relaxed);

import "sync/atomic"

var counter int64
atomic.AddInt64(&counter, 1)
value := atomic.LoadInt64(&counter)

class LockFreeLogger {
    static constexpr size_t SIZE = 1024;
    std::atomic<size_t> head{0};
    std::array<std::string, SIZE> buffer;

public:
    void log(const std::string& msg) {
        size_t idx = head.fetch_add(1, std::memory_order_relaxed) % SIZE;
        buffer[idx] = msg;  // 주의: 동시 쓰기 가능, 실제로는 더 정교하게
    }
};

use std::sync::atomic::{AtomicU64, Ordering};

struct IdGenerator {
    next_id: AtomicU64,
}

impl IdGenerator {
    fn next(&self) -> u64 {
        self.next_id.fetch_add(1, Ordering::Relaxed)
    }
}

class SpinLock {
    std::atomic_flag flag = ATOMIC_FLAG_INIT;
public:
    void lock() {
        while (flag.test_and_set(std::memory_order_acquire)) {
            // 바쁘게 대기 (busy wait)
        }
    }
    void unlock() {
        flag.clear(std::memory_order_release);
    }
};

while (flag.test_and_set(std::memory_order_acquire)) {
    _mm_pause();  // CPU 힌트
}

struct Counters {
    std::atomic<int> a;
    std::atomic<int> b;  // 같은 캐시 라인!
};

struct Counters {
    alignas(64) std::atomic<int> a;
    alignas(64) std::atomic<int> b;
};