[CS/운영체제] Deadlock(데드락)

💡 정의

두 개 이상의 프로세스가 무한정 자원을 기다리게 되는 상태

💡 발생 조건

⇒ 4가지 모두 만족해야함

1. 상호 배제 (Mutual exclusion): 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2. 점유와 대기**(Hold and wait)**: 자원을 할당받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
3. 비선점**(No preemption)**: 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못함
4. 원형 대기**(Circular wait)**: 프로세스들이 원형(순환) 형태로 자원을 대기하는 상태

💡 해결 방법

1. 예방 : 발생 조건 중 하나 제거 ⇒ (-)자원 활용률 ⬇️
   1. 상호 배제 X: 모든 자원을 공유 가능 하게
   2. 점유와 대기 X: 특정 프로세스에 자원 모두 할당 or 아예 할당하지 않음
   3. 비선점 X: 선점이 가능한 자원(ex.CPU)에 한해 효과적
   4. 원형 대기 X: 자원에 번호를 붙이고 오름차순으로 할당. 이 순서대로 자원 요구 ⇒ 일렬 형태
2. 회피
   1. 교착 상태의 원인을 무분별한 자원 할당으로 봄
   2. 배분할 수 있는 자원의 양을 고려하여 교착상태가 발생하지 않을 만큼 자원 배분
   3. 안전상태(안전순서열O)를 유지하도록 자원 할당
   4. ex) 은행원 알고리즘 : 프로세스 당 요청할 자원들의 최대치를 통해 자원 할당 가능 여부를 파악
      1. (-) 모든 할당 요청을 검사해야 하므로 계산 오버헤드 가능
      2. (-) 동적 시스템(실시간 시스템)에 적합하지 않음
3. 검출 후 회복
   1. 선점을 통한 회복 : 교착 상태가 해결될 때까지 한 프로세스 씩 자원을 몰아줌
   2. 프로세스 강제 종료를 통한 회복
      1. 교착상태에 놓인 프로세스 모두 강제 종료 (→ 작업 내역 잃을 위험)
      2. 교착상태가 해결될 때까지 한 프로세스 씩 강제 종료(→ 오버헤드)