[OS] 데드락 (Deadlock)

데드락 (Deadlock)

• 여러 개의 프로세스나 스레드가 서로 자원을 점유하고 있어, 다음 단계를 진행하지 못하고 무한정 대기 상태에 빠지는 상황
• 즉, 각 프로세스나 스레드가 다른 프로세스나 스레드가 점유한 자원을 요청하면서 서로 자원을 점유한 상태에서 다음 단계로 진행하지 못하게 되는 것

 

데드락 조건

아래 4가지 조건이 모두 성립해야 데드락이 발생한다. 즉, 하나라도 성립하지 않으면 데드락 문제를 해결할 수 있다.

1. 상호배제 (Mutual exclusion) : 자원은 한 번에 하나의 프로세스나 스레드에 의해서만 사용될 수 있다.
2. 점유 대기(Hold and wait) : 최소한 하나의 자원을 점유한 상태에서 다른 자원을 요청하고 대기하는 프로세스나 스레드가 존재 한다.
3. 비선점(No preemption) : 다른 프로세스나 스레드가 사용 중인 자원을 강제로 선점할 수 없다.
4. 순환 대기(Circular wait) : 각 프로세스나 스레드는 다음 프로세스나 스레드가 점유한 자원을 요청하고 대기하는 사이클이 형성된다.

 

데드락에 의해 발생하는 문제

• 시스템 성능 저하
• 자원 낭비

 

데드락 해결 방법

(1) 교착 상태 회피(Avoidance)

데드락이 발생하지 않도록 사전에 예방하는 방법

1. 상호배제(Mutual Exclusion) 방지 : 두 개 이상의 프로세스나 스레드가 동시에 점유하지 못하도록 자원의 공유나 동시 접근을 제한한다.
2. 점유 대기(Hold and Wait) 방지 : 프로세스가 자원을 요청할 때, 이미 점유하고 있는 자원을 반납하고 요청한 자원만을 할당받도록 한다.
3. 비선점(No Preemption) 방지 : 프로세스나 스레드가 자원을 점유하고 있는 상태에서, 다른 프로세스나 스레드가 해당 자원을 강제로 뺏을 수 없도록 한다.
4. 순환 대기(Circular Wait) 방지 : 자원을 순환적으로 요청하는 프로세스나 스레드를 막는다.
5. 은행원 알고리즘(Banker's Algorithm)
   • 자원 요청 시 프로세스의 안전 상태(Safe State)를 확인하여 요청이 수락될 경우에만 자원을 할당하는 방식
   • 안전 상태에 도달하지 못하는 요청은 데드락을 발생시킬 수 있으므로, 안전 상태에 도달할 수 있는지 사전에 확인한다.

 

(2) 교착 상태 탐지(Detection)

교착상태를 감지하여, 어떤 프로세스나 스레드가 자원을 점유하고 있는지 파악하는 방법

1. 자원 할당 그래프 알고리즘
   • 자원 할당 그래프를 생성하고, 그래프에서 사이클이 형성되어 교착 상태를 표현하는지 여부를 탐지한다.

 

(3) 교착 상태 회복(Recovery)

이미 발생한 데드락 상태를 해결하는 과정

1. 자원 할당 해제(Resource Allocation Release) : 교착상태가 발생한 프로세스나 스레드가 점유한 자원을 강제로 해제한다.
2. 프로세스나 스레드 중단(Process Termination) : 교착상태가 발생한 프로세스나 스레드를 강제로 중단시킨다.

 

데드락(Deadlock) vs 기아상태 (Starvation)

1. 발생 원인

• 데드락 : 데드락은 한정된 자원을 서로 점유하고 있어 다른 프로세스가 자원을 기다리며, 상호간에 원형으로 대기하는 상태
• 기아상태 : 기아상태는 프로세스가 자원을 계속해서 얻지 못하고 꾸준히 우선순위가 낮아져 자원 할당을 받지 못하는 상태
  
  

2. 주요 특징

• 데드락 : 모든 프로세스가 대기 상태에 머무르며, 아무런 작업을 수행하지 않는다.
• 기아상태 : 다른 프로세스들이 자원을 얻으면서 진행하지만, 특정 프로세스는 계속해서 자원을 얻지 못하고 기다리는 상태이다.

 

기아상태 해결 방법

• 우선순위 변경
  • 프로세스 우선순위를 수시로 변경해서, 높은 우선순위를 가질 기회를 공평하게 준다.
  • 오래 기다린 프로세스의 우선순위를 높여준다.
  • 우선순위가 아닌, 요청 순서대로 처리하는 FIFO 기반 큐를 사용한다.

 

•