[OS] 교착상태(DeadLock)란?

교착상태란?

다중프로그래밍을 지원하는 프로세스는 한정된 데이터를 읽고 쓰기 위해 경쟁하게 된다. 이 경쟁 과정에서 생길 수 있는 문제를 예방하기 위해 데이터는 프로세스가 점유 상태라면 다른 프로세스의 접근을 막는 방법을 주로 사용하게 되는데 그 결과 같은 두개의 데이터를 필요로 하는 두 프로세스가 각각 하나씩 점유하게 되면 무한정 대기상태에 빠지게 되는데 이러한 상태를 교착상태라 한다.

교착 상태가 생기기 위한 조건

교착상태는 아래의 네가지 조건을 충족해야 일어난다

• 상호배제(mutual exclusion)
• 한 리소스는 한번에 한 프로세스만이 사용 할 수 있음(화장실 키)
• 점유하며 대기(hold-and-height)
  프로세스는 최소한 하나의 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 대기하고 있어야 한다.
• 비선점(no-preemption)
  자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 프로세스에 의해 자발적으로만 방출될 수 있다.
• 순환대기(circular-wait)
  각 프로세스가 꼬리를 물며 자원을 점유하고 있어야 한다.

시스템에 교착 상태가 생기는 이유

프로세스가 자원을 사용하기 위해서는 다음과 같은 순서의 수행을 하게된다.

1. 요청
   프로세스가 자원에 점유를 요청. 만일 점유할 수 없는 상태라면 프로세스는 대기상태에 놓임.
2. 사용
   프로세스가 자원을 점유하고 있는 상태.
3. 방출
   프로세스가 자원 사용을 마치고 자원으로 점유 상태를 잃은 상태.

이러한 특징을 가지고 있는 프로세스로 인해 시스템의 메모리, CPU 등 에서 교착 상태가 생길 수 있다.

교착 상태를 극복하는 방법

1. 무시
   교착상태를 인지하였으나 이를 해결하지 않고 의도적으로 무시하는 방법. 교착상태를 해결하는 것이 무시하는 것 보다 큰 비용을 지불할 시에 주로 사용. 현대 시스템에서 가장 많이 사용되는 방법.(유닉스, 윈도우 등)
2. 예방
   필요조건 중 하나 이상을 거부함으로써 해결하는 방법. 교착 상태의 필요악을 잘 보여주는 부분. 예방 방법을 사용한다면 효율적인 동시성 프로그래밍을 설계하기가 힘듦.
3. 회피
   시스템을 안정 상태, 불안정 상태로 구분하고 불안정 상태이면 교착 상태를 발생시킬 가능성이 있다 판단하여 데이터에 접근을 막는 방법. 많은 데이터가 빠른 시간내에 이동해야하는 현대 시스템에서 사실상 적용하기 힘든 방법. 또한 요청이전에 시스템의 상태를 확인하는 알고리즘을 실행시켜야 하기에 오버헤드가 큼.
4. 회복
   교착상태가 일어날 수 있는 데이터를 탐지하는 알고리즘과 이를 복구하는 알고리즘을 사용하는 방법. 탐지의 기준은 기술자가 정할 수 있으음.(CPU 이용률, 시간 등) 또한 복구를 위한 알고리즘은 탐지 알고리즘으로 교착 상태를 발생 시킬 수 있는 프로세스를 찾아 복구가 될 때 까지 이를 삭제하는 방법, 프로세스 전체를 삭제하는 방법 등이 있음.