Lock-Free Queue

Lock-Free Queue

잠금(Lock) 없이 CAS(Compare-And-Swap) 같은 원자적 연산을 사용하여 동시성 안전을 보장하는 큐 자료구조로, 멀티스레드 환경에서 대기 없이 높은 처리량을 제공

목적: 고성능 동시성, 락 경합 제거, 대기 시간 감소, 데드락 방지

특징: CAS(Compare-And-Swap): 원자적 비교·교환 연산 기반, 락 없음, 논블로킹, ABA 문제: 값이 A→B→A로 변경 시 CAS가 변경을 감지 못하는 문제, 높은 처리량

구성요소: ① 연결 리스트 ② head·tail 포인터(원자적) ③ CAS 연산

동작

• •enqueue: ① 새 노드 생성 → ② tail.next를 CAS로 새 노드 연결 → ③ tail을 CAS로 갱신 → 실패 시 재시도
• •dequeue: ① head.next 확인 → ② head를 CAS로 다음 노드로 갱신 → 실패 시 재시도

ABA 문제: 포인터 A → B → A 변경 시 CAS가 성공 → 버전 카운터 또는 Hazard Pointer로 해결

메모리 회수: Epoch-Based Reclamation, Hazard Pointers, 가비지 컬렉션

시간 복잡도: enqueue·dequeue 평균 O(1), 경합 시 재시도

공간 복잡도: O(n)

장점: 높은 처리량, 락 경합 없음, 데드락 없음, 확장성, 낮은 대기

단점: 구현 복잡도, ABA 문제, 메모리 회수 어려움, CPU 캐시 경합

적용사례: 멀티스레드 큐, 생산자-소비자, 고성능 서버, 네트워크 스택, 메시지 큐

비교: Lock-Free(락없음/CAS/복잡) vs Mutex Queue(락/간단/경합)

연관: CAS, 원자적 연산, ABA 문제, Hazard Pointer, 동시성