[Network] 교착상태(Deadlock : 데드락)란?

✅ 교착 상태란?

두 개 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며,
서로의 작업을 끝나기만을 기다리다 둘 다 영원히 끝나지 않는 상황

즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황

예를 들어, 위와 같이 자동차(프로세스)들이 현재 위치한 길(자원)을 점유함과 동시에 다른 차가
사용하는 길을 사용하려고 대기하고 있지만 다른 길을 사용할 수 없으며 현재의 길에서도
벗어나지 못하는 상태를 말함.

📌 교착상태의 발생 조건 4가지

아래의 4가지 조건이 모두 만족 될 경우 발생할 가능성이 있으며, 하나라도 만족하지 않으면 교착상태가 발생하지 않는다.

1. 상호 배제 ( Mutual Exclusion )
   • 한 번에 한 개의 프로세스만이 공유자원을 사용할 수 있음 → 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 대기
2. 점유 대기 ( Hold and Wait )
   • 프로세스가 할당 된 자원을 가진 상태에서 다른 자원을 기다림
3. 비선점 ( No Preemption )
   • 프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때까지 기다림 (이미 할당 된 자원을 강제적으로 빼앗을 수 없음)
4. 순환 대기 ( Circular Wait )
   • 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루면서 대기하는 조건
   • 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

📌 교착상태의 대처 방안

1. 예방(Prevention)(or 방지)

교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법
교착상태 발생의 4가지 조건 중 어느 하나라를 제거함으로써 수행됨

• 상호배제 조건 방지
  • 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게함 ( 추후 동기화 관련 문제 발생 가능성 有 )
• 점유 대기 조건 방지
  • 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 함
• 비선점 조건 방지
  • 모든 자원에 대한 선점을 허용함
• 환형 대기 조건 방지
  • 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 요구할 수 있도록 함

이러한 조건을 방지해서 데드락을 예방하는 방법은 시스템의 처리량이나 효율성을 떨어뜨리는 단점이 발생한다.
⇒ 자원낭비가 제일 심함

2. 회피(Avoidance)

교착상태가 발생할 가능성이 있는 자원 할당(Unsafe allocation)을 하지 않고,
안전한 상태 (safe state)에서만 자원 요청을 허용하는 방법
하지만 교착 상태를 회피하기 위해서는 아래와 같은 가정이 필요하다.

1. 프로세스 수 고정
2. 자원의 종류와 수 고정
3. 프로세스가 요구하는 최대 자원의 수 파악
4. 프로세스는 자원 사용 후 반드시 반납

⇒ 이처럼 교착상태 회피 방법의 가장 큰 문제는 문제 발생에 대한 일광성과 가정이 완벽할 것이라는 것을 보장하기가 현실적으로 어려움

⇒ 시스템이 작은 규모의 운영체제라면 고려해볼만한 방법이지만 멀티 리소스, 멀티 프로세스의 복잡한 운영체제 환경에서는 자원 할당 그래프를 분석하면서 safe state를 파악하기 상당히 어려움

• 은행원 알고리즘(Banker’s Algorithm)
  • 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구를 충족할 수 있도록 현금을 대출하는 것에서 유래함
  • 자원 할당 결정전에 예상되는 모든 자원의 최대 할당량을 가지고 세뮬레이션을 하여 safe state에 들 수 있는지 여부를 검사하여 교착 상태의 가능성을 미리 조사
  • “CPU는 최소한 하나의 프로세스에게 할당해줄 만큼의 자원을 항상 보유하고 있어야한다.”
  • 미리 자원의 최대 요구량을 알아야하고, 할당 할 수 있는 자원의 수가 일정해야하는 등 사용에 제약조건이 많음
• 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)
  • 자원 할당 그래프에 예약 간선을 추가하여 예약 간선으로 설정한 자원에 대해서만 자원 할당을 요청할 수 있고 사이클이 형성되지 않을 때만 자원을 할당 받는 방법
    • 자원 할당 그래프 - 프로세스가 어떤 자원을 사용 중이고, 어떤 자원을 기다리는지 방향성 있는 그래프로 표시한 것
    • 예약 간선 - 향후 요청할 수 있는 자원을 가리키는 점섬으로 표시된 간선

3. 탐지(Detection)(or 발견)

• 시스템에 데드락이 발생했는지에 대한 여부를 탐색하고 회복 기법 알고리즘에 활용하는 것을 의미
• 교착상태가 감지되었다면 회복 기법을 통해 교착상태를 복구함
• 지속적으로 교착상태를 확인하는 작업이 필요하기 때문에 오버헤드(기능 저하)가 발생됨
• 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있음

4. 회복(Recovery)

교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여
프로세스나 자원을 회복하는 것

• 사용자의 처리
  • 교착상태에 있는 프로세스 중 하나의 프로세스를 사용자가 강제 종료
• 시스템 처리
  1. 프로세스 중지
     1. 교착상태에 속해 있는 모든 프로세스를 중지
     2. 교착상태가 해결될 때까지 한 프로세스씩 중지
  2. 자원 선점
     1. 프로세스들로부터 자원을 빼앗아 교착상태가 해결될 때까지 다른 프로세스들에게 자원을 할당
     2. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점합니다.