1. 데드락 발생의 필수 조건

• 데드락이 발생하려면 아래의 4가지 조건을 필수로 만족해야 함

1. 상호 배제 (Mutual Exclusion)
   자원은 한 번에 한 프로세스만 사용할 수 있어야 함

2. 점유와 대기 (Hold and Wait)
   최소한 하나의 자원을 점유한 채로, 다른 프로세스에 할당된 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함

3. 비선점 (No Preemption)
   다른 프로세스에 할당된 자원을 강제로 뺏을 수 없어야 함

4. 환형 대기 (Circular Wait)
   대기 프로세스 집합이 순환 형태로 자원을 대기해야 합니다. (A는 B의 자원을, B는 A의 자원을 대기)

2. 데드락 해결 방법

2.1. 발생 조건을 예방

• 발생 조건 4가지 중 하나를 미리 부정하여 데드락 가능성을 차단

1. 상호 배제 부정: 모든 자원을 공유하게 함

2. 점유 대기 부정

   • 프로세스 실행 전 필요한 모든 자원을 한번에 요청하여 다 받고 사용
   • 다 못 받으면 아무것도 가지지 않고 대기

3. 비선점 부정: 자원을 기다려야 하면 가진 자원을 반납

4. 환형 대기 부정

   • 가장 실무적이고 효율적인 예방법
   • 자원에 고유 번호를 할당하고 프로세스는 반드시 번호가 낮은 순서에서 높은 순서로만 자원을 요청할 수 있게 함

• 자원 효율성이 떨어지고 비용이 많이 든다는 단점이 있음

2.2. 은행원 알고리즘

• 안전 상태 : 시스템이 모든 프로세스의 최대 자원 요구량을 차례대로 들어줄 수 있는 순서(Safe Sequence)가 존재하는 상태

• 프로세스가 자원을 요청하면, 시스템은 해당 자원을 빌려준 뒤에도 안전 순서열이 존재하는지 가상으로 시뮬레이션 함

• 안전 순서열이 존재한다면 자원을 할당하고, 그렇지 않다면 다른 프로세스가 자원을 반납할 때까지 할당을 거부

• 최대 자원 요구량을 미리 알아야 하고 오버헤드가 큼

참고 은행원 알고리즘 만화

2.3. 탐지 및 복구

• 예방하는 것 자체가 오버헤드가 크기 때문에, 데드락 발생을 허용하되 주기적으로 체크하고 발견 시 조치함

• 자원 할당 그래프를 통해 사이클을 찾게되면

  • 데드락에 빠진 모든 프로세스를 Kill하거나 (실하지만 작업 손실이 큼)

  • 순서대로 Kill하며 복구확인 (비용 계산이 필요)

  • 자원을 강제로 선점하여 다른 프로세스에게 부여 (자원을 계속 뺏기기만 하는 기아 발생 가능)

2.4. 타조 알고리즘

• 근데 애초에 데드락이 아주 드물게 발생하기도 하고, 예방하는 것도, 탐지하고 복구하는 것도 너무 큰 오버헤드

• 그래서 타조가 모래에 머리박고 모르쇠하듯이 OS에서는 아무것도 안하고 사용자가 처리하도록 함

• 현대의 많은 OS(Windows, Linux 등)가 채택하는 방식으로, 데드락 해결 비용보다 시스템을 그냥 재부팅하거나 사용자가 프로세스를 종료하는 것이 경제적이라고 판단