[OS] 데드락(Deadlock, 교착 상태)

1. 데드락

 

두 개 이상의 프로세스나 스레드가 서로 처리할 자원을 이용하지 못해서 다음 작업을 하지 못하는 상태를 나타내며, 상호 간의 작업이 끝나기만을 무한히 대기하는 상태를 일컫는다.

 

이러한 상태를 데드락(Deadlock)이라고 하며, 교착상태라고도 한다.

 

[ 출처 : https://www.geeksforgeeks.org/introduction-of-deadlock-in-operating-system/]

 

 

2. 데드락 발생 조건

 

• 상호 배제(Mutual exclusion) : 자원은 한 번에 한 개의 프로세스만 사용이 가능
• 점유 대기(Hold and wait) : 하나의 이상의 자원을 점유하며, 다른 프로세스에 할당된 자원을 점유하기 위해서는 대기하는 프로세스가 존재
• 비선점(No preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 탈취가 불가능(대기)
• 순환 대기(Circular wait) : 프로세스의 집합에서 각 프로세스가 요구할 자원은 다음 프로세스가 보유

 

 

3. 해결 방안

 

• 예방(Prevention) : 데드락 발생 조건 중 하나 이상을 제거하며 해결(자원의 낭비가 발생)
  • 상호 배제의 부정 : 다수의 프로세스가 공유되는 자원을 사용(현실적으로 불가능)
  • 점유 대기의 부정 : 프로세스 실행 전 가용될 모든 자원을 미리 할당
  • 비선점의 부정 : 자원의 점유 중인 프로세스가 다른 프로세스에 할당된 자원을 요구하면 해당 자원을 반납
  • 순환 대기의 부정 : 자원의 고유 번호를 할당하여 순서대로 자원을 할당

 

• 회피(Avoidance) : 데드락 발생 시 회피하는 방법으로 은행원 알고리즘/자원 할당 그래프 알고리즘 이용
  • 은행원 알고리즘(Banker's Algorithm) : 프로세스가 자원을 요구할 때, 자원을 할당한 이후의 상태를 미리 판단하여, 안정적이다 판단하면 자원을 할당하고, 문제가 발생한다고 판단이 되면 자원의 점유가 끝날 때까지 대기하는 알고리즘 
  • 자원 할당 그래프 알고리즘(Resouce Allocation Graph Algorithm) : 그래프에 요청 간선과 할당 간선을 두어, 사이클을 구축하고, 한 가지의 자원 유형의 두 가지 이상의 사례가 존재하면, 데드락이라 판단하고 그래프의 간선을 조정하는 알고리즘

 

• 탐지(Detection) 및 회복(Recovery) : 데드락을 허용하고 이를 탐지하며, 발생 시 회복 절차를 수행(성능에 영향)
  • 탐지 : 자원 요청 시 데드락 탐지 알고리즘을 통하여, 현재 시스템 자원의 데드락 여부를 탐지
  • 회복 : 데드락 탐지 시 프로세스 종료, 자원 할당의 해제 또는 자원의 선점을 통한 회복 절차 수행