URL: https://www.siliceum.com/en/blog/post/spinning-around/?s=r

빙글빙글 돌기: 제발 하지 마세요! - siliceum

Intro

1년도 채 안 되는 기간 동안 스핀 루프(spin-loop) 문제를 가진 프로젝트를 벌써 3번째로 보게 됐습니다. 저는 수년간 “돌고 있는(스핀하는)” 스레드들을 상대해 왔고, 솔직히 말하면 그동안 가해자이기도 했고 피해자이기도 했습니다.

같은 문제가 계속 반복되는 걸 보는 데 지쳤습니다. 보통 이런 때가 블로그 글을 쓰기 좋은 이유가 되죠. 사람들이 이 글을 읽고, 다른 사람들이 했던 실수를 또다시 반복하지 않기를 바랍니다.

사실 이 주제는 이미 많은 사람들이 다뤘습니다. 스핀 락과 관련된 다양한 이슈를 다룬 글들도 많고요123456. 그래도 이런 주제는 아무리 자료가 많아도 부족한 듯합니다. 어떤 글은 속도에 대해, 어떤 글은 공정성에 대해, 또 몇몇은 우선순위 역전(priority inversion), NUMA, 심지어는 실제로 깨진 코드에 대해서까지 다룹니다.

이 목록만으로도 스핀 락을 쓰면 일이 쉽게 “통제 불능으로 빙글빙글” 돌아간다는 것, 그리고 OS 프리미티브를 쓰는 편이 낫다는 점이 충분히 설득되지 않았다면 계속 읽어보세요. 여기서는 스핀 락을 직접 구현할 때 하지 말아야 할 것들을 다룹니다. 제가 “해야 할 것”이 아니라 하지 말아야 할 것이라 말한 걸 주목하세요. 왜냐하면 다시 한 번 말하지만, 요즘에는 스핀 락을 아마도 쓰지 않는 게 좋기 때문입니다.

그리고 정말로 써야 한다면… 당신이 무엇을 하는지 정말, 정말, 정말 잘 알고 있어야 합니다(스포일러: 가장 예상 못한 순간에 반드시 발목을 잡힙니다).

참고로 이 글은 스핀 루프 일반에 대한 이야기이지, 다양한 락킹 알고리즘 자체에 대한 이야기는 아닙니다(그쪽은 이미 많습니다5).

깨진 스핀 락

기본부터 시작해 봅시다. 여러분은 스핀 락을 직접 구현하고 싶습니다.

🤪 “쉽죠! 그냥 불리언 하나 두고 lock, unlock 함수 만들면 끝.”

그렇겠죠…

데모 목적상 bool 대신 int를 사용합니다. 락 상태에 메타데이터(예: 스레드 ID)를 넣는 등 더 복잡한 일을 할 수도 있으니까요. 또한 엄밀히 ‘스핀 락’을 구현하는 게 아니라 포인터 같은 다른 내용을 변경(mutate)하는 코드들도 꽤 있습니다.

cpp
class BrokenSpinLock
{
    // Using int32_t instead of bool on purpose, don't mind it.
    int32_t isLocked = 0;
public:
    void lock()
    {
        while (isLocked != 0) // (1)
        {
            // Loop again until not locked anymore
        }
                            // (2)
        isLocked = 1;       // (3)
    }                       // (4)

    void unlock()
    {
        isLocked = 0;
    }
};

멀티스레딩을 조금이라도 해본 사람이라면 즉시 문제를 알아챌 겁니다. 이 코드는 스레드 안전(thread-safe)하지 않습니다. 여러 스레드가 이 락을 사용하려고 하면 isLocked의 잘못된 값을 읽을 수 있습니다(이론적으로는, 그리고 CPU의 워드 크기에서 tearing이 발생할 수 있는 경우). 더 나쁜 건, tearing이 없더라도 치명적인 레이스 컨디션이 생길 수 있다는 점입니다.

예를 들어 두 스레드가 정확히 같은 시점에 lock을 호출하면:

text
(1) ThreadA: Sees `isLocked == 0` | ThreadB: Sees `isLocked == 0` 
(2) ThreadA: Leaves the loop      | ThreadB: Leaves the loop       
(3) ThreadA: Writes 1 to isLocked | ThreadB: Writes 1 to isLocked

이제 두 스레드 모두 “락을 잡았다”고 착각합니다!

또 어떤 사람은 atomic 변수/연산이라는 반짝이는 도구를 떠올릴지도 모릅니다.

아주 단순화해서 말하면: 원자적(atomic) 연산은 다른 스레드가 그 연산의 부분/중간 상태를 관찰할 수 없음을 보장하므로(해당 연산과 해당 메모리에서는) 레이스 컨디션이 발생할 수 없습니다.

💡 그리스어 atomos(“나눌 수 없는 것”)에서 이름을 따왔지만, atomic 연산은 원자력만큼이나 위험하고 다루기 어려울 수도 있습니다.

isLocked를 원자 버전인 std::atomic<int>로 바꿔봅시다. 데이터 자체에 대한 레이스 컨디션은 사라지지만, 여전히 isLocked를 1로 만든 스레드가 “락의 소유자”인지 알 수는 없습니다. 하지만 이제 exchange 연산을 원자적으로 수행할 수 있고, 이게 문제를 해결해 줍니다!

락이 잠겨있는지 먼저 확인한 다음 쓰는 대신, 단일 원자 연산으로 값을 “써버리고” 이전 값을 받아옵니다! 이전 값이 0이었다면 내가 실제로 락을 잡은 것이고, 1이었다면 이미 누군가가 잡고 있었거나 다른 스레드의 exchange가 내 것보다 먼저 끝난 겁니다.

