[C] Lock-free Stack

Lock-free Stack은 동기화 객체 없이 동시성을 보장하는 스택 자료구조를 말한다.
주로 Compare-And-Swap( CAS ) 같은 원자적 연산을 활용하여 구현된다.

 

📌 핵심 개념

Lock-free의 정의: 적어도 하나의 스레드가 유한한 시간 내에 진행을 보장받는 알고리즘이다.

하나의 스레드가 무한히 지연되더라도 다른 스레드들은 계속 작업을 수행할 수 있다.

 

📌 구현 원리

Lock-free Stack은 단방향 연결 리스트로 구현되고, head 포인터에 대한 원자적 업데이트를 통해 동작한다.

Push 연산

1. 새 노드를 생성하고 데이터를 저장
2. 새 노드의 next를 현재 head로 설정
3. CAS를 사용하여 head를 새 노드로 원자적으로 업데이트
4. CAS가 실패하면 다른 스레드가 head를 변경한 것이므로 재시도

Pop 연산

1. 현재 head 읽기
2. head가 null이면 스택이 비어있음
3. head->next를 새로운 head로 설정하려고 CAS 시도
4. CAS가 성공하면 이전 head 노드의 데이터 반환
5. 실패하면 재시도