모범답안 — 라이브락, 기아(starvation), 우선순위 역전, 공정성

난이도: 중

핵심 답변

라이브락 vs 데드락: 데드락은 스레드들이 멈춘 채로 서로를 기다린다(CPU 안 씀). 라이브락은 스레드들이 계속 실행·상태 변경(서로 양보/재시도) 하지만 전체적으로 진전이 없다(CPU는 바쁘게 도는데 일이 안 끝남). "복도에서 서로 비키려다 같은 방향으로만 움직여 계속 막히는" 상황.
기아: 특정 스레드가 필요한 자원/CPU를 계속 다른 스레드에 빼앗겨 영원히(또는 매우 오래) 진행하지 못하는 상태. 비공정(unfair) 락, 우선순위 기반 스케줄링(낮은 우선순위가 굶음), 끝없이 도착하는 reader 때문에 writer가 굶는 RW락 등에서 발생. 공정성↔처리량: 공정성을 위해 도착 순서(FIFO)를 강제하면 캐시가 핫한 스레드에 락을 바로 못 줘 처리량이 떨어진다. 비공정 락은 방금 푼 스레드가 즉시 재획득(barging)해 빠르지만 일부가 굶을 수 있다.
우선순위 역전: 높은 우선순위 스레드 H가, 낮은 우선순위 L이 쥔 락을 기다리는데, 중간 우선순위 M이 L을 선점해 L이 진행을 못 하면 H가 M보다 늦게 끝나는 역전이 생긴다. 해결: 우선순위 상속(priority inheritance) — L이 H가 기다리는 락을 쥔 동안 일시적으로 H의 우선순위를 물려받아 빨리 끝내고 락을 놓게 한다. (priority ceiling도 대안.)

깊이 있는 설명 (메커니즘, 왜)

시나리오는 라이브락이다

데드락이 아니다 — 데드락이면 두 스레드가 B를 기다리며 블로킹되어 CPU를 안 쓴다. 여기서는 둘 다 A를 잡고, B 실패를 감지하고, A를 놓고, 즉시 다시 A를 잡는다. 상태는 계속 변하지만(락을 잡았다 놨다) 둘이 완벽히 동기화된 스텝으로 동작해 매번 똑같이 충돌한다. CPU 100%인데 아무도 끝내지 못하는 것 → 전형적 라이브락.

왜 진전이 없나

문제는 재시도가 즉각적이고 결정적이라는 점이다. 두 스레드가 같은 속도로 "잡고-실패-놓고-재시도"를 반복하면 위상이 영원히 맞아 떨어진다. 진전을 보장하려면 이 대칭을 깨야 한다.

최소 수정: 백오프 + 지터(jitter)

재시도 전에 무작위 시간만큼 쉬어 두 스레드의 위상을 어긋나게 한다.

var rng = new Random();
while (true) {
    lockA.Enter();
    if (lockB.TryEnter()) {
        // 작업
        lockB.Exit(); lockA.Exit();
        return;
    }
    lockA.Exit();
    Thread.SpinWait(rng.Next(1, 1 << backoff)); // 지수 백오프 + 랜덤
    if (backoff < cap) backoff++;
}

랜덤 지터로 한 스레드가 먼저 A·B를 모두 잡고 끝낼 틈이 생긴다. 이게 이더넷 CSMA/CD, CAS 재시도 루프에서 쓰는 지수 백오프(exponential backoff) 와 같은 원리다.

더 근본적인 수정: 락 순서 강제

사실 try-lock 백오프보다 전역 락 순서(항상 A→B 순으로 잡기) 가 더 깔끔하다(문제 2의 해법). 순서를 강제하면 순환 대기가 없어 try-lock/재시도 자체가 필요 없고 라이브락도 안 생긴다. try-lock 백오프는 순서를 강제할 수 없는 동적 상황의 대안이다.

기아와 공정성

백오프로 라이브락을 풀어도, 운 나쁜 스레드가 매번 양보만 해 계속 굶을 수 있다(특히 처리량 우선 비공정 락에서). 공정성 확보:

FIFO/티켓 락: 도착 순서대로 락을 부여(ticket lock, lock(fair: true)/ReentrantLock(true)). 굶주림은 없지만 처리량은 다소 손해.
백오프 상한 + 한도 보장: 일정 횟수 실패하면 백오프를 멈추고 우선권을 주거나, 양보 횟수에 상한(bounded waiting)을 둔다.
RW락의 writer 기아: reader가 끝없이 오면 writer가 굶으니, writer 대기 중이면 새 reader를 막는 writer-우선/공정 RW락을 쓴다. 이론적으로 좋은 임계구역 해법은 bounded waiting(유한 대기)을 보장해 기아를 막는다.

우선순위 역전과 상속

H(높음)가 L(낮음)이 쥔 락을 대기 → M(중간)이 L을 선점 → L이 못 끝내 락을 못 놓음 → H가 M보다 늦어짐. 우선순위 상속: L이 락을 쥔 동안 대기 중인 H의 우선순위를 임시로 받아 M에게 선점당하지 않고 빨리 락을 놓게 한다. 1997년 화성 Pathfinder가 우선순위 역전으로 시스템 리셋을 반복했는데, VxWorks의 우선순위 상속 옵션을 원격으로 켜서 고친 유명한 사례다.

응용/실무 연결 (게임서버에서)

CAS 재시도 백오프: lock-free 자료구조의 CAS 루프가 고경합에서 라이브락 비슷하게 재시도만 폭주할 수 있다. 지수 백오프/pause 명령으로 완화.
공정성이 필요한 곳 선택: 매칭 큐, 작업 큐는 도착 순서 보장(FIFO)이 사용자 경험상 중요해 공정 큐를 쓴다. 반면 순수 성능 핫스팟의 짧은 락은 비공정(빠른 barging)이 유리.
우선순위 역전 회피: 게임서버는 보통 모든 워커를 같은 우선순위로 두고 우선순위 기반 락 경쟁을 피한다. 실시간 오디오/물리 같은 고우선 스레드가 일반 워커와 락을 공유하면 우선순위 상속 가능한 OS 뮤텍스를 쓰거나, 아예 락을 공유하지 않는 설계(잡큐 분리)로 회피.

흔한 오답·함정

"라이브락은 데드락의 일종" → 다르다. 데드락은 블로킹·정지, 라이브락은 바쁘게 돌지만 무진전. CPU 사용률로 구분된다.
"try-lock으로 바꾸면 데드락이 해결된다" → 데드락은 피하지만 라이브락을 새로 만들 수 있다. 백오프/지터가 짝이다.
"공정한 락이 항상 좋다" → FIFO 강제는 캐시 지역성·처리량을 희생한다. 굶주림이 실제 문제일 때만 공정성을 택한다.
"우선순위를 잘 주면 역전이 없다" → 오히려 우선순위가 있어야 역전이 생긴다. 상속/실링 메커니즘이 필요.
"백오프는 고정 시간이면 된다" → 고정 시간은 위상이 다시 맞아 라이브락 재발. 랜덤 지터 + 지수 증가가 핵심.

꼬리질문 대비

Q: progress 보장 강도(blocking / obstruction-free / lock-free / wait-free)를 라이브락 관점에서 정리하면? A: lock-free는 시스템 전체로는 항상 누군가 진전(개별 스레드는 굶을 수 있음 → 기아 가능, 라이브락 아님). wait-free는 모든 스레드가 유한 단계에 끝남(기아·라이브락 모두 없음, 가장 강함). obstruction-free는 혼자 실행되면 끝나지만 경합 시 서로 방해해 라이브락 가능.
Q: 비공정 락이 처리량에서 유리한 구체적 이유는? A: 락을 막 푼 스레드는 그 자료의 캐시가 핫하고 이미 실행 중이라, 바로 재획득(barging)하면 컨텍스트 스위칭 없이 진행한다. FIFO로 다음 대기자에게 넘기면 그 스레드를 깨우는 스위칭 + 콜드 캐시 비용이 든다. 그래서 짧은 핫 락은 비공정이 빠르다.
Q: 우선순위 상속 외에 우선순위 역전 대책은? A: priority ceiling protocol(락마다 최고 우선순위 천장을 정해 락을 쥐면 그 천장으로 올림), 우선순위가 다른 스레드 간 락 공유 자체를 없애기(메시지 패싱/잡큐 분리), 또는 우선순위를 안 쓰는 균일 스케줄링.

7. 라이브락, 기아(starvation), 우선순위 역전, 공정성