Treiber stack

개요

Treiber's 스택은 Lock free데이터 구조중 singly linked list를 구현하는 방식중 하나이다. Treiber's stack은 1986년 R.Kent Treiber가 발표하였다.

기본 원칙

알고리즘의 기본 원리는 데이터에 접근할 때 추가하려는 항목이 추가된 유일한 항목임을 파악하고 스택에 새로운 것을 추가하는 것이다. 이는 Compare and swap(CAS)을 사용하여 수행된다.

스택에 푸쉬할때, 먼저 스택의 맨 위 (즉 제일 오래된 헤드)를 가져와, 새 항목 뒤에 배치하여 새 헤드를 생성한다. 그뒤 그 오래된 헤드를 현재 헤드와 비교한다. 만약 두개가 일치한다면, 접근이 없었다는 것 임으로 이전 헤드를 새 헤드로 교체하며, 일치하지 않으면, 다른 스레드가 스택에 푸쉬하였음을 의미하기 때문에, 이 경우 다시 푸쉬를 시도한다. 스택의 팝동작 또한 팝 도중 다른 스레드가 새 항목을 추가하지 않았음을 확인한후 팝하게 된다.

ABA Problem

Treiber stack은 ABA문제라는 단점이 존재한다. 스택에서 팝을 수행하는 도중에서, 다른 스레드가 헤드의 포인터가 동일하도록 자료구조를 변경할 수 있다. 이 경우, 헤드의 포인터 값이 일치하기 때문에 Treiber stack은 변경된 스택에서 팝을 수행하게 된다. 이러한 문제는 GC와 같은 강력한 포인터 재사용 정책을 제공하는 자료구조와 같은 경우에는 일어나지 않는 문제이지만, C처럼 포인터에 대한 사용을 개발자에게 위임하는 언어의 경우 심각하게 그리고 은닉되어서 발생할 수 있기 때문에 주의를 요한다.

이러한 ABA문제는 여러 해결책이 있다.

Garbage collection: GC는 포인터에 대해서 메모리 재사용을 안전한 상황에서 Fee되기 전까지 막는다. 따라서 ABA문제가 일어나지 않는다.
Memory pin하기: Rust의 Crossbeam 라이브러리에서는 특정 메모리를 pin할 수 있는 기능이 있다. Memory를 pin하면 pin한 스레드가 일이 끝날 때까지 기다리기 때문에 ABA문제가 발생하지 않는다.
Memory tagging: 사용하지 않는 메모리의 특정 비트를 사용하여서 Memory를 tagging하여 현재 메모리 할당이 안전한지를 표시한다.

예시

    /// Pushes a value on top of the stack.
    pub fn push(&self, t: T) {
        let mut n = Owned::new(Node {
            data: ManuallyDrop::new(t),
            next: ptr::null(),
        });

        let mut guard = crossbeam_epoch::pin();

        loop {
            let head = self.head.load(Relaxed, &guard);
            n.next = head.as_raw();

            match self
                .head
                .compare_exchange(head, n, Release, Relaxed, &guard)
            {
                Ok(_) => break,
                Err(e) => n = e.new,
            }

            // Repin to ensure the global epoch can make progress.
            guard.repin();
        }
    }

    /// Attempts to pop the top element from the stack.
    ///
    /// Returns `None` if the stack is empty.
    pub fn pop(&self) -> Option<T> {
        let mut guard = crossbeam_epoch::pin();
        loop {
            let head = self.head.load(Acquire, &guard);
            let h = unsafe { head.as_ref() }?;
            let next = Shared::from(h.next);

            if self
                .head
                .compare_exchange(head, next, Relaxed, Relaxed, &guard)
                .is_ok()
            {
                // Since the above `compare_exchange()` succeeded, `head` is detached from `self` so
                // is unreachable from other threads.

                // SAFETY: We are returning ownership of `data` in `head` by making a copy of it via
                // `ptr::read()`. This is safe as no other thread has access to `data` after `head`
                // is unreachable, so the ownership of `data` in `head` will never be used again.
                let result = ManuallyDrop::into_inner(unsafe { ptr::read(&h.data) });

                // SAFETY: `head` is unreachable, and we no longer access `head`.
                unsafe { guard.defer_destroy(head) };

                return Some(result);
            }

            // Repin to ensure the global epoch can make progress.
            guard.repin();
        }
    }