[ComputerScience] 교착 상태

교착 상태

교착 상태(Deadlock)는 멀티스레드 또는 멀티프로세스 환경에서 둘 이상의 실행 단위가 서로가 가진 자원을 기다리면서 영원히 진행되지 못하는 상태를 의미합니다.
즉, 프로세스들이 서로가 가진 자원을 점유한 채로 대기만 하게 되어 더 이상 실행이 불가능한 상황입니다.

발생 조건

교착 상태의 발생 조건은 다음과 같습니다.

1. 상호 배제(Mutual Exclusion)
   • 교착 상태가 발생하는 근본적인 원인은 한 번에 하나의 프로세스만 해당 자원을 이용 가능하기 때문입니다.
   • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상호 배제의 상황에서 교착 상태가 발생합니다.
2. 점유와 대기(Hold and Wait)
   • 한 프로세스가 어떤 자원을 할당받은 상태(점유)에서 다른 자원을 할당받기를 기다리는 상태입니다.
3. 비선점(No Preemption)
   • 해당 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 자원을 이용할 수 있는 상태입니다.
   • 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우 교착 상태가 발생합니다.
4. 원형 대기(Circular Wait)
   • 프로세스와 프로세스가 요청한 자원이 원의 형태를 이루는 상태입니다.
   • 각각의 프로세스가 서로 점유한 자원을 할당받기 위해 원의 형태로 대기할 경우 교착 상태가 발생합니다.

해당 조건 중 하나의 조건이라도 충족하지 않을 경우 교착 상태는 발생하지 않습니다.

예방 및 해결 방법

교착 상태를 해결하기 위한 방법은 다음과 같습니다.

• 예방(Prevention): 교착 상태 발생 조건 중 하나 이상을 원천적으로 깨뜨린다.
  • 상호 배제 제거: 자원을 여러 프로세스가 동시에 사용할 수 있도록 설계
  • 점유와 대기 제거: 자원을 요청할 때 모든 자원을 한꺼번에 요청하도록 설계
  • 비선점 제거: 특정 자원을 선점 가능하게 설계
  • 순환 대기 제거: 자원에 우선순위를 매겨 정해진 순서로만 요청하도록 설계
• 회피(Avoidance): 교착 상태가 발생하지 않도록 안전 상태(Safe State)를 유지한다.
  • 은행원 알고리즘(Banker’s Algorithm)을 참고할 수 있습니다.
• 탐지 및 회복(Detection & Recovery): 교착 상태 발생을 허용한 뒤, 주기적으로 탐지하여 해결한다.
  • 교착 상태 탐지 알고리즘을 사용합니다.
  • 교착 상태에 빠진 프로세스를 종료하거나 자원을 회수하는 사후 조치입니다.

예시

두 스레드가 각각 뮤텍스 A와 B를 잡은 상태를 예시로 들어보겠습니다.

스레드 1은 A를 잡고 B를 기다립니다.
스레드 2는 B를 잡고 A를 기다립니다.

이 경우 두 스레드는 서로가 가진 자원을 기다리면서 교착 상태에 빠지게 됩니다.