멀티스레드에서 큐가 깨지는 이유와 CAS로 Lock free 구조까지 가는 길

멀티스레딩에서 터지는 곳은 보통 자료구조입니다

• 멀티스레드는 결국 공유 데이터에서 문제가 납니다.
• 공유 데이터는 보통 자료구조로 표현됩니다.
• 그중에서도 큐는 멀티스레드와 자주 엮입니다.
• 그래서 큐에는 레이스 컨디션이 따라붙기 쉽습니다.

큐가 왜 자주 등장하나

• UI와 파일 처리처럼 “일을 분리”하면 중간에 이벤트 전달 통로가 필요합니다.
• 그 통로가 보통 이벤트 큐입니다.
• 이벤트 큐는 보통 선형 구조입니다.
  • 배열 기반 큐일 수 있습니다.
  • 연결 리스트 기반 큐일 수 있습니다.

연결 리스트와 멀티스레드를 같이 쓰면 뭐가 깨지나

• 연결 리스트는 사실상 “자료구조 전체”의 축약판입니다.
• 노드 추가와 삭제는 포인터(참조)를 여러 번 바꿉니다.
• 이 “여러 번”이 레이스 컨디션의 핵심입니다.

레이스 컨디션이 만들어지는 전형적 상황

• 파일 처리 스레드가 큐에 이벤트를 추가합니다.
• UI 스레드가 큐에서 이벤트를 삭제합니다.
• 둘이 같은 시점에 같은 링크를 건드리면 아래가 발생합니다.
  • 조회 중에 노드가 끼어듭니다.
  • 삭제 중에 노드가 다시 연결됩니다.
  • 결과적으로 리스트가 찢어지거나 루프가 생길 수 있습니다.

임계 영역은 어디로 잡아야 하나

• 임계 영역은 “공유 불변식”이 깨지는 구간입니다.

• 연결 리스트의 불변식은 아래처럼 정리할 수 있습니다.

• 불변식 예시

  • prev.next == this
  • next.prev == this
  • head.next와 tail.prev가 항상 일관됩니다.
  • counter가 실제 노드 개수와 일치합니다.

• 즉 아래가 동시에 바뀌는 구간이 임계 영역입니다.

  • 링크 갱신
  • head tail 갱신
  • 길이 카운터 갱신

예제 코드로 보는 레이스 포인트

노드 추가 appendNode

public boolean appendNode(String name) {
    UserData newUser = new UserData(name);
    newUser.prev = tail.prev;
    newUser.next = tail;
    tail.prev.next = newUser; // A Start
    tail.prev = newUser;
    ++counter; // A End
    return true;
}

• 여기서 위험한 지점은 아래입니다.
  • tail.prev.next = newUser
  • tail.prev = newUser
  • ++counter
• 이 구간은 “작은 것처럼 보여도” 하나의 트랜잭션입니다.
• 중간에 끼어들면 tail 체인이 깨질 수 있습니다.

counter도 같이 깨집니다

• counter++는 원자 연산이 아닙니다.
• 그래서 동기화 없이 쓰면 값이 틀어질 수 있습니다.
• counter는 아래 중 하나가 필요합니다.
  • 임계 영역 안에서만 갱신
  • AtomicInteger 사용

노드 삭제 removeAtHead

public UserData removeAtHead() {
    if (isEmpty()) return null;
    UserData node = head.next; // 임계영역 Start
    node.next.prev = head;
    head.next = node.next;
    --counter; // 임계영역 End
    return node;
}

• 여기서도 링크 2개와 카운터 1개가 한 묶음입니다.
• 이 도중에 append가 끼면 아래가 나옵니다.
  • 삭제한 노드가 다시 참조됩니다.
  • head.next가 잘못된 노드를 가리킵니다.
  • 리스트가 끊기거나 순환할 수 있습니다.

join이 있을 때는 왜 멀쩡해 보이나

• producer.join()을 하면 생산이 끝난 뒤 소비가 시작됩니다.
• 그래서 동시에 같은 링크를 건드릴 일이 줄어듭니다.
• 즉 레이스가 사라진 게 아니라 환경이 안전해진 것입니다.

join 없이 동시에 돌리면 왜 터지나

• 생산과 소비가 같은 자료구조를 동시에 만집니다.
• 임계 영역이 없으면 연결 구조가 쉽게 손상됩니다.
• 그래서 counter가 깨지고 구조 자체도 깨질 수 있습니다.

해결 1 synchronized로 감싸기

• 가장 쉬운 개선은 메서드를 통째로 동기화하는 것입니다.

public synchronized boolean appendNode(String name) { ... }
public synchronized UserData removeAtHead() { ... }

• 장점
  • 구현이 단순합니다.
  • 구조 손상이 거의 사라집니다.
• 단점
  • 필요 없는 코드까지 임계 영역이 됩니다.
  • 경쟁이 늘면 병목이 커집니다.

