문제 18 해설 — 뮤텍스 내부 구현

난이도: 상

1. 무경합 경로(fast path)

현대 뮤텍스(glibc pthread_mutex, Windows SRWLOCK/CRITICAL_SECTION, C++ std::mutex)는 상태를 사용자 공간의 원자 변수 하나로 유지한다(예: 0=unlocked, 1=locked). 경합이 없으면 lock 은 커널을 전혀 부르지 않는다.

lock: CAS(state, 0 → 1) 한 번. 성공하면 끝. 실패(이미 1)면 slow path.
unlock: state = 0(적절한 메모리 순서로) + "대기자가 있으면" 깨우기.

무경합 락이 "거의 공짜"인 이유: 시스템 콜(수백~수천 사이클, 모드 전환·스케줄러 개입)이 없고, 한 번의 원자적 RMW(수~수십 사이클) + 메모리 배리어만 든다. 그래서 락 비용의 대부분은 경합과 캐시 라인 이동에서 온다.

2. 경합 경로와 futex

이미 잠긴 락을 다른 스레드가 CAS 로 못 얻으면, 바쁜 대기 대신 **커널에 "이 주소가 이 값인 동안 나를 재워달라"**고 요청해야 한다. Linux futex 가 이를 제공한다.

스레드가 state 를 "경합 있음(예: 2)"으로 표시하고 futex(FUTEX_WAIT, &state, expected) 호출 → 커널은 state == expected 를 원자적으로 확인하고 맞으면 그 주소에 매달린 커널 대기 큐에 스레드를 넣고 블록한다. 값이 이미 바뀌었으면 즉시 반환(놓친 깨우기 방지).
unlock 하는 스레드는 대기자가 있을 때만 futex(FUTEX_WAKE, &state, n) 로 하나(또는 n개)를 깨운다.

핵심은 **"경합이 있을 때만 커널로 내려간다"**는 점. 무경합이면 futex 호출 자체가 없다. 이 하이브리드(사용자 공간 CAS + 필요 시 커널 대기)가 pthread 뮤텍스의 본질이다. Windows 는 WaitOnAddress/WakeByAddressSingle 로 같은 개념을 제공한다.

3. 스핀 vs 블록, adaptive mutex

락을 못 얻었을 때 선택지:

즉시 블록(커널 대기): 컨텍스트 스위치 비용(수 μs, 캐시·TLB 오염). 임계 구역이 길거나 곧 안 풀릴 때 유리 — 그동안 CPU 를 남에게 양보.
스핀(사용자 공간 바쁜 대기): 컨텍스트 스위치 없음. 임계 구역이 매우 짧아 곧 풀릴 때 유리. 하지만 오래 스핀하면 코어를 낭비하고, 락 소유자가 다른 코어에서 실행 중이 아니면(선점됨) 영원히 헛돈다.

adaptive mutex: "짧게 스핀(수십~수백 사이클, 또는 소유자가 아직 실행 중인지 확인하며)하다가 안 되면 futex 로 블록". 임계 구역이 대체로 짧은 실제 워크로드에서 컨텍스트 스위치를 피하면서, 길어질 때는 CPU 를 양보한다. glibc 의 PTHREAD_MUTEX_ADAPTIVE_NP, 상당수 런타임의 기본 락이 이 전략을 쓴다.

4. 스핀락과의 경계

순수 스핀락(항상 바쁜 대기, 커널 대기 없음):

유리: 임계 구역이 극도로 짧고(수~수십 명령), 코어 수가 충분해 소유자가 다른 코어에서 계속 실행 중이며, 컨텍스트 스위치 비용이 임계 구역보다 훨씬 클 때. 인터럽트 핸들러·커널 내부·락프리 자료구조의 보조로 자주 쓰인다.
재앙: 임계 구역이 길거나, 코어보다 스레드가 많아 락 소유자가 선점(preempt) 되면 대기자들이 소유자가 스케줄될 때까지 코어를 태우며 헛돈다(특히 우선순위 역전: 낮은 우선순위 소유자가 높은 우선순위 스피너에 밀려 못 끝냄). 유저 공간 범용 락으로 순수 스핀락은 위험하다.
실무 절충: 바운디드 스핀 + 백오프(pause 명령) 후 블록. _mm_pause/YIELD 로 하이퍼스레드 형제에 양보하고 전력·경합을 줄인다.

5. 게임 서버 적용

아주 짧은 임계 구역(원자 카운터, 통계 증가, 플래그): 락 대신 원자적 연산(Interlocked/std::atomic fetch_add, CAS). 락 자체가 불필요.
짧은 임계 구역(락프리로 짜기 어려운 작은 자료구조 갱신, 큐 push/pop): 뮤텍스(adaptive) 또는 잘 검증된 바운디드 스핀락. 무경합 fast path 가 저렴하므로 기본은 뮤텍스로 시작하고 프로파일링으로 경합을 확인.
긴 임계 구역(DB 콜백 대기, 대용량 직렬화, 파일 I/O): 반드시 블로킹 뮤텍스(스핀 금지). 더 나아가 락을 잡은 채 I/O 를 하지 말고 임계 구역을 데이터 준비만으로 축소하거나, 작업을 큐로 넘겨 단일 소유 스레드가 처리(액터/샤드)해 경합 자체를 없앤다.
읽기 편중: shared_mutex(RW락) 또는 RCU/에포크 기반 락프리 스냅샷으로 읽기 경합 제거.

원칙: 경합을 측정한 뒤 고른다. 무경합이면 뮤텍스도 싸다. 경합이 심하면 락을 잘게 나누거나(샤딩), 임계 구역을 줄이거나, 자료구조를 락프리/단일 소유로 바꾸는 것이 락 종류 교체보다 효과가 크다.

핵심 요약

무경합 락 = 사용자 공간 CAS 한 번(거의 공짜). 비용은 경합·캐시 라인 이동에서 온다.
futex = "경합할 때만 커널로 내려가 대기/깨우기". 무경합이면 커널 호출 없음.
adaptive mutex = 짧게 스핀 후 블록. 순수 스핀락은 짧은 임계 구역·여유 코어에서만 안전, 선점되면 재앙.
짧으면 원자적/뮤텍스, 길면 블로킹 뮤텍스 + 임계 구역 축소/단일 소유.