Wait-Free 프로그래밍 연구 노트

1. 진행 보장(Progress Guarantee) 4단계

Blocking (Mutex)

한 스레드가 락을 잡고 컨텍스트 스위치되면 → 나머지 전부 블로킹. 최악의 경우 전체 시스템이 멈춤.

Obstruction-Free

다른 스레드가 모두 멈추면 → 나는 진행 가능. 실전에서는 거의 쓰이지 않음.

Lock-Free

전체 시스템에서 최소 1개 스레드는 항상 진행. 단, 특정 스레드가 CAS 경합에서 계속 지면 그 스레드는 무한정 밀릴 수 있음 (starvation). A가 컨텍스트 스위치되어도 B, C는 멈추지 않고 자기 CAS를 진행. 문제는 A가 깨어나서 CAS할 때마다 다른 스레드한테 밀리면 A만 계속 굶는 것. 현실에선 드물지만 보장이 없음.

Wait-Free

모든 스레드가 유한 스텝(O(N)) 내에 반드시 완료. 어떤 스레드도 굶지 않음. 가장 강한 진행 보장.

2. Lock-Free의 한계

CAS 루프 기반 Lock-Free Push 예시:

while (true) {
    auto oldTop = _top;
    node->next = oldTop;
    if (CAS(&_top, oldTop, node))  // 성공하면 탈출
        break;
    // 실패하면 재시도 — 운 나쁘면 계속 실패 가능
}

스레드 A가 CAS를 시도할 때마다 스레드 B, C가 먼저 성공하면, A는 이론적으로 무한 재시도할 수 있다. 실시간 보장이 필요한 시스템에서는 문제.

3. Wait-Free의 핵심 메커니즘: Helping

아이디어

Lock-Free는 CAS 한 번에 바로 시도하지만, Wait-Free는 "나 이거 할 거야"를 먼저 공유 배열(announce)에 게시하는 방식.

[Lock-Free Push]
1. 노드 준비
2. CAS로 연결 시도
3. 실패하면 재시도 (무한 반복 가능)

[Wait-Free Push]
1. 노드 준비
2. 공유 배열(announce)에 "나 이 노드 넣을 거야" 게시
3. CAS로 연결 시도
4. 실패해도 괜찮음 — 다른 스레드가 내 게시물을 보고 대신 넣어줌