Lock-free Queue

Lock-free Queue는 락(lock)을 사용하지 않고 동시성을 제공하는 FIFO(First-In-First-Out) 자료구조이다.
이 자료구조는 여러 생산자(producer)와 소비자(consumer)가 동시에 큐에 접근할 수 있으며, 시스템 전체의 진행을 보장한다.

특징

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

구현 방식

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

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

장점

  1. 높은 동시성: 여러 스레드가 동시에 작업을 수행할 수 있어 성능이 향상된다.
  2. 데드락 방지: 락을 사용하지 않아 데드락 문제가 발생하지 않는다.
  3. 우선순위 역전 문제 해결: 락 기반 구현에서 발생할 수 있는 우선순위 역전 문제를 해결한다.

응용

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

동작 원리

  1. 엔큐 연산: 새 노드를 생성하고 CAS 연산을 사용하여 테일 포인터를 업데이트한다.
  2. 디큐 연산: CAS 연산을 사용하여 헤드 포인터를 업데이트하고 노드를 제거한다.
  3. ABA 문제 해결: 포인터에 카운터를 추가하거나 hazard pointer를 사용한다.

구성 요소

  1. 노드: 데이터와 다음 노드를 가리키는 포인터를 포함한다.
  2. 헤드 포인터: 큐의 첫 번째 요소를 가리킨다.
  3. 테일 포인터: 큐의 마지막 요소를 가리킨다.
  4. 원자적 연산: CAS 연산을 위한 하드웨어 지원이 필요하다.

응용 분야

  1. 실시간 시스템: 시간 제약이 엄격한 실시간 애플리케이션
  2. 고성능 메시징 시스템: 대량의 메시지를 처리하는 시스템
  3. 작업 스케줄러: 병렬 작업 처리를 위한 스케줄링 시스템
  4. 네트워크 패킷 처리: 고성능 네트워크 애플리케이션

예시 코드

 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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> {
    private class Node {
        T value;
        AtomicReference<Node> next;
        
        Node(T value) {
            this.value = value;
            this.next = new AtomicReference<>(null);
        }
    }
    
    private AtomicReference<Node> head, tail;
    
    public LockFreeQueue() {
        Node dummy = new Node(null);
        head = new AtomicReference<>(dummy);
        tail = new AtomicReference<>(dummy);
    }
    
    public void enqueue(T value) {
        Node newNode = new Node(value);
        
        while (true) {
            Node currentTail = tail.get();
            Node tailNext = currentTail.next.get();
            
            if (currentTail == tail.get()) {
                if (tailNext == null) {
                    if (currentTail.next.compareAndSet(
                        null, newNode)) {
                        tail.compareAndSet(currentTail, newNode);
                        return;
                    }
                } else {
                    tail.compareAndSet(currentTail, tailNext);
                }
            }
        }
    }
    
    public T dequeue() {
        while (true) {
            Node currentHead = head.get();
            Node currentTail = tail.get();
            Node headNext = currentHead.next.get();
            
            if (currentHead == head.get()) {
                if (currentHead == currentTail) {
                    if (headNext == null) {
                        return null;
                    }
                    tail.compareAndSet(currentTail, headNext);
                } else {
                    T value = headNext.value;
                    if (head.compareAndSet(currentHead, headNext)) {
                        return value;
                    }
                }
            }
        }
    }
}

참고 및 출처