SMP Spinlock 구현 — LDREX/STREX·Ticket Lock·MCS·WFE/SEV

#한 줄 요약

“SMP spinlock의 뼈대는 LDREX/STREX와 DMB 둘입니다.” — 그 위에서 fairness와 cache 비용을 어떻게 균형 잡느냐가 변주입니다.

#어떤 문제를 푸는가

4-07편에서 본 것처럼 SMP critical section은 spinlock + IRQ disable 조합이 필요합니다. 그런데 spinlock 자체를 어떻게 구현해야 할까요. 다음 세 가지 요구를 동시에 만족시켜야 합니다.

첫째, 짧은 critical section에서만 씁니다. sleep이 불가능한 ISR 컨텍스트나 수십 cycle짜리 자료구조 갱신처럼 block-based mutex로는 비용이 더 큰 구간이 대상입니다. 둘째, atomic하게 lock state를 갱신해야 합니다. test-and-set이 atomic하지 않으면 두 core가 동시에 lock을 잡는 race가 생깁니다. 셋째, spin 동안 시스템에 미치는 영향을 최소화해야 합니다. cache line이 core 사이를 핑퐁하면 다른 작업까지 느려집니다.

이번 편은 ARM atomic primitive에서 시작해 spinlock의 다양한 형태와 trade-off를 정리합니다.

#LDREX/STREX — ARM Exclusive Monitor

ARMv7-A/R/M의 atomic은 load-linked / store-conditional 패러다임입니다.

1
spin_lock:
2
    ldrex   r1, [r0]       @ load + exclusive monitor 설정
3
    cmp     r1, #0
4
    bne     spin_lock      @ 이미 locked — retry
5
    mov     r2, #1
6
    strex   r3, r2, [r0]   @ exclusive store 시도
7
    cmp     r3, #0
8
    bne     spin_lock      @ store 실패 — retry
9
    dmb                    @ acquire barrier
10
    bx      lr

핵심은 exclusive monitor입니다. core마다 thread-local hardware flag가 있어, LDREX가 그 flag를 set하고 접근한 address를 tag해 둡니다. STREX는 flag와 tag를 확인하고, 유효하면 store가 성공하고 flag를 clear합니다. 다른 core가 같은 address에 write하면 exclusive monitor가 클리어되어 STREX가 실패합니다.

실패하면 retry입니다. 이 load + check + conditional store + retry 루프가 모든 atomic 연산의 기본 골격입니다.

#ARMv8.1 LSE — 단일 명령 Atomic

ARMv8.1부터는 LSE(Large System Extensions)가 도입되어 단일 명령 atomic이 가능해졌습니다. Cortex-A55, A75 이후가 지원합니다.

1
@ Compare-and-Swap with Acquire-Release
2
casal   w0, w1, [x2]
3

4
@ Load-Add with Acquire-Release
5
ldaddal w0, w1, [x2]
6

7
@ Atomic Swap
8
swpal   w0, w1, [x2]

LDREX/STREX 루프 4~5 cycle이 CASAL 한 줄 3 cycle로 줄어듭니다. contention이 심할수록 차이가 더 벌어집니다.

embedded SMP에서 ARMv8.1+ chip을 쓴다면 LSE 활용이 표준입니다. compiler flag로 -march=armv8.1-a 또는 -moutline-atomics를 줘서 자동 선택하게 둡니다.

#C 추상화 — <stdatomic.h>

직접 어셈블리를 만지지 않아도 <stdatomic.h>가 같은 시맨틱을 제공합니다.

1
#include <stdatomic.h>
2

3
void spin_lock(atomic_int *l) {
4
    int expected = 0;
5
    while (!atomic_compare_exchange_weak_explicit(
6
                l, &expected, 1,
7
                memory_order_acquire,
8
                memory_order_relaxed)) {
9
        expected = 0;
10
        cpu_relax();
11
    }
12
}
13

14
void spin_unlock(atomic_int *l) {
15
    atomic_store_explicit(l, 0, memory_order_release);
16
}

memory_order_acquire와 memory_order_release가 acquire/release barrier를 표현합니다. compiler가 ARMv8.1 LSE를 알면 CASAL로, 그렇지 않으면 LDREX/STREX 루프로 내려갑니다.

#Test-and-Test-and-Set — Cache 절약

기본 test-and-set spinlock에는 큰 문제가 있습니다. spin 루프 안의 STREX가 매번 cache line에 write를 시도합니다. 다른 core들이 spin하면 cache line이 core 사이를 끊임없이 이동합니다.

해결책이 TTAS(test-and-test-and-set)입니다.

1
void spin_lock_ttas(atomic_int *l) {
2
    for (;;) {
3
        /* 1단계 — 읽기만 (cache line shared 상태 유지) */
4
        while (atomic_load_explicit(l, memory_order_relaxed) != 0) {
5
            cpu_relax();
6
        }
7
        /* 2단계 — 한 번 atomic 시도 */
8
        int expected = 0;
9
        if (atomic_compare_exchange_weak_explicit(
10
                l, &expected, 1,
11
                memory_order_acquire, memory_order_relaxed)) {
12
            return;
13
        }
14
    }
15
}