해결 2 ReentrantLock으로 임계 영역만 줄이기

• 핵심은 “링크 갱신 구간만” 락으로 묶는 것입니다.

import java.util.concurrent.locks.ReentrantLock;
class LinkedQueue {
    private final ReentrantLock lock = new ReentrantLock();
    private int counter = 0;
    public boolean appendNode(String name) {
        lock.lock();
        try {
            // 링크 갱신 + counter 갱신만 보호
            // tail.prev.next = newUser;
            // tail.prev = newUser;
            // counter++;
            return true;
        } finally {
            lock.unlock();
        }
    }
    public UserData removeAtHead() {
        lock.lock();
        try {
            // 링크 갱신 + counter 갱신만 보호
            // head.next = node.next;
            // node.next.prev = head;
            // counter--;
            return null;
        } finally {
            lock.unlock();
        }
    }
}

• 장점
  • 임계 영역을 줄이기 쉽습니다.
  • tryLock() 같은 선택지도 생깁니다.
• 단점
  • 락 해제를 빼먹으면 장애로 이어집니다.
  • 설계 난도가 올라갑니다.

CAS Compare And Swap이란 무엇인가

• CAS는 Compare And Swap 또는 Compare And Set입니다.
• 락 없이 원자적으로 바꾸기 위한 핵심 원리입니다.
• CPU가 제공하는 원자 명령을 이용합니다.
  • 대표적으로 cmpxchg 계열이 유명합니다. (CPU/아키텍처마다 표현은 다릅니다)
• CAS는 아래를 “한 번에” 처리합니다.
  • 현재 값이 기대값인지 비교
  • 기대값이면 새 값으로 교체
  • 성공 실패를 반환

왜 CAS가 Lock free를 가능하게 하나

• 임계 영역을 “잠그는 방식”이 아닙니다.
• 대신 “충돌하면 다시 시도하는 방식”입니다.
• 그래서 커널 블로킹을 줄일 수 있습니다.

Spin lock은 무엇인가

• 스핀 락은 락을 얻을 때까지 반복문으로 재시도합니다.
• 반복문은 CPU 시간을 계속 씁니다.
• 그래서 스핀 락은 아래에서만 이득입니다.
• 이득 조건
  • 임계 영역이 매우 짧습니다.
  • 경쟁 스레드 수가 적습니다.
  • 락이 곧 풀릴 가능성이 큽니다.

CAS 기반 SpinLock 예제

• 보통은 직접 구현하지 않습니다.
• 학습 목적이나 특수한 경우에만 구현합니다.

AtomicBoolean + LockSupport.parkNanos 예제

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.locks.LockSupport;
class SpinLock {
    private final AtomicBoolean locked = new AtomicBoolean(false);
    public void lock() {
        while (!locked.compareAndSet(false, true)) {
            // 너무 공격적으로 돌면 CPU를 태움
            LockSupport.parkNanos(1_000); // 1us 정도 쉬며 재시도
        }
    }
    public void unlock() {
        locked.set(false);
    }
}

• compareAndSet(false, true)가 CAS입니다.
• parkNanos는 불필요한 CPU 소모를 줄이는 데 도움이 될 수 있습니다.
• 단, 값은 상황별로 튜닝이 필요합니다. (정답은 없습니다)

Lock free 큐가 좋은 예가 되는 이유

• 큐는 선형 자료구조입니다.
• 단일 연결 리스트 기반 큐는 핵심 참조가 단순합니다.
  • head 참조
  • tail 참조
  • node.next 참조
• 이 참조 변경에 CAS를 적용하면 lock free 접근이 가능해집니다.

AtomicReference를 쓰는 이유

• 참조자 변경이 “원자적으로” 이뤄져야 합니다.
• 그래서 AtomicReference<Node>로 head나 tail을 감쌉니다.
• 핵심은 “참조자 한 칸 교체”를 CAS로 만드는 것입니다.

lock free가 항상 이기나

• lock free는 경합이 적고 임계 영역이 작을 때 유리할 수 있습니다.
• 경합이 심해지면 재시도가 늘어서 비용이 커질 수 있습니다.
• 그래서 어느 순간에는 ReentrantLock과 큰 차이가 없어질 수 있습니다. (상황 의존입니다)

결론

• 멀티스레드에서 큐가 자주 등장하고 자주 깨집니다.
• 연결 리스트는 포인터 갱신이 여러 단계라 레이스에 취약합니다.
• 해결은 단계적으로 접근하는 게 좋습니다.
• 1단계
  • synchronized로 correctness를 먼저 확보합니다.
• 2단계
  • ReentrantLock으로 임계 영역을 줄입니다.
• 3단계
  • CAS 기반으로 lock free 구조를 검토합니다.
• 임계 영역 판단이 결국 성능과 안정성을 갈라놓습니다.