cpp
void lock()
{
    while (isLocked.exchange(1) != 0) {}
}

시나리오를 다시 돌려봅시다. 두 스레드가 동시에 exchange를 실행하더라도, 원자성 덕분에 하나는 다른 하나보다 먼저 끝나게 됩니다. 예를 들어 B 스레드가 먼저 끝난다면:

text
ThreadA: `isLocked.exchange(1)` | ThreadB: `isLocked.exchange(1)` 
ThreadA: Writes 1, sees 1       | ThreadB: Writes 1, sees 0       
ThreadA: Writes 1, sees 1       | ThreadB: Now owns the lock!
ThreadA: ...                    | ThreadB: ... 
ThreadA: ...                    | ThreadB: `unlock()`, writes 0 
ThreadA: Writes 1, sees 0       | ThreadB: ... 
ThreadA: Now owns the lock!     | ThreadB: ...

좋습니다. 이제 동작하는 스핀 락이 됐지만, 갈 길은 멉니다.

💡 CPU 용어로, 메모리 read/write는 메모리 load/store라고 부릅니다.

CPU를 태워버린 스핀 락

우리 스핀 락은… 말 그대로 아무 것도 안 하면서 “스핀”합니다. 루프 바디가 비어있죠.

🤪 “좋네요, 더 빨리 락을 잡으려 하겠죠”

CPU를 태우고 싶다면야 그렇겠죠. CPU는 당신이 “대기” 중인지 의미 있는 일을 하는지 알 방법이 없어서 높은 주파수에 머무를 수 있습니다. 현대 CPU는 에너지 절약을 위해 코어 주파수를 바꾸고, 결과적으로 온도도 낮춥니다. 특히 모바일/임베디드 장치에서는 이런 행동이 явно 바람직하지 않습니다.

그래도 설득이 안 되나요, 혹은 지구 따위는 관심 없나요? (부끄럽네요!) 그럼 최소한 사용자 전기요금이라도 생각해 봅시다. 그래도 설득이 안 되나요? 루프에서 “뭔가”를 하는 게 오히려 더 빠를 수도 있다고 하면요?

많은 스레드가 동시에 이 스핀 락을 잡으려 한다고 상상해 보세요. 이길 수 있는 건 하나뿐입니다. 그런데 더 나쁜 건, 이 방식은 본질적으로 항상 메모리 쓰기(store)를 수행한다는 점입니다. 이는 CPU의 서로 다른 코어 간에 동기화되어야 합니다!

Intel 최적화 레퍼런스 매뉴얼3 11.4.2에서:

초스칼라 추측 실행 엔진을 가진 현대 마이크로프로세서에서 이런 루프는 스핀하는 스레드로부터 여러 개의 동시 read 요청을 발행하게 된다. 이 요청들은 보통 out-of-order로 실행되며, 각 read 요청은 버퍼 리소스를 할당받는다. 작업 스레드가 진행 중인 load에 대해 write를 수행하는 것이 감지되면, 프로세서는 메모리 순서 위반이 없음을 보장해야 한다. 대기 중인(outstanding) 메모리 연산들의 순서를 유지해야 하는 필요성은 필연적으로 프로세서에 큰 페널티를 부과하며, 이는 모든 스레드에 영향을 준다.

그리고 이 문제는 코어가 많은 최신 CPU, NUMA 메모리를 가진 CPU에서 더 커집니다.

이 페널티는 Intel Core Solo 및 Intel Core Duo에서 발생한다. 다만 이들 프로세서에서의 페널티는 Intel Xeon에서의 페널티에 비해 작다. Xeon에서는 루프를 빠져나오는 성능 페널티가 약 25배 더 심각하다.

SMT(하이퍼스레딩)를 켜면 더 나빠집니다:

Intel HT를 지원하는 프로세서에서 스핀 대기 루프는 프로세서 실행 대역폭의 상당 부분을 소모할 수 있다. 한 논리 프로세서가 스핀 대기 루프를 실행하면, 다른 논리 프로세서의 성능을 심각하게 악화시킬 수 있다.

이제 관심이 생겼기를 바라며, 이 문제를 해결 완화하는 방법을 보겠습니다.

이웃 코어를 “괴롭히지” 않는 최선의 방법은 스핀 루프를 피하는 것 CPU에 “대기 중이며 스핀 루프를 돌고 있다”는 걸 알려주는 것입니다! x86에서는 PAUSE 명령으로 합니다. 정확히 이 용도를 위해 설계됐습니다!

스핀 대기 루프에서 빠져나오는 페널티는 루프에 PAUSE 명령을 삽입함으로써 피할 수 있다. 이름과 달리 PAUSE는 루프에 약간의 지연을 도입하고 메모리 read 요청이 동기화 변수의 store를 즉시 감지할 수 있는 속도로 발행되게 만들어 성능을 향상시킨다. 이는 메모리 순서 위반으로 인한 긴 지연이 발생하는 것을 방지한다.

컴파일러 intrinsic으로 다음처럼 수정할 수 있습니다:

cpp
void cpu_pause()
{
#if defined(__i386__) || defined(__x86_64__) || defined(_M_IX86) || defined(_M_X64)
    _mm_pause();
#elif defined(__arm__) || defined(__aarch64__) || defined(_M_ARM) || defined(_M_ARM64) || defined(_M_ARM64EC)
    __yield();
#else
    #error "unknown instruction set"
#endif
}

