Lock-free Stack Lock-free Stack은 락(lock)을 사용하지 않고 동시성을 제공하는 LIFO(Last-In-First-Out) 자료구조. 이 자료구조는 여러 스레드가 동시에 스택에 접근할 수 있으며, 시스템 전체의 진행을 보장한다. 특징 동시성 지원: 여러 스레드가 동시에 스택에 접근하고 수정할 수 있다. 락 사용 없음: 전통적인 동기화 기법인 락을 사용하지 않는다. 진행 보장: 시스템 전체의 진행을 보장하며, 개별 스레드의 기아 현상이 발생할 수 있다. 원자적 연산 사용: Compare-And-Swap(CAS)과 같은 원자적 연산을 사용한다. 구현 방식 Lock-free Stack은 주로 다음과 같은 방식으로 구현된다: ...
Concurrent Hash Map ConcurrentHashMap은 여러 스레드가 동시에 안전하게 접근할 수 있도록 설계된 HashMap의 동시성 버전이다. 이 자료구조는 멀티스레드 환경에서 높은 성능과 확장성을 제공하면서도 스레드 안전성을 보장한다. Java의 동시성 컬렉션 중 하나로, 멀티스레드 환경에서 안전하게 사용할 수 있도록 설계된 Map 구현체이다. Java를 제외한 프로그래밍 언어와 라이브러리에서도 동시성을 지원하기 위해 구현되어 있는 자료 구조이다. 특징 Thread-safe: 내부적으로 동기화 처리가 되어 있어 멀티스레드 환경에서 안전하다. 높은 동시성: 여러 스레드가 동시에 맵을 수정할 수 있으며, 읽기 작업은 락 없이 수행된다. 원자적 연산 지원: putIfAbsent(), replace(), remove() 등의 원자적 연산을 제공한다. 일관성 있는 반복자: 반복자가 생성된 시점의 맵 상태를 반영하며, ConcurrentModificationException을 발생시키지 않는다. 락 스트라이핑(Lock Striping): 맵을 여러 부분으로 나누어 각각 독립적으로 잠금을 걸어 동시성을 향상시킨다. Null 불허: 키와 값에 null을 허용하지 않는다. 이는 동시성 환경에서 null의 의미가 모호해질 수 있기 때문이다. 약한 일관성: 순간적으로 맵의 상태가 일관되지 않을 수 있지만, 최종적으로는 일관된 상태로 수렴한다. 구현 방식 ConcurrentHashMap은 다음과 같은 기술을 사용하여 구현된다: ...
Concurrent Skip List Concurrent Skip List는 Skip List 자료구조를 기반으로 하여 멀티스레드 환경에서 동시에 삽입, 삭제, 검색 작업을 수행할 수 있도록 구현된 동시성 자료구조이다. Skip List는 여러 계층의 연결 리스트로 구성된 정렬된 데이터 구조인데, ConcurrentSkipList는 이를 멀티스레드 환경에서 안전하게 사용할 수 있도록 구현한 것이다. 이 자료구조는 락-프리(lock-free) 또는 세밀한 동기화 메커니즘을 사용하여 높은 동시성을 제공한다. 특징 동시성 지원: 여러 스레드가 동시에 자료구조에 접근하고 수정할 수 있다. 락-프리 구현: 대부분의 연산에서 락을 사용하지 않고 Compare-and-Swap(CAS) 연산을 활용한다. 확장성: 멀티코어 시스템에서 높은 확장성을 제공한다. 로그 시간 복잡도: 평균적으로 O(log n) 시간 복잡도로 검색, 삽입, 삭제 연산을 수행한다. 확률적 균형: 재조정 작업 없이 확률적으로 균형을 유지한다. 구현 방식 레벨별 락-프리 리스트: 각 레벨의 리스트를 락-프리 연결 리스트로 취급한다. CAS 연산 사용: 노드 삽입 시 CAS 연산을 사용하여 동시성을 제어한다. 마킹 기법: 노드 삭제 시 다음 참조를 마킹하여 논리적 삭제를 수행한다. 도움 메커니즘: find() 메서드가 마킹된 노드를 정리하는 역할을 수행한다. 장점 높은 동시성: 여러 스레드가 동시에 작업을 수행할 수 있어 성능이 향상된다. 확장성: 스레드 수가 증가해도 성능 저하가 적다. 간단한 구현: 동시성 트리 구조에 비해 구현이 상대적으로 간단하다. 메모리 효율성: 일부 트리 구조보다 메모리 효율적일 수 있다. 응용 동시성 우선순위 큐: 멀티스레드 환경에서 효율적인 우선순위 큐 구현에 사용된다. 데이터베이스 시스템: 동시성 인덱싱 구조로 활용된다. 분산 시스템: 분산 환경에서의 정렬된 데이터 관리에 사용된다. 캐시 시스템: 동시성 캐시 구현에 활용될 수 있다. 동작 원리 Concurrent Skip List는 여러 레벨의 연결 리스트로 구성되며, 각 레벨은 이전 레벨의 “빠른 경로"로 작용한다. 검색, 삽입, 삭제 작업은 상위 레벨에서 시작하여 하위 레벨로 이동하면서 수행된다. ...
Read-Copy-Update (RCU) List RCU List는 동시성을 지원하는 연결 리스트 구조로, 여러 스레드가 동시에 안전하게 접근하고 수정할 수 있도록 설계되었다. RCU List는 Read-Copy-Update 메커니즘을 사용하여 구현된 동시성 연결 리스트로 읽기 작업에 대해 락을 사용하지 않으면서도 동시에 업데이트를 수행할 수 있게 해준다. 특징 락 없는 읽기: 읽기 작업은 동기화 없이 수행된다. 동시성 지원: 여러 스레드가 동시에 리스트에 접근할 수 있다. 읽기 성능 최적화: 읽기 작업의 성능이 매우 뛰어나다. 공간-시간 트레이드오프: 더 많은 공간을 사용하여 빠른 연산을 가능하게 한다. 구현 방식 삽입: 새 노드를 생성하고 원자적으로 리스트에 연결한다. 삭제: 노드를 리스트에서 제거한 후, 일정 시간이 지난 뒤 메모리를 해제한다. 읽기: 동기화 없이 리스트를 순회한다. 장점 높은 읽기 성능: 읽기 작업이 매우 빠르다. 확장성: 다중 코어 시스템에서 좋은 성능을 보인다. 데드락 방지: 읽기 작업에서 락을 사용하지 않아 데드락 위험이 줄어든다. 응용 운영체제 커널 데이터베이스 시스템 네트워크 스택 고성능 멀티스레드 애플리케이션 동작 원리 읽기 작업: 동기화 없이 리스트를 순회한다. 쓰기 작업: 새로운 버전의 데이터를 생성하고, 원자적으로 포인터를 업데이트한다. 삭제: 노드를 리스트에서 제거한 후, 모든 읽기 작업이 완료될 때까지 기다렸다가 메모리를 해제한다. 구성 요소 노드: 데이터와 다음 노드를 가리키는 포인터를 포함한다. 헤드 포인터: 리스트의 첫 번째 노드를 가리킨다. 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; } // 실패하면 다시 시도 } } } 참고 및 출처
Lock-free Queue Lock-free Queue는 락(lock)을 사용하지 않고 동시성을 제공하는 FIFO(First-In-First-Out) 자료구조이다. 이 자료구조는 여러 생산자(producer)와 소비자(consumer)가 동시에 큐에 접근할 수 있으며, 시스템 전체의 진행을 보장한다. 특징 동시성 지원: 여러 스레드가 동시에 큐에 접근하고 수정할 수 있다. 락 사용 없음: 전통적인 동기화 기법인 락을 사용하지 않는다. 진행 보장: 시스템 전체의 진행을 보장하며, 개별 스레드의 기아 현상이 발생할 수 있다. 원자적 연산 사용: Compare-And-Swap(CAS)과 같은 원자적 연산을 사용한다. 구현 방식 Lock-free Queue는 주로 다음과 같은 방식으로 구현된다: ...