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 등)가 채택하는 방식으로, 데드락 해결 비용보다 시스템을 그냥 재부팅하거나 사용자가 프로세스를 종료하는 것이 경제적이라고 판단

3. 게임에서의 사례

게임 스레드에서 캐릭터 자원을 로드하고 총모델을 필요로 함. 다른 스레드에서 총모델을 로드하고 캐릭터 자원이 필요로 함. 이럴 때 서로 데드락이 걸린다.

또, 게임 스레드와 AI관련 스레드가 있을 때 게임 스레드에선 AI연산이 끝나면 업데이트하려고 기다리고 AI스레드는 게임 스레드가 업데이트 되어야 연산하려고 기다리는 상황. 이렇게 자원이 아니라 스레드 간의 데드락도 존재