락프리 데이터 구조: C++, Java 및 .NET 예제를 포함한 완벽 가이드

뮤텍스는 간단합니다. 잠그고, 공유 상태를 수정하고, 다시 잠금을 해제하면 됩니다. 접근을 원하는 모든 스레드는 차례를 기다립니다. 문제는 바로 이 "차례를 기다리는 것"입니다. 코어 수가 많고 처리량이 높은 시스템에서는 직렬화 자체가 한계가 됩니다. 잠금을 보유한 스레드가 선점되면 다른 모든 스레드가 유휴 상태가 될 수 있습니다. 우선순위 반전으로 인해 우선순위가 낮은 스레드가 우선순위가 높은 스레드를 차단할 수도 있습니다. 수십 개의 코어에서 초당 수백만 개의 연산을 처리하는 시스템에서는 뮤텍스 경합이 단순히 속도를 저하시키는 것을 넘어 처리량을 급격히 떨어뜨립니다.

락 프리 데이터 구조는 상호 배제를 원자적 연산으로 대체합니다. 충돌을 방지하는 대신, 충돌을 허용하고 복구합니다. 비교 및 ​​교환 연산에 실패한 스레드는 업데이트된 상태로 재시도합니다. 어떤 스레드도 다른 스레드를 차단하지 않으며, 적어도 하나의 스레드는 항상 작업을 진행합니다. 결과적으로, 높은 경쟁 상황에서 처리량이 크게 향상되고, 컨보이 효과 없이 예측 가능한 지연 시간을 제공하며, 설계상 교착 상태와 우선순위 역전을 방지합니다. 하지만 구현 복잡성이 단점입니다. ABA 문제, 메모리 회수 위험, 거짓 공유, 미묘한 메모리 순서 요구 사항 등은 락 기반 코드에서는 존재하지 않는 함정입니다. 이 글에서는 구체적인 코드를 통해 이러한 함정들을 모두 다룹니다.

락프리, 웨이트프리, 뮤텍스: 어떤 것을 사용해야 할까요?

구현 방식을 선택하기 전에, 시스템에 실제로 필요한 진행 보장이 무엇인지 먼저 질문해야 합니다. 세 가지 모델은 스레드 간 경쟁이 발생할 때 보장하는 내용이 서로 다릅니다.

모델	진행 보장	일반적인 대기 시간	복잡성	지원 기기
뮤텍스/락 기반	차단 중, 스레드 대기	논쟁 중 예측 불가능	높음	경쟁이 적은 공유 상태, 간단한 정확성 요구 사항
잠금장치 없음	시스템 전체적으로, 적어도 하나의 스레드가 진행됩니다.	경쟁이 치열한 상황에서 낮은	높음	고처리량 큐, 스택, 카운터
대기 시간 없음	각 스레드는 스레드별로 정해진 단계 내에 완료됩니다.	제한된 최악의 경우	매우 높은	실시간 시스템, 안전 필수, 엄격한 지연 시간 SLA
장애물 없음	솔로 진행은 경쟁자가 없을 때만 가능합니다.	논쟁 없이 낮음	중급	거래 기억 프로토타입, 연구 맥락

락프리(Lock-free) 방식 은 고동시성 운영 시스템에서 실질적으로 기본 설정입니다. 마이클-스콧 큐, 트라이버 스택, 그리고 대부분의 실제 MPMC 링 버퍼는 락프리 방식으로 작동합니다. 극심한 경쟁 상황에서는 개별 스레드가 자원 고갈로 멈출 수 있지만, 시스템 전체는 정상적으로 작동합니다.

대기 없는(Wait-free) 방식은 스레드별 제한된 진행률을 보장하지만, 훨씬 더 복잡한 알고리즘을 요구합니다. 범용적인 구성 방식은 존재하지만 오버헤드가 높습니다. 대기 없는 알고리즘은 평균 처리량보다 꼬리 지연 시간이 더 중요한 엄격한 실시간 환경에 적합합니다.

