확장 가능한 락: 스핀락의 한계와 티켓·MCS·CLH 락, 백오프 · 해설

난이도: 상

1. 단순 스핀락과 캐시 일관성 붕괴

test-and-set(TAS): while (atomic_exchange(&lock, 1) == 1) {} — 락 변수에 계속 원자 쓰기를 시도. 실패해도 매 시도가 쓰기라 그 캐시 라인을 자기 코어로 Exclusive/Modified 상태로 끌어온다. 여러 코어가 동시에 하면 라인이 코어 사이를 계속 오가는 캐시 라인 핑퐁이 발생, 인터커넥트가 포화된다.
test-and-test-and-set(TTAS): while (lock == 1) {} 로 먼저 읽기만 하며 대기하고, 0으로 보이면 그때 TAS를 시도. 스핀 중에는 라인이 각 코어의 Shared 상태로 캐시돼 로컬 읽기라 버스 트래픽이 없다. 락이 풀리는 순간(쓰기)에만 Shared 사본들이 Invalidate → 몰려서 TAS. 단순 TAS보다 훨씬 낫지만, 해제 때마다 모든 대기자의 라인이 무효화되어 코어 수 N에 대해 O(N) 트래픽이 남는다.
MESI 관점: 스핀락 성능의 핵심은 "대기 중 얼마나 자주 공유 라인을 무효화시키는가"다. 쓰기가 잦을수록 나쁘다.

지수 백오프: 실패할 때마다 대기 간격을 늘려(1,2,4,… 상한까지) 재시도 빈도를 줄인다 → 캐시 무효화·경합 완화. 트레이드오프: 락이 일찍 풀려도 백오프 중이면 늦게 잡아 지연 증가, 대기 순서가 무작위라 공정성 저하(기아 가능).
PAUSE(x86)/yield: 스핀 루프에서 파이프라인 힌트를 줘 하이퍼스레드 형제 코어에 자원을 양보하고 전력·메모리 오더 위반 페널티를 줄인다. PAUSE는 CPU 양보이지 스레드 양보가 아님. 경합이 길면 sched_yield/블로킹으로 넘어가야 한다.

동작: 두 카운터 next_ticket, now_serving. 락 요청 시 my = fetch_add(next_ticket,1), 그다음 while (now_serving != my) spin. 해제 시 now_serving++.
이점: FIFO 공정성 — 도착 순서대로 락을 얻어 기아가 없다(단순 스핀락은 순서 보장 X).
남는 문제: 모든 대기자가 동일한 now_serving 을 스핀한다. 해제로 now_serving이 바뀌면 모든 대기자의 캐시 라인이 무효화되고 전원이 다시 읽는다 → 해제당 O(N) 트래픽. 공정하지만 확장성은 TTAS 수준.

핵심 아이디어: 각 스레드가 자기만의 지역 노드에서 스핀하게 만들어, 해제 시 다음 한 명의 노드만 무효화한다 → 해제당 O(1) 트래픽. 대기자들이 서로의 스핀 위치를 공유하지 않는다.
MCS 락: 대기자들이 명시적 큐(연결 리스트)를 이룬다. 새 대기자는 자기 노드를 tail에 붙이고 자기 노드의 flag를 스핀. 락 보유자가 해제 시 자기 다음 노드의 flag를 풀어준다(직접 후계자 지정). 노드는 스레드가 소유(스택에 두기도). 큐가 tail→head로 이어짐.
CLH 락: 각 스레드가 직전(predecessor) 노드의 flag를 스핀. 자기 노드를 tail에 스왑으로 붙이고, 이전 노드가 풀리길 기다린다. 노드 소유권이 이동(내 predecessor 노드를 다음에 재사용) 하는 점이 MCS와 다르다. 원격 노드를 스핀하므로 NUMA에서는 MCS가 대체로 유리(항상 로컬 노드 스핀). CLH는 캐시 일관성 하드웨어에서 단순·효율적.
비용: 노드 관리(메모리/포인터), 구현 복잡도, API가 노드를 요구(획득/해제에 노드 전달). 공정성은 FIFO. 고경합·다코어에서 티켓/TTAS를 압도.

임계 구역이 수십 ns로 매우 짧고 경합 낮음: TTAS 스핀락 + PAUSE + 약한 백오프. 단순·빠름.
경합 높고 코어 많음(다수 워커가 같은 락): 공정성이 필요하면 티켓, 확장성까지 필요하면 MCS/CLH. NUMA면 MCS.
임계 구역이 길거나 블로킹 I/O 포함: 스핀은 코어를 태우므로 OS 뮤텍스(futex 기반, 적응형: 잠깐 스핀 후 잠듦)가 정답.
근본적 고경합: 락 자체를 줄이는 샤딩/락 스트라이핑/락프리/RCU로 설계 전환.
스핀락의 위험: 스레드 수 > 코어 수(오버서브스크립션)거나 선점형 스케줄러에서 락 보유자가 선점되면, 대기 스레드들이 CPU를 태우며 무의미하게 도는데 정작 보유자는 실행되지 못한다 (convoy/우선순위 역전 악화). 이 환경에선 스핀 대신 양보/블로킹이 필수. 실시간 틱 루프에서 스핀락은 "코어 전용 배치 + 아주 짧은 임계 구역"이 보장될 때만.

캐시 일관성 하드웨어에서 "여러 코어가 한 주소를 스핀"하면 그 주소 쓰기 한 번이 O(N) 무효화를 부른다. MCS/CLH는 각자 다른 주소(지역 노드)를 스핀하므로 해제가 정확히 후계자 한 명만 건드린다 — 이것이 다코어 확장성의 핵심이다.