Embedded C++ for Real Systems · 32/41

Lock-free Container 구현 — SPSC Queue·Ring Buffer

2026년 5월 1일 · Hawk · 5분 읽기

cpp embedded lock-free queue stack ring-buffer spsc mpmc

Twitter LinkedIn

#한 줄 요약

“SPSC는 atomic 변수 두 개면 끝납니다.” MPMC는 복잡하므로 검증된 라이브러리를 권장합니다.

#어떤 문제를 푸는가

Part 4-03에서 원리를 다뤘다면, 이 글은 실용적인 자료구조 구현을 다룹니다.

임베디드에서 자주 등장하는 패턴은 다음과 같습니다.

ISR에서 main task로의 통신 (SPSC)
Worker pool (MPMC queue)
Free list (lock-free pool)
Statistics counter (atomic)

각 패턴의 구현과 trade-off를 살펴봅니다.

#SPSC Ring Buffer — 가장 기본

Ring buffer의 구조는 다음과 같습니다. Producer는 head만 전진시키고 Consumer는 tail만 전진시키므로 두 인덱스가 같은 메모리를 동시에 건드릴 일이 없습니다.

SPSC ring buffer — head/tail 분리

Part 4-03에서 본 코드를 다시 옮기면 다음과 같습니다.

1
template<typename T, size_t N>
2
class SpscQueue {
3
    static_assert((N & (N - 1)) == 0, "N must be power of 2");
4

5
    T buffer_[N];
6
    alignas(64) std::atomic<size_t> head_{0};   // cache line 분리
7
    alignas(64) std::atomic<size_t> tail_{0};
8
    static constexpr size_t kMask = N - 1;
9

10
public:
11
    bool push(const T& value) {
12
        size_t h = head_.load(std::memory_order_relaxed);
13
        size_t next = (h + 1) & kMask;
14

15
        if (next == tail_.load(std::memory_order_acquire)) return false;
16

17
        buffer_[h] = value;
18
        head_.store(next, std::memory_order_release);
19
        return true;
20
    }
21

22
    bool pop(T& out) {
23
        size_t t = tail_.load(std::memory_order_relaxed);
24
        if (t == head_.load(std::memory_order_acquire)) return false;
25

26
        out = buffer_[t];
27
        tail_.store((t + 1) & kMask, std::memory_order_release);
28
        return true;
29
    }
30
};

핵심은 다음과 같습니다.

Producer는 head만, Consumer는 tail만 수정합니다.
서로의 변수는 acquire로 읽고 자기 것은 release로 씁니다.
alignas(64)로 head와 tail을 다른 cache line에 두어 false sharing을 회피합니다.

#False Sharing — `alignas(64)`의 의의

Multi-core에서 같은 cache line의 변수를 다른 core가 동시에 수정하면 cache invalidation이 일어나 성능이 폭락합니다.

1
struct Bad {
2
    std::atomic<size_t> a;   // core 1 사용
3
    std::atomic<size_t> b;   // core 2 사용
4
};   // 같은 cache line — false sharing
5

6
struct Good {
7
    alignas(64) std::atomic<size_t> a;
8
    alignas(64) std::atomic<size_t> b;
9
};   // 다른 cache line — no false sharing

ARM Cortex-A multi-core에서는 중요합니다. Cortex-M single core에서는 무관하지만 습관적으로 alignas를 붙입니다.

#Lock-free Stack (Treiber Stack)

MPMC가 가능한 단순한 lock-free stack입니다.

1
template<typename T>
2
class TreiberStack {
3
    struct Node {
4
        T value;
5
        Node* next;
6
    };
7

8
    std::atomic<Node*> top_{nullptr};
9

10
public:
11
    void push(Node* node) {
12
        Node* old_top = top_.load(std::memory_order_relaxed);
13
        do {
14
            node->next = old_top;
15
        } while (!top_.compare_exchange_weak(
16
            old_top, node,
17
            std::memory_order_release,
18
            std::memory_order_relaxed));
19
    }
20

21
    Node* pop() {
22
        Node* old_top = top_.load(std::memory_order_acquire);
23
        while (old_top) {
24
            if (top_.compare_exchange_weak(
25
                old_top, old_top->next,
26
                std::memory_order_acquire,
27
                std::memory_order_acquire)) {
28
                return old_top;
29
            }
30
        }
31
        return nullptr;
32
    }
33
};

MPMC이며 모든 thread가 push/pop 모두 수행할 수 있습니다.

