여기서는 락프리 데이터 구조를 설명한다. 락프리(lock-free) 란 배타락을 이용하지 않고 처리를 수행하는 데이터 구조 및 그에 대한 조작 알고리즘을 총칭한다.

왜 락프리인가?

전통적인 동시성 제어 방법인 뮤텍스나 세마포어는 여러 문제점을 가지고 있다:

성능 저하: 락 경합(lock contention)으로 인한 대기 시간
데드락: 여러 스레드가 서로의 락을 기다리는 상황
우선순위 역전: 낮은 우선순위 스레드가 높은 우선순위 스레드를 블로킹
컨텍스트 스위칭: 락 대기 중 발생하는 오버헤드

락프리 알고리즘은 이러한 문제들을 아토믹한 연산을 통해 해결한다.

락프리 스택

락프리 스택은 선두 요소에 대한 push와 pop 조작만 가진 리스트로 구성된다. 가장 대표적인 구현은 Treiber 스택이다.

참고 자료: 위키피디아-Treiber 스택

Treiber 스택

Treiber 스택은 락프리 스택 알고리즘의 하나로 여러 스레드가 동시에 접근해도 락 없이 안전하게 동작하는 스택이다.

한 문장으로 아이디어를 요약하자면 이렇다.

내가 작업을 시작했을 때의 상태가 그대로라면 내 작업을 진행한다. 누군가가 중간에 이를 바꿔 상태가 바뀌었다면 처음부터 다시 시도한다.

use std::ptr::null_mut;
use std::sync::atomic::{AtomicPtr, Ordering};

/// Lock-free 스택의 노드 구조체
/// 
/// 단일 연결 리스트의 노드로, 각 노드는 다음 노드에 대한 원자적 포인터와
/// 실제 데이터를 포함한다.
/// 
/// # Type Parameters
/// * `T` - 스택에 저장될 데이터의 타입
struct Node<T> {
    /// 다음 노드를 가리키는 원자적 포인터
    /// AtomicPtr을 사용하여 동시성 환경에서 안전한 포인터 조작을 보장
    next: AtomicPtr<Node<T>>,
    /// 노드가 저장하는 실제 데이터
    data: T,
}

/// Lock-free 스택 구현
/// 
/// Treiber 스택 알고리즘을 사용한 락프리 스택 알고리즘
/// 여러 스레드가 동시에 push/pop 작업을 수행 가능

pub struct LockFreeStack<T> {
    /// 스택의 최상단 노드를 가리키는 아토믹 포인터
    head: AtomicPtr<Node<T>>,
}

impl<T> LockFreeStack<T> {
    /// 새로운 빈 스택을 생성
    /// 
    /// # Returns
    /// 빈 lock-free 스택 인스턴스
    pub fn new() -> Self {
        LockFreeStack {
            head: AtomicPtr::new(null_mut()),
        }
    }

    /// 스택에 새로운 요소를 추가
    /// 
    /// # Arguments
    /// * `v` - 추가할 데이터
    /// 
    /// # Algorithm
    /// 1. 새 노드를 생성
    /// 2. CAS(Compare-And-Swap) 루프를 통해 head 업데이트 시도
    /// 3. 성공할 때까지 재시도
    /// 
    /// # 동작 과정
    /// 1. 현재 head를 읽음
    /// 2. 새 노드의 next를 현재 head로 설정
    /// 3. CAS로 head를 새 노드로 아토믹하게 교체
    /// 4. 다른 스레드가 먼저 변경했다면 1부터 재시도
    pub fn push(&self, v: T) {
        let node = Box::new(Node {
            next: AtomicPtr::new(null_mut()),
            data: v,
        });

        // Box를 raw 포인터로 변환
        // 이 시점부터 메모리 관리는 수동으로 해야 함
        let ptr = Box::into_raw(node);

        // CAS 루프: head가 변경되지 않을 때까지 반복
        loop {
            // 현재 head 읽기
            // Acquire: 이 읽기 이후의 모든 메모리 연산이 이 읽기 이후에 발생하도록 보장
            let head = self.head.load(Ordering::Acquire);

            // 새 노드의 next를 현재 head로 설정
            unsafe {
                (*ptr).next.store(head, Ordering::Release);
            }

            // CAS: head가 여전히 같은 값이면 ptr로 교체
            // compare_exchange_weak는 spurious failure를 허용하여 성능 향상
            match self.head.compare_exchange_weak(
                head,
                ptr,
                Ordering::Release,  // 성공 시: 다른 스레드가 새 head를 볼 수 있도록 Release
                Ordering::Acquire   // 실패 시: 다른 스레드의 변경사항을 읽기 위해 Acquire
            ) {
                Ok(_) => break,     // 성공: 루프 종료
                Err(_) => continue, // 실패: 재시도
            }
        }
    }

