Lock-Free 알고리즘과 CAS 연산

멀티스레드 환경에서 특히 여러 스레드가 공유 자원에 접근할 때 발생하는 Race condition을 해결하는 방법 중 하나로 Lock-Free 알고리즘이 있습니다. 이번 글에서는 Lock-Free 알고리즘의 개념부터 CAS 연산에 대해서 살펴보겠습니다.

Lock-Based vs Lock-Free

Lock-Free 알고리즘이란, 공유 자원에 여러 스레드가 동시에 접근하고 수정할 때, 전통적인 락(lock) 기법을 사용하지 않으면서도 시스템 전체적으로 Deadlock에 빠지지 않고 계속해서 진행(progress)을 보장하는 알고리즘을 의미합니다.

Lock-Free 알고리즘의 핵심 특징은 전체 시스템이 항상 일정 수준 이상의 작업을 처리해나간다는 것입니다. 한 스레드가 느리거나 멈춰도 다른 스레드가 작업을 계속 이어갈 수 있어 전체 시스템의 진행이 보장됩니다.

먼저, 전통적인 락(lock) 기법인 Lock-based 구조부터 살펴보겠습니다.

이 접근 방식의 장점은 락이 필요 없다는 것입니다. 그러나 발생할 수 있는 문제는 Thread 2(또는 다른 스레드들)가 높은 빈도로 데이터에 접근한다면, Thread 1이 최종적으로 성공하기까지 많은 수의 시도가 필요하게 된다는 점입니다. 따라서 Thread 1은 기아(starvation) 상태에 빠질 수 있습니다.

이제 논블로킹 알고리즘에 대해 먼저 설명하고, 이후 CAS(compare-and-swap) 연산이 어떻게 논블로킹 접근을 가능하게 하는지 살펴보려고 합니다.

Non-Blocking 알고리즘

Non-Blocking 알고리즘에는 세 가지 수준으로 구분할 수 있습니다.

1. Obstruction-Free: 가장 약한 형태로, 다른 모든 스레드가 일시 중단되면 하나의 스레드는 진행이 보장됩니다. Thread 1(상단 스레드)은 다른 스레드들(Thread 2, ... n) 이 일시 중단(하단의 노란색으로 표시된 영역)되자마자 진행(녹색 화살표)할 수 있습니다.
2. Lock-Free: 항상 하나 이상의 스레드가 진행을 보장받습니다. 다른 스레드들은 기아 상태에 빠질 수 있지만, 시스템 전체는 항상 진행됩니다. Obstruction-Free와의 차이점은 스레드가 일시 중단되지 않아도 적어도 하나의 스레드는 기아 상태가 아니라는 것입니다. 최소한 Thread 1은 다른 스레드들(Thread 2, ... n) 이 기아 상태(빨간색 화살표)에 있을 수 있는 동안에도 진행할 수 있습니다.
3. Wait-Free: 가장 이상적인 형태로, 모든 스레드가 유한 시간 안에 반드시 작업을 완료함을 보장합니다. 모든 스레드가 기아 상태 없이 진행됩니다. 위 그림에서도 볼 수 있듯이 다른 스레드들(Thread 2, ... n) 이 일정 기간의 기아 상태(빨간색 화살표) 후에 계속 진행(녹색 화살표)할 수 있음을 보장합니다.

CAS(Compare-And-Set/Swap) 연산

락을 피하기 위해 사용되는 기본 연산 중 하나인 CAS(Compare-And-Set 또는 Compare-And-Swap) 연산의 아이디어는 어떤 변수를 메인 메모리에서 값을 가져온 시점의 값과 여전히 동일한 경우에만 업데이트한다는 것입니다. CAS는 원자적 연산으로, 읽기와 업데이트가 함께 단일 연산으로 처리됩니다.

여기서 두 스레드 모두 메인 메모리에서 값 3을 읽습니다. Thread 2가 성공(녹색)하여 변수를 8로 업데이트합니다. Thread 1의 첫 번째 CAS는 값이 여전히 3이기를 기대하므로, CAS는 실패(빨간색)합니다. 따라서 Thread 1은 값을 다시 읽고, 두 번째 CAS는 성공합니다. 여기서 중요한 점은 CAS가 자료구조에 락을 획득하지 않고, 업데이트가 성공하면 'true'를 반환하고, 그렇지 않으면 'false'를 반환한다는 것입니다.

fun compareAndSet(expectedValue: T, newValue: T): Boolean {
    if (currentValue == expectedValue) {
        currentValue = newValue
        return true  // 성공
    }
    return false  // 실패
}

예상 값과 여전히 같을 때만 새 값으로 업데이트하고, 그렇지 않으면 'false'를 반환합니다. 다음 코드 스니펫은 CAS를 어떻게 호출할 수 있는지에 대한 예시입니다.

fun testCas() {
    var v = value
    var x = v + 1
    while (!cas(v, x)) {
        v = value
        x = v + 1
    }
}