문제는 ABA problem입니다. Pop이 old_top->next를 읽는 중에 다른 thread가 old_top을 pop했다가 다른 노드를 push한 뒤 다시 old_top을 push하면, CAS는 성공하지만 next pointer가 잘못된 값을 가리킵니다.

해결책은 다음과 같습니다.

Tagged pointer — 64-bit으로 ptr과 counter를 묶습니다.
Hazard pointer를 사용합니다.

#Tagged Pointer

1
template<typename Node>
2
struct TaggedPtr {
3
    Node* ptr;
4
    uintptr_t tag;
5
};
6

7
std::atomic<TaggedPtr<Node>> top;   // 16 byte atomic on 64-bit

ARM Cortex-M(32-bit)에서는 64-bit atomic이 불가능하므로 32-bit pointer에 작은 counter를 packing합니다.

1
struct PackedPtr {
2
    uint32_t value;   // 16-bit ptr (작은 주소 공간) + 16-bit tag
3
};

구현이 복잡하므로 작은 임베디드에서는 lock-free MPMC를 보통 회피합니다.

#Lock-free Free List

Part 3-03 Pool Allocator의 lock-free 버전입니다.

1
template<typename T, size_t N>
2
class LockFreePool {
3
    union Slot {
4
        alignas(T) std::byte storage[sizeof(T)];
5
        std::atomic<Slot*> next;
6
    };
7

8
    Slot slots_[N];
9
    std::atomic<Slot*> free_head_;
10

11
public:
12
    LockFreePool() {
13
        for (size_t i = 0; i < N - 1; ++i) {
14
            slots_[i].next.store(&slots_[i + 1], std::memory_order_relaxed);
15
        }
16
        slots_[N - 1].next.store(nullptr, std::memory_order_relaxed);
17
        free_head_.store(&slots_[0], std::memory_order_release);
18
    }
19

20
    T* allocate() noexcept {
21
        Slot* head = free_head_.load(std::memory_order_acquire);
22
        while (head) {
23
            Slot* next = head->next.load(std::memory_order_relaxed);
24
            if (free_head_.compare_exchange_weak(
25
                head, next,
26
                std::memory_order_release,
27
                std::memory_order_acquire)) {
28
                return reinterpret_cast<T*>(&head->storage);
29
            }
30
        }
31
        return nullptr;
32
    }
33

34
    void deallocate(T* p) noexcept {
35
        if (!p) return;
36
        Slot* slot = reinterpret_cast<Slot*>(p);
37
        Slot* head = free_head_.load(std::memory_order_relaxed);
38
        do {
39
            slot->next.store(head, std::memory_order_relaxed);
40
        } while (!free_head_.compare_exchange_weak(
41
            head, slot,
42
            std::memory_order_release,
43
            std::memory_order_relaxed));
44
    }
45
};

ABA 문제가 발생할 수 있으므로 주의가 필요합니다.

#Boost.Lockfree

Boost가 검증된 lock-free 자료구조를 제공합니다.

1
#include <boost/lockfree/spsc_queue.hpp>
2
#include <boost/lockfree/queue.hpp>
3
#include <boost/lockfree/stack.hpp>
4

5
// SPSC — 가장 빠름
6
boost::lockfree::spsc_queue<int, boost::lockfree::capacity<128>> q;
7

8
// MPMC — fixed capacity
9
boost::lockfree::queue<int, boost::lockfree::capacity<128>> mpmc_q;
10

11
// Stack — LIFO MPMC
12
boost::lockfree::stack<int, boost::lockfree::capacity<128>> stack;

Boost는 내부적으로 tagged pointer와 정교한 알고리즘을 쓰므로 직접 구현하는 것보다 안전합니다.

임베디드에서 Boost가 부담스럽다면 일부 헤더만 포함할 수 있습니다.

#moodycamel::ConcurrentQueue

가장 빠른 MPMC 구현으로, Cameron Desrochers의 고성능 lock-free queue입니다.

1
#include <concurrentqueue.h>
2

3
moodycamel::ConcurrentQueue<int> q;
4
q.enqueue(42);
5
int v;
6
q.try_dequeue(v);

수십만 ops/sec를 달성하며 임베디드 multi-core에 적합합니다.

#임베디드 — ISR + 여러 task