void lock()
{
    while (isLocked.exchange(1) != 0)
    {
        cpu_pause();
    }
}

충분히 기다리지 않았던 스핀 락

앞서 말했듯, CPU 코어 간 데이터 동기화 비용은 코어가 늘고, 여러 코어 컴플렉스나 NUMA 아키텍처가 되면서 점점 비싸집니다. 여러 코어가 원자 store를 하려는 충돌을 완화해야 하죠. 전통적인 방법은 백오프(backoff) 전략을 사용해서, 락 시도 횟수가 늘어날수록 PAUSE 횟수를 늘리는 겁니다.

가장 흔히 쓰이는(Intel 최적화 매뉴얼 2.7.4에서도 권장하는) 방식은 지수(exponential) 백오프입니다:

cpp
void lock()
{
    const int maxPauses = 64; // MAX_BACKOFF
    int nbPauses = 1;
    while (isLocked.exchange(1) != 0)
    {
        for (int i = 0; i<nbPauses; i++)
            cpu_pause();
        // Multiply the number of pauses by 2 until we reach the max backoff count.
        nbPauses = nbPauses < maxPauses ? nbPauses * 2 : nbPauses;
    }
}

Intel의 설명:

PAUSE 명령 개수는 어떤 MAX_BACKOFF에 도달할 때까지 2배씩 증가하며, MAX_BACKOFF는 튜닝 대상이다.

rdtsc를 사용해 약간의 랜덤성(jitter)도 섞어봅시다. 그리고 yield 부분을 구조체로 리팩터링해서 쉽게 교체할 수 있게 하죠:

cpp
struct Yielder
{
    static const int maxPauses = 64; // MAX_BACKOFF
    int nbPauses = 1;
    void do_yield()
    {
        // jitter is in the range of [0;nbPauses-1].
        // We can use bitwise AND since nbPauses is a power of 2.
        const int jitter = static_cast<int>(__rdtsc() & (nbPauses - 1));
        // So subtracting we get a value between [1;nbPauses]
        const int nbPausesThisLoop = nbPauses - jitter;
        for (int i = 0; i < nbPausesThisLoop; i++) 
            cpu_pause();
        // Multiply the number of pauses by 2 until we reach the max backoff count.
        nbPauses = nbPauses < maxPauses ? nbPauses * 2 : nbPauses;
    }
}

void lock()
{
    Yielder yielder;
    while (isLocked.exchange(1) != 0)
    {
        yielder.do_yield();
    }
}

너무 오래 기다렸던 스핀 락

위에서 MAX_BACKOFF는 튜닝 대상이라고 했죠? 실제로 돌릴 CPU에 맞춰 튜닝해야 합니다.

다음 표는 PAUSE의 사이클 단위 측정값7입니다:

문제가 보이죠. 아키텍처에 따라 PAUSE 한 번당 사이클 수가 10배 이상 차이날 수 있습니다.

옛날 CPU는 Intel 기준 ~10 사이클, AMD 기준 ~3 사이클이었는데, 새 아키텍처에서는 Intel 100~160 사이클, AMD는 ~60 사이클입니다. 그리고 앞으로 더 나빠질 수도 있어요!

이건 최신 Intel 최적화 레퍼런스 매뉴얼3 2.7.4에도 들어갔습니다:

이전 세대 마이크로아키텍처에서 PAUSE의 지연은 약 10 사이클이었지만, Skylake Client 마이크로아키텍처에서는 최대 140 사이클까지 확장되었다.

어떻게 고치냐고요? Intel의 조언대로, 카운터가 아니라 CPU 사이클 기준으로 PAUSE 루프의 지속 시간을 제한합시다:

cpp
static inline bool before(uint64_t a, uint64_t b)
{
    return ((int64_t)b - (int64_t)a) > 0;
}
void pollDelay(uint32_t clocks)
{
    uint64_t endTime = _rdtsc()+ clocks;
    for (; before(_rdtsc(), endTime); )
        cpu_pause();
}

PAUSE 지연이 크게 증가했으므로 PAUSE 지연에 민감한 워크로드는 성능 손실을 겪을 수 있다.

[…]

Skylake Client 마이크로아키텍처에서는 RDTSC 명령이 현재 프로세서 클럭과 무관하게(즉 INVARIANT TSC 특성) 기계가 보장하는 P1 주파수로 카운트된다. 따라서 Intel® Turbo Boost 모드에서 실행될 때 지연은 일정하게 유지되지만, 실행될 수 있었던 명령의 수는 달라진다.

이를 구현해 봅시다:

cpp
struct Yielder
{
    static const int maxPauses = 64; // MAX_BACKOFF
    int nbPauses = 1;
    
    const int maxCycles = /*Some value*/;
    
    void do_yield()
    {
        uint64_t beginTSC = __rdtsc();
        uint64_t endTSC = beginTSC + maxCycles; // Max duration of the yield
        // jitter is in the range of [0;nbPauses-1].
        // We can use bitwise AND since nbPauses is a power of 2.
        const int jitter = static_cast<int>(beginTSC & (nbPauses - 1));
        // So subtracting we get a value between [1;nbPauses]
        const int nbPausesThisLoop = nbPauses - jitter;
        for (int i = 0; i < nbPausesThisLoop && before(__rdtsc(), endTSC); i++) 
            cpu_pause();
        // Multiply the number of pauses by 2 until we reach the max backoff count.
        nbPauses = nbPauses < maxPauses ? nbPauses * 2 : nbPauses;
    }
}

