Lock-Based, Lock-Free, Wait-Free Program

References

• Ch6, The Art of Writing Efficient Programs

Contents

• Amdahl's Law
• Compare-And-Swap (CAS)
• Lock-based, Lock-free, and Wait-free Programs
• Spinlock
• Deadlock, Livelock, Convoying

---

포스팅에서 사용되는 전체 코드는 link를 참조

 

 

Memory Model (Memory Order and Barrier)

지난 포스팅에서는 동시성 프로그램의 성능에 영향을 미치는 기본 요소에 대해서 살펴봤다. 이번 포스팅에서는 이를 실제로 활용하고 스레드로부터 안전한 프로그램을 위한 방법을 살펴본다.

 

동시성을 최대로 활용하려면 문제와 해결 전략을 고수준의 관점에서 살펴봐야 한다. 사용할 자료구조, 작업을 분할하는 방법, 때로는 솔루션을 구성하는 요소에 대한 정의조차 성능에 결정적인 영향을 미친다. 성능은 캐시에서 데이터의 배열과 같은 저수준의 요소에 의해 크게 영향을 받으며, 아무리 좋은 디자인이더라도 잘못된 구현으로 성능이 나빠질 수 있다. 이러한 저수준의 세부 정보는 분석하기 어려우며, 코드로 표현하기도 어렵기 때문에 매우 신중해야 한다. 따라서, 이러한 복잡성을 캡슐화할 최선의 방법을 고민해야 한다.

 

---

Amdahl's Law

기본적으로 동시성을 사용하여 성능을 향상시키는 것은 매우 간단하다. 실제로는 두 가지 작업만 수행해주면 된다. 첫 번째는 동시 스레드와 프로세스가 항상 바쁘도록 충분한 작업을 수행하는 것이다. 두 번째는 공유 데이터의 사용을 줄이는 것이다. 이전에 살펴봤듯, 공유 변수에 동시에 액세스하는 것은 비용이 크다. 나머지는 구현의 문제일 뿐이다.

 