1
// ISR가 producer, 여러 task가 consumer
2
class EventBus {
3
    SpscQueue<Event, 256> queue_;
4
    SemaphoreHandle_t event_sem_;
5

6
public:
7
    // ISR에서 호출
8
    void post_isr(const Event& e) {
9
        if (queue_.push(e)) {
10
            BaseType_t woken = pdFALSE;
11
            xSemaphoreGiveFromISR(event_sem_, &woken);
12
            portYIELD_FROM_ISR(woken);
13
        }
14
    }
15

16
    // Task에서 호출
17
    bool wait(Event& out, TickType_t timeout) {
18
        if (queue_.pop(out)) return true;
19

20
        if (xSemaphoreTake(event_sem_, timeout) == pdTRUE) {
21
            return queue_.pop(out);
22
        }
23
        return false;
24
    }
25
};

SPSC queue로 ISR에서 단일 task로 전달합니다. 여러 task가 받아야 한다면 queue를 따로 둡니다.

#임베디드 — Atomic Counter

가장 단순하면서 가장 흔한 패턴입니다.

1
std::atomic<uint32_t> packets_sent{0};
2
std::atomic<uint32_t> packets_dropped{0};
3

4
void send_packet() {
5
    if (try_send()) {
6
        packets_sent.fetch_add(1, std::memory_order_relaxed);
7
    } else {
8
        packets_dropped.fetch_add(1, std::memory_order_relaxed);
9
    }
10
}
11

12
uint32_t get_stats_sent() {
13
    return packets_sent.load(std::memory_order_relaxed);
14
}

counter 값 자체가 의미를 갖고 순서는 무관하므로 relaxed로 충분합니다.

#측정 — SPSC queue 성능

1
# Cortex-M4, 1M operations
2

3
Mutex-based queue:    ~10 M cycles
4
SPSC lock-free:       ~1.2 M cycles    (~8x faster)
5
Boost MPMC:           ~2.5 M cycles    (~4x faster)
6
moodycamel MPMC:      ~1.8 M cycles    (~5x faster)

SPSC가 가장 빠르지만 producer와 consumer가 정확히 하나씩일 때만 쓸 수 있습니다.

#자주 보는 함정과 안티패턴

#1. SPSC를 MPMC처럼 사용

Producer 둘이 push하면 race가 발생합니다. SPSC는 producer가 정확히 하나여야 합니다.

#2. Memory order `seq_cst` 남용

기본 seq_cst는 가장 느립니다. 필요한 최소 order만 씁니다.

#3. 큰 객체에 atomic 시도

1
std::atomic<HugeStruct> obj;   // hardware atomic 안 됨 → mutex fallback

pointer를 atomic swap하는 방식으로 우회합니다.

#4. ABA problem 무시

Treiber stack 같은 복잡한 lock-free에는 tagged pointer를 적용하거나 전문 라이브러리를 사용합니다.

#5. Cache line alignment 무시

false sharing으로 성능이 폭락합니다. alignas(64)로 분리합니다.

#6. retry loop 무한 반복 가능성

Contention이 높으면 CAS retry가 무한히 반복될 수 있습니다. exponential backoff나 limit을 둡니다.

1
int retries = 0;
2
while (retries++ < 100) {
3
    if (cas(...)) break;
4
    // 짧은 wait
5
}

#ARM Cortex-M의 LDREX/STREX

std::atomic은 내부적으로 LDREX/STREX를 사용합니다.

1
# atomic compare_exchange (간소화)
2
loop:
3
    LDREX  r0, [addr]      ; exclusive load
4
    CMP    r0, expected
5
    BNE    fail
6
    STREX  r1, new, [addr] ; exclusive store
7
    CMP    r1, #0           ; STREX 성공?
8
    BNE    loop             ; 실패시 retry

ARMv7-M의 exclusive monitor가 atomic을 보장합니다. DMA 같은 다른 master가 같은 주소에 접근하면 STREX가 실패합니다.

중요: 일부 peripheral 주소는 exclusive monitor를 지원하지 않으므로 RAM에서만 안전합니다.

#Lock-free의 실용적 한계

1
사용 OK:
2
✓ ISR ↔ task 통신 (SPSC)
3
✓ Statistics counter (atomic)
4
✓ Flag/state (atomic)
5
✓ 검증된 라이브러리 사용 (Boost, moodycamel)
6

7
피하는 게 좋음:
8
✗ 직접 MPMC 구현 (ABA, hazard pointer 복잡)
9
✗ 복잡한 자료구조 (RB-tree, hash map)
10
✗ Cortex-M0/M0+ (atomic 미지원)
11