장애물 없는(Obstruction-free) 방식 은 실제 운영 환경에서 직접적으로 사용되는 경우는 드뭅니다. 일부 트랜잭션 메모리 구현에서 나타나며, 알고리즘의 정확성을 입증할 때 디딤돌 역할을 합니다.

대부분의 고동시성 시스템에서는 경합이 적고 정확성이 간단할 때는 뮤텍스를 사용하고, 경합 상황에서의 처리량이 중요할 때는 락프리(lock-free) 방식을 사용하며, 최악의 경우 스레드별 지연 시간이 필수적인 경우에만 웨이트프리(wait-free) 방식을 사용합니다.

락프리 데이터 구조란 무엇인가요?

데이터 구조가 락프리(lock-free) 라는 것은 해당 구조를 연산하는 모든 스레드 중 적어도 하나는 다른 스레드의 작업이나 스케줄링 방식과 관계없이 유한한 단계 내에 연산을 완료한다는 것을 보장하는 것을 의미합니다. 이 공식적인 정의는 다음과 같은 정확한 함의를 갖습니다. 락프리 알고리즘은 교착 상태에 빠질 수 없습니다. 하나의 스레드가 정지되거나, 일시 중단되거나, 느리게 실행되더라도 다른 스레드는 계속해서 작업을 진행할 수 있습니다.

이 메커니즘은 원자적 연산, 즉 하나의 분할 불가능한 단위로 실행되는 CPU 명령어에 기반합니다. 보편적인 기본 연산은 CAS(Compare-and-Swap) 입니다.

CAS(location, expected, new_value):
  if *location == expected:
    *location = new_value
    return true
  else:
    return false  // someone else changed it first

CAS는 하드웨어 수준에서 원자적입니다. x86에서는 다음과 같습니다. CMPXCHG 명령어입니다. ARM에서는 다음과 같이 구현됩니다. LDXR/STXR (로드 전용/저장 전용)은 LL/SC(로드 연결/저장 조건부) 변형입니다. 스레드는 값을 읽고 새 값을 계산한 다음, 다른 스레드에서 값을 변경하지 않은 경우에만 CAS를 사용하여 해당 값을 설치합니다. CAS가 실패하면 스레드는 새 값으로 다시 시도합니다.

C++11 이상 버전에서는 이 기능이 다음과 같이 노출됩니다. std::atomic:

CPP

#include <atomic>

// Atomic increment using CAS loop
void atomic_add(std::atomic<int>& counter, int delta) {
    int expected = counter.load(std::memory_order_relaxed);
    while (!counter.compare_exchange_weak(
        expected,
        expected + delta,
        std::memory_order_release,
        std::memory_order_relaxed))
    {
        // expected is updated on failure -- retry with fresh value
    }
}

compare_exchange_weak CAS 기본 요소입니다. 실패 시 업데이트됩니다. expected 현재 값으로 자동 변환되어 재시도 루프가 관용적인 표현이 됩니다.

ABA 문제: Lock-Free의 가장 위험한 함정

ABA 문제는 락프리 프로그래밍에서 가장 직관적이지 않은 정확성 위험 요소입니다. CAS는 새로운 값을 저장하기 전에 메모리 위치에 예상 값이 여전히 존재하는지 확인합니다. 하지만 읽기 작업과 CAS 호출 사이에 해당 값이 변경되었다가 다시 원래대로 되돌아갔는지 여부는 감지할 수 없습니다. 메모리 위치는 겉보기에는 원래 값처럼 보이지만, 시스템의 근본적인 상태는 CAS가 감지할 수 없는 방식으로 변경되었을 수 있습니다.

시나리오 단계별 설명

단일 포인터를 사용하는 락프리 스택을 생각해 보세요. top:

