1. 교착 상태(Deadlock)

1-1. 교착 상태란?

2개 이상의 스레드가 서로가 가지고 있는 자원을 기다리며 영원히 멈춰 버리는 상태 (순환 대기)

→ 자원 취득 순서 / 타임 아웃 / 검출 알고리즘 필요

• e.g. 식사하는 철학자 문제

[교착 상태를 해결하기 위해서]

1. 교착 상태가 발생했을 때 상황을 표현
2. 교착 상태가 일어나는 근본적 이유 이해

1-2. 자원 할당 그래프

교착상태가 어떤 조건에서 발생하는지 파악할 수 있음

• 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

c.f. 식사하는 철하자의 자원할당그래프

• 교착 상태가 일어난 그래프는 자원할당그래프가 원의 형태를 띄고 있음
  

1-3. 교착 상태 발생 조건 (Coffman의 4가지 조건)

교착 상태는 아래 4가지 조건이 모두 동시에 만족될 때 발생함

1. 상호 배제 (Mutual Exclusion)
   자원은 한 번에 오직 하나의 프로세스만 사용할 수 있음
2. 점유와 대기(hold & wait)
   자원을 할당 받은 상태에서 다른 자원을 기다리고 있는 상태
3. 비선점 (No Preemption)
   어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗을 수 없음
4. 원형 대기 (Circular Wait)
   프로세스들이 원의 형태로 자원을 대기하는 형태

1-4. 교착 상태 해결 방법

교착 상태를 해결하는 방법으로는 크게 3가지가 있음

: 예방, 회피, 검출 후 회복

1) 교착 상태 예방 (Prevention)

애초에 교착 상태가 발생하지 않도록

교착 상태 조건(4가지) 중 하나를 없애기

1. 상호 배제 X → 모든 자원을 공유 가능하게 만들기
   현실적으로 모든 자원을 공유하는 것은 불가능함

2. 점유와 대기 X → 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
   → 자원의 활용률을 낮출 수 있는 방식

3. 비선점 조건 X → 선점이 가능한 자원 (e.g. CPU)에 한해 효과적
   → 모든 자원이 선정 가능한 것은 아님

4. 원형 대기 조건 X → 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당

   하지만 모든 자원에 번호를 붙이는 작업은 어려움
   어떤 자원에 어떤 번호를 부여하는지에 따라 활용률이 다름

2) 교착 상태 회피 (Avoidance)

교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주함

교착 상태가 발생하지 않을만큼 조심하여 할당함

배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분함

• 안전 순서열: 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서
  e.g. A-B-C: 교착 상태 , A-C-A: 교착 상태 X → 안전 순서열!
• 안전 상태: 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
  → 안전 순서열이 있는 상태
• 불안전 상태: 교착 상태가 발생할 수도 있는 상태
  → 안전 순서열이 없는 상태
• 교착 상태 회피는 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식
  항시 안전 상태를 유지하도록 자원을 할당함
  e.g. 은행원 알고리즘

3) 교착 상태 검출 후 회복 (Detection & Recovery)

교착 상태의 발생을 인정하고 사후에 조치하는 방식

프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복

• 선점을 통한 회복
  교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 프로세스 강제 종료를 통한 회복
  교착 상태에 놓인 프로세스 모두 강제 종료 (작업 내역을 잃을 위험)
  교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (오버헤드)