Compare-And-Swap 패턴 — Stack·Counter·Linked List 적용

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

1
expected에 현재 *p를 in/out로 받음
2
*p == expected이면 *p = desired, return true
3
아니면 expected = *p, return false (재시도용)

1
typical CAS loop
2
do {
3
    T cur = atomic_load(p);
4
    T new_val = compute(cur);
5
} while (!atomic_compare_exchange_weak(p, &cur, new_val));

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

3
void inc_saturating(int max) {
4
    int cur, next;
5
    do {
6
        cur = counter.load(std::memory_order_relaxed);
7
        if (cur >= max) return;
8
        next = cur + 1;
9
    } while (!counter.compare_exchange_weak(
10
                cur, next, std::memory_order_release, std::memory_order_relaxed));
11
}

1
struct node { node *next; int val; };
2
std::atomic<node *> top;
3

4
void push(int v) {
5
    node *n = new node{nullptr, v};
6
    node *cur = top.load(std::memory_order_relaxed);
7
    do {
8
        n->next = cur;
9
    } while (!top.compare_exchange_weak(cur, n,
10
                std::memory_order_release, std::memory_order_relaxed));
11
}

1
std::atomic<int> locked{0};
2

3
bool try_lock(void) {
4
    int expected = 0;
5
    return locked.compare_exchange_strong(
6
        expected, 1, std::memory_order_acquire);
7
}
8

9
void unlock(void) {
10
    locked.store(0, std::memory_order_release);
11
}

1
/* loop 밖 — strong (단순한 의도) */
2
int expected = 0;
3
if (!locked.compare_exchange_strong(expected, 1)) {
4
    /* 누가 이미 잡고 있음 */
5
}
6

7
/* loop 안 — weak (spurious 허용, ARM에서 빠름) */
8
do {
9
    cur = p.load();
10
} while (!p.compare_exchange_weak(cur, cur + 1));

1
void cas_with_backoff(std::atomic<int> *p) {
2
    int delay = 1;
3
    int cur;
4
    do {
5
        cur = p->load();
6
        for (int i = 0; i < delay; i++)
7
            __asm__ volatile("yield" ::: "memory");
8
        if (delay < 1024) delay *= 2;
9
    } while (!p->compare_exchange_weak(cur, cur + 1));
10
}

1
struct tagged_ptr {
2
    node *p;
3
    uint64_t tag;
4
};
5
std::atomic<tagged_ptr> top;     /* DCAS 또는 __int128 atomic 필요 */
6

7
void push(int v) {
8
    node *n = new node{nullptr, v};
9
    tagged_ptr old, neu;
10
    do {
11
        old = top.load();
12
        n->next = old.p;
13
        neu = { n, old.tag + 1 };   /* tag 증가 */
14
    } while (!top.compare_exchange_weak(old, neu));
15
}

1
struct slot {
2
    std::atomic<uint64_t> seq;
3
    T data;
4
};
5

6
bool try_enqueue(T v) {
7
    uint64_t pos = enq_pos.load();
8
    slot &s = buf[pos & mask];
9
    uint64_t seq = s.seq.load(std::memory_order_acquire);
10
    intptr_t diff = (intptr_t)seq - (intptr_t)pos;
11

12
    if (diff == 0) {
13
        if (enq_pos.compare_exchange_weak(pos, pos + 1)) {
14
            s.data = v;
15
            s.seq.store(pos + 1, std::memory_order_release);
16
            return true;
17
        }
18
    } else if (diff < 0) return false;   /* full */
19
    return false;
20
}

1
연산                        시간 (Cortex-A72, no contention)
2
atomic load (relaxed)       2 cycle
3
atomic store (release)      4 cycle
4
CAS (uncontended)          ~6 cycle
5
CAS (contended, 2 thread)  ~80 cycle (cache line ping)
6
CAS (contended, 8 thread)  >300 cycle (강한 contention)

1
backoff 효과 (8 thread, 1M iteration)
2
backoff 없음             8.2 s
3
linear backoff           4.1 s
4
exponential backoff      2.3 s

1
do {
2
    cur = p.load();
3
} while (!p.compare_exchange_strong(cur, cur + 1));   /* weak가 더 빠름 */

1
p.compare_exchange_weak(cur, new);    /* return 무시 — fail 처리 안 함 */

1
while (!p.compare_exchange_weak(cur, cur + 1));   /* contention 시 burn */

1
p.compare_exchange_weak(cur, new, std::memory_order_relaxed);   /* publish 안 됨 */

1
/* pointer만 CAS — ABA 발생 가능 */
2
do { cur = p.load(); } while (!p.compare_exchange_weak(cur, cur->next));