위 코드는 CAS 연산이 성공할 때까지 값을 업데이트하려고 시도합니다. 그러나 스레드가 기아(starvation) 상태에 빠질 가능성이 있습니다. 다른 스레드들이 동시에 같은 변수에 대해 CAS를 수행하면, 특정 스레드에서는 연산이 절대 성공하지 않거나(또는 성공하는 데 비합리적으로 많은 시간이 걸릴 수 있습니다). 그럼에도 불구하고, CAS가 실패하면 다른 스레드가 성공했다는 것을 알 수 있으므로, lock-free에 필요한 전체적인 진행을 보장합니다. 하드웨어가 락 사용 없이 진정한 원자적 연산으로 만들기 위해 CAS를 지원해야 한다는 점이 중요한데, Java는 Atomic 변수를 통해 CAS의 구현을 제공합니다.

A-B-A 문제

CAS는 A-B-A 문제를 방지하지 않습니다. 이전에 보았듯이, CAS는 메인 메모리의 값이 여전히 우리가 예상하는 값인 경우에만 값을 업데이트합니다. 그러나 값이 변경되었다가 다시 이전 값으로 돌아온 경우에도 CAS는 성공합니다. 아래 이미지는 이 상황을 보여줍니다.

Thread 1과 Thread 2는 모두 변수의 값인 3을 읽습니다. 그런 다음 Thread 2가 CAS를 수행하여 변수를 8로 설정하는 데 성공합니다. 또한 Thread 2는 CAS를 수행하여 변수를 다시 3으로 설정하는 데 성공합니다. 마지막으로 Thread 1이 값이 3일 것을 예상하며 CAS를 수행하고, 그 사이에 변수의 값이 두 번 수정되었음에도 불구하고 성공합니다. 이것을 A-B-A 문제라고 합니다. 물론 이 동작은 사용 사례에 따라 문제가 되지 않을 수 있습니다. 그러나 일부에게는 원하지 않는 결과일 수 있습니다.

마치며

Lock-Free 알고리즘은 멀티스레드 환경에서 높은 성능과 안정성을 제공할 수 있는 강력한 기술입니다. 그 중 CAS(Compare-And-Swap)가 가장 널리 알려진 연산이지만, LL/SC(Load-Link/Store-Conditional)나 Fetch-and-Add와 같은 다른 원자적 연산들도 존재합니다. 이러한 다양한 접근법은 각각 고유한 장단점을 가지고 있습니다.

Lock-Free 알고리즘의 구현은 복잡하고 ABA 문제와 같은 특수한 상황을 고려해야 하므로 신중한 접근이 필요합니다. 특히 CAS 연산만으로는 ABA 문제를 해결할 수 없기 때문에, 버전 카운터나 스탬프를 사용하는 방식을 도입해야 합니다. (Java의 AtomicStampedReference와 같은 클래스)

실제 프로젝트에서는 Java의 java.util.concurrent 패키지나 Kotlin의 kotlinx.coroutines.sync와 같은 검증된 라이브러리를 활용하는 것이 좋습니다. 이러한 라이브러리들은 이미 복잡한 동시성 문제를 해결하고 최적화된 구현을 제공합니다.

또한, Lock-Free 알고리즘은 모든 스레드가 진행을 보장받지는 못합니다. 특정 상황에서는 일부 스레드가 기아 상태에 빠질 수 있습니다. 더 강력한 보장을 원한다면 Wait-Free 알고리즘을 고려할 수 있지만, 이는 구현이 훨씬 복잡하고 성능 비용도 큽니다.

비록 저는 안드로이드 개발자이지만, 지연 시간이 중요한 실시간 시스템이나 높은 처리량이 필요한 서버 애플리케이션에서는 Lock-Free 알고리즘이 큰 차이를 만들 수 있다고 생각할 뿐만 아니라, UDP 기반으로 동작하는 클라이언트 이미지 처리기를 생각해본다면, 네트워크를 통해 수신되는 이미지 패킷들을 실시간으로 처리하고 렌더링해야 하는 경우, 패킷 수신과 이미지 처리 간의 동기화 작업에 충분히 Lock-Free 큐를 활용할 수 있을 것 같다고 생각합니다. 특히 패킷 손실 가능성이 있는 UDP 환경에서는 빠른 처리가 중요한데, 수신 스레드가 패킷을 받아 Lock-Free 큐에 넣고, 처리 스레드가 이를 소비하는 방식으로 구현하면 전통적인 락 기반 구현보다 처리량과 반응성을 크게 향상시킬 수 있을 것 같습니다. 이런 시나리오에서는 ABA 문제가 거의 발생하지 않기 때문에 단순한 CAS 기반 구현으로도 충분할 수 있다고 생각합니다.

이 글이 Lock-Free 알고리즘을 이해하고 적용할 수많은 백엔드, 클라이언트 개발자분들께 도움이 되었기를 바랍니다.

참고 자료

1. Lock-Free Stacks Are Even Cooler in Kotlin
2. Introduction to Lock-Free Data Structures with Java Examples
3. Compare-and-swap