12
대안:
13
- Critical section (짧음)
14
- RTOS queue (xQueueSend) — 검증됨
15
- Mutex + condition variable

대부분의 임베디드 multi-task는 RTOS queue로 충분합니다. Lock-free는 극한 성능이 필요하거나 ISR 통신이 필요할 때만 씁니다.

#정리

SPSC queue가 임베디드 lock-free의 표준이며, ISR과 task 통신에 적합합니다.
Producer는 head, Consumer는 tail만 다루므로 서로 무관하며 CAS가 필요 없습니다.
alignas(64)로 cache line을 정렬해 false sharing을 회피합니다.
MPMC는 복잡하므로 검증된 라이브러리(Boost, moodycamel)를 사용합니다.
ABA problem에는 tagged pointer나 hazard pointer를 쓰거나 MPMC 자체를 회피합니다.
Cortex-M0/M0+는 atomic을 지원하지 않으므로 critical section을 사용합니다.

#관련 항목

Part 4-03: Lock-free 기초
Part 3-03: Pool Allocator — lock-free pool
Part 4-01: Intrusive Containers
Practical RTOS Internals

#다음 글

Part 4-05: Type-safe Flags — bit flag를 enum class로 type-safe하게.

Embedded C++ for Real Systems · 33 of 41

임베디드 Lock-free 기초 — atomic·memory ordering·CAS

Atomic, CAS, memory order — mutex 없이 동시성. 임베디드의 ISR-safe 패턴.

2026년 5월 1일·cpp

임베디드 HAL 설계 패턴 — Static·Dynamic·Hybrid 비교

범용 HAL 구조 — 벤더 종속성 격리, 다중 보드/MCU 지원, 시리즈 마무리.

2026년 5월 2일·cpp

Peripheral 추상화 — UART·SPI·I2C 공통 인터페이스 설계

UART, SPI, I2C — peripheral을 type-safe class로. Blocking, interrupt, DMA 패턴.

2026년 5월 2일·cpp

Lock-free Container 구현 — SPSC Queue·Ring Buffer

#한 줄 요약

#어떤 문제를 푸는가

#SPSC Ring Buffer — 가장 기본

#Lock-free Stack (Treiber Stack)

#Tagged Pointer

#Lock-free Free List

#Boost.Lockfree

#moodycamel::ConcurrentQueue

#임베디드 — ISR + 여러 task

#임베디드 — Atomic Counter

#측정 — SPSC queue 성능

#자주 보는 함정과 안티패턴

#1. SPSC를 MPMC처럼 사용

#2. Memory order `seq_cst` 남용

#3. 큰 객체에 atomic 시도

#4. ABA problem 무시

#5. Cache line alignment 무시

#6. retry loop 무한 반복 가능성

#ARM Cortex-M의 LDREX/STREX

#Lock-free의 실용적 한계

#정리

#관련 항목

#다음 글

Embedded C++ for Real Systems · 33 of 41

관련 글

임베디드 Lock-free 기초 — atomic·memory ordering·CAS

임베디드 HAL 설계 패턴 — Static·Dynamic·Hybrid 비교

Peripheral 추상화 — UART·SPI·I2C 공통 인터페이스 설계

이 글을 참조하는 글 (5)

#한 줄 요약

#어떤 문제를 푸는가

#SPSC Ring Buffer — 가장 기본

#False Sharing — alignas(64)의 의의

#Lock-free Stack (Treiber Stack)

#Tagged Pointer

#Lock-free Free List

#Boost.Lockfree

#moodycamel::ConcurrentQueue

#임베디드 — ISR + 여러 task

#임베디드 — Atomic Counter

#측정 — SPSC queue 성능

#자주 보는 함정과 안티패턴

#1. SPSC를 MPMC처럼 사용

#2. Memory order seq_cst 남용

#3. 큰 객체에 atomic 시도

#4. ABA problem 무시

#5. Cache line alignment 무시

#6. retry loop 무한 반복 가능성

#ARM Cortex-M의 LDREX/STREX

#Lock-free의 실용적 한계

#정리

#관련 항목

#다음 글

Embedded C++ for Real Systems · 33 of 41

관련 글

임베디드 Lock-free 기초 — atomic·memory ordering·CAS

임베디드 HAL 설계 패턴 — Static·Dynamic·Hybrid 비교

Peripheral 추상화 — UART·SPI·I2C 공통 인터페이스 설계

이 글을 참조하는 글 (5)

#False Sharing — `alignas(64)`의 의의

#2. Memory order `seq_cst` 남용