하지만, 구현은 일반적으로 상당히 어려운 경향이 있으며, 원하는 성능 향상이 크고 하드웨어가 더 강력하면 그 난이도는 더 높아진다. 이는 암달의 법칙(amdahl's law) 때문이다.

 

암달의 법칙 자체는 매우 간단하다. 이 법칙은 병렬 부분(확장 가능한 부분)과 단일 스레드로 수행해야 하는 부분이 있는 프로그램에서 최대로 얻을 수 있는 속도 향상을 알려준다.

\[s = \frac{s_0}{s_0 (1 - p) + p} \]

여기서 \(s_0\) 은 프로그램에서 병렬 부분의 속도이며, \(p\) 는 프로그램에서 병렬 부분이 차지하는 비율이다. 예를 들어, 256개의 코어가 있는 멀티프로세서 시스템에서 병렬 부분에 256개의 코어를 완전히 활용하지만(병렬 부분에서 256배의 속도 향상 기대), 프로그램 전체에서 병렬 부분이 차지하는 비율이 255/256이라면, 얻을 수 있는 전체 속도 향상은 전체 코어의 절반인 128배이다.

\[\frac{256}{ 256 (1 - \frac{255}{256}) + \frac{255}{256}} \simeq 128\]

즉, 프로그램의 1/256 정도의 비율만 순차적으로 단일 스레드에서 실행되고 나머지는 모두 병렬로 수행되는 경우, 이론적으로 256개의 코어를 모두 활용하여 최대 256배의 속도 향상을 하지만 병렬 부분을 아무리 최적화하더라도 얻을 수 있는 최대 속도 향상은 128배라는 것이다.

 

이러한 이유로 동시성 프로그램을 디자인하고 구현하고 최적화할 때, 단일 스레드에서의 계산을 동시에 수행하고 프로그램이 공유 데이터에 액세스하는 시간을 줄이는 데 초점을 맞추어야 하는 이유이다.

 

연산을 동시에 수행하도록 하기 위한 첫 번째 목표는 알고리즘 선택으로 시작된다. 하지만 설계 부분에서 결과에 영향을 많이 미치기 때문에 이에 대해서 많이 알아야 한다. 두 번째는 데이터를 공유하는 비용을 줄이는 것이다. 모든 스레드가 일부 공유 변수나 락에 액세스하기를 기다릴 때, 프로그램은 액세스 권한이 있는 단일 스레드로만 동작하는 것과 같다. 이 때문에 global lock이나 전역적으로 공유되는 데이터를 사용할 때 성능이 좋지 않다.

 

공유 데이터의 필요성은 근본적으로 풀고자 하는 문제 자체의 성격에 따라 결정된다. 특정 문제에 대해 사용해야 하는 공유 데이터의 크기는 알고리즘, 데이터 구조, 기타 설계 및 구현에 의해 크에 영향을 받을 수 있다.

 

따라서 두 가지 측면에서 살펴봐야 한다. 먼저, 일정 크기의 공유 데이터가 불가피하다는 점을 고려하여 프로세서를 보다 효율적으로 만드는 방법을 살펴봐야 한다. 그런 다음, 공유 데이터에 대한 액세스를 기다리는 데 소요되는 시간을 줄이는 설계 및 구현 기법을 고려해야 한다.

 

Locks and Alternatives

데이터 공유가 불가피한 경우에는 공유 데이터의 동시 액세스에서 동기화가 필요하다. 이러한 동기화없이 동일한 데이터에 동시에 액세스한다면 data race 및 undefined behavior이 발생하게 된다.

 

가장 기본적인 동기화 방법은 뮤텍스를 사용하는 것이다.

std::mutex m;
size_t count; // guarded by m
... on the threads ...
{
    std::lock_guard l(m);
    ++count;
}

위 코드는 C++17의 템플릿 타입 추론을 활용하고 있으며, C++17 이전 버전에서는 템플릿 타입 인자를 명시적으로 지정해주어야 한다.

 

뮤텍스를 사용하는 것은 간단하다. 공유 데이터에 액세스하는 모든 코드는 크리티컬 섹션 내에 존재해야 한다. 즉, 뮤텍스를 잠그고 해제하는 코드 사이에 존재해야 한다. 뮤텍스 구현에는 하드웨어나 컴파일러가 크리티컬 섹션 내의 코드를 크리티컬 섹션 밖으로 이동할 수 없도록 메모리 장벽(memory barrier)이 함께 제공된다 (컴파일러는 이러한 장벽을 만족하는 내에서 코드 이동 등의 최적화를 수행할 수 있다).

 

뮤텍스의 비용이 얼마나 큰 지 비교하기 위해서는 비교군이 필요하다. 뮤텍스 대신 사용되는 것 중 하나는 아토믹 변수를 사용하는 것이다.

std::atomic<size_t> count;
... on the threads ...
++count;

이전 포스팅(Memory Model (Memory Order and Barrier))에서 살펴봤듯이 아토믹 연산에 필요한 메모리 순서를 고려해야 한다. 나중에 카운터를 사용하여 배열에 인덱싱하는 경우에는 release-acquire memory order가 필요할 수 있다. 그러나 단지 카운트만 하고 마지막에 그 갯수만 리포트하는 경우라면 어떠한 메모리 순서 제약도 필요하지 않다. 그럼 아래와 같이 relaxed memory order를 지정할 수 있다.

count.fetch_add(1, std::memory_order_relaxed);

실제로 메모리 장벽이 있는지 여부는 하드웨어에 따라 다르다. x86 시스템에서 아토믹 증분 명령에는 bidirectional memory barrier가 내장되어 있기 때문에 relaxed memory order를 지정하더라도 실제로는 이를 사용하지 않으며, 따라서, 더 빨라지지 않는다. 다만, 이식성과 명확성을 위해 코드에 실제로 필요한 요구 사항을 지정하는 것이 중요하다.

 

아토믹 증분 연산에는 락이 없으며 필요하지도 않다. 이는 특정 하드웨어 기능에 의존하는데, 즉, 프로세서에 아토믹 증분 명령어가 있으면 된다. 하지만 지원하는 명령어는 제한적이다. 예를 들어, C++에는 atomic multiplication은 없는데, 일반적으로 이러한 명령어를 가진 하드웨어 또한 없다. 이런 경우에는 어떻게 할 수 있을까?

 

다행히, 다양한 연산에 대해서 read-modify-write 연산을 구현하는데 사용할 수 있는 일종의 보편적인 아토믹 연산을 지원한다. 이러한 연산을 compare-and-swap(CAS)라고 하며, C++에서는 compare_exchange라고 한다. 여기에는 두 개의 파라미터가 필요한데, 하나는 아토믹 변수의 현재 예상되는 값이고, 다른 하나는 원하는 새로운 값이다. 실제 아토믹 변수의 값이 현재 예상되는 값과 다르면 아무 일도 발생하지 않고, 아토믹 변수도 변경되지 않는다. C++의 compare_exchange는 아토믹 변수에 write가 발생했는지 여부를 bool 변수로 리턴한다. 또한, 아토믹 변수의 실제 값이 예상 값과 일치하지 않으면 실제 값이 첫 번째 파라미터에 반환된다. CAS를 사용하면 아래와 같은 방식으로 아토믹 증분 연산을 구현할 수 있다.

std::atomic<size_t> count;
... on the threads ...
size_t c = count.load(std::memory_order_relaxed);
while (!count.compare_exchange_strong(c, c + 1,
    std::memory_order_relaxed, std::memory_order_relaxed)) {}

C++에서 이에 대한 실제 함수 이름은 compare_exchange_strong이며, compare_exchange_weak도 있다. 둘의 차이점은 현재 값과 예상 값이 일치하는 경우에도 weak 버전이 때때로 false를 반환할 수 있다는 것이다 (x86 시스템에서는 둘의 차이가 없지만 일부 플랫폼에서는 weak 버전이 전체 작업을 조금 더 빨리 수행할 수 있다).

또한, 이 함수는 두 개의 메모리 순서를 지정하고 있다. 첫 번째로 지정되는 메모리 순서는 비교가 성공하고 write가 발생할 때 적용되는 것이며, 두 번째는 비교가 실패할 때 적용된다.

위 구현이 어떻게 동작하는지 천천히 살펴보자. 먼저 카운트의 현재 값인 c를 아토믹으로 읽는다. 그럼 증가된 값은 c+1이지만, 아토믹 변수를 읽은 후에 다른 스레드가 카운트를 증가시킬 수 있기 때문에 바로 할당할 수는 없다. 따라서 conditional write를 수행해야 한다. 카운트의 현재 값이 여전히 c라면 아토믹 변수에 증가된 값인 c+1로 바꾼다. 그렇지 않으면 c를 현재 아토믹 변수의 값으로 업데이트한 뒤, 다시 CAS를 시도한다. while 루프는 아토믹 변수를 마지막으로 읽은 순간과 업데이트하는 순간에 아토믹 변수가 변경된 상태가 아닐 때만 종료된다. 이러한 접근 방식으로 프리미티브 명령어로 제공되지 않는 아토믹 연산을 구현하여 동작시킬 수 있다.

 

위에서 살펴본 세 가지 버전(mutex, atomic, CAS)은 모두 동일한 작업을 수행하지만, 이들 사이에 근본적으로 어떠한 차이점이 있는지 살펴볼 필요가 있다.

Lock-Based, Lock-Free, and Wait-Free Programs

뮤텍스를 사용하는 버전이 매우 간단하다. 하나의 스레드가 언제든지 락을 유지할 수 있기 때문에 추가 조치없이 카운트를 증가시킬 수 있다. 락이 해제되면 다른 스레드가 락을 획득하고 카운트를 증가시킬 수 있다. 즉, 언제든지 최대 하나의 스레드만 락을 유지하고 카운트를 증가시킨다. 이것이 가장 빠르지는 않지만 이해하고 추론하기는 쉬운 일반적인 lock-based 프로그램이다.

 

두 번째, 아토믹 변수의 시나리오는 많이 다르다. 아토믹 증분 연산에 도달하는 모든 스레드들은 지연없이 이를 실행한다. 물론, 하드웨어 자체는 이 연산의 원사성을 보장하기 위해 다른 스레드에 의한 공유 데이터에 대한 액세스를 막는다 (이는 한 번에 하나의 프로세서에 전체 캐시 라인에 독점적인 액세스를 부여하여 수행된다). 프로그래머 관점에서 볼 때, 이러한 배타적인 액세스는 아토믹 연산을 실행하는데 걸리는 시간이 증가하는 것으로 나타난다. 이런 종류의 프로그램을 wait-free 라고 한다. Wait-free 프로그램에서는 모든 스레드가 항상 진행된다. Wait-free 구현은 일반적으로 매우 간단한 작업(카운트 증가와 같은)에서만 가능하지만, 가능하다면 lock-based 구현보다 훨씬 간단한 경우가 많다.

 

마지막 구현인 CAS에는 락이 없다. 그러나, 횟수를 알 수 없는 루프가 있다. 이러한 점에서 구현 자체는 락과 유사하다. 그러나 한 가지 주요한 차이점이 있다. Lock-based 프로그램에서는 스레드가 락 획득에 실패하여 다시 시도하는 경우, 다른 스레드가 락을 획득하고 있다고 추론할 수 있다. 해당 스레드가 조만간 락을 해제할 것인지, 실제로 작업을 완료하고 보유하고 있는 락을 해제하는 방향으로 진행 중인지 확신할 수 없다. 반면, CAS 기반 프로그램에서 스레드가 공유되는 카운트 업데이트하는데 실패하는 유일한 방법은 다른 스레드가 먼저 업데이트했기 때문이다. 따라서, 동시에 카운트를 증가시키려는 모든 스레드 중 하나가 항상 성공한다는 것을 알고 있다. 이러한 종류의 프로그램을 lock-free 라고 한다.

 

세 가지 타입의 동시 프로그램을 정리하면 다음과 같다.

• Wait-free 프로그램에서 각 스레드는 필요한 작업을 실행하고 있으며, 항상 진행 중이다. 액세스를 기다리거나 작업을 다시 수행할 필요가 없다.
• Lock-free 프로그램에서 여러 스레드가 동일한 공유 데이터 값을 업데이트하려고 시도할 수 있지만 그중 하나만 성공한다. 나머지는 원래 값을 기반으로 이미 수행한 작업을 취소한 뒤, 업데이트 값을 읽고 다시 수행해야 한다. 그러나 적어도 하나의 스레드는 항상 작업을 커밋하고 다시 실행할 필요가 없도록 보장된다. 따라서 전체 프로그램 속도가 최고 속도는 아니지만 프로그램은 항상 진행 중이다.
• Lock-based 프로그램에서는 하나의 스레드가 공유 데이터에 대한 액세스를 제공하는 락을 보유하고 있다. 하지만 락을 보유하고 있다고 해서 이 데이터로 무언가 작업을 수행한다는 의미는 아니다. 따라서, 동시에 액세스가 발생할 때, 적어도 하나의 스레드만 진행할 수 있지만 이것이 보장되지는 않는다.

세 프로그램의 차이점은 이론상 분명하다. 그렇다면 이 중 어느 것이 더 빠를까? 각 버전의 벤치마크를 통해 이를 측정해볼 수 있다.

std::atomic<unsigned long> xa(0);
void BM_atomic(benchmark::State &state) {
    std::atomic<unsigned long> &x = xa;
    for (auto _ : state) {
        benchmark::DoNotOptimize(++x);
    }
    state.SetItemsProcessed(state.iterations());
}

unsigned long x = 0;
std::mutex M;
void BM_mutex(benchmark::State& state) {
    if (state.thread_index() == 0) x = 0;
    for (auto _ : state) {
        std::lock_guard<std::mutex> L(M);
        benchmark::DoNotOptimize(++x);
    }
    state.SetItemsProcessed(state.iterations());
}

void BM_cas(benchmark::State& state) {
    std::atomic<unsigned long>& x = xa;
    if (state.thread_index() == 0) x = 0;
    for (auto _ : state) {
        unsigned long xl = x.load(std::memory_order_relaxed);
        while (!x.compare_exchange_strong(xl, xl + 1, std::memory_order_relaxed, std::memory_order_relaxed)) {}
    }
    state.SetItemsProcessed(state.iterations());
}

스레드 간 공유되어야 하므로 공유 데이터는 전역으로 선언된 것을 볼 수 있으며, 초기화 단계에서는 한 스레드에서만 수행되도록 한다. 위 벤치마크의 결과는 다음과 같다.

벤치마크 순서대로 atomic-based, mutex-based, lock-free 이다. 스레드 갯수가 4개 미만일 때 mutex-based가 성능이 가장 좋지 않지만, 스레드 갯수가 그 이상이 되면 lock-free 또한 성능이 mutex-based 만큼 좋지 않은 것으로 측정된다.

 

참고 문헌에서의 결과는 아래와 같이 리포트하고 있으며, mutex의 성능이 압도적으로 좋지 않다는 것으로 보여준다. 결과는 하드웨어에 따라서 조금씩 다른 것으로 보인다.

 

 

Spinlock

방금 벤치마크 결과를 통해 mutex-based의 성능이 매우 좋지 않다는 것을 확인할 수 있다(lock-free 또한 스레드 갯수가 많아지면 좋지 않음). 특히, 많은 스레드가 동시에 뮤텍스를 사용하여 공유 변수를 수정하려고 할 때, 성능은 매우 하락한다. 하지만, 이러한 성능의 원인은 구현의 문제일까, 아니면 락 자체에 내제된 문제일까 ? 우선 lock-based 에서는 락 자체에 공유 변수가 또 존재하기 때문에, 아토믹 카운터를 사용하는 경우보다 다소 비효율적이라고 예상할 수는 있다. 실제로 OS에서 제공하는 뮤텍스는 일반적으로 카운터를 증가시키는 아주 짧은 명령어에 대해서는 특히나 효율적이지 못하다.

모든 뮤텍스는 락이지만, 모든 락이 뮤텍스인 것은 아니다. 즉, 뮤텍스를 사용하지 않고 더 효율적인 락을 구현할 수 있다.

 

아주 간단한 증가 연산을 위한 효율적인 락 중 하나는 스핀락(spinlock)이다. 스핀락의 기본 아이디어는 락 자체를 0과 1, 두 가지 값을 가지는 플래그로 취급하는 것이다. 플래그 값이 0이면 스레드가 락을 소유할 수 있으며, 락을 소유하는 스레드는 이 값을 1로 설정하고 계속 연산을 진행할 수 있다. 당연히 플래그를 읽고 1로 설정하는 작업은 단일 아토믹 연산이어야 한다. 이 플래그 값이 1이라고 읽은 스레드들은 플래그 값이 0으로 변경되어 락을 소유할 수 있는 상황이 될 때까지 기다려야 한다. 플래그를 0에서 1로 변경한 스레드가 작업을 끝내고 다시 락을 해제할 준비가 되면 플래그 값을 0으로 변경한다.

 

스핀락의 단순 구현은 다음과 같다.

class Spinlock {
public:
    Spinlock() : flag_(0) {}
    void lock() {
        while (flag_.exchange(1, std::memory_order_acquire)) {}
    }
    void unlock() { flag_.store(0, std::memory_order_release); }

private:
    std::atomic<unsigned int> flag_;
};

위 스핀락을 통해 뮤텍스와 성능을 비교해볼 수 있지만, 이 스핀락의 성능은 매우 좋지 않을 것이다. 실제로 사용하려면 몇 가지 최적화가 필요하다.

 

우선, 플래그의 값이 1이라고 확인했으면, 실제로 1로 바꾸는 작업을 수행하지 않아도 된다. exchange 연산은 read-modify-write 연산이다. 즉, 이전 값이 1이더라도 값을 변경하며, 따라서, 사실 변경하지 않아도 되지만 해당 플래그가 포함된 캐시 라인에 단독으로 액세스하게 된다. 단지 플래그 값을 읽을 때에는 독점적으로 액세스할 필요가 없다는 것이다. 락을 다른 스레드가 소유 중이라면 스레드는 값이 0으로 변경되기를 기다린다. 기다리는 스레드들은 플래그 값을 변경할 필요가 없으며, 이들은 모두 동일한 메모리 복사본을 캐시에 가지고 있고 복사본은 최신이다. 락이 해제되기를 기다리는 스레드들은 업데이트할 필요가 없다는 것이다. 최적화한 스핀락 코드는 다음과 같다.

class Spinlock {
public:
    Spinlock() : flag_(0) {}
    void lock() {
        while (flag_.load(std::memory_order_relaxed) ||
        	flag_.exchange(1, std::memory_order_acquire)) {}
    }
    void unlock() { flag_.store(0, std::memory_order_release); }

private:
    std::atomic<unsigned int> flag_;
};

최적화된 lock() 함수는 먼저 플래그 값을 0으로 읽은 후에 이 값을 1로 바꾸는 연산을 수행한다. 이때, 다른 스레드가 락을 소유한 시점과 이 스레드가 exchange 연산을 수행하는 시점 사이에 값이 1로 변경되었을 수 있다.

 

하지만, 위의 최적화를 적용해도 스핀락의 성능은 매우 좋지 않다.

이는 OS가 스레드의 우선 순위를 지정하는 방식과 관련이 있다. 일반적으로 연산을 많이 수행하는 스레드는 유용한 작업을 수행한다고 간주되어 더 많은 CPU 시간을 얻게 된다. 하지만, 위 코드의 경우에 가장 많이 컴퓨팅하는 스레드는 플래그가 변경되기를 기다리는 스레드들이다. 이로 인해서 락을 얻으려고 시도하는 스레드들에게 CPU가 할당되지만, 락을 해제하려는 스레드는 일정 시간 동안 CPU가 할당되지 않는 상황이 발생할 수 있다. 이를 해결하려면 락을 기다리는 스레드가 여러 번 락을 얻으려고 시도한 이후에 CPU 점유를 포기하여 다른 스레드가 실행될 수 있도록 하는 것이다.

 

스레드가 CPU에 대한 제어를 해제하는 방법은 여러 가지가 있지만, 대부분은 시스템 함수 호출을 통해 수행된다. 리눅스의 경우에는 nanosleep()을 호출하여 매우 짧은 시간(수 나노초) 동안 sleep 상태가 되도록 하면 좋은 성능 결과를 얻을 수 있다. 일반적으로 CPU 액세스를 반환하는 또 다른 시스템 함수인 sched_yield()를 호출하는 것보다 더 좋다고 한다. 모든 시스템 콜은 하드웨어 명령어에 비해서 비용이 크기 때문에 너무 자주 호출하지 않는 것이 좋다. 락을 얻기 위해 여러 번 시도한 이후에 다른 스레드에 CPU를 양보하고 다시 시도하면 최상의 밸런스를 달성할 수 있다.

class Spinlock {
public:
    Spinlock() : flag_(0) {}
    void lock() {
        static const timespec ns = { 0, 1 };
        for (int i = 0; flag_.load(std::memory_order_relaxed) || flag_.exchange(1, std::memory_order_acquire); ++i) {
            if (i == 8) {
                i = 0;
                nanosleep(&ns, NULL);
            }
        }
    }
    void unlock() { flag_.store(0, std::memory_order_release); }

private:
    std::atomic<unsigned int> flag_;
};

CPU 점유를 포기하기 전에 락을 획득하려는 최적의 시도 횟수는 하드웨어와 스레드의 갯수에 따라 다르지만 일반적으로 8~16 사이의 값에서 잘 동작한다.

 

결과는 다음과 같다.

스핀락의 성능은 CAS 구현(lock-free) 및 아토킥 구현(atomic-based; wait-free)보다 훨씬 뛰어나다는 것을 보여준다.

 

스핀락의 성능이 이렇게 훌륭하다면 스핀락을 사용하지 않는 이유는 무엇일까 ? 그리고, 스핀락이 있는데 왜 아토믹 연산이 필요할까 ?

 

첫 번째 질문은 다양한 문제에 맞는 최적의 락이 있기 때문이다. 스핀락의 단점은 대기하는 스레드가 계속해서 CPU를 사용하는 busy waiting 상태라는 것이다. 반면, 뮤텍스를 기다리는 스레드는 대부분 유후(idle; sleeping) 상태라는 것이다. 벤치마크 코드처럼 단순히 카운트를 증가시키는 명령처럼 단 몇 주기만 소모하는 경우에는 busy waiting이 유용하며, 유후 상태로 전환하는 것보다 훨씬 빠르다. 반면, 많은 연산으로 구성된 경우에는 스핀락에서 대기 중인 스레드들이 CPU 시간을 많이 낭비하고, 작업을 수행하는 스레드에서 필요한 하드웨어 리소스 액세스를 빼앗는다. 전반적으로 C++ 뮤텍스(std::mutex) 또는 OS 뮤텍스는 밸런스를 위해 선택된다. 단일 명령어를 수행하기 위해서는 뮤텍스가 비효율적이지만 수십 나노초가 걸리는 경우에는 괜찮으며, 오랫동안 락을 유지해야 하는 경우에는 다른 방법들보다 낫다 (여기서 오랫동안의 기준은 상대적이며, 프로세서 기준으로 1ms도 매우 긴 것으로 간주할 수 있다).

 

극한의 성능을 목표로 하고 HPC를 타겟으로 한다면, 자체적으로 성능이 더 좋은 락을 구현하거나 이를 제공하는 라이브러리르 쓰는 경우가 많다.

 

Lock-Based vs. Lock-Free

Lock-free 프로그래밍의 장점은 일반적으로 더 빠르다는 것이다. 하지만, 항상 그런 것은 아니다. 락 구현은 특정 작업에 최적화되었을 때 매우 효율적이다. 그러나, Lock-based 접근 방식에 내재되어 있고 구현에 의존하지 않는 단점들이 있다.

 

우선 교착 상태, 데드락(deadlock)의 가능성이 있다. 이는 프로그램에 여러 개의 락을 사용할 때 발생할 수 있다. 두 락을 동시에 획득할 때, 항상 동일한 순서로 락을 획득하면 데드락을 피할 수 있다. C++에는 이를 위해 유틸리티 함수인 std::lock()을 제공한다. 하지만, 락을 동시에 획득할 수 없는 경우가 많다 (lock1을 획득할 때, lock2도 필요하다는 정보는 lock1로 보호되는 데이터에 숨겨져 있으므로). 여러 개의 락을 안정적으로 획득할 수 없다면, 락을 획득하려고 시도한 다음 모든 락을 획득하지 못하면 이미 보유 중인 락들을 해제하여 다른 스레드가 락을 획득할 수 있도록 하는 것이 해결책이 될 수 있다. C++의 대부분 락 구현에서는 락을 획득하거나 실패했을 때 false를 반환하는 try_lock() 인터페이스가 있다. 락을 획득하는데 실패하면 락을 해제하고 다시 락을 얻으려고 시도한다. 이는 간단한 테스트에서는 동작할 수 있지만, 이는 라이브락(livelock)을 유발할 수 있다. 라이브락은 두 스레드가 지속적으로 락을 해제하고 다른 스레드에게 락을 전달하는 경우이다. 간단히 말하자면, 두 스레드가 같은 시점에 락을 얻으려고 시도하고, 실패하여 락을 해제한다면 두 스레드 모두 진행되지 못한다. 결과적으로 성공적으로 여러 락을 획득하는 알고리즘이 있지만, 어렵고 복잡하다.

 

다중 락을 처리할 때 근본적인 문제는 두 개 이상의 락을 하나로 결합할 수 있는 좋은 방법이 없다는 것이다.

 

라이브락과 데드락 문제가 발생하지 않더라도 lock-based 프로그램은 다른 문제로 어려움을 겪을 수 있다. 가장 빈번하게 발생하며 진단하기 어려운 문제 중 하나는 convoying이다. 이는 우선순위가 동일한 여러 스레드들이 동일한 락을 놓고 반복적으로 경합할 때 발생한다. 락을 획득하려고 시도하는 스레드들에서는 실패할 때마다 컨텍스트 전환의 오버헤드가 발생하여 전반적인 성능이 떨어지게 된다.

 

락을 또 다른 문제점은 우선순위 개념을 반영하지 않는다는 것이다. 현재 락을 보유하고 있는 우선순위가 낮은 스레드는 동일한 락이 필요한 우선순위가 높은 스레드를 선점한다. 따라서, 높은 우선순위의 스레드가 낮은 우선순위의 스레드가 락을 해제할 때까지 기다리며, 우선순위 개념을 무시한다. 이러한 시나리오를 우선순위 역전(priority inversion)이라고 부른다.

 

이를 통해 락의 문제가 성능에만 국한되지 않는다는 것을 이해할 수 있다.

 

 

이번에는 lock-free 프로그램이 동일한 문제에 대해서 어떻게 처리되는지 살펴보자.

우선, lock-free 프로그램에서는 최소한 하나의 스레드가 블락되지 않도록 보장된다. 최악의 시나리오에서는 모든 스레드가 CAS 연산에 동시에 도달하여 아토믹 변수의 현재 값을 예상할 때, 이들 중 하나면 예상하는 값을 볼 수 있도록 보장된다. 나머지 모든 스레드들은 계산 결과를 버리고 아토믹 변수를 다시 로드하고 CAS 연산을 반복해야 한다. CAS에서 성공한 단 하나의 스레드만 다음 작업으로 이동할 수 있다. 이렇게 하면 데드락이 발생할 가능성이 없어진다. 데드락을 회피하려는 시도 또한 필요하지 않으므로 라이브락에 대해서도 걱정할 필요가 없다. 모든 스레드는 CAS와 같은 아토믹 연산을 위한 연산을 하느라 바쁜 상태이기 때문에 우선순위가 높은 스레드가 먼저 CAS에 도달하여 결과를 커밋할 가능성이 높고 우선순위가 낮은 스레드는 CAS를 실패하고 결과를 버릴 가능성이 높다. CAS 연산을 수행하여 결과를 커밋하는 스레드가 다른 모든 스레드에 비해서 어떠한 이점도 가지지 않는다. 따라서, 자연스럽게 convoying 문제가 제거된다.

 

그렇다면 lock-free 프로그램의 단점은 무엇일까?

첫 번째는 장점에서 발생하는 단점이다. CAS를 실패한 스레드도 계속 사용 중이다. 이는 우선순위 문제를 해결하지만 비용이 매우 크다. 경합이 높은 경우에 작업을 다시 수행하는데 많은 CPU 시간이 낭비된다. 이러한 스레드들이 관련 없는 다른 스레드로부터 CPU 리소스를 빼앗는다는 것이다.

 

두 번째 단점은 성격이 많이 다르다. 대부분의 동시 프로그램이 작성하거나 이해하기 쉽지 않지만, lock-free 프로그램은 더욱 어렵다. Lock-based 프로그램은 단일의 논리적 트랜잭션을 구성하는 모든 작업들이 락 아래에서 실행되도록 보장하면 된다. 전체가 아닌 일부 공유 데이터가 여러 다른 트랜잭션에 공통되는 등의 여러 논리적 트랜잭션이 있는 경우에는 더 어려워진다. 이때, lock-based 프로그램은 다중 락을 사용하게 된다.

 

반면, lock-free 프로그램에서는 아주 다양한 데이터 동기화 방식이 있다. 스레드가 일시 중지되지 않으므로 스레드가 아토믹 작업을 실행하는 순서에 관계없이 결과가 정확하다는 것을 스스로 확신해야 한다. 더욱이 명확하게 정의된 크리티컬 섹션 이점없이 아토믹 변수뿐만 아니라 프로그램의 모든 데이터에 대한 메모리 순서와 가시성에 대해 고민해야 한다. 메모리 순서의 요구 사항이 충분히 엄격하지 않기 때문에 한 스레드가 데이터를 변경할 때 다른 스레드가 변경되기 전 데이터를 보는 것은 아닌지 고민해야 한다.

 

이렇게 복잡한 문제에 대한 일반적인 해결책은 모듈화(modularization)과 캡슐화(encapsulation)이다. 어려운 코드를 각각 잘 정의된 인터페이스와 명확한 요구 사항 및 보장을 갖춘 모듈들로 구성하며, 다양한 동시 알고리즘을 구현하는 모듈에 집중하는 것이 좋다. 또한, 동시 프로그램에 적합한 데이터 자료구조를 사용하는 것도 중요하다.