읽기 루프가 cache line을 shared 상태로 유지하므로 bus traffic이 0에 가까워집니다. 누군가 unlock하면 그제야 line이 invalidate되고 CAS를 한 번 시도합니다. uncontended 비용은 같지만 contended 비용이 수 배 줄어듭니다.

#WFE / SEV — 저전력 Spin

ARM은 spin loop을 위한 hint instruction을 제공합니다. *WFE(Wait For Event)*가 들어오면 core가 clock을 멈추고 대기 상태로 들어갑니다. 다른 core가 *SEV(Send Event)*를 보내거나 IRQ가 들어오면 깨어납니다.

1
void spin_lock_wfe(atomic_int *l) {
2
    int expected = 0;
3
    while (!atomic_compare_exchange_weak_explicit(
4
                l, &expected, 1,
5
                memory_order_acquire, memory_order_relaxed)) {
6
        expected = 0;
7
        __asm volatile ("wfe");   /* 다음 SEV 또는 IRQ까지 sleep */
8
    }
9
}
10

11
void spin_unlock_wfe(atomic_int *l) {
12
    atomic_store_explicit(l, 0, memory_order_release);
13
    __asm volatile ("dsb sy; sev");   /* waiter 전원 깨우기 */
14
}

전력이 중요한 IoT나 wearable에서는 단순 spin 대신 WFE/SEV를 쓰는 편이 전류 mA 단위로 차이가 납니다. 단점은 깨는 latency가 약간 더 든다는 것뿐입니다.

STREX는 exclusive monitor가 clear되면 자동으로 event를 발생시키므로, store 쪽에서 별도로 SEV를 호출하지 않아도 되는 변형도 있습니다.

#Ticket Lock — Fairness 보장

지금까지 본 spinlock은 공평하지 않습니다. unlock 직후 우연히 가까운 cache line을 가진 core가 항상 먼저 잡아 starvation이 생길 수 있습니다. ticket lock은 이를 해결합니다.

1
typedef struct {
2
    atomic_int next;
3
    atomic_int now_serving;
4
} ticket_lock_t;
5

6
void ticket_lock(ticket_lock_t *l) {
7
    int my = atomic_fetch_add_explicit(
8
                 &l->next, 1, memory_order_relaxed);
9
    while (atomic_load_explicit(&l->now_serving,
10
                                memory_order_acquire) != my) {
11
        cpu_relax();
12
    }
13
}
14

15
void ticket_unlock(ticket_lock_t *l) {
16
    atomic_fetch_add_explicit(&l->now_serving, 1,
17
                              memory_order_release);
18
}

은행 번호표와 똑같습니다. 도착 순서대로 next에서 번호를 받고, now_serving이 자기 번호가 될 때까지 기다립니다. FIFO 공평성이 보장됩니다.

문제는 모든 waiter가 같은 cache line을 spin한다는 것입니다. unlock 시점에 now_serving이 갱신되면 모든 waiter의 cache line이 invalidate됩니다. 수십 core가 기다리면 매 unlock마다 broadcast invalidation이 폭주합니다. 4~8 core까지는 견딜 만하지만 그 이상은 한계가 옵니다.

#MCS Lock — Per-CPU Cache Line

MCS lock은 waiter마다 자기 cache line에서 spin하도록 설계되었습니다. 1991년 Mellor-Crummey와 Scott가 제안한 구조입니다.

1
typedef struct mcs_node {
2
    struct mcs_node *next;
3
    atomic_int       locked;
4
} mcs_node_t;
5

6
typedef struct {
7
    atomic_uintptr_t tail;   /* 마지막 waiter의 node 주소 */
8
} mcs_lock_t;
9

10
void mcs_lock(mcs_lock_t *l, mcs_node_t *me) {
11
    me->next = NULL;
12
    me->locked = 1;
13
    mcs_node_t *prev = (mcs_node_t*)atomic_exchange_explicit(
14
        &l->tail, (uintptr_t)me, memory_order_acq_rel);
15
    if (prev != NULL) {
16
        prev->next = me;
17
        while (atomic_load_explicit(&me->locked,
18
                                    memory_order_acquire)) {
19
            cpu_relax();
20
        }
21
    }
22
}
23

24
void mcs_unlock(mcs_lock_t *l, mcs_node_t *me) {
25
    if (me->next == NULL) {
26
        mcs_node_t *expected = me;
27
        if (atomic_compare_exchange_strong_explicit(
28
                &l->tail, (uintptr_t*)&expected, 0,
29
                memory_order_release, memory_order_relaxed)) {
30
            return;
31
        }
32
        while (me->next == NULL) cpu_relax();
33
    }
34
    atomic_store_explicit(&me->next->locked, 0,
35
                          memory_order_release);
36
}

