[운영체제] 교착 상태(deadlock)

교착 상태는 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리면서 무한 대기하며 중단된 상태를 말한다.

예를 들어, 프로세스 A가 프로세스 B가 점유한 자원 R1을 요청할 때 프로세스 B도 프로세스 A가 점유한 자원 R2를 요청하는 상태이다. 

프로세스 A가 자원 R1을 요청하면 프로세스 A는 프로세스 B가 자원 R1을 반납할 때까지 대기 상태에 들어간다. 그리고 프로세스 B가 자원R2를 요청하면 프로세스 A가 자원 R2를 반납할 때까지 대기 상태에 들어간다. 이와 같이 서로에 의해 대기 상태에 들어가 무한 대기하는 데드락이 발생하는 것이다. 

교착 상태의 원인

• 상호 배제 : 한 프로세스가 자원을 독점하고 있으며 다른 프로세스들은 접근이 불가능하다. 
• 점유 대기 : 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하는 상태이다.
• 비선점 : 다른 프로세스의 자원을 강제적으로 가져올 수 없다.
• 환형 대기 : 프로세스 A는 프로세스 B가 점유한 자원을 요청하고, 프로세스 B는 프로세스 A가 점유한 자원을 요청하는 등 서로가 서로의 자원을 요구하는 상황이다. 

위 네 가지 조건이 모두 만족되는 경우 교착상태가 발생할 가능성이 있다.

 

교착 상태의 해결 방법

• 예방 기법
  • 교착 상태의 원인이 되는 4가지 중 하나를 부정하는 방식으로 교착상태를 예방한다.
  • 상호 배제 부정 : 여러 개의 프로세스가 동시에 공유 자원을 사용할 수 있다.
  • 점유 대기 부정 : 프로세스가 실행되기 전에 필요한 모든 자원을 할당해서 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원 요청을 받도록 한다.
  • 비선점 부정 : 모든 자원에 대한 선점을 허용한다.
  • 순환 대기 부정 : 자원을 선형으로 분류해서 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유번호보다 앞이나 뒤 중 한쪽 방향으로만 자원을 요구하도록 한다.
  • 하지만, 이러한 예방 기법은 시스템의 자원 처리량이나 자원 사용의 효율성을 떨어트리는 경향이 있다.
• 회피 기법
  • 교착 상태 가능성이 없는 경우에만 자원이 할당되며, 프로세스당 요청할 자원들의 최대치를 통해 자원 할당 가능 여부를 판단하는 '은행원 알고리즘'을 사용한다.
  • 은행원 알고리즘 : 총 자원의 양과 현재 할당된 자원의 양을 기준으로 교착 상태가 발생하지 않고 모든 프로세스가 완료될 수 있는 안정 상태와 교착 상태가 발생할 가능성이 있는 불안정 상태로 나누고, 안정 상태로 가도록 자원을 할당하는 알고리즘이다.
• 탐지 기법
  • 시스템에 교착 상태가 발생했는지 찾는다. 은행원 알고리즘처럼 자원의 할당 상태를 보고 파악하거나, 자원 할당 그래프 등을 이용해서 교착 상태가 발생했는지 파악다.
• 회복 기법
  • 탐지 기법을 이용해서 데드락을 발견했으면 데드락으로부터 벗어나는 방법을 찾는다.
  • 교착 상태에 빠진 프로세스를 모두 중단시킴
    • 연산중이던 프로세스들이 모두 중단되기 때문에 중간 결과가 모두 폐기되는 부작용이 있다.
  • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시킴
    • 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있다.

 

교착 상태는 매우 드물게 일어나기 때문에 이를 처리하는 비용이 더 커서 교착 상태가 발생하면 사용자가 작업을 종료한다. 

현대 운영체제에서는 이 방법을 채택했다. 예를 들어, 프로세스를 실행시키다 '응답 없음'이라고 뜰 때가 있는데, 교착 상태가 발생할 경우 이와 같은 상황이 발생하기도 한다.