1. 스레드 A는 다음과 같습니다. top = Node1Node1의 다음 포인터는 Node2입니다.
2. 스레드 A는 실행이 완료되기 전에 선점되었습니다.
3. 스레드 B는 Node1을 팝하고(top은 Node2가 됨), 그 다음 Node2를 팝합니다(top은 null이 됨).
4. 스레드 B가 새 노드를 푸시하는데, 이 노드는 Node1과 동일한 메모리 주소에 할당됩니다(자유 목록 할당자에서 흔히 볼 수 있는 현상). Top = Node1(동일한 포인터, 다른 내용).
5. 스레드 A가 재개됩니다. 해당 CAS는 다음과 같이 봅니다. top == Node1 (기대값)이 성공하면 설정됩니다. top = Node2하지만 Node2는 이미 사용 가능했습니다. 큰일 났네.

ABA 문제는 각 데이터 구조에서 서로 다른 방식으로 나타납니다.

• 스택CAS는 성공하지만 오래된 다음 포인터를 설치하여 해제 후 사용 오류를 발생시킵니다.
• 열머리나 꼬리를 가리키는 포인터는 겉보기에는 변하지 않았지만 구조는 바뀌었습니다.
• 연결된 목록노드가 여전히 제 위치에 있는 것처럼 보이지만 실제로는 제거되어 재할당되었습니다.

LL/SC는 ABA 문제를 피할 수 있을까요?

네, LL/SC(Load-Linked/Store-Conditional)는 CAS보다 강력한 의미 체계를 제공하며 ABA(Analytic Hierarchy Assessment)를 자연스럽게 방지합니다. LL은 로드된 메모리 주소를 "연결됨"으로 표시합니다. 동일한 주소에 대한 SC는 LL 이후 해당 주소에 저장 작업이 발생한 경우, 값이 원래 상태로 복원되었더라도 실패합니다. 수정 이력은 현재 값뿐만 아니라 하드웨어 수준에서도 추적됩니다.

하지만 실제 하드웨어에서 LL/SC를 구현하는 데에는 현실적인 한계가 있습니다. ARM 및 POWER 아키텍처에서는 컨텍스트 스위치나 캐시 제거와 같은 경쟁 상황이 없더라도 LL/SC 오류가 발생할 수 있습니다. 따라서 코드는 실제 충돌이 없더라도 재시도 루프를 고려해야 합니다. x86 아키텍처에는 네이티브 LL/SC 기능이 없으며, CAS가 하드웨어 프리미티브입니다. x86 코드의 경우, ABA(애플리케이션 기반 캐시)는 소프트웨어적으로 방지해야 합니다.

ABA 개선 방안: 세 가지 접근법

1. 버전 카운터(태그된 포인터)

버전 카운터를 포인터와 동일한 원자 워드에 저장합니다. CAS 작업이 성공할 때마다 카운터가 증가합니다. 포인터가 원래 값으로 돌아가더라도 카운터 값은 달라집니다.

CPP

#include <atomic>
#include <cstdint>

struct TaggedPtr {
    uintptr_t ptr : 48;  // pointer (48-bit virtual address space)
    uintptr_t tag : 16;  // version counter
};

std::atomic<TaggedPtr> top;

bool cas_with_tag(std::atomic<TaggedPtr>& loc,
                  TaggedPtr expected,
                  void* new_ptr) {
    TaggedPtr desired = { (uintptr_t)new_ptr, expected.tag + 1 };
    return loc.compare_exchange_strong(expected, desired);
}

이것이 실제 표준 접근 방식입니다. 16비트 태그는 65,536번의 연산 후에 다시 돌아오는데, 이론적으로는 안전하지 않지만 대부분의 시스템에서는 실질적으로 충분합니다. 스레드가 동일한 위치에서 정확히 65,536번의 CAS 사이클 동안 선점될 가능성은 극히 낮습니다.

2. 위험 지표

각 스레드는 현재 접근 중인 노드를 가리키는 포인터인 "위험 포인터" 집합을 유지합니다. 스레드는 노드를 해제하기 전에 모든 위험 포인터 레지스트리를 확인하여 다른 스레드가 해당 노드에 접근하고 있지 않은지 확인합니다. 위험 포인터에 나타나는 노드는 해당 포인터가 해제될 때까지 해제가 지연됩니다.

