카테고리 없음

[TIL] DeadLock

s00ng 2025. 3. 3. 08:10

Deadlock이란?

  • 둘 이상의 Thread가 각기 다른 Thread가 점유하고 있는 자원을 서로 기다릴 때, 무한 대기에 빠지는 상황을 말한다.
  • deadlock이 발생하는 조건은 상호배제(Mutual Exclusion), 점유대기(hold-and-wait), 비선점(no preemption), 순환대기 (circular wait)를 모두 만족했을 때 이다.
  • deadlock 문제를 해결하는 방법에는 무시, 예방, 회피, 탐지-회복 의 4가지 방법이 있다.

 

Deadlock 발생 조건

deadlock은 다음 4가지 조건이 동시에 성립할 때 발생할 수 있다.

 

1. 상호 배제

  • 동시에 하나의 Thread만 자원을 점유할 수 있는 상황이다.
    • 다른 Thread가 자원을 사용하려면 자원이 방출될 때까지 기다려야한다.

 

2. 점유 대기

  • Thread가 자원을 보유한 상태에서 다른 Thread가 보유한 자원을 추가로 기다리는 상태

 

3. 비선점

  • 다른 Thread가 사용중인 자원을 강제로 선점할 수 없는 상황
  • 자원을 점유하고 있는 Thread에 의해서만 자원이 방출됨

 

4. 순환 대기

  • 대기 중인 Thread들이 순환 상태로 자원을 대기하고 있는 형태

 

 

Deadlock 해결 방법

deadlock 문제를 해결하는 방법에는 무시, 예방, 회피, 탐지-회복 의 4가지 방법이 있다.

 

1. 무시

deadlock 발생 확률이 낮은 시스템에서 아무런 조치를 취하지 않고 무시하는 방법
  • 무시 기법은 시스템 성능 저하가 없다는 큰 장점  
  • 현대 시스템에서는 deadlock이 잘 발생하지 않고, 해결 비용이 크기 때문에 무시 기법이 자주 사용됨

 

2. 예방

교착 상태의 4가지 발생 조건중 하나가 성립하지 않도록 하는 방법
  • 순환 대기 조건이 성립하지 않도록 하는 것이 현실적
  • 자원 사용의 효율이 떨어지고 비용이 크다

 

3. 회피

thread가 앞으로 자원을 어떻게 요청할지에 대한 정보를 통해 순환 대기 상태가 되지 않도록 자원을 할당하는 방법
  • 자원 할당 그래프 알고리즘
  • 은행원 알고리즘

 

4. 탐지 - 회복

시스템 검사를 통해 deadlock 발생을 탐지하고, 이를 찾아서 회복하는 방법
  • 자원 사용의 효율성이 떨어지고 비용이 크다.

 

Deadlock 예방

  1. Mutual Exclusion 부정
    1. 리소스 공유를 가능하게 함
    2. Mutual Exclution을 보장해야하는 일부 case가 있기 때문에 현실적으로 불가능한 방법
  2. Hold And Wait 부정
    1. 실행에 필요한 리소스를 한 번에 획득한 뒤 시작
  3. No Preemption 부정
    1. 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 즉, 빼앗을 수 있도록 해야한다.
  4. Circular wait 부정
    1. 모든 리소스에 순서 체계를 부여하여 오름차순으로 리소스 요청
    2. 4개의 리소스에 대해 1, 2, 3, 4번 리소스를 순차적으로만 요청할수 있는

 

Deadlock 회피

  • Banker Algorithm
    • 리소스 요청을 허락해줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 안전할 때 까지 계속 요청을 거절하는 알고리즘

 

Deadlock 탐지와 회복

  • 데드락을 허용하고 데드락이 발생하면 복구하는 전략
  1. 데드락이 발생한 프로세스 Kill 이후 다시 Run
  2. 리소스의 일시적인 선점을 허용