[CS 스터디] 교착상태

1. 교착상태(Deadlock)의 본질

• 개념: 2개 이상의 프로세스(또는 스레드)가 각자 자원을 쥔 상태로
  상대방의 자원을 무한정 기다리며 시스템이 완전히 정지하는 현상이다.

• 기아 현상(Starvation)과의 차이점: 기아 현상은 우선순위가 밀려
  자원 할당이 '지연' 되는 것이라면 교착상태는 관련된 모든 프로세스의 작업이
  '정지'하는 보다 근본적이고 심각한 문제이다.

• 발생 환경: 운영체제 자원뿐만 아니라 데이터베이스 시스템,
  Java의 잠금 즉 락을 사용하는 멀티스레드 환경 등 동시성 제어가
  필요한 모든 곳에서 발생할 수 있다.

2. 교착상태 발생의 4가지 절대 조건

1. 상호 배제: 하나의 자원은 한 번에 하나의 프로세스만 사용할 수 있어야 한다.

2. 비선점: 다른 프로세스가 이미 점유한 자원을 강제로 뺏어올 수 없다.

3. 점유와 대기: 자신이 이미 최소 하나의 자원을 쥐고 있으면서, 다른 자원이 나기를 기다려야 한다.

4. 순환 대기: 자원을 기다리는 형태가 꼬리에 꼬리를 무는 원형(Cycle) 구조를 이루어야 한다.

3. 교착상태 해결 전략 4가지 (왜 완벽한 해결은 어려운가?)

예방

• 원리: 교착상태의 4가지 필요조건 중 하나를 원천적으로 차단한다.

• 왜 사용하기 어려운가?: 시스템 효율과 유연성을 극도로 떨어뜨린다.

  • 상호 배제 파괴: 물리적으로 불가능한 자원(프린터 등)이 존재.

  • 비선점 파괴: 강제 회수 시 작업 롤백 및 기아 현상 발생.

  • 점유와 대기 파괴: 'All or Nothing' 방식. 한꺼번에
    모든 자원을 할당받지 못하면 실행 불가 (극심한 자원 낭비).

  • 순환 대기 파괴: 자원에 번호를 매겨 한 방향으로만 요청 강제 (작업 유연성 저하).

회피

• 원리: 자원 할당 시 교착상태 가능성을 미리 계산하여
  작업을 끝낼 수 있는 '안정 상태(Safe State)'가 보장될 때만 자원을 내어준다.

• 은행원 알고리즘 (Banker's Algorithm): 은행이 대출 상환 능력을 보고 돈을 빌려주듯
  가용 자원으로 프로세스의 남은 요구량을 채워줄 수 있을 때만 할당한다.

• 왜 한계가 있는가?: 프로세스가 앞으로 사용할 '최대 자원 수'를 미리 운영체제에
  신고해야 하는데 현실적으로 예측이 어렵다.
  또한 최악의 상황을 가정하므로 보수적인 자원 할당으로 낭비가 발생한다.

검출 및 무시

• 원리: 일단 시스템을 자유롭게 돌리고, 교착상태가 발생했는지 사후에 모니터링합니다.

• 가벼운 검출 (타임아웃): 일정 시간 응답이 없으면
  멈춘 것으로 간주하고 프로세스를 닫는다. (윈도우의 '응답 없음' 창)
  단, 진짜 교착상태가 아닌 일시적 지연 프로세스도 억울하게 종료될 수 있다.

• 무거운 검출 (자원할당 그래프): 자원과 프로세스의 방향 그래프를 그려
  순환 구조(Cycle)를 직접 찾는다.
  정확하지만 매번 검사하면 오버헤드가 매우 크다.

회복

• 원리: 교착상태가 검출되면 얽힌 프로세스를 강제 종료하여 자원을 회수한다.

• 방법: 교착상태 프로세스 전체를 한 번에 날리거나
  우선순위/작업시간/자원사용량 등을 기준으로 하나씩 종료하며 해결되는지 관찰한다.

4. 백엔드 관점: 강제 종료 시 데이터는 어떻게 되는가? (트랜잭션 복구)

• 문제점: 교착상태로 프로세스가 강제 종료되면
  실행 중이던 데이터(예: 송금 중인 계좌)의 일관성이 깨질 수 있다.

• 해결책 (체크포인트와 롤백): 데이터베이스 등에서는 잠금(Lock) 요청 시 현재 상태를
  스냅샷으로 찍어두는 '체크포인트(Checkpoint)'를 생성한다.
  교착상태로 중단 시 이 스냅샷을 이용해 문제 발생 이전의
  안전한 상태로 되돌리는 롤백을 수행하여 데이터 원자성을 보장한다.

멀티 인스턴스 환경에서는 자원할당 그래프의 순환 구조(Cycle) 발견만으로는
교착상태를 100% 확신할 수 없다.
시스템 내 여유 자원 현황에 따라 순환 구조가 풀릴 가능성도 존재한다.

[궁금증] 회피 전략: 프로세스의 '최대 자원 수'는 왜 현실적으로 예측하기 어려운가?

자료에는 프로세스가 앞으로 사용할 최대 자원 수를 미리 운영체제에 신고해야 하지만 현실적으로 예측이 어렵고 보수적인 자원 할당으로 낭비가 발생한다고 명시되어 있다.
"개발자가 프로그램을 직접 짰는데, 왜 자기가 만든 프로그램이
자원을 얼마나 쓸지 모른다는 거지?"라는 궁금증이 생길 수 있다.

프로그램의 실행 흐름은 정적이지 않고 동적이다.

왜 예측이 어려운가?: 코드 내부의 조건문(if-else), 반복문의 횟수,
그리고 사용자 입력 데이터의 크기나 실시간 네트워크 상태 등에 따라
메모리나 스레드 같은 자원 요구량이 실행 도중에 계속 변한다.

결과: 실행 전에 '정확한 최대치'를 확정하는 것은 불가능하다.
시스템 셧다운을 막기 위해 무조건 발생 가능한 최악의 상황(가장 큰 최대치)을
가정해 신고한다면, 은행(운영체제)은 그만큼의 자원을 대출해주기 위해
항상 금고에 묵혀두어야 하므로 막대한 자원 낭비로 이어진다.