void lock()
{
    Yielder yield;
    while (isLocked.exchange(1) != 0)
    {
        yield.do_yield();
    }
}

이 방법은 주요 장점이 두 가지 있습니다:

• PAUSE 루프의 최대 지속 시간을 TSC 사이클로 정의합니다. 이는(대부분의 현대 CPU에서) 코어의 실제 주파수나 PAUSE 자체의 지속 시간과 독립적입니다.
• 운영체제가 루프 중간에 스레드를 선점(preempt)하더라도, 다시 스케줄되어 깨어났을 때 최대 지속 시간을 이미 넘었다면 yield를 멈춥니다. 그렇지 않으면 스레드가 깨어난 뒤 불필요하게 PAUSE를 더 많이 호출할 수 있습니다.

지수 백오프는 여전히 단순 카운터로 유지한 것을 볼 수 있습니다. PAUSE 한 번의 지속 시간을 계산하는 일을 피하기 위함입니다(그렇게 하려면 jitter를 없애야 할 겁니다). 다만 maxCycles 값을 선택해야 합니다. 이 역시 경험적으로 튜닝이 필요하지만, 컨텍스트 스위치 시간은 대략 3µs 정도라고 가정할 수 있습니다(시스템과 실제 스위치에 따라 더 크거나 작을 수 있지만, 대략 같은 자릿수일 겁니다). 3.2GHz라면 대략 3200cycles/µs로 변환할 수 있죠. TSC의 흔한 주파수로 2.5GHz도 있습니다. 물론 정확하진 않지만 PC에서의 기본값으로는 그럭저럭 괜찮은 추정입니다. 최악의 경우 실제값과 2배 정도 차이날 가능성이 큰데, PAUSE 지속 시간 변동으로 생길 수 있는 10배 오차보단 훨씬 낫습니다!

다만 이건 기본값일 뿐이고, 가장 좋은 건 OS에서 가져오거나 측정해서 실제 값을 얻는 것입니다. 아쉽게도 Linux/Windows는 TSC 캘리브레이션을 공식적으로 노출하지 않으므로, 시스템의 고해상도 클럭과 TSC를 비교해 측정하는 게 가장 낫습니다. 이상적으로는 비동기로 해야 합니다(애플리케이션 부팅 시 메인 스레드에서 하지 마세요 제발).

cpp
// Please, do this asynchronously and not during your main thread init
// Otherwise you will make your application boot longer for nothing!
// Note there are more accurate ways to do this, but we do not need a very high precision nor accuracy.
// You may also split this function in two and do some meaningful amount of work instead of sleeping.
uint64_t MeasureCyclesPerUs()
{
    const auto clockBefore = std::chrono::high_resolution_clock::now();
    const uint64_t cyclesBefore = __rdtsc();
    std::this_thread::sleep_for(std::chrono::microseconds{10});
    const auto clockAfter = std::chrono::high_resolution_clock::now();
    const uint64_t cyclesAfter = __rdtsc();
    const auto clockDelta = clockAfter - clockBefore;
    const uint64_t cyclesDelta = cyclesAfter - cyclesBefore;
    const uint64_t cyclesPerUs = (1000 * cyclesDelta) / std::chrono::nanoseconds(clockDelta).count();
    return cyclesPerUs;
}

💡 Windows는 커널 공유 데이터의 0x2D6 오프셋에 있는 CyclesPerYield로 이 값을 “노출”합니다. 동기화 프리미티브는 내부적으로 이 값을 사용해 몇 번의 PAUSE를 실행할지 결정합니다. 하지만 값 검증을 하지 않는 코드라면 이런 내부값을 쓰는 건 추천하지 않습니다.

장벽(barrier)을 너무 많이 쓴 스핀 락

atomic에 대해서는 아주 잠깐만 얘기했죠. 모든 원자 연산에는 선택적으로 메모리 오더 파라미터가 있습니다. 이 주제는 쉽지 않고 강연 하나가 통째로 들어갈 정도라 여기서 깊게 다루진 않겠습니다.

하지만 이것만은 알아두세요: 파라미터를 주지 않으면 std::memory_order_seq_cst(순차 일관성)을 쓰는 것과 같고, 이는 가장 강한 제약을 걸어줍니다. 어떤 플랫폼에서는 메모리 배리어로 캐시를 플러시하기도 합니다! 앞의 예시는 acquire/release로 다시 쓸 수 있습니다:

cpp
void lock()
{
    Yielder yield;
    while (isLocked.exchange(1, std::memory_order_acquire) != 0)
    {
        yield.do_yield();
    }
}

void unlock()
{
    isLocked.store(0, std::memory_order_release);
}

제 x64 머신에서 지수 백오프 기준:

컴파일러 익스플로러 예시에서 생성된 어셈블리를 볼 수 있습니다: https://godbolt.org/z/GjEEWPsj8

로드 포트를 포화시킨 스핀 락

스핀 락은 빨라야 합니다. 그렇지 않으면 그냥 일반적인 시스템 락을 쓰면 되죠. jitter와 지수 백오프로 코어 간 동기화를 완화했지만, 경쟁(contended) 상황에서 캐시 코히어런시8 트래픽을 줄이는 방법이 있습니다. 예전부터 많이 언급돼 왔고91011 다시 상기시켜도 나쁠 건 없습니다. Test-And-Set(=CAS)만 반복하지 말고, _Test_와 _Test-And-Set_을 함께 쓰는 편이 좋습니다! Load-And-Test(=Exchange)에도 동일하게 적용됩니다.

즉, 다음 대신:

cpp
void lock()
{
    Yielder yield;
    while (isLocked.exchange(1, std::memory_order_acquire) != 0)
    {
        yield.do_yield();
    }
}

이렇게 하세요:

cpp
void lock()
{
    Yielder yield;
    // Actually start by an exchange, we assume the lock is not already taken
    // This is because the main use case of a spinlock is when there's no contention!
    while (isLocked.exchange(1, std::memory_order_acquire) != 0)
    {
        // To avoid locking the cache line with a write access, always only read before attempting the writes
        do {
            yield.do_yield(); // Yield while we fail to obtain the lock.
        } while (isLocked.load(std::memory_order_relaxed) != 0);
    }
}

우선순위 역전을 처리하지 못한 스핀 락

우선순위 역전은 스핀 락에서 일어날 수 있는 최악의 일 중 하나입니다. 그리고 “가장 스핀 락이 필요한” 플랫폼에서 가장 치명적으로 터집니다!(임베디드, RTOS 등) 문제를 봅시다:

1. 낮은 우선순위 스레드가 스핀 락을 획득
2. 높은 우선순위 스레드가 락을 잡으려다 스핀 시작
3. OS 스케줄러가 낮은 우선순위 스레드를 선점하고, 중간/높은 우선순위(‘low’보다 높은 어떤 것이든) 다른 스레드를 실행
4. 남은 코어는 모두 높은 우선순위 스레드가 사용 중이라 낮은 우선순위 스레드를 실행할 코어가 없음
5. 높은 우선순위 스레드는 영원히 스핀하며 CPU 사이클을 태움

🤪 “std::this_thread::yield() 쓰면 되지 않나요?”

음… 여러 시스템에서 테스트해 보셨나요? 일단 해봅시다.

cpp
struct Yielder
{
    void do_yield_expo_and_jitter()
    {
        // Same as before, exponential backoff and jitter
    }

    void do_yield()
    {
        do_yield_expo_and_jitter();
        if (nbPauses >= maxPauses)
        {
            std::this_thread::yield(); // Yield thread back to the OS
            nbPauses = 1;
        }
    }
}

최대 반복 횟수에 도달하면 스레드가 OS에 양보하도록 합니다(Windows에선 SwitchToThread, Linux에선 sched_yield). 실제로는 가끔 이게 문제를 완화할 수도 있습니다. OS가 다른 스레드, 특히 낮은 우선순위 스레드를 스케줄할 여지를 주니까요. 하지만 필수로 그렇게 되는 건 아닙니다! 어떤 구현은 방금 yield한 스레드를 다시 스케줄할 수도 있습니다(우선순위가 더 높으니까요).

Windows에서 Sleep(0)를 쓰는 구현도 본 적 있을 겁니다. 이는 SwitchToThread보다 낫습니다. SwitchToThread는 문서에 따르면 현재 코어에서 실행 준비가 된 스레드에게만 양보할 수 있기 때문입니다12. (일반 Linux 스케줄러에서도 비슷합니다13.) 하지만 Sleep(0)는 예전에는14 같거나 더 높은 우선순위 스레드에게만 양보했고, 실시간(real-time) 버전 OS에서는 지금도 그렇습니다! 예를 들어 임베디드 장치나 콘솔 같은 곳이요. 실시간 커널(Windows든 Linux든)에서 우선순위와 상관 없이 어떤 스레드든 실행시키는 유일한 방법은 0이 아닌 시간으로 sleep하는 것인데… 당연히 우리는 그걸 피하고 싶죠!

그래서 DotNet 런타임 팀이 제시한 해법은 SwitchToThread 다음 Sleep(0), 그 다음 Sleep(1)을 섞는 것입니다!

text
// We prefer to call Thread.Yield first, triggering a SwitchToThread. This
// unfortunately doesn't consider all runnable threads on all OS SKUs. In
// some cases, it may only consult the runnable threads whose ideal processor
// is the one currently executing code. Thus we occasionally issue a call to
// Sleep(0), which considers all runnable threads at equal priority. Even this
// is insufficient since we may be spin waiting for lower priority threads to
// execute; we therefore must call Sleep(1) once in a while too, which considers
// all runnable threads, regardless of ideal processor and priority, but may
// remove the thread from the scheduler's queue for 10+ms, if the system is
// configured to use the (default) coarse-grained system timer.

즉 최악의 경우를(라이브락) 어느 정도 피하는 대신 잠재적 sleep 비용을 치른 셈입니다.

🤪 “배포하죠!”

제발 그러지 마세요… 네, 최악의 시나리오(라이브락)는 (아마) 피할 수 있겠지만, 정말 괜찮나요?

여기서 잠깐 멈추고, 우리가 절대로 sleep하지 않고 yield만 했다고 가정해 봅시다.

이미 눈치챘겠지만, 라이브락은 이야기의 절반일 뿐입니다(이거 계속 반복되는 패턴이죠?). 사실 이 문제는 모든 스레드의 우선순위가 같아도 발생할 수 있습니다! (우선순위를 없애면 해결될 거라 생각한 당신, 예상했습니다.) 다음 시나리오를 생각해 보세요:

• 4코어 머신
• 우선순위 높은 스레드 4개: A, B, C, D (당신의 스레드 풀)
• 우선순위 높은 스레드 4개: X, Y, W, Z (서드파티가 제어. 최악이죠. 라이브러리 작성자 여러분, 제발 임의로 스레드 만들지 마세요!)
• 스레드 A가 락을 획득
• B, C, D는 락을 잡으려 스핀

이때는 이렇게 됩니다:

• 스레드 X가 스케줄됨(A는 어떤 이유로 퀀텀을 양보했지만 락은 계속 잡고 있음)

• B가 yield, Y가 스케줄됨

• Y가 yield, B가 다시 스케줄됨. C, D는 yield해서 W, Z로 바뀜

이런 식으로 아주 오래 계속될 수 있습니다. 스레드 A가 다시 스케줄될 수도 있지만, 안 될 수도 있습니다! 스케줄러 내부에 달렸고, 특히 yield가 현재 코어의 ready 스레드로만 양보하는 구현이라면 더 그렇습니다1213. 이 글을 쓰는 시점에서 이것은 Address Sanitizer에서 알려진 이슈이기도 합니다!

그리고 설령 A가 다시 스케줄되더라도, 스레드 전환 비용으로 시간을 많이 잃었을 겁니다. 전형적인 lock convoy15죠. 리누스 토발즈가 아래에서 대략 말하는 것도 이겁니다41613:

그리고 아니, 스핀 락을 스핀하면서 랜덤하게 “sched_yield()”를 추가하는 건 사실 도움이 되지 않는다. 잘못된 프로세스들에게 yield하면서 스케줄링 폭풍(scheduling storms)을 쉽게 만들어낸다.

즉, 단순히 우선순위를 같게 하거나 sleep하는 건 답이 아닙니다. 다른 방법을 봅시다.

OS와 대화한 스핀 락

스핀 루프를 돈다는 건 “빠르게 끝날 것”을 기대하고 기다리는 것입니다.

하지만 그런 방식으로 yield를 해버리면 커널의 많은 휴리스틱을 무너뜨립니다. 커널은 당신 의도를 알 방법이 없어서, 당신 프로세스의 스레드가 아닌 어떤 것이든(혹은 아무것도) 스케줄할 수 있습니다. 더 나쁘게는 스레드 우선순위를 낮추거나, 저주파 코어로 옮기거나, 락이 풀리며 깨어날 때 받아야 할 우선순위 부스트를 잃을 수도 있습니다…

이건 우리가 원하는 게 아니죠. OS에 의도를 전달할 수만 있다면…

그게 바로 Linux가 futex API를 도입하며 한 일입니다! 값이 바뀌길 루프에서 기다리고 있으니, OS에 알려주고 이후는 OS가 처리하게 하자는 거죠. Windows도 WaitOnAddress API로 이를 제공합니다. 여기서는 Windows를 예로 듭니다:

cpp
void do_yield(int32_t* address, int32_t comparisonValue, uint32_t timeoutMs)
{
    do_yield_expo_and_jitter();
    if (nbPauses >= maxPauses)
    {
        // The thread will stay asleep while the value at the given address doesn't change and `WakeByAddressSingle`/`WakeByAddressAll` isn't called.
        // We might have a spurious wakeup though, so the value needs to be checked afterward, which we already do since we spin.
        WaitOnAddress(address, &comparisonValue, sizeof(comparisonValue), timeoutMs);
        nbPauses = 1;
    }
}
void lock()
{
    Yielder yield;
    while (isLocked.exchange(1, std::memory_order_acquire) != 0)
    {
        do {
            yield.do_yield(&isLocked, 1 /*while locked*/ , 1 /*ms*/);
        } while (isLocked.load(std::memory_order_relaxed) != 0);
    }
}
void unlock()
{
    isLocked = 0;
    WakeByAddressSingle(&isLocked); // Notify a potential thread waiting, if any.
}

Windows의 WaitOnAddress는 내부적으로 시스템 콜을 호출하기 전 단 한 번의 스핀을 수행하지만, Linux의 futex는 직접 시스템 콜입니다. 그래서 WaitOnAddress는 조금 스핀한 뒤에만 호출합니다.

이렇게 하면 플랫폼 전반에서 비슷한 스핀 전략을 가져갈 수 있어, 더 일관된 동작을 보장할 수 있습니다.

💡 위 코드는 대기 중인 스레드가 없어도 항상 WakeByAddressSingle을 호출하는 것을 볼 수 있습니다. Windows에서는 그리 느리지 않지만 Linux에서는 시스템 콜이라 느립니다. 이를 피하려면 보통 “대기 중(parked) 스레드 수” 같은 상태를 저장합니다.

🤪 “잠깐! 표준에 std::atomic_wait가 최근에 추가되지 않았나요?”

맞습니다! 구현자들이 처음부터 제대로 했고(더 중요한 건 모든 구현이 같은 방식으로 했고)… 그랬다면 이것을 썼어야 합니다. 하지만 현실은 아니었습니다…17

• libc++(clang)는 예전에는 futex 전에 thread yield 기반 지수 백오프를 했습니다. 2025년 1월에 수정되긴 했지만 여전히 지수 백오프를 합니다.
• MSVC STL은 첫 구현부터 OS로 거의 바로 들어가는(제 개인 의견으로) 올바른 방식™을 합니다. 잘했습니다!
• libstdc++(GCC)도 그렇습니다!

따라서 std::atomic_wait를 쓰더라도, 구현에 따라 내장 지수 백오프가 있을 수도 없을 수도 있습니다. 두 접근 모두 구현자 입장에서는 합리적일 수 있습니다(사용자가 자체 백오프 전략과 함께 쓸까요? 아니면 조건변수처럼 바로 쓸까요?). 하지만 이 차이는 구현 간 동작이 달라지는 문제를 만듭니다.