    /// 스택에서 최상단 요소를 제거하고 반환
    /// 
    /// # Returns
    /// * `Some(T)` - 스택이 비어있지 않은 경우 최상단 요소
    /// * `None` - 스택이 비어있는 경우
    /// 
    /// # Algorithm
    /// 1. 현재 head 읽기
    /// 2. head가 null이면 None 반환
    /// 3. CAS를 통해 head를 다음 노드로 업데이트 시도
    /// 4. 성공할 때까지 재시도
    /// 
    /// # 주의사항
    /// pop 연산 중 다른 스레드의 간섭으로 인해 
    /// 여러 번의 재시도가 필요할 수 있음
    pub fn pop(&self) -> Option<T> {
        loop {
            // 현재 head 읽기
            let head = self.head.load(Ordering::Acquire);

            // 스택이 비어있는지 확인
            if head == null_mut() {
                return None;
            }

            // head의 다음 노드 읽기
            // 여기서 ABA 문제가 발생할 수 있음 (아래 설명 참조)
            let next = unsafe { (*head).next.load(Ordering::Acquire) };

            // CAS: head를 next로 교체 시도
            match self.head.compare_exchange_weak(
                head,
                next,
                Ordering::Release,  // 성공 시: 메모리 순서 보장
                Ordering::Acquire   // 실패 시: 다른 스레드의 변경사항 읽기
            ) {
                Ok(_) => {
                    // 성공: 이전 head 노드를 Box로 변환하여 자동 메모리 해제
                    let boxed_node = unsafe { Box::from_raw(head) };
                    return Some(boxed_node.data);
                }
                Err(_) => continue, // 실패: 재시도
            }
        }
    }
}

/// 스택이 drop될 때 모든 노드의 메모리를 해제
impl<T> Drop for LockFreeStack<T> {
    fn drop(&mut self) {
        // 모든 노드를 순회하며 메모리 해제
        // drop 시점에는 다른 스레드가 접근하지 않으므로 Relaxed 순서 사용
        let mut current = self.head.load(Ordering::Relaxed);

        while current != null_mut() {
            let node = unsafe { Box::from_raw(current) };
            current = node.next.load(Ordering::Relaxed);
            // node는 스코프를 벗어나면서 자동으로 drop됨
        }
    }
}

/// Send trait 구현: T가 Send면 LockFreeStack<T>도 Send
/// 
/// 다른 스레드로 안전하게 전송 가능함을 나타냄
unsafe impl<T: Send> Send for LockFreeStack<T> {}

/// Sync trait 구현: T가 Send면 LockFreeStack<T>는 Sync
/// 
/// 여러 스레드에서 동시에 참조 가능함
/// T가 Send여야 하는 이유: pop()이 T를 다른 스레드로 이동시킬 수 있기 때문
unsafe impl<T: Send> Sync for LockFreeStack<T> {}

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::Arc;
    use std::thread;

    #[test]
    fn test_single_thread() {
        let stack = LockFreeStack::new();

        // Push 테스트
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // Pop 테스트 (LIFO 순서)
        assert_eq!(stack.pop(), Some(3));
        assert_eq!(stack.pop(), Some(2));
        assert_eq!(stack.pop(), Some(1));
        assert_eq!(stack.pop(), None);
    }

    #[test]
    fn test_concurrent_operations() {
        let stack = Arc::new(LockFreeStack::new());
        let num_threads = 4;
        let operations_per_thread = 1000;

        // 여러 스레드에서 동시에 push/pop 수행
        let mut handles = vec![];

        for i in 0..num_threads {
            let stack_clone = Arc::clone(&stack);
            let handle = thread::spawn(move || {
                for j in 0..operations_per_thread {
                    stack_clone.push(i * operations_per_thread + j);
                    stack_clone.pop();
                }
            });
            handles.push(handle);
        }

        // 모든 스레드 종료 대기
        for handle in handles {
            handle.join().unwrap();
        }
    }
}

메모리 순서

Rust의 원자적 연산에서 사용되는 메모리 순서는 다음과 같다:

Relaxed: 가장 약한 순서 보장. 단일 원자적 변수에 대한 순서만 보장
Acquire: 이 연산 이후의 모든 메모리 연산이 이 연산 이후에 발생하도록 보장
Release: 이 연산 이전의 모든 메모리 연산이 이 연산 이전에 발생하도록 보장
AcqRel: Acquire와 Release의 조합
SeqCst: 가장 강한 순서 보장. 모든 스레드에서 동일한 순서를 관찰

락프리 스택에서는 주로 Acquire/Release 쌍을 사용하여 데이터 경쟁을 방지한다.

락프리에서의 문제점

ABA 문제

락프리 스택은 대부분의 경우 문제가 없으나 특정한 조건에서 ABA 문제가 발생할 수 있다.

ABA 문제는 다음과 같은 예로 설명될 수 있는데

그림에서는 2개의 스레드가 락프리 스택에 push와 pop을 수행하고 있다.

초기 락프리 스택에는 3개의 데이터가 존재하고 각 노드의 주소를 A, B, C라고 하자.

시각 0: 스레드 1은 head의 주소 A와 A의 다음 노드 주소인 B를 기억한다.

시각 1: 스레드 2가 2번의 pop 조작을 수행한다. 그러면 노드 A와 B는 스택에서 제거되고 메모리는 비게(free) 된다.

시각 2: 스레드 2가 새로운 데이터를 push한다. 이때 프리 영역이 된 노드 A가 재사용되면 스택은 A→C라는 상태가 된다.