각 waiter가 자기 node의 locked 필드를 spin합니다. unlock은 바로 다음 waiter의 cache line만 invalidate합니다. broadcast가 없어집니다.

Linux kernel의 qspinlock(4.2+)이 MCS 변형입니다. 64 core 시스템에서 ticket lock 대비 10배 이상 빠른 결과가 보고되어 있습니다. embedded 4 core 환경에서는 ticket lock으로도 충분하지만, 인식해 둘 가치는 있습니다.

#ESP-IDF portMUX_TYPE — RTOS 통합 예

ESP32(dual core)의 ESP-IDF는 FreeRTOS SMP variant 위에서 portMUX_TYPE을 제공합니다.

1
#include "freertos/FreeRTOS.h"
2
#include "freertos/task.h"
3

4
static portMUX_TYPE mux = portMUX_INITIALIZER_UNLOCKED;
5

6
void critical_section(void) {
7
    portENTER_CRITICAL(&mux);
8
    /* 수십 cycle짜리 짧은 작업 */
9
    shared_counter++;
10
    portEXIT_CRITICAL(&mux);
11
}

portENTER_CRITICAL이 spinlock acquire + IRQ disable을 한 번에 처리합니다. ISR 컨텍스트에서는 portENTER_CRITICAL_ISR을 씁니다. 내부 구현은 LDREX/STREX 기반의 ticket-like lock입니다.

#Spinlock vs Mutex — 결정 기준

규칙은 단순합니다. 기다리는 시간이 context switch 비용보다 짧으면 spinlock, 그렇지 않으면 mutex입니다. context switch 비용이 ~1 µs라면 그보다 짧은 critical section만 spinlock이 합리적입니다.

#Spinlock 측정 — Cortex-A72 4 core

uncontended와 contended 시 acquire latency 차이를 측정한 예입니다.

contention 환경에서 기본 test-and-set이 가장 비싸고, MCS가 가장 우수합니다. 다만 MCS는 per-waiter node가 필요하므로 ISR에서 쓰기 까다롭습니다. embedded 4 core 환경의 현실적 선택은 TTAS + IRQ disable 또는 ticket lock입니다.

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

경고 — LDREX와 STREX 사이에 다른 memory access

1
ldrex r1, [r0]
2
ldr   r2, [r3]    @ ← exclusive monitor가 clear됨 — STREX 항상 실패
3
strex r3, r2, [r0]

LDREX와 STREX 사이는 반드시 짧고 단순해야 합니다. 함수 호출, 다른 memory access, IRQ 진입이 들어가면 exclusive monitor가 깨져 무한 retry에 빠집니다.

경고 — Acquire/Release barrier 누락

1
spin_lock(&l);
2
shared = 42;            /* barrier 없으면 다른 core가 늦게 봄 */
3
spin_unlock(&l);

unlock 직전에 release barrier가 없으면 shared = 42 write가 unlock store보다 뒤로 reorder될 수 있습니다. memory_order_release를 명시하면 컴파일러가 적절한 DMB ISH를 삽입합니다.

경고 — Spinlock 안에서 sleep/block

1
spin_lock(&l);
2
xQueueReceive(q, &msg, portMAX_DELAY);   /* ← 다른 core 전원 대기 */
3
spin_unlock(&l);

spinlock은 짧은 critical section 전용입니다. block이 가능한 RTOS API를 spinlock 안에서 호출하면 모든 core가 멈춥니다. 이런 패턴이 의심되면 mutex로 교체합니다.

경고 — Nested lock의 ordering 무시

1
core 0: spin_lock(&a); spin_lock(&b);
2
core 1: spin_lock(&b); spin_lock(&a);
3
                                       /* → SMP deadlock */

두 lock 이상을 잡을 때는 전역 ordering 규칙을 정해 두고 모든 코드에서 같은 순서로 잡아야 합니다. lock address 오름차순이 가장 흔한 규칙입니다.

#정리

• ARMv7 SMP spinlock의 뼈대는 LDREX/STREX + DMB 두 가지로, exclusive monitor가 atomic을 보장합니다.
• ARMv8.1 LSE의 CASAL은 단일 명령 atomic으로 contention 환경에서 큰 이득을 줍니다.
• <stdatomic.h>의 memory_order_acquire/release로 barrier가 명시된 휴대성 있는 코드를 만들 수 있습니다.
• TTAS는 cache line을 shared로 유지하며 spin해 bus traffic을 줄입니다.
• WFE/SEV는 spin 중 core를 sleep시켜 전력을 아낍니다.
• ticket lock은 FIFO 공평성을, MCS lock은 per-CPU cache line으로 broadcast invalidation 회피를 제공합니다.
• spinlock과 mutex의 결정 기준은 critical section이 context switch 비용보다 짧은가입니다.

다음 편은 4-09 Software Timer에서 daemon task 기반 timer 구조를 다룹니다.

#관련 항목

• 3-01: Critical Section
• 3-09: ISR-Safe API
• 4-07: SMP RTOS 설계
• 4-09: Software Timer
• Perf Eng 4-04: Spinlock