47. 2-스레드 상호 배제의 StoreLoad 재배열: acquire/release로는 부족 (C#)

난이도 최상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 2-스레드 상호 배제의 StoreLoad 재배열: acquire/release로는 부족 (C#)

난이도: 최상

요약

Peterson 알고리즘은 순차 일관(SC) 아래에서만 상호 배제가 증명된다. 이 구현은 Volatile.Write(release 의미)·Volatile.Read(acquire 의미)만 사용하는데, 이 조합은 Store→Load 재배열을 막지 못한다. 각 스레드의 "내 의사 게시(store)"와 "상대 의사 확인(load)" 사이가 재배열될 수 있어, 두 스레드가 서로의 _want 를 아직 false 로 보고 동시에 임계 구역에 진입한다.

문제점

분류 태그: StoreLoad 재배열 / 불충분한 메모리 순서(release·acquire ≠ 순차 일관)

증상: 대부분은 정상 동작하다가, 두 스레드가 거의 동시에 Enter 를 호출하는 드문 인터리빙에서 상호 배제가 깨져 공유 버퍼가 찢긴다(torn read/write, 스냅샷 오염, 산발적 크래시). 재현이 극히 어렵고 빌드·CPU·부하에 따라 빈도가 변한다.

재현 조건(핵심 인터리빙):

T0: _want[0]=true (A) 실행 → 그러나 CPU/JIT가 이 store 를 뒤의 load 보다 늦게 반영(store buffer 에 머묾).
T1: _want[1]=true (A) 실행 → 역시 store buffer 에.
T0: (B)에서 _want[1] 을 읽음 → 아직 false 로 관측(T1 의 store 가 전역 가시화 전) → 대기 없이 진입.
T1: (B)에서 _want[0] 을 읽음 → 역시 false → 진입.
결과: 둘 다 임계 구역.

근본 원인: release store 는 "그 이전 연산들이 이 store 보다 먼저 보이게" 하고, acquire load 는 "그 이후 연산들이 이 load 보다 늦게 보이게" 한다. 하지만 하나의 스레드에서 앞선 store 와 뒤따르는 load 사이의 순서(StoreLoad) 는 어느 쪽도 강제하지 않는다. .NET 메모리 모델에서도 Volatile.Write 다음 Volatile.Read 사이에는 전체 울타리가 없어, store 가 지연 가시화되면 위 인터리빙이 성립한다. 즉 "가시성"은 줬지만 SC가 요구하는 StoreLoad 순서를 주지 못한다.

수정안

의사 게시(store)와 상대 의사 확인(load) 사이에 전체 메모리 배리어를 넣어 StoreLoad 를 막는다.

public void Enter(int me)
{
    int other = 1 - me;

    Volatile.Write(ref _want[me], true);
    Volatile.Write(ref _turn, other);

    Interlocked.MemoryBarrier();   // 전체 울타리: 위 store 들이 아래 load 보다 먼저 전역 가시화

    while (Volatile.Read(ref _want[other]) && Volatile.Read(ref _turn) == other)
        Thread.SpinWait(1);
}

Interlocked.MemoryBarrier()(= Thread.MemoryBarrier())는 store buffer 를 비워 이후 load 가 최신 값을 보게 한다. 이로써 Peterson 이 가정하는 SC 순서가 복원되어 상호 배제가 성립한다.

더 안전한 실무 대안: 손수 짠 저수준 상호 배제를 쓰지 않는다. lock (Monitor) 나 SemaphoreSlim, 또는 단일 스레드로 소유권을 몰아주는 설계로 대체한다. 손수 구현은 이런 StoreLoad 함정 때문에 검증 비용이 매우 크다.

더 나은 설계

뮤텍스/락 사용: 핫패스라도 경합이 드물면 lock 의 비용은 무시할 만하다("드물게"라는 전제와 모순되는 최적화였다).
단일 소유 스레드: 공유 버퍼를 한 스레드가 소유하고 다른 스레드는 메시지/큐로 요청 — 상호 배제 자체가 사라진다.
더블 버퍼 + 원자 스왑: 읽기/쓰기 버퍼를 분리하고 원자적 포인터 스왑으로 교대하면 잠금 없이도 안전.
트레이드오프: 배리어를 정확히 넣은 Peterson 도 옳지만, 검증 난이도·유지보수 위험이 커 실무에선 표준 동기화 도구가 낫다.

면접 포인트

release/acquire 가 보장하는 순서(SS·LL·LS)와 보장하지 않는 순서(SL)를 구분해 설명.
Peterson 이 왜 SC를 전제로만 옳은지, Interlocked.MemoryBarrier() 가 무엇을 복원하는지.
"드물게 접근"하는 자원에 굳이 손수 짠 락을 쓴 최적화의 타당성 재평가.

해설 · C++

해설 — 2-스레드 상호 배제의 StoreLoad 재배열: release/acquire로는 부족 (C++)

난이도: 최상

요약

Peterson 알고리즘은 순차 일관(SC) 아래에서만 상호 배제가 증명된다. 이 구현은 memory_order_release store 와 memory_order_acquire load 만 쓰는데, 이 조합은 Store→Load 재배열을 허용한다. 각 스레드에서 "내 의사 게시(A)"와 "상대 의사 확인(B)" 사이가 재배열/지연 가시화되어, 두 스레드가 서로의 want_ 를 false 로 관측하고 동시에 임계 구역에 진입한다.

문제점

분류 태그: StoreLoad 재배열 / 불충분한 메모리 순서(acq-rel ≠ seq_cst)

증상: 상호 배제가 드물게 깨져 공유 버퍼가 찢기고(데이터 레이스, UB), 산발적 크래시·손상. TSan 은 임계 구역 내부 접근에서 data race 를 보고할 수 있다.

재현 조건: x86-64 는 하드웨어가 대체로 강한 순서를 주지만 StoreLoad 만은 재배열을 허용한다(store buffer). 따라서:

T0: want_[0].store(true, release) — store buffer 에 머묾.
T1: want_[1].store(true, release) — store buffer 에.
T0: want_[1].load(acquire) → 아직 false 관측 → 진입.
T1: want_[0].load(acquire) → 아직 false 관측 → 진입.
둘 다 임계 구역. ARM/POWER 같은 약한 모델에서는 더 쉽게 발생.

근본 원인: acquire/release 는 LoadLoad, LoadStore, StoreStore 는 정렬하지만 StoreLoad 는 정렬하지 않는다. 한 스레드에서 앞선 release-store 와 뒤따르는 acquire-load 는 서로에 대해 순서 보장이 없다. SC가 요구하는 전역 단일 순서를 얻으려면 이 지점에 seq_cst 강도가 필요하다.

수정안

방법 1 — 플래그·순번을 memory_order_seq_cst 로(기본값):

void enter(int me) {
    int other = 1 - me;
    want_[me].store(true, std::memory_order_seq_cst);   // 기본값이 seq_cst
    turn_.store(other, std::memory_order_seq_cst);
    while (want_[other].load(std::memory_order_seq_cst) &&
           turn_.load(std::memory_order_seq_cst) == other)
        std::this_thread::yield();
}

방법 2 — store 와 load 사이에 seq_cst 스레드 펜스:

want_[me].store(true, std::memory_order_release);
turn_.store(other, std::memory_order_release);
std::atomic_thread_fence(std::memory_order_seq_cst);   // StoreLoad 차단
while (want_[other].load(std::memory_order_acquire) &&
       turn_.load(std::memory_order_acquire) == other) ...

seq_cst store/load 는 모든 seq_cst 연산에 대한 단일 전역 순서에 참여하므로, 한 스레드의 store 가 다른 스레드의 후속 load 이전에 순서지어져 Peterson 의 SC 전제가 복원된다. seq_cst 펜스는 x86 에서 대략 mfence(또는 locked 연산)로 낮아져 store buffer 를 비운다.

실무 권고: 직접 짠 락을 피하라. std::mutex 또는 단일 소유 스레드가 정답. "핫패스에서 뮤텍스 회피"는 접근이 드물다는 전제와 모순된다.

더 나은 설계

std::mutex / 단일 소유 스레드 / 더블 버퍼 원자 스왑 — 상호 배제 자체를 없애거나 표준 도구로.
정적 검증: 손수 짠 동기화는 TSan + 스트레스 + (가능하면) 모델 체킹(CDSChecker 등) 없이는 신뢰 불가.
트레이드오프: seq_cst 는 acq-rel 보다 약간 비싸지만(펜스/락 연산), 상호 배제의 정확성과 맞바꿀 수 없다. x86 에서 비용은 대개 무시할 만하다.

면접 포인트

acquire/release 가 정렬하는 3쌍과 정렬하지 못하는 StoreLoad 를 구분.
왜 x86 이라도 store buffer 때문에 StoreLoad 재배열이 남는가, mfence/seq_cst 가 무엇을 하는가.
atomic_thread_fence(seq_cst) vs 모든 접근을 seq_cst 로 두는 것의 차이와 비용.

← 문제로 돌아가기