Read-Copy-Update (RCU) List

RCU List는 동시성을 지원하는 연결 리스트 구조로, 여러 스레드가 동시에 안전하게 접근하고 수정할 수 있도록 설계되었다.

RCU List는 Read-Copy-Update 메커니즘을 사용하여 구현된 동시성 연결 리스트로 읽기 작업에 대해 락을 사용하지 않으면서도 동시에 업데이트를 수행할 수 있게 해준다.

특징

  1. 락 없는 읽기: 읽기 작업은 동기화 없이 수행된다.
  2. 동시성 지원: 여러 스레드가 동시에 리스트에 접근할 수 있다.
  3. 읽기 성능 최적화: 읽기 작업의 성능이 매우 뛰어나다.
  4. 공간-시간 트레이드오프: 더 많은 공간을 사용하여 빠른 연산을 가능하게 한다.

구현 방식

  1. 삽입: 새 노드를 생성하고 원자적으로 리스트에 연결한다.
  2. 삭제: 노드를 리스트에서 제거한 후, 일정 시간이 지난 뒤 메모리를 해제한다.
  3. 읽기: 동기화 없이 리스트를 순회한다.

장점

  1. 높은 읽기 성능: 읽기 작업이 매우 빠르다.
  2. 확장성: 다중 코어 시스템에서 좋은 성능을 보인다.
  3. 데드락 방지: 읽기 작업에서 락을 사용하지 않아 데드락 위험이 줄어든다.

응용

  1. 운영체제 커널
  2. 데이터베이스 시스템
  3. 네트워크 스택
  4. 고성능 멀티스레드 애플리케이션

동작 원리

  1. 읽기 작업: 동기화 없이 리스트를 순회한다.
  2. 쓰기 작업: 새로운 버전의 데이터를 생성하고, 원자적으로 포인터를 업데이트한다.
  3. 삭제: 노드를 리스트에서 제거한 후, 모든 읽기 작업이 완료될 때까지 기다렸다가 메모리를 해제한다.

구성 요소

  1. 노드: 데이터와 다음 노드를 가리키는 포인터를 포함한다.
  2. 헤드 포인터: 리스트의 첫 번째 노드를 가리킨다.
  3. RCU 동기화 프리미티브: rcu_read_lock(), rcu_read_unlock(), synchronize_rcu() 등

예시 코드

 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

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeStack<T> {
    private static class Node<T> {
        final T value;
        Node<T> next;
        
        Node(T value) {
            this.value = value;
        }
    }
    
    private AtomicReference<Node<T>> head = 
        new AtomicReference<>(null);
    
    public void push(T value) {
        Node<T> newNode = new Node<T>(value);
        while (true) {
            Node<T> currentHead = head.get();
            newNode.next = currentHead;
            // CAS로 head를 새 노드로 업데이트 시도
            if (head.compareAndSet(currentHead, newNode)) {
                return;
            }
            // 실패하면 다시 시도
        }
    }
    
    public T pop() {
        while (true) {
            Node<T> currentHead = head.get();
            if (currentHead == null) {
                return null;
            }
            // CAS로 head를 다음 노드로 업데이트 시도
            if (head.compareAndSet(
                currentHead, 
                currentHead.next)) {
                return currentHead.value;
            }
            // 실패하면 다시 시도
        }
    }
}

참고 및 출처