결국 std 라이브러리에서는 흔히 그렇듯, 제어 가능한 “진짜 휴대성(portable behavior)”을 원한다면 OS 프리미티브를 직접 쓰는 게 낫습니다.

앞서 말했듯 Windows의 WaitOnAddress는 시스템 콜 전에 한 번 스핀합니다. PAUSE 지속 시간은 프로세스 시작 시 로더가 LdrpInitializeProcess에서 계산해 ntdll.dll!RtlpWaitOnAddressSpinCycleCount에 저장합니다.

불공정했던 스핀 락

일부 락 알고리즘은 불공정할 수 있습니다. 경쟁 상태에서 특정 스레드가 다른 스레드들보다 느리면, 영원히 락 소유권을 얻지 못하는 경우죠.

이번에는 경고만 하고 넘어가겠습니다(글이 너무 길어지고 있으니까요). 공정성을 높이려고 하는 “티켓 락(ticket lock)”을 본 적이 있을 겁니다. 종이 위에서는 좋아 보이지만, 실제로는 그다지 좋지 않습니다.

복잡성 때문에 느릴 뿐 아니라, 앞서 말했듯 스케줄링에 무엇이 좋은지는 결국 OS만이 압니다. 그리고 futex 같은 API를 쓰려면 특정 스레드 하나만 깨우는 게 아니라 모든 대기자를 깨워야 하는 경우가 생깁니다. 그러니 공정성은 OS 프리미티브에 맡기세요. (설령 그런 프리미티브가 없더라도 랜덤+지수 백오프가 티켓 락보다 나을 수 있습니다!)

거짓 공유(false sharing)를 일으킨 스핀 락

CPU 아키텍처 상식 하나 더: 서로 다른 변수에 쓰더라도 같은 캐시라인을 공유할 수 있습니다! 그리고 서로 다른 주소라도 같은 캐시라인에서 원자 연산을 하면 성능에 정말 나쁩니다. 이를 해결하려면 변수 정렬(alignment)을 강제하거나 struct에 패딩을 넣을 수 있습니다. false sharing은 destructive interference로도 알려져 있고, 그래서 표준에 std::hardware_destructive_interference_size 같은 값이 생겼습니다!

cpp
alignas(std::hardware_destructive_interference_size) MyLock lock1;
alignas(std::hardware_destructive_interference_size) MyLock lock2;

하지만 이것도 만능은 아닙니다!

false sharing은 피하겠지만, TLB와 L1 캐시를 더 빨리 채워서 캐시 스래싱이 늘어날 수 있습니다.

캐시 뱅크 충돌(cache bank conflict)을 만날 수도 있습니다. 일부 CPU에만 존재하지만, 제조사가 알아서 피해준다고 믿지 마세요. Intel 최적화 매뉴얼 3.6.1.3에서:

• “Sandy Bridge 마이크로아키텍처에서 L1D 캐시의 내부 구성은 […]으로 드러날 수 있다.”
• “L1D 캐시 뱅크 충돌 이슈는 Haswell 마이크로아키텍처에는 적용되지 않는다.”
• “Golden Cove 마이크로아키텍처에서는 여러 load가 […]에 접근할 때 뱅크 충돌이 자주 발생한다.”

💡 즉, 한 번 문제가 됐다가 고쳐졌는데, 다른 형태로 다시 돌아왔습니다.

이런 문제는 랜덤+지수 백오프로 어느 정도 완화되지만, 점점 더 나빠지고 있습니다(여기까지 왔으면 이 “예, 하지만…” 패턴이 정말 짜증나야 정상입니다. 이 글의 목적이 그거예요).

가능하면 타이트한 루프에서 같은 메모리 위치를 반복해서 읽거나, 여러 load 연산을 사용하는 것을 피하라.

그리고 이를 진짜로 고치는 유일한 방법은… futex 같은 OS 프리미티브를 호출해서 스레드를 실제로 park(대기)시키는 것입니다! 또한 앞서 언급했듯 루프당 여러 번 load하는 것도 피해야 합니다(“로드 포트를 포화시킨 스핀 락” 절 참고).

특수 명령은 어떨까요?

🤪 “MWAIT랑 TPAUSE에 대해 읽어봤어요.”

더 읽었어야 했습니다. 저건 특권(privileged) 명령입니다! 다만 futex의 wait/wake와 비슷해 보이니 유혹적이긴 하죠. 공정하게 말하면 AMD는 유저 영역 대안으로 monitorx와 mwaitx를 제공하고, 이건 우리가 사용할 수 있습니다!

mwaitx의 장점 중 하나는 루프를 돌지 않고도 “주어진 TSC 카운트까지” CPU가 기다리도록 할 수 있다는 점입니다! 지원되는 환경에서는 _mm_pause 루프를 대체할 수 있고, 실제로 Windows의 WaitOnAddress나 AcquireSRWLockExclusive 같은 락 프리미티브가 내부적으로 이렇게 합니다! “API”도 더 쉽고(깨울 타임스탬프를 주면 됨) 전력도 아낄 수 있습니다19

다만 긴 시간에는 쓰지 마세요. OS에 명시적으로 양보하지 않기 때문에 다른 스레드의 일을 지연시키고 있기 때문입니다.

💡 mwaitx는 가끔 허위(spurious)로 깨어날 수 있지만, 우리는 깨어나면 다시 스핀해서 시도하면 되므로 이 용도에서는 괜찮습니다.

Conclusion

ARM은 거의 언급하지 않았는데, 제가 이 아키텍처 경험이 충분하지 않기 때문입니다. 다만 “적절한 메모리 오더링을 써서 성능을 확보하라” 정도만 말할 수 있겠습니다.