CPP

// Simplified hazard pointer pattern
thread_local void* hazard_ptr = nullptr;

void* safe_load(std::atomic<void*>& head) {
    void* ptr;
    do {
        ptr = head.load(std::memory_order_acquire);
        hazard_ptr = ptr;                          // announce we are using this
        // memory fence ensures announcement is visible before validation
        std::atomic_thread_fence(std::memory_order_seq_cst);
    } while (ptr != head.load(std::memory_order_acquire)); // validate still valid
    return ptr;
}

void safe_release() {
    hazard_ptr = nullptr;
}

위험 포인터는 메모리 회수 수준에서 ABA(액티브 스레드 자동화)를 방해합니다. 즉, 어떤 스레드라도 해당 노드에 대한 위험 포인터를 보유하고 있는 동안에는 노드를 재사용할 수 없습니다. 따라서 메모리를 해제하기 전에 모든 스레드의 위험 포인터를 검사해야 하므로 스레드 수에 비례하는 오버헤드가 발생합니다.

3. 시대 기반 복원(EBR)

스레드는 전역적으로 추적되는 "에포크" 단위로 작동합니다. 종료된 노드는 에포크별로 버퍼링되며, 모든 스레드가 해당 노드가 종료된 에포크를 지나간 후에야 해제됩니다. EBR은 위험 포인터보다 사용이 간편하고 연산당 오버헤드가 낮지만, 대기 기간 동안 메모리 사용량이 제한적이지만 예측 불가능하게 증가할 수 있다는 단점이 있습니다.

자바에서는 AtomicStampedReference 참조와 정수 스탬프를 짝지어 ABA 문제를 직접적으로 해결합니다.

자바

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<Node> top =
    new AtomicStampedReference<>(null, 0);

void push(Node newNode) {
    int[] stamp = new int[1];
    Node current;
    do {
        current = top.get(stamp);
        newNode.next = current;
    } while (!top.compareAndSet(current, newNode, stamp[0], stamp[0] + 1));
}

락프리 큐 구현

큐는 가장 일반적으로 필요한 락프리(lock-free) 구조입니다. 대표적인 락프리 큐는 마이클-스콧(Michael-Scott) 큐로, 두 개의 포인터(헤드와 테일)와 센티널 노드를 사용하여 동시적인 큐 추가 및 제거 작업을 허용합니다.

SPSC 큐: 최소한의 동기화로 최대의 성능 구현

단일 생산자-단일 소비자 큐는 쓰기-쓰기 및 읽기-읽기 경합을 모두 제거합니다. 한 스레드는 큐의 끝에 쓰고, 다른 스레드는 끝에 읽습니다. 생산자와 소비자 간에 공유되는 것은 끝에 대한 포인터뿐입니다.

CPP

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer;
    alignas(64) std::atomic<size_t> head{0}; // consumer reads head
    alignas(64) std::atomic<size_t> tail{0}; // producer writes tail
    // alignas(64) puts each on a separate cache line -- prevents false sharing

public:
    bool push(const T& item) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % Capacity;
        if (next == head.load(std::memory_order_acquire))
            return false; // full
        buffer[t] = item;
        tail.store(next, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t h = head.load(std::memory_order_relaxed);
        if (h == tail.load(std::memory_order_acquire))
            return false; // empty
        item = buffer[h];
        head.store((h + 1) % Capacity, std::memory_order_release);
        return true;
    }
};

The alignas(64) 헤드와 테일의 순서는 매우 중요합니다. 순서가 없으면 두 작업 모두 동일한 캐시 라인에 저장됩니다. 테일에 대한 모든 쓰기 작업은 코어 읽기 헤드에서 볼 수 있는 캐시 라인 무효화를 유발하고, 반대로 테일에 대한 쓰기 작업이 헤드에서 헤드로 전달되면 잘못된 공유가 발생하여 독립적이어야 할 작업이 직렬화됩니다.