시각 3: 스레드 1이 pop 조작 이후 CAS 조작을 수행하면 head는 외관상 바뀌지 않지만 해제된 노드B를 이용해 업데이트를 수행하게 된다.

락프리 스택에서는 CAS 조작에 따라 head가 업데이트되지 않았음을 확인한 이후에 데이터의 push와 pop이 이루어지는데, 메모리 영역이 재사용되면 문제가 발생한다.

head가 외관상 바뀌지 않지만 의미적으로는 다른 연산이 수행되었을 수 있는 것이다. 이처럼 ABA문제는 A가 실제로는 중도에 다른 상태(B)로 바뀌었음에도 처음과 끝은 A이므로 처음과 연산 종료 후 결과를 통해서는 업데이트 여부를 제대로 파악할 수 없다는 문제이다.

ABA 문제가 발생하는 이유

ABA 문제가 발생하는 이유는 업데이트 유무가 CAS 처리에 의한 값 비교로 수행되기 때문이다. 값 비교로 작업이 수행되기 때문에 해당 메모리에 어떤 쓰기 작업이 있었는지는 검증하는 과정이 없었다.

그렇다면 문제는 간단해진다. 메모리의 쓰기 작업을 감지할 수 있도록 하면 된다. 이는 Load-Link/Store-Conditional 명령을 이용하면 구현할 수 있다.

ABA 문제 해결 방법

ABA 문제를 해결하는 방법은 여러 가지가 있는데 LL/SC (Load-Link/Store-Conditional): 하드웨어 수준에서 메모리 변경 감지하는 등의 방법이 존재한다.

멀티스레드에서 참조에 대한 문제

락프리 구조는 멀티스레드에서 데이터 삭제에 대한 문제를 일으키기도 한다. 아래 예시는 멀티스레드 참조에 관한 문제를 그림으로 보여준다.

초기 상태에서 리스트는 A→B→C로 연결되어 있다.

시각 0: 스레드 1이 선두 노드를 참조했다고 가정하자.

시각 1: 스레드 2가 pop조작을 수행하고, 선두 노드를 파기한다. 그런데 이때 스레드 1의 참조 x가 댕글링 포인터가 되어버린다.

물론 러스트의 경우 소유권 규칙에 따라 위와 같은 작동을 하는 코드가 컴파일러 선에서 막히기 때문에 실제로 작동될 일은 없으나 가비지 컬렉션(GC)가 없는 언어의 경우 문제가 될 수 있다.

락프리의 분류

락프리는 원래 뮤텍스와 같은 구조들(즉, 락을 말한다)에 의존하지 않는다는 의미로 넓게 사용되었으나 락프리의 정의를 더 좁게 가져가자면

분류	배타락 사용	라이브락 발생 가능	starvation 발생 가능	진행 보장
배타 락프리	X	O	O	없음
락프리	X	X	O	시스템 전체 진행 보장
웨이트 프리	X	X	X	모든 스레드 진행 보장

락프리 분류 더 알아보기

배타 락프리 (Obstruction-Free)

가장 약한 진행 보장
다른 스레드가 없을 때만 진행 보장
실용적이지 않아 잘 사용되지 않음

락프리 (Lock-Free)

시스템 전체적으로 항상 적어도 하나의 스레드는 진행
개별 스레드는 starvation 가능
실용적이면서도 구현 가능한 수준

웨이트 프리 (Wait-Free)

가장 강한 진행 보장
모든 스레드가 유한한 단계 내에 완료
구현이 매우 어렵고 성능 오버헤드가 큼

배타 락프리, 웨이트 프리와 구분되어 부르는 락프리는 라이브락이 발생하지 않는, 락에 의존하지 않는 구조로 정의할 수 있겠다.

가장 보편적으로 락프리라 함은 배타 락을 사용하지 않는 구조, 즉 배타 락프리에 더 가깝다고 할 수 있다.

락프리 데이터 구조와 알고리즘

Comments

Programming

소프트웨어 트랜잭셔널 메모리

More from this blog

소프트웨어 트랜잭셔널 메모리

공평한 배타 제어

KernelSnitch[논문 리뷰]

멀티태스크와 액터 모델

왜 락프리인가?

락프리 스택

Treiber 스택

메모리 순서

락프리에서의 문제점

ABA 문제

ABA 문제가 발생하는 이유

ABA 문제 해결 방법

멀티스레드에서 참조에 대한 문제

락프리의 분류

락프리 분류 더 알아보기

배타 락프리 (Obstruction-Free)

락프리 (Lock-Free)

웨이트 프리 (Wait-Free)

Command Palette

Comments

Programming

소프트웨어 트랜잭셔널 메모리

More from this blog

왜 락프리인가?

락프리 스택

Treiber 스택

메모리 순서

락프리에서의 문제점

ABA 문제

ABA 문제가 발생하는 이유

ABA 문제 해결 방법

멀티스레드에서 참조에 대한 문제

락프리의 분류

락프리 분류 더 알아보기

배타 락프리 (Obstruction-Free)

락프리 (Lock-Free)

웨이트 프리 (Wait-Free)