여기까지 읽었다면 다시 말하겠습니다. 대부분(거의 모든) 경우에 여러분은 락 성능을 걱정할 필요조차 없습니다. 최고의 락은 애초에 쓰지 않는 락입니다.

리누스의 말을 다시 인용하면4:

당신은 절대로 “내가 충분히 똑똑해서” 락킹 루틴을 직접 쓸 수 있다고 생각하면 안 된다. 왜냐하면 그럴 가능성은 거의 없기 때문이다(그리고 여기서 ‘당신’에는 나 자신도 포함한다. 우리는 커널 내부 락킹을 수십 년 동안 다듬어왔고, 단순 test-and-set에서 티켓 락, 캐시라인 효율적인 큐잉 락 등 여러 변천을 거쳤지만, 무엇을 하는지 아는 사람도 여러 번 틀리곤 한다).

락킹에 대해 수십 년치 학술 논문이 있는 데는 이유가 있다. 정말로. 어렵다.

그래도 모든 경고를 무시하고 하겠다면, 최소한 모범 사례를 따르고 스핀 락이 효율적이기 위한 전제조건을 만족시키세요:

• 경쟁이 낮다(low contention)
• 임계 구역(락 아래에서 수행하는 작업)이 매우 작다. (여기서 “작다”의 기준은 경쟁하는 스레드 수에 따라 달라집니다…)
• OS에 당신의 의도를 알린다(futex, WaitOnAddress 등)

Bonus!

제가 우연히 마주친, 잘못 구현했거나(혹은 과거에 그랬던) 프로젝트/라이브러리 목록:

• RPMalloc: 이 불평글의 계기가 된 녀석입니다. 콘솔에서 이를 사용하는 의존성이 있었는데 라이브락을 일으켰습니다. CPU yield 한 번만 하며 루프를 돕니다. 성능에도 나쁘고, 실시간 스케줄러를 가진 임베디드 플랫폼에서는 사용이 불가능(즉, 망가짐)합니다.

• OpenBSD libc: 곧바로 OS 스레드 yield로 갑니다.

• Glibc: 기본적으로 곧바로 futex로 갑니다.

  • 기본 mutex는 “simple”이며 값 한 번만 확인하고 곧바로 OS로 들어갑니다.
  • PTHREAD_MUTEX_ADAPTIVE_NP는 대부분 괜찮습니다! 기본 스핀 횟수는 고정이지만 tunable인 glibc.pthread.mutex_spin_count로 조정할 수 있습니다.

• Intel TBB:

  • tbb::spinlock: 16회 yield를 포함한 단순 백오프
  • tbb::mutex: 고정 카운트의 _mm_pause 백오프 후, 스레드 yield 백오프, 그 다음 Linux에선 futex wait, 다른 플랫폼에선 세마포어

• Webkit:

  • CAS 실패 시 OS Thread yield (SwitchToThread/sched_yield)
  • 하드코딩된 스핀 카운트
  • 여기에도 중복
  • 여기에도 동일
  • 속도/공정성 벤치마크가 있음에도!

• AddressSanitizer (ASAN)

  • 이슈 => 실시간 스케줄러에서 라이브락 가능
  • 구현
  • Linux에선 sched_yield, Windows에선 Sleep(0)

• DotNet 런타임은 여전히 WaitOnAddress 대신 Sleep을 사용

• 그리고 더 많은 것들…

Footnotes

1. Measuring Mutexes, Spinlocks and how Bad the Linux Scheduler Really Is - Malte Skarupke ↩

2. Spinlocks Considered Harmful - matklad ↩

3. Intel® 64 and IA-32 Architectures Optimization Reference Manual↩↩2↩3

4. Linus Torvalds on spinlocks (1) - Real World Technologies Forum ↩↩2↩3

5. Lock–Unlock: Is That All? A Pragmatic Analysis of Locking in Software Systems - Rachid Guerraoui, Hugo Guiroux, Renaud Lachaize, Vivien Quéma, Vasileios Trigonakis. ACM Transactions on Computer Systems, 2019, pp.1-149. ↩↩2

6. Spin Locks Considered Harmful, and How to Write Them When We Must - Intel (via The Wayback Machine) ↩

7. uops.info table for PAUSE↩

8. Cache coherency primer - Fabian Giesen ↩

9. AMD Ryzen Processor Software Optimization (GDC 2024) - Ken Mitchell ↩

10. AMD RYZEN™ Cpu Optimization (GDC 2018) - Ken Mitchell & Elliot Kim ↩

11. Correctly implementing a spinlock in C++ - Erik Rigtorp ↩

12. SwitchToThread docs - Microsoft ↩↩2

13. Linus Torvalds on spinlocks (3) - Real World Technologies Forum ↩↩2↩3

14. Sleeping vs. Yielding - Ken Henderson ↩

15. A Complete Guide to Lock Convoys - Dave Kilian ↩

16. Linus Torvalds on spinlocks (2) - Real World Technologies Forum ↩

17. Implementing atomic wait and notify - Blat Blatnik ↩

18. SpecialK’s commit automating mwaitx’s usage - Andon M. Coleman ↩

19. An Analysis of User-space Idle State Instructions on x86 Processors - Malte-Christian Kuns, Hannes Tröpgen, Robert Schöne. ICPE ‘25: Proceedings of the 16th ACM/SPEC International Conference on Performance Engineering, 2025, pp.232-239. ↩

Written by

Clément GRÉGOIRE

Performance & Optimization Expert

View profile