MPMC 대기열: 다중 생산자 다중 소비자

완전 동시 실행 MPMC 큐는 훨씬 더 복잡합니다. 실제 구현에서는 락 없이 생산자와 소비자를 조정하기 위해 슬롯당 순번을 사용합니다.

CPP

#include <atomic>
#include <array>

template<typename T, size_t Capacity>
class MPMCQueue {
    struct Slot {
        std::atomic<size_t> sequence;
        T data;
    };

    alignas(64) std::array<Slot, Capacity> slots;
    alignas(64) std::atomic<size_t> enqueue_pos{0};
    alignas(64) std::atomic<size_t> dequeue_pos{0};

public:
    MPMCQueue() {
        for (size_t i = 0; i < Capacity; ++i)
            slots[i].sequence.store(i, std::memory_order_relaxed);
    }

    bool push(const T& item) {
        size_t pos = enqueue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        // wait for the slot to be ready for writing
        while (seq != pos) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        slot.data = item;
        slot.sequence.store(pos + 1, std::memory_order_release);
        return true;
    }

    bool pop(T& item) {
        size_t pos = dequeue_pos.fetch_add(1, std::memory_order_relaxed);
        Slot& slot = slots[pos % Capacity];
        size_t seq = slot.sequence.load(std::memory_order_acquire);
        while (seq != pos + 1) {
            seq = slot.sequence.load(std::memory_order_acquire);
        }
        item = slot.data;
        slot.sequence.store(pos + Capacity, std::memory_order_release);
        return true;
    }
};

.NET 동시 큐: 내부 작동 방식

.NET의 ConcurrentQueue<T> .NET 5 이상에서는 세그먼트 배열 구조를 사용합니다. 각 세그먼트는 헤드 및 테일 인덱스로 관리되는 고정 크기 배열입니다. Interlocked (하드웨어의 CAS에 매핑되는) 연산입니다. 세그먼트는 휘발성 메모리를 통해 연결됩니다. _nextSegment 포인터입니다. enqueue는 현재 테일 세그먼트에 데이터를 추가하고, 세그먼트 체인이 가득 차면 크기를 늘립니다. dequeue는 헤드 세그먼트에서 데이터를 읽고 헤드 인덱스를 원자적으로 증가시킵니다.

핵심 설계 결정은 글로벌 고착을 피하는 것입니다. 생산자는 현재 세그먼트의 꼬리 지수에서만 경쟁하고, 소비자는 머리 지수에서만 경쟁합니다. 어떤 생산자도 소비자와 직접 경쟁하지 않습니다. 이것이 바로 ConcurrentQueue<T> 생산자-소비자 파이프라인에 매우 효율적입니다.

날카로운

using System.Collections.Concurrent;
using System.Threading;

// .NET ConcurrentQueue -- lock-free, thread-safe, FIFO
var queue = new ConcurrentQueue<int>();

// Producer thread
var producer = Task.Run(() => {
    for (int i = 0; i < 1_000_000; i++)
        queue.Enqueue(i);
});

// Consumer thread
var consumer = Task.Run(() => {
    long sum = 0;
    while (!queue.IsEmpty || !producer.IsCompleted) {
        if (queue.TryDequeue(out int item))
            sum += item;
        else
            Thread.SpinWait(1);  // brief spin before retry
    }
    return sum;
});

await Task.WhenAll(producer, consumer);

락프리 코드에서의 캐시 일관성과 거짓 공유

락프리 구현에서 캐시 일관성은 눈에 보이지 않는 성능 변수입니다. 코어가 메모리 위치에 쓰기를 수행하면 해당 위치를 포함하는 64바이트 캐시 라인 전체가 다른 모든 코어의 캐시에서 무효화됩니다. 따라서 다른 코어들은 읽기 전에 업데이트된 라인을 가져와야 합니다. 원자적 업데이트가 빈번하게 발생하는 락프리 코드에서는 이러한 캐시 라인 무효화가 주요 비용 요소가 될 수 있습니다.

