본문 바로가기

Programming/Operating System

운영체제 · 교착상태 (데드락)

교착상태 (Deadlock)


운영체제(또는 소프트웨어)에서 자원을 사용할 때, 두 개 이상의 작업이 순차적으로 상대방의 작업이 끝나기를 기다리면서, 아무것도 진행되지 않는 상태를 말한다.


[그림 1] 교통을 통해 표현한 교착상태




교착상태 발생 조건


✓ 교착상태는 다음 네 가지 조건이 모두 성립될 때 발생한다.

  • 상호 배제 (Mutual exclusion) : 한 번에 하나의 프로세스만 공유 자원을 사용할 수 있다.
  • 점유 대기 (Hold and wait) : 각 프로세스가 하나의 자원을 점유하고 있으면서, 다른 프로세스가 사용하고 있는 자원을 추가로 점유하기 위해 대기한다.
  • 비선점 (No preemption) : 각 프로세스는 다른 프로세스가 사용하고 있는 자원을 강제로 빼앗을 수 없다.
  • 순환 대기 (Circular wait) : 각 프로세스는 순환적으로(원형 형태) 다음 프로세스가 요구하는 자원을 가지고 있다.






교착상태 해결 방법


예방 기법 (Deadlock Prevention)

  • 교착상태가 발생되지 않도록 사전에 예방하는 방법이다.
  • 교착상태 발생 조건 네 가지 중 적어도 하나가 성립하지 않게 만드는 방법이다.
  • 순환 대기를 막는 방법이 네 가지 중 가장 효율적이다. 자원에 순서를 부여하고, 각 프로세스가 오름차순으로 자원을 요청하도록 구현한다.
  • 예방 기법은 일반적으로 자원 사용 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.


회피 기법 (Deadlock Avoidance)

  • 교착상태가 발생하는 조건인지 확인하면서 적절히 회피하는 방법이다.
  • Circular wait가 발생하지 않도록 자원 할당 상태를 검사하면서, 시스템이 안전 상태(Safe state)인지 확인한다.
  1. 자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm) : 자원 할당에 대한 그래프를 구성한 후, 그래프에 사이클이 없을 때에만 자원을 할당한다.
  2. 은행원 알고리즘 (Banker's Algorithm) : 자원 할당 그래프 알고리즘은 프로세스가 하나의 자원만 사용하는 시스템에서 사용된다. 이에 반해 은행원 알고리즘은 프로세스가 자원을 여러 개 사용하는 경우에도 사용할 수 있는 알고리즘이다.


탐지와 회복 기법 (Deadlock Detection & Recovery)

  • 시스템에 교착 상태가 발생했는지 확인하기 위해 시스템의 상태를 검사한다.
  • 탐지 후, 교착 상태를 일으킨 프로세스를 종료하거나, 교착상태의 프로세스에 할당된 자원을 선점하여 교착상태를 제거한다.


무시 기법 (Deadlock Ignorance)

  • 교착상태 자체를 무시하고, 특별한 조치를 취하지 않는다. 교착상태의 발생 확률이 낮은 상황에서 효율적이다.
  • 만약 교착상태가 발생한다면, 프로세스를 종료하거나 자원을 선점하여 회복한다.
  • UNIX, Windows 등 대부분의 운영체제가 이 방법을 사용한다.