Lock-Free 자료구조 성능 — CAS·ABA·Hazard Pointer·Epoch Reclamation

1
Obstruction-free: thread 혼자 실행되면 진행 보장
2
Lock-free       : 시스템 전체에서 적어도 한 thread는 진행
3
Wait-free       : 모든 thread가 n cycle 안에 진행 보장

1
bool cas(int *ptr, int *expected, int desired) {
2
    if (*ptr == *expected) {
3
        *ptr = desired;
4
        return true;
5
    }
6
    *expected = *ptr;
7
    return false;
8
}

1
loop:
2
    ldrex r1, [r0]
3
    cmp   r1, expected
4
    bne   fail
5
    strex r2, desired, [r0]
6
    cmp   r2, #0
7
    bne   loop

1
atomic_int counter;
2

3
void inc(void) {
4
    int old;
5
    do {
6
        old = atomic_load(&counter);
7
    } while (!atomic_compare_exchange_weak(&counter, &old, old + 1));
8
}
9

10
/* 또는 atomic_fetch_add — 한 명령 */
11
atomic_fetch_add(&counter, 1);

1
struct node { int value; struct node *next; };
2

3
struct node *top;
4

5
void push(int v) {
6
    struct node *new_node = malloc(sizeof(*new_node));
7
    new_node->value = v;
8
    struct node *old_top;
9
    do {
10
        old_top = atomic_load(&top);
11
        new_node->next = old_top;
12
    } while (!atomic_compare_exchange(&top, &old_top, new_node));
13
}
14

15
bool pop(int *out) {
16
    struct node *old_top;
17
    do {
18
        old_top = atomic_load(&top);
19
        if (!old_top) return false;
20
    } while (!atomic_compare_exchange(&top, &old_top, old_top->next));
21
    *out = old_top->value;
22
    free(old_top);   /* ABA·use-after-free 위험 */
23
    return true;
24
}

1
Thread 1 starts pop:
2
  old_top = X (X->next = Y)
3
  preempt
4
Thread 2: pop X, pop Y, push X (재사용)
5
  top = X (그러나 X->next는 이제 Z)
6
  resume Thread 1
7
Thread 1: CAS(top, X, Y) — 성공
8
  → top = Y (그런데 Y는 이미 free됨)

1
struct { void *ptr; uint64_t tag; } top;   /* 128-bit */
2

3
push:
4
  loop:
5
    old = top;
6
    new->next = old.ptr;
7
    new_pair = { new, old.tag + 1 };
8
    CAS(top, old, new_pair);

1
__thread void *hp;
2
struct node *hp_list[MAX_THREADS];
3

4
void pop(...) {
5
    struct node *top_;
6
    do {
7
        top_ = atomic_load(&top);
8
        hp = top_;   /* 보호 등록 */
9
        if (top_ != atomic_load(&top)) continue;
10
    } while (!CAS(&top, top_, top_->next));
11

12
    retire(top_);   /* 즉시 free하지 않고 retired list로 */
13
}
14

15
void scan_and_free(void) {
16
    for (each retired r) {
17
        if (no_hp_points_to(r)) free(r);
18
    }
19
}

1
atomic_int global_epoch;
2
__thread int local_epoch;
3

4
void read(void) {
5
    local_epoch = atomic_load(&global_epoch);
6
    /* access shared ptr */
7
    local_epoch = -1;
8
}
9

10
void writer(void) {
11
    /* modify, retire old */
12
    atomic_fetch_add(&global_epoch, 1);
13
    wait_until_all_threads_pass_epoch();
14
    free(retired);
15
}

1
struct spsc {
2
    alignas(64) atomic_size_t head;   /* producer */
3
    alignas(64) atomic_size_t tail;   /* consumer */
4
    alignas(64) T buf[CAPACITY];
5
};
6

7
bool push(struct spsc *q, T v) {
8
    size_t h = atomic_load_explicit(&q->head, memory_order_relaxed);
9
    size_t t = atomic_load_explicit(&q->tail, memory_order_acquire);
10
    if (h - t == CAPACITY) return false;
11
    q->buf[h % CAPACITY] = v;
12
    atomic_store_explicit(&q->head, h + 1, memory_order_release);
13
    return true;
14
}
15

16
bool pop(struct spsc *q, T *out) {
17
    size_t t = atomic_load_explicit(&q->tail, memory_order_relaxed);
18
    size_t h = atomic_load_explicit(&q->head, memory_order_acquire);
19
    if (h == t) return false;
20
    *out = q->buf[t % CAPACITY];
21
    atomic_store_explicit(&q->tail, t + 1, memory_order_release);
22
    return true;
23
}

1
struct cell { atomic_size_t sequence; T data; };
2
struct mpmc {
3
    alignas(64) atomic_size_t enqueue_pos;
4
    alignas(64) atomic_size_t dequeue_pos;
5
    struct cell buf[CAPACITY];
6
};

1
atomic_store(&flag, 1, memory_order_relaxed);   /* producer */
2
/* consumer가 data 변경을 못 봄 */

1
push: malloc(node);   /* lock-free가 아니라 lock 안에 있음 */

1
                          Latency      Throughput
2
Mutex (uncontended)        30 ns        13 M/s
3
Mutex (contended)           2 µs         2 M/s
4
Spinlock (contended)      200 ns        20 M/s
5
CAS retry loop            100 ns        40 M/s
6
atomic_fetch_add (LDADD)   50 ns       320 M/s
7
SPSC queue                 25 ns       400 M/s