데드락 (Deadlock, 교착상태)

데드락을 만드는 네 가지 조건

1. Mutual exclusion - 리소스를 공유해서 사용할 수 없다.
2. Hold and wait - 프로세스가 이미 하나 이상의 리소스를 취득한(hold) 상태에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다린다 (wait)
3. No preemption - 리소스 반환은 오직 그 리소스를 취드간 프로세스만 할 수 있다.
4. Circular wait - 프로세스들이 순환(circular) 형태로 서로의 리소스를 기다린다.

네 가지 조건을 모두 만족해야 데드락이 걸림

OS의 데드락 해결 방법

1. 데드락 방지
2. 데드락 회피
3. 데드락 감지와 복구
4. 데드락 무시

데드락 방지 (Deadlock prevention)

• 네 가지 조건 중 하나가 충족되지 않게 시스템을 디자인
  • #1 리소스를 공유 가능하게 함 → 현실적으로 불가능함. (리소스를 공유할 수 없음..!)
  • #2 사용할 리소스들을 모두 획득한 뒤에 시작
  • 리소스를 전혀 가지지 않은 상태에서만 리소스 요청 → 이 때 기아와 리소스 낭비 현상이 발생할 수 있음.
  • → 만약 내가 2, 3 번의 리소스가 필요하고, 있어서 갔는데 2번이 오래걸리는 작업이라면 3번은 그때동안 놀게됨.
  • #3 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 한다. → 모니터도 이 전략과 비슷하다고 할 수 있다.
  • #4 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 요청 ← 가장 많이 사용되는 방법

데드락 회피

• 실행 환경에서 추가적인 정보를 활요해서 데드락이 발생할 것 같은 상황을 회피하는 것
  • 추가적인 정보라는 것은 실행환경에서 운영체제가 실행되고 있는데 현재 사용가능한 리소스들 이미 누군가에게 할당된 리소스들 미래에 있을 리소스 요청이나 반환등에 관한 정보들을 의미한다.
• 따라서 데드락 회피에 대한 유명한 알고리즘이 있다.
  • Banker algorithm
    • 리소스 요청을 허락해줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 안전할 때 까지 계속 요청을 거절하는 알고리즘

데드락 감지와 복구

• 데드락을 허용하고 데드락이 발생하면 복구하는 전략
  • 복구 전략 방법
    1. 프로세스를 종료한다. 또는 하나씩 종료 시킨다. (최후의 방법)
    2. 리소스의 일시적인 선점을 허용한다.

데드락 무시

• 아몰랑 ㅋㅋ 개발자가 알아서 하겠지 ㅋㅋ

프로그래밍 레벨에서 데드락 (java.ver)

출처 | 쉬운코드 유튜브