Lock-free Stack

Lock-free Stack은 락(lock)을 사용하지 않고 동시성을 제공하는 LIFO(Last-In-First-Out) 자료구조.
이 자료구조는 여러 스레드가 동시에 스택에 접근할 수 있으며, 시스템 전체의 진행을 보장한다.

특징

  1. 동시성 지원: 여러 스레드가 동시에 스택에 접근하고 수정할 수 있다.
  2. 락 사용 없음: 전통적인 동기화 기법인 락을 사용하지 않는다.
  3. 진행 보장: 시스템 전체의 진행을 보장하며, 개별 스레드의 기아 현상이 발생할 수 있다.
  4. 원자적 연산 사용: Compare-And-Swap(CAS)과 같은 원자적 연산을 사용한다.

구현 방식

Lock-free Stack은 주로 다음과 같은 방식으로 구현된다:

  1. 연결 리스트 기반: 노드들을 연결 리스트로 구성하고, 톱(top) 포인터를 사용한다.
  2. 원자적 연산: CAS 연산을 사용하여 톱 포인터를 안전하게 업데이트한다.
  3. ABA 문제 해결: 메모리 재사용 시 발생할 수 있는 ABA 문제를 해결하기 위한 기법을 사용한다.

장점

  1. 높은 동시성: 여러 스레드가 동시에 작업을 수행할 수 있어 성능이 향상된다.
  2. 데드락 방지: 락을 사용하지 않아 데드락 문제가 발생하지 않는다.
  3. 확장성: 스레드 수가 증가해도 성능 저하가 적다.

응용

  1. 고성능 멀티스레드 시스템
  2. 실시간 시스템
  3. 운영체제 커널
  4. 데이터베이스 시스템
  5. 네트워크 패킷 처리

동작 원리

  1. 푸시(Push) 연산: 새 노드를 생성하고 CAS 연산을 사용하여 톱 포인터를 업데이트한다.
  2. 팝(Pop) 연산: CAS 연산을 사용하여 톱 포인터를 업데이트하고 노드를 제거한다.
  3. 재시도 로직: CAS 연산이 실패할 경우, 작업을 재시도한다.

구성 요소

  1. 노드: 데이터와 다음 노드를 가리키는 포인터를 포함한다.
  2. 톱 포인터: 스택의 최상위 요소를 가리킨다.
  3. 원자적 연산: CAS 연산을 위한 하드웨어 지원이 필요하다.

예시 코드 (Java)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class LockFreeStack<T> {
    private AtomicReference<Node<T>> top = new AtomicReference<>(null);
    
    private static class Node<T> {
        T item;
        Node<T> next;
        
        Node(T item) {
            this.item = item;
        }
    }
    
    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        while (true) {
            Node<T> oldTop = top.get();
            newNode.next = oldTop;
            if (top.compareAndSet(oldTop, newNode)) {
                return;
            }
        }
    }
    
    public T pop() {
        while (true) {
            Node<T> oldTop = top.get();
            if (oldTop == null) {
                return null;
            }
            Node<T> newTop = oldTop.next;
            if (top.compareAndSet(oldTop, newTop)) {
                return oldTop.item;
            }
        }
    }
}

참고 및 출처