Brain락-프리 자료구조 (Lock-Free Data Structures)
핵심 인사이트 (3줄 요약)
- 본질: 락-프리 (Lock-Free) 자료구조는 뮤텍스 없이 CAS (Compare-And-Swap) 같은 하드웨어 원자적 명령어만으로 동시성을 제어하여, 스레드 중 최소 하나는 항상 전진한다는 Live 보장을 제공한다.
- 가치: 뮤텍스의 스케줄러 암전(Preemption Under Lock), 우선순위 역전, 데드락 문제를 완전히 제거하며, 멀티코어 확장성이 극도로 높아 고성능 시스템에서 핵심 알고리즘으로 사용된다.
- 융합: Java의
ConcurrentLinkedQueue,LongAdder, Linux 커널의ring buffer, Go runtime의 goroutine 채널 내부, Rust std의Mutex-free 타입들이 락-프리 알고리즘 기반이다.
Ⅰ. 개요 및 필요성
전통적인 뮤텍스 기반 동기화의 핵심 문제는 스케줄러 암전 (Preemption Under Lock) 이다. 뮤텍스를 보유한 스레드가 선점당하면, 뮤텍스를 기다리는 모든 스레드가 선점된 스레드가 재실행될 때까지 차단된다. 이로 인해 최악의 경우 스레드 100개가 1개 스레드가 재실행되기를 기다리는 병목이 발생한다.
락-프리 알고리즘은 뮤텍스를 사용하지 않고 CAS (Compare-And-Swap) 루프로 갱신을 시도한다. 실패하면 재시도하므로, 하나의 스레드가 전진을 방해받아도 다른 스레드는 계속 진행한다.
💡 비유: 뮤텍스는 창구 줄서기 — 앞 사람이 느리면 모두 기다려야 한다. 락-프리는 팝업 스토어 재고 선점 — 빠른 사람이 먼저 가져가고, 늦은 사람은 재시도한다.
┌──────────────────────────────────────────────────────────┐
│ 락-프리 vs 뮤텍스 기반 — 처리량 비교 │
├──────────────────────────────────────────────────────────┤
│ │
│ 처리량 │
│ ▲ │
│ │ [락-프리] │
│ │ ·········· │
│ │ ········· │
│ │ ······· │
│ │····· │
│ │ [뮤텍스] 경합이 증가하면 처리량 급락 │
│ │ ────────\────────────────────────────── │
│ │ \\ │
│ │ \────────────────── │
│ └──────────────────────────────────────▶ 스레드 수 │
│ │
│ 락-프리는 코어 수 증가에 선형적 확장성 유지 │
└──────────────────────────────────────────────────────────┘
📢 섹션 요약 비유: 락-프리는 교통경찰 없는 회전교차로 — 누군가 막혀도 다른 방향 차량은 계속 진행합니다.
Ⅱ. 아키텍처 및 핵심 원리
CAS 루프 기반 카운터
// C/C++ 원자적 카운터 (락 없음)
#include <stdatomic.h>
atomic_int counter = 0;
// 읽기-수정-쓰기를 원자적으로
atomic_fetch_add(&counter, 1); // counter++ 원자적
// CAS 기반 조건부 갱신
int expected = 5;
int desired = 10;
bool success = atomic_compare_exchange_strong(&counter, &expected, desired);
// counter == 5 이면 10으로 변경 → true 반환
// counter != 5 이면 실패, expected에 실제 값 저장 → false 반환
락-프리 스택 구현
┌──────────────────────────────────────────────────────────────┐
│ 락-프리 스택 Push 동작 (CAS 루프) │
├──────────────────────────────────────────────────────────────┤
│ │
│ Push(new_node): │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ do { │ │
│ │ head = atomic_load(&stack->head); │ │
│ │ new_node->next = head; // 새 노드를 head로 설정│ │
│ │ } while (!CAS(&stack->head, head, new_node)); │ │
│ └─────────────────────────────────────────────────────┘ │
│ │
│ 시나리오: T1과 T2 동시 Push │
│ │
│ 초기: [head → A] │
│ │
│ T1: head=A, new->next=A, CAS(A, B) → 성공 │
│ 상태: [head → B → A] │
│ │
│ T2: head=A (구 값), new->next=A, CAS(A, C) → 실패! │
│ (head가 이미 B로 변경됨) │
│ T2 재시도: head=B, new->next=B, CAS(B, C) → 성공 │
│ 상태: [head → C → B → A] │
│ │
│ 보장: 어느 시점이든 최소 1개 스레드는 Push에 성공 │
└──────────────────────────────────────────────────────────────┘
[다이어그램 해설] CAS 루프의 핵심은 "내가 읽은 값이 아직도 그대로인가"를 원자적으로 확인한 후 수정하는 것이다. T2가 실패했을 때 T1은 이미 성공했으므로 시스템 전체는 전진한다 — 이것이 락-프리의 Live 보장이다. 단, T2는 재시도해야 하므로 개별 스레드의 완료를 보장하지는 않는다 (Wait-free는 아님).
ABA 문제 — 락-프리의 핵심 함정
┌──────────────────────────────────────────────────────────┐
│ ABA 문제 발생 시나리오 │
├──────────────────────────────────────────────────────────┤
│ │
│ 초기: [head → A → B → C] │
│ │
│ T1: head 읽음 = A │
│ (CAS 전에 T1이 선점당함) │
│ │
│ T2: Pop A (head = B), Pop B (head = C) │
│ A를 재사용해 Push: head = A → C │
│ (A의 next는 이제 C, B는 해제됨!) │
│ │
│ T1: CAS(A, new) 성공! (head=A이므로) │
│ head = new → next는 B (이미 해제된 메모리!) │
│ → Use-After-Free 취약점! │
│ │
│ 해결: Tagged Pointer — 포인터에 카운터를 함께 저장 │
│ (A, tag=1) → (A, tag=2): CAS가 tag까지 비교하므로 실패 │
└──────────────────────────────────────────────────────────┘
[다이어그램 해설] ABA 문제는 값이 A→B→A로 바뀌었지만 CAS가 이 변화를 감지하지 못하는 현상이다. 해결법은 포인터와 함께 변경 카운터(tag)를 유지하는 Tagged Pointer 기법으로, 포인터 하위 비트(정렬 보장 영역)나 128비트 CAS(cmpxchg16b)를 활용한다. Java의 AtomicStampedReference가 이 패턴의 표준 구현이다.
📢 섹션 요약 비유: ABA 문제는 친구가 지갑을 빌렸다가 돌려줬는데, 그 사이에 내용이 바뀐 것을 모르고 "지갑이 그대로네"라고 착각하는 상황입니다.
Ⅲ. 융합 비교 및 다각도 분석
동시성 보장 수준 비교
┌──────────────────┬──────────────┬──────────────┬───────────────┐
│ 보장 수준 │ 블로킹 락 │ 락-프리 │ 웨이트-프리 │
├──────────────────┼──────────────┼──────────────┼───────────────┤
│ 데드락 가능성 │ 있음 │ 없음 │ 없음 │
│ 기아 가능성 │ 있음 │ 없음 │ 없음 │
│ 개별 완료 보장 │ 있음 │ 없음 │ 있음 │
│ 구현 복잡도 │ 낮음 │ 높음 │ 매우 높음 │
│ 실무 적용 │ 일반 목적 │ 고성능 큐/스택│ 하드리얼타임 │
└──────────────────┴──────────────┴──────────────┴───────────────┘
실무 적용 사례
- Java LongAdder:
AtomicLong보다 높은 처리량을 위해 내부적으로 셀 배열에 분산하여 CAS 충돌을 줄이는 락-프리 설계. - Linux kernel ring buffer:
kfifo는 단일 생산자-소비자 환경에서 락 없이 동작하는 lock-free FIFO. - Go channel 내부: goroutine 간 채널 통신의 기저가 CAS 기반 링 버퍼.
📢 섹션 요약 비유: 락-프리는 고속도로 요금소에서 하이패스 차선 — 멈추지 않고 통과하되, 충돌이 나면 재시도하는 시스템입니다.
Ⅳ. 실무 적용 및 기술사적 판단
실무 시나리오
- 고처리량 메시지 큐: 뮤텍스 기반 큐는 생산자-소비자 수 증가 시 락 경합으로 처리량 감소.
ConcurrentLinkedQueue(락-프리)는 코어 수 증가에 선형 확장. - 실시간 로그 수집: 락 없는 링 버퍼로 인터럽트 핸들러(생산자)와 로그 수집 스레드(소비자)가 뮤텍스 없이 통신, 지연 보장.
안티패턴
- ABA 무시: 포인터 재사용이 있는 환경에서 Tagged Pointer 없이 CAS 사용 → 희귀하지만 치명적 메모리 오류.
- 과도한 재시도 스핀: 극심한 경쟁 환경에서 CAS 루프가 계속 실패하면 CPU 낭비(라이브락). 백오프(Backoff) 전략 필요.
📢 섹션 요약 비유: 락-프리의 CAS 재시도 과도함은 마치 마트에서 계산대 자리를 잡으려고 계속 뛰어다니는 것 — 가끔 잠깐 쉬어가는(backoff) 전략이 오히려 전체 효율을 높입니다.
Ⅴ. 기대효과 및 결론
| 구분 | 뮤텍스 | 락-프리 CAS |
|---|---|---|
| 데드락 위험 | 있음 | 없음 |
| 코어 확장성 | 경합 급증 | 선형 확장 |
| 구현 난이도 | 낮음 | 높음 (ABA 등 함정) |
| 최적 환경 | 일반 동기화 | 고성능 생산자-소비자 |
📌 관련 개념 맵
| 개념 | 관계 |
|---|---|
| CAS (Compare-And-Swap) | 락-프리의 핵심 하드웨어 원시 연산 |
| ABA 문제 | 락-프리 포인터 조작의 핵심 함정 |
| 웨이트-프리 (Wait-free) | 락-프리보다 강한 개별 완료 보장 |
| 메모리 순서 (Memory Order) | CAS 정확성을 위한 메모리 배리어 설정 |
| Java LongAdder | 락-프리 분산 카운터의 실무 구현 |
👶 어린이를 위한 3줄 비유 설명
- 락-프리는 마트 쿠폰 선착순 — 자기 쿠폰을 먼저 잡으면 되고, 실패하면 다시 시도해요. 누군가는 항상 성공합니다!
- ABA 문제는 쿠폰 번호가 같지만 내용이 달라진 상황을 알아채지 못하는 버그예요 — 번호에 버전을 붙이면 해결돼요.
- 웨이트-프리는 더 강한 보장 — 모든 사람이 정해진 시간 안에 반드시 성공해요. 구현은 훨씬 어렵지만요!