교착 상태 (Deadlock)

대처 전략 네 가지

예방 전략을 조건별로 보면, 점유와 대기는 필요한 자원을 시작 시점에 한꺼번에 요청하게 해서 깨고, 비선점은 추가 자원을 얻지 못하면 쥔 자원을 모두 내려놓게 해서 깬다. 순환 대기는 모든 자원에 전역 순서 번호를 매기고 반드시 오름차순으로만 요청하게 해서 깨는데, 실무에서 락 순서 규칙(lock ordering)으로 가장 널리 쓰인다.

개발자가 교착 상태를 가장 자주 만나는 곳은 데이터베이스다. 두 트랜잭션이 서로 다른 순서로 같은 행들의 락을 잡으면 교착 상태가 되는데, MySQL의 InnoDB 같은 엔진은 대기 그래프를 검사해 이를 즉시 탐지하고 한쪽 트랜잭션을 강제 롤백시킨 뒤 오류를 돌려준다. 즉 탐지와 회복 전략을 실제로 구현한 사례이며, 응용 코드는 이 오류를 받으면 트랜잭션을 재시도하도록 작성해야 한다. 멀티스레드 응용에서는 모든 스레드가 멈췄을 때 스레드 덤프(thread dump)를 떠서 각 스레드가 쥔 락과 기다리는 락을 확인하면 순환 대기를 눈으로 찾을 수 있다. 락을 잡은 채 외부 호출을 하지 않기, 락 범위를 최소화하기, 일정 시간 안에 락을 얻지 못하면 포기하는 타임아웃(timeout)을 두기 같은 습관도 실전에서 유효한 예방책이다.

은행원 알고리즘의 핵심 아이디어

회피 전략의 대표인 은행원 알고리즘(Banker's Algorithm)은 자원 요청을 승인했다고 가정한 뒤, 남은 자원으로 모든 프로세스가 최대 요구량까지 채우고 종료할 수 있는 순서가 하나라도 존재하는지 검사한다. 그런 순서가 있으면 안전 상태(safe state)이므로 승인하고, 없으면 요청을 보류한다. 안전 상태에 머무는 한 교착 상태로 들어가지 않는다는 것이 핵심이지만, 프로세스별 최대 요구량을 사전에 알아야 한다는 전제가 범용 시스템에서는 비현실적이라 주로 이론적 기준으로 다뤄진다.

교착 상태와 구별할 개념

기아(starvation)는 자원이 계속 다른 프로세스에 돌아가서 특정 프로세스만 무한정 기다리는 상황으로, 시스템 전체는 진행되고 있다는 점에서 교착 상태와 다르다. 라이브락(livelock)은 프로세스들이 서로 양보를 반복하며 상태는 계속 바뀌지만 실제 진전이 없는 상황이다. 좁은 복도에서 두 사람이 같은 방향으로 계속 비켜서는 모습에 비유된다. 셋 다 진행 불가라는 결과는 비슷하지만 원인과 해법이 다르므로 구분해서 설명할 수 있어야 한다. 예를 들어 기아는 스케줄링이나 락 획득의 공정성(fairness)을 보장해 해결하고, 라이브락은 재시도 전에 무작위 지연(random backoff)을 넣어 양보가 계속 겹치지 않게 해서 해결한다.

면접에서 이렇게 물어본다

• 교착 상태의 네 가지 필요조건을 말하고 각각을 깨는 예방 방법을 하나씩 제시해 보라.
• 교착 상태와 기아, 라이브락의 차이를 예를 들어 설명해 보라.
• 멀티스레드 코드에서 락 두 개로 교착 상태가 나는 시나리오를 만들고 락 순서 규칙으로 고쳐 보라.
• 은행원 알고리즘에서 안전 상태란 무엇이며 왜 실무에 그대로 적용하기 어려운가.
• 대부분의 범용 운영체제가 교착 상태를 무시하는 전략을 택하는 이유는 무엇인가.