144. 교착상태

교착상태의 개요

• 교착상태(Dead Lock)는 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미한다.
• 아래 그림과 같이 자동차(프로세스)들이 현재 위치한 길(자원)을 점유함과 동시에 다른 차가 사용하는 길을 사용하려고 대기하고 있지만 다른 길을 사용할 수 없으며 현재 길에서도 벗어나지 못하는 상태이다.

교착상태 발생의 필요 충분 조건

• 교착상태가 발생하기 위해서는 다음의 네 가지 조건이 충족되어야 하는데, 이 네 가지 조건 중 하나라도 충족되지 않으면 교착상태가 발생하지 않는다.
• 상호 배제(Mutual Exclusion)
  • 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
• 점유와 대기(Hold and Wait)
  • 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
• 비선점(Non-preemption)
  • 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
• 환형 대기(Circular Wait)
  • 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 지원을 요구해야 한다.

교착상태의 해결 방법

• 예방 기법(Prevention)
  • 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로, 교착상태 발생의 네 가지 조건 중에서 어느 하나를 제거(부정)함으로써 수행된다.
  • 자원의 낭비가 가장 심한 기법이다.
• 회피 기법(Avoidance)
  • 교착상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 피해나가는 방법으로, 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.
  • 은행원 알고리즘(Banker's Algorithm): E. J. Dijkstra가 제안한 것으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법
• 발견 기법(Detection)
  • 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미한다.
  • 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다.
• 회복 기법(Recovery)
  • 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점 하여 프로세스나 자원을 회복하는 것을 의미한다.