거짓 공유는 두 스레드가 캐시 라인을 공유하는 서로 다른 변수를 수정할 때 발생합니다. 두 스레드 모두 동일한 데이터에 접근하는 것이 아니지만, 캐시 일관성 프로토콜은 전체 캐시 라인을 경쟁이 있는 것으로 간주합니다.

CPP

// BAD: head and tail on the same cache line
struct BadQueue {
    std::atomic<size_t> head;   // bytes 0-7
    std::atomic<size_t> tail;   // bytes 8-15
    // both fit in the same 64-byte cache line
    // producer writing tail invalidates head in consumer's cache
};

// GOOD: head and tail on separate cache lines
struct GoodQueue {
    alignas(64) std::atomic<size_t> head;
    alignas(64) std::atomic<size_t> tail;
    // each on its own cache line -- no false sharing
};

MESI 프로토콜(Modified, Exclusive, Shared, Invalid)은 x86 CPU가 캐시 라인 소유권을 어떻게 조정하는지 설명합니다. 코어가 다른 코어와 공유하는 위치(Shared 상태)에 쓰기 작업을 수행하려면 쓰기 요청을 브로드캐스트하고, 모든 공유 코어로부터 승인을 기다린 후 Modified 상태로 전환해야 합니다. 이러한 일관성 프로토콜 왕복 과정은 멀티 소켓 시스템에서 50~300 사이클 이상을 소모합니다. 잘못된 공유(False sharing)는 독립적인 스레드 로컬 작업을 캐시 일관성 트래픽으로 전환시켜 코어 수에 비례하여 선형적으로 확장되어야 하는 성능을 저하시킵니다.

허위 공유 감지: 사용 perf stat -e cache-misses,L1-dcache-load-misses Linux 또는 Windows의 Visual Studio CPU 성능 프로파일러에서 확인할 수 있습니다. 캐시에 들어갈 수 있는 멀티스레드 프로그램에서 L1 캐시 미스율이 높다는 것은 거짓 공유(false sharing)의 강력한 지표입니다.

메모리 순서 지정: 왜 중요할까요? memory_order_relaxed 항상 충분한 것은 아닙니다.

C + + std::atomic 이 연산들은 C++11 메모리 모델에서 제공하는 모든 메모리 순서 지정 방식을 보여줍니다. 잘못된 순서 지정은 ABA 문제 다음으로 락프리 코드에서 두 번째로 흔한 버그입니다.

CPP

// The five memory orderings and when each applies:

// relaxed: no synchronization, only atomicity
// Use for: counters where only the final value matters
counter.fetch_add(1, std::memory_order_relaxed);

// acquire: reads see all writes by threads that released this location
// Use for: reading shared state protected by a flag
if (ready.load(std::memory_order_acquire)) {
    use(data); // guaranteed to see all writes made before ready was set
}

// release: writes are visible to threads that acquire this location
// Use for: publishing shared state
data = compute();
ready.store(true, std::memory_order_release);

// acq_rel: acquire + release in one operation
// Use for: read-modify-write operations like CAS in the middle of a chain
node.compare_exchange_strong(expected, desired,
    std::memory_order_acq_rel,   // success
    std::memory_order_acquire);  // failure

// seq_cst: total order across all seq_cst operations, all cores
// Use for: when you need a global consistent view (but slowest)
flag.store(true, std::memory_order_seq_cst);

흔히 저지르는 실수: 사용 relaxed 릴리스 플래그의 경우. 설정하는 스레드 ready = true 과 relaxed 순서가 앞선 쓰기 작업이 반드시 뒤따라오는 것을 보장하지는 않습니다. data 다른 스레드에서 읽을 때 볼 수 있습니다. ready획득/해제 쌍은 작성자와 판독자를 연결하는 선행 관계를 생성합니다.

트라이버 스택: C++의 락프리 스택

트라이버 스택은 가장 간단한 비자명 락프리 데이터 구조입니다. 이는 단일 객체에 대한 CAS 루프를 사용합니다. top 바늘:

CPP

#include <atomic>

template<typename T>
class TreiberStack {
    struct Node {
        T data;
        Node* next;
        explicit Node(T d) : data(std::move(d)), next(nullptr) {}
    };

    std::atomic<Node*> top{nullptr};

public:
    void push(T data) {
        Node* node = new Node(std::move(data));
        node->next = top.load(std::memory_order_relaxed);
        while (!top.compare_exchange_weak(
            node->next,          // expected -- updated on failure
            node,                // desired
            std::memory_order_release,
            std::memory_order_relaxed))
        { /* retry */ }
    }

    bool pop(T& result) {
        Node* node = top.load(std::memory_order_acquire);
        while (node) {
            if (top.compare_exchange_weak(
                node,
                node->next,      // new top
                std::memory_order_acquire,
                std::memory_order_relaxed))
            {
                result = std::move(node->data);
                // WARNING: cannot free node here safely without hazard pointers or EBR
                // delete node; -- ABA hazard if another thread reads node->next
                return true;
            }
        }
        return false; // empty
    }
};

댓글 delete node 이는 매우 중요합니다. 단순 삭제는 앞서 설명한 ABA 위험 요소입니다. 실제 Treiber 스택 환경에서 노드 회수를 위해서는 위험 요소 포인터, 에포크 기반 회수 또는 가비지 컬렉션(Java/C#은 이를 자동으로 처리함)이 필요합니다.

Java 락프리 데이터 구조

Java 표준 라이브러리는 프로덕션 수준의 락프리(lock-free) 구현을 제공합니다. java.util.concurrent:

클래스	Structure	진행	노트
AtomicReference<T>	단일 값	잠금장치 없음	객체 참조에 대한 CAS
AtomicStampedReference<T>	가격 + 우표	잠금장치 없음	버전 카운터를 통한 ABA 예방
ConcurrentLinkedQueue<T>	마이클-스콧 대기열	잠금장치 없음	FIFO, 무제한
ConcurrentLinkedDeque<T>	잠금 해제 데크	잠금장치 없음	양쪽 끝
LongAdder	계수기	잠금장치 없음	줄무늬형, 고처리량 계수

LongAdder 특히 주목할 만한 점은 모든 스레드에서 경쟁하는 단일 원자적 카운터 대신, 스레드 하위 집합에서 각각 접근할 수 있는 카운터들의 스트라이프 배열을 유지한다는 것입니다. 따라서 경쟁은 한 곳에 집중되지 않고 스트라이프 전체에 분산됩니다. 총합은 지연 계산 방식으로 계산됩니다. sum()여러 스레드에 걸쳐 빈번하게 증가하는 연산 작업을 수행할 때, LongAdder 현저하게 뛰어난 성과를 낸다 AtomicLong.incrementAndGet():

자바

import java.util.concurrent.atomic.LongAdder;

// BAD for high-concurrency counting: all threads contend on one location
AtomicLong counter = new AtomicLong(0);
counter.incrementAndGet(); // single CAS -- all threads collide

// GOOD for high-concurrency counting: contention distributed across stripes
LongAdder adder = new LongAdder();
adder.increment();  // updates thread-local stripe -- minimal contention
long total = adder.sum(); // sum all stripes lazily

방법 SMART TS XL 락 프리 시스템 개발을 지원합니다.

락 프리 코드는 제대로 작성하기 가장 어려운 코드 유형 중 하나입니다. 버그는 비결정적이며, 특정 실행 순서에서만 나타나고, 대규모 운영 환경에서만 발견되는 경우가 많습니다. 정적 분석은 경쟁 조건이 발생할 때까지 기다리는 대신 실행 전에 코드의 구조적 특성을 검사함으로써 이러한 문제를 해결합니다.

SMART TS XL 이 도구는 동시 실행 코드의 전체 실행 경로를 분석하여 원자적 연산이 보호하는 메모리 위치와 어떻게 관련되는지 추적합니다. 락 프리 코드와 레거시 구성 요소 또는 다중 언어 아키텍처가 혼합된 시스템의 경우, 단일 언어 도구로는 불가능한 경계 간 가시성을 제공합니다. 예를 들어 락 프리 C++ 구성 요소가 액세스하는 공유 메모리 영역이 해당 영역에서 읽는 Java 서비스와 어떻게 관련되는지, 또는 동시 실행 큐가 COBOL 기반 처리 파이프라인에 어떻게 연결되는지 등을 파악할 수 있습니다.

정적 코드 분석 기능은 동시성 위험과 관련된 패턴을 식별합니다. 예를 들어, 상응하는 획득 의미 체계가 없는 원자적 로드, 실패 시 예상 값을 업데이트하지 않는 CAS 루프, 서로 다른 스레드에서 접근하는 필드가 정렬 패딩 없이 같은 위치에 있는 공유 데이터 구조 등이 있습니다. 영향 분석 기능은 공유 동시성 데이터 구조에 의존하는 하위 구성 요소를 추적하여 구조의 인터페이스 또는 회수 전략을 변경하기 전에 변경 범위를 정확하게 지정할 수 있도록 합니다.

락프리(lock-free) 구성 요소가 기존 배치 처리, 메시지 큐잉 미들웨어 및 최신 서비스 계층과 공존해야 하는 엔터프라이즈 시스템의 경우, SMART TS XL의 종속성 매핑 이 문서는 시스템 스택 전체에 걸쳐 서로 다른 언어로 작성된 구성 요소를 연결하는 동시 데이터 경로의 아키텍처적 관점을 제공합니다.

잠금장치가 없는 것이 잘못된 선택일 때

락프리 방식이 항상 뮤텍스 방식보다 나은 것은 아닙니다. 락프리 구조가 유리한지는 실제 워크로드의 경합 양상에 따라 달라집니다. 스레드 수가 적거나 경합이 낮은 경우에는 잘 구현된 뮤텍스 방식이 원자적 재시도 루프와 코어 간 캐시 라인 무효화에 따른 오버헤드를 줄여주기 때문에 더 빠를 수 있습니다.

다음과 같은 경우에 뮤텍스를 사용하십시오:

• 실의 밀도가 낮거나(4~8개 미만) 실 뭉침 현상이 드물다
• 중요 구간은 길고 복잡합니다(단면적 대비 잠금 방지 루프를 사용하는 데 비용이 많이 듭니다).
• 정확성이 처리량보다 더 중요하며, 락을 사용하면 알고리즘이 더 간단해집니다.
• 이 플랫폼은 효율적인 futex 기반 잠금 기능을 갖추고 있습니다(리눅스). pthread_mutex(윈도우 SRWLOCK)

다음과 같은 경우 잠금 해제 기능을 사용하세요:

• 실의 밀도가 높고 긴장감이 지속됩니다.
• 연산 시간은 짧습니다 (CAS 루프 오버헤드가 연산 시간에 비해 작습니다).
• 블로킹은 허용되지 않습니다 (실시간 스레드, 인터럽트 핸들러, 시그널 핸들러).
• 락이 락 순서 종속성을 유발할 수 있는 다른 락 프리 구조와 함께 구성합니다.

다음과 같은 경우 대기 시간 없이 사용하세요:

• 모든 스레드는 다른 스레드와 관계없이 정해진 시간 내에 완료되어야 합니다.
• 기아 상태가 용납될 수 없는 긴급한 실시간 요구 사항 또는 안전 필수 요구 사항
• 이 알고리즘은 스레드별로 제한된 단계 수만큼 완료되도록 구성될 수 있습니다.

락프리 프로그래밍의 핵심은 모든 곳에서 락프리를 선택하는 것이 아니라, 락프리의 속성, 즉 비차단 진행, 교착 상태 제거, 선점 허용 등이 시스템의 실제 요구 사항과 정확히 일치하는 곳에서 락프리를 선택하는 것입니다.