40. 손수 짠 스핀락의 비원자 획득(check-then-set)으로 깨지는 상호 배제 (C#)

난이도 상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 손수 짠 스핀락의 비원자 획득(check-then-set)으로 깨지는 상호 배제 (C#)

난이도: 상

요약

Enter의 "잠겼는지 확인(A) → 안 잠겼으면 내가 잡는다"는 두 개의 분리된 연산이라 원자적이지 않다. 두 스레드가 동시에 _locked==false를 보고 둘 다 통과해 함께 임계구역에 진입한다(check-then-set TOCTOU). volatile은 가시성만 도울 뿐 이 경쟁을 막지 못한다. 결과적으로 상호 배제가 깨져 _value = _value + 1이 겹치며 갱신이 유실된다. 원자적 획득은 Interlocked.CompareExchange로 해야 한다.

문제점

분류: 비원자 락 획득(check-then-act) → 상호 배제 붕괴 + (부수적으로) 메모리 순서.
증상:
1. 이중 진입: 스레드 A·B가 거의 동시에 Enter. 둘 다 while(_locked)를 _locked==false로 통과하고, 둘 다 _locked=true를 쓴 뒤 동시에 임계구역. _value = _value + 1(load-add-store)이 인터리브되어 갱신 유실 → 최종값 < N*K.
2. 락 자체의 유실: 여러 스레드가 _locked=true를 겹쳐 써도 아무도 "내가 못 잡았다"를 모른다. 획득 성공 여부를 반환하지 않기 때문.
3. 메모리 순서(B): volatile은 C#에서 acquire/release 의미를 갖지만, 획득이 애초에 원자적이지 않으므로 순서 이전에 상호 배제가 무너진다. 스핀락은 lock에 acquire, unlock에 release 의미가 필요하다.
재현 조건: 다중 코어에서 두 스레드가 락 획득을 시도하는 시점이 겹칠 때. 코어가 많고 임계구역이 짧을수록 자주.
근본 원인: "확인"과 "설정"이 분리된 비원자 연산. 상호 배제는 "비었으면 원자적으로 잡기"라는 단일 원자 read-modify-write로만 성립한다. 두 명령으로 나누면 그 사이 다른 스레드가 끼어든다.

수정안

Interlocked.CompareExchange로 "0(false)이면 1(true)로 원자 교체, 성공한 스레드만 진입"하게 한다.

public sealed class SpinLockFixed
{
    private int _state; // 0=free, 1=held

    public void Enter()
    {
        // 원자적으로 0->1 교체에 성공한 스레드만 획득. 실패하면 스핀.
        while (Interlocked.CompareExchange(ref _state, 1, 0) != 0)
        {
            // 경합 완화: 스핀 힌트/양보
            Thread.SpinWait(1);
        }
        // Interlocked 는 full barrier → 이후 임계구역 읽기에 acquire 효과
    }

    public void Exit()
    {
        // release: 임계구역 쓰기를 먼저 커밋한 뒤 해제 공개
        Volatile.Write(ref _state, 0);
    }
}

핵심: 획득을 단일 원자 CAS로 만들어 오직 한 스레드만 0→1에 성공하게 한다. CompareExchange는 full memory barrier라 임계구역 진입에 acquire 효과를 주고, Volatile.Write로 해제 시 release를 보장한다.

더 나은 설계

표준 프리미티브 우선: .NET의 System.Threading.SpinLock(정확·경합 관리 내장), 또는 짧은 임계구역이라도 대개 lock(Monitor)이 안전하고 충분하다. 손수 짠 스핀락은 버그 원천이다.
원자 연산으로 락 자체를 제거: 카운터라면 락을 없애고 Interlocked.Increment(ref _value) 한 줄이면 정확·최속. "락으로 보호하는 대상이 단일 변수"면 락보다 원자 연산이 정답.
경합 시 백오프: 스핀락은 코어 수보다 스레드가 많거나 임계구역이 길면 CPU를 낭비하고 성능이 급락. SpinWait/지수 백오프, 그리고 일정 스핀 후 블로킹으로 전환.
TTAS: 순수 test-and-set은 캐시 라인 경합이 심하다. test-and-test-and-set (먼저 read로 스핀하다 풀렸을 때만 CAS)으로 버스 트래픽을 줄인다.

면접 포인트

"왜 while(_locked){} _locked=true;가 틀렸나?" → 확인과 설정이 분리된 비원자 연산이라 두 스레드가 동시에 통과한다. 상호 배제는 단일 원자 RMW(CAS/test-and-set)로만.
"volatile 이면 되지 않나?" → volatile은 가시성/순서를 도울 뿐 원자적 read-modify-write를 제공하지 않는다. 획득의 원자성은 Interlocked가 담당.
"스핀락 vs 뮤텍스?" → 임계구역이 매우 짧고 경합이 낮으며 코어가 남을 때만 스핀락이 유리. 아니면 블로킹 뮤텍스. 그리고 대상이 단일 변수면 락 대신 원자 연산.

해설 · C++

해설 — 손수 짠 스핀락의 비원자 획득과 메모리 순서 결함 (C++)

난이도: 상

요약

lock()의 "잠겼는지 확인(A) → 비었으면 store(true)"은 두 개의 분리된 원자 연산이라, 그 사이 다른 스레드가 끼어든다. 두 스레드가 함께 false를 보고 둘 다 임계구역에 진입한다(check-then-set). 게다가 모든 연산이 relaxed(B)라 임계구역 읽기/쓰기가 락 경계 밖으로 재배열되어 가시성도 깨진다. 실측에서 8스레드×20만 증가가 기대 160만이 아니라 ~118만으로 나온다(상호 배제 붕괴). 획득은 단일 원자 exchange/CAS + acquire/release로 해야 한다.

재현 (8스레드 × 20만 증가로 실행하면)

expected = 1600000, got = 1178058   (실행마다 다름, 항상 < 1600000)
expected = 1600000, got = 1302744

(N=8, K=200000 워커로 Counter.increment 를 돌리면 상호 배제가 깨져 갱신이 유실된다.)

문제점

분류: 비원자 락 획득(check-then-set) → 상호 배제 붕괴 + 메모리 순서(relaxed) 오류.
증상:
1. 이중 진입: load로 false를 확인한 것과 store(true) 사이가 원자적이지 않다. 두 스레드가 같은 순간 false를 보고 둘 다 통과·둘 다 true 저장 → 동시 임계구역. g_value = g_value + 1(load-add-store) 인터리브로 갱신 유실.
2. relaxed 재배열(B): unlock의 store(false, relaxed)는 release가 아니라서, 임계구역 안의 쓰기가 락 해제 뒤로(또는 다음 획득의 acquire 없이) 재배열/미가시될 수 있다. 락이 있어도 "보호된 쓰기가 다음 소유자에게 온전히 보인다"는 보장이 없다.
재현 조건: 다중 코어에서 획득 시점이 겹칠 때. 코어가 많고 임계구역이 짧을수록 빈번.
근본 원인: 상호 배제는 "비었으면 원자적으로 잡기"라는 단일 read-modify-write로만 성립한다. 확인/설정을 두 명령으로 나누면 그 틈에 경쟁이 생긴다. 또 락은 lock에 acquire, unlock에 release 순서가 필요하다.

수정안

exchange(또는 CAS)로 획득을 원자화하고 acquire/release를 건다.

class SpinLock {
public:
    void lock() {
        // 원자적으로 true 로 바꾸고 '이전 값'을 본다. 이전이 false 였던 스레드만 획득.
        while (locked_.exchange(true, std::memory_order_acquire)) {
            // 이미 잠김: TTAS 로 캐시 라인 경합 완화 (풀릴 때까지 read 로 스핀)
            while (locked_.load(std::memory_order_relaxed))
                std::this_thread::yield();  // 또는 __builtin_ia32_pause / _mm_pause
        }
    }
    void unlock() {
        locked_.store(false, std::memory_order_release); // 임계구역 쓰기 커밋 후 해제 공개
    }
private:
    std::atomic<bool> locked_{false};
};

핵심: ① exchange(true, acquire)의 반환값(이전 상태) 으로 오직 한 스레드만 획득하게 만든다(단일 원자 RMW). ② acquire(lock)/release(unlock)로 임계구역이 락 경계 안에 갇히도록 순서를 보장한다. ③ 안쪽 load 스핀(TTAS)으로 경합 중 캐시 라인 무효화 폭풍을 줄인다.

더 나은 설계

표준/검증된 것 우선: std::mutex(짧은 경합엔 충분), C++20 std::atomic_flag의 test_and_set/wait/notify, 또는 잘 검증된 스핀락 라이브러리. 손수 짠 락은 버그 원천.
락 제거: 대상이 카운터 하나면 락 없이 g_value.fetch_add(1, relaxed) 가 정확·최속. "락으로 보호하는 게 단일 변수"면 원자 연산이 정답.
경합 시 백오프: 스핀락은 코어보다 스레드가 많거나 임계구역이 길면 CPU 낭비. pause/지수 백오프, 일정 스핀 후 블로킹 전환(하이브리드).
거짓 공유 회피: 락과 보호 데이터가 서로 다른 캐시 라인에 오도록 정렬.

면접 포인트

"while(load) {} store(true) 가 왜 틀렸나?" → 확인과 설정이 분리된 비원자 연산이라 두 스레드가 동시에 통과. 상호 배제는 단일 원자 RMW(exchange/CAS)로만.
"스핀락에 필요한 메모리 순서?" → lock에 acquire, unlock에 release. relaxed면 임계구역이 경계 밖으로 새어 가시성 보장이 없다.
"test-and-set vs test-and-test-and-set?" → 순수 TAS는 매 시도가 캐시 라인을 무효화해 경합 시 느리다. TTAS는 풀릴 때까지 read로 스핀하다 그때만 RMW 시도해 트래픽을 줄인다.

← 문제로 돌아가기