교착 상태 (Deadlock)

1. 교착 상태

교착 상태(Deadlock)란 멀티프로세싱 환경에서 둘 이상의 프로세스(또는 스레드)가 상대방이 점유한 자원을 기다리며 무한 대기에 빠져, 시스템 전체의 진행이 멈추는 현상을 의미한다. 이는 단순히 성능 저하를 넘어 시스템의 가용성을 위협하는 문제다.

2. 교착 상태의 형식적 정의와 발생 조건

2.1. 자원 할당 그래프 (Resource-Allocation Graph)

교착 상태는 자원 할당 그래프를 통해 형식적으로 모델링할 수 있다. 이 그래프는 프로세스(원)와 자원 유형(사각형)이라는 두 종류의 정점(vertex)으로 구성된다.

• 프로세스 정점(P): 시스템 내의 활성 프로세스 집합 {P₁, P₂, ...}
• 자원 정점(R): 시스템 내 자원 유형의 집합 {R₁, R₂, ...}. 사각형 안의 점은 해당 자원의 인스턴스(instance) 수를 의미한다.
• 요청 간선(Request Edge): Pᵢ → Rⱼ. 프로세스 Pᵢ가 자원 Rⱼ의 인스턴스를 요청하며 대기 중임을 의미한다.
• 할당 간선(Assignment Edge): Rⱼ → Pᵢ. 자원 Rⱼ의 인스턴스가 프로세스 Pᵢ에 할당되었음을 의미한다.

그래프와 교착 상태의 관계:

1. 그래프에 사이클(cycle)이 없다면, 교착 상태는 절대 발생하지 않는다.
2. 그래프에 사이클이 존재하고, 모든 자원이 단일 인스턴스만 갖는다면, 교착 상태가 반드시 발생한다.
3. 그래프에 사이클이 존재하고, 자원이 다중 인스턴스를 갖는다면, 교착 상태가 발생할 수도 있고 아닐 수도 있다. 사이클은 교착 상태의 필요조건이지만, 충분조건은 아니다.

2.2. 교착 상태 발생의 4가지 필요조건 (Coffman's Conditions)

교착 상태는 아래 4가지 조건이 동시에 모두 성립될 때만 발생할 수 있다.

1. 상호 배제 (Mutual Exclusion): 최소 하나 이상의 자원이 비공유(non-sharable) 모드로 점유되어야 한다. 즉, 한 번에 한 프로세스만 사용할 수 있다.
2. 점유와 대기 (Hold and Wait): 프로세스가 최소 하나의 자원을 점유한 상태에서, 다른 프로세스가 점유한 자원을 추가로 요청하며 대기한다.
3. 비선점 (No Preemption): 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다. 자원은 점유한 프로세스가 자발적으로 해제해야만 한다.
4. 환형 대기 (Circular Wait): 대기하고 있는 프로세스들의 집합 {P₀, P₁, ..., Pₙ}에서, P₀는 P₁이 점유한 자원을, P₁은 P₂가 점유한 자원을, ..., 그리고 Pₙ은 P₀가 점유한 자원을 기다리는 원형의 대기 사슬이 존재해야 한다.

3. 교착 상태 처리 전략 심층 분석

3.1. 예방 (Prevention)

교착 상태의 4가지 필요조건 중 하나를 원천적으로 부정하여 교착 상태 발생을 막는 가장 강력한 방법이다.

• 상호 배제 부정: 현실적으로 불가능한 경우가 많다. 프린터와 같은 자원은 본질적으로 공유될 수 없다. (단, 스풀링(spooling)을 통해 공유되는 것처럼 보이게 할 수는 있다.)
• 점유와 대기 부정: 프로세스 시작 전 모든 자원을 한 번에 요청하게 하거나, 자원을 요청할 때 아무것도 점유하지 않도록 강제한다. 자원 이용률이 급격히 떨어지고, 특정 프로세스가 자원을 영원히 할당받지 못하는 기아(starvation) 상태가 발생할 수 있다.
• 비선점 부정: 자원을 할당받을 수 없는 프로세스의 기존 자원을 강제로 빼앗는다. CPU나 메모리처럼 상태 저장이 쉬운 자원에만 적용 가능하며, 구현이 복잡하다.
• 환형 대기 부정: 모든 자원 유형에 순서를 부여하고, 모든 프로세스가 그 순서에 따라 오름차순으로만 자원을 요청하도록 강제한다. (예: 락 순서 지정, Lock Ordering). 가장 실용적인 예방책이지만, 시스템 전체에 걸쳐 일관된 순서를 설계하고 강제해야 하는 부담이 있다.

3.2. 회피 (Avoidance)

자원 할당 시, 해당 할당이 시스템을 불안전 상태(unsafe state) 로 만들 가능성이 있다면 요청을 지연시키는 방식이다. 시스템은 항상 안전 상태(safe state) 를 유지해야 한다.

• 안전 상태: 시스템 내의 모든 프로세스들에게 자원을 할당해 줄 수 있는 안전 순서(safe sequence) <P₁, P₂, ...>가 존재하는 상태. 즉, 시스템이 교착 상태를 유발하지 않고 모든 프로세스를 정상적으로 종료시킬 수 있음이 보장되는 상태다.
• 은행원 알고리즘 (Banker's Algorithm): 대표적인 회피 알고리즘.
  • 자료구조: Available(가용 자원), Max(프로세스별 최대 필요 자원), Allocation(현재 할당된 자원), Need(추가 필요 자원).
  • 동작:
    1. 프로세스가 자원을 요청하면, 일단 요청을 수락했다고 가정한다.
    2. 그 상태에서 안전성 알고리즘(Safety Algorithm) 을 실행하여, 시스템이 여전히 안전 순서를 찾을 수 있는지(안전 상태인지) 검사한다.
    3. 안전하다면 요청을 실제로 할당하고, 안전하지 않다면 요청을 거부하고 프로세스를 대기시킨다.
  • 단점: 프로세스가 필요로 할 자원의 최대 개수를 미리 선언해야 하고, 자원 요청마다 O(m×n²)의 복잡도를 갖는 안전성 알고리즘을 실행해야 하므로 오버헤드가 매우 크다. 이 때문에 범용 OS에서는 거의 사용되지 않는다.

3.3. 탐지 및 회복 (Detection & Recovery)

교착 상태 발생을 허용한 뒤, 주기적으로 탐지 알고리즘을 실행하여 교착 상태를 발견하고, 발견 시 회복 알고리즘으로 해결하는 사후 처리 방식이다.

• 탐지 알고리즘:
  • 자원 유형별 인스턴스가 하나뿐이라면, 자원 할당 그래프에서 사이클을 찾는 것만으로 충분하다 (O(n+e)).
  • 인스턴스가 여러 개라면, 은행원 알고리즘과 유사한 방식의 알고리즘을 사용한다 (O(m×n²)).
• 회복 전략:
  • 프로세스 종료: 가장 간단한 방법. 교착 상태에 빠진 모든 프로세스를 종료하거나, 사이클이 없어질 때까지 하나씩 종료한다. '희생양(victim)'을 선택하는 기준(우선순위, 실행 시간 등)이 필요하다.
  • 자원 선점: 교착 상태의 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당한다.
    • 희생양 선택: 어떤 프로세스의 어떤 자원을 빼앗을지 결정해야 한다.
    • 롤백 (Rollback): 자원을 빼앗긴 프로세스를 어느 시점으로 되돌릴지 결정해야 한다. 가장 안전한 방법은 프로세스를 완전히 재시작하는 것이다.
    • 기아 상태: 특정 프로세스가 계속해서 희생양으로 선택되어 영원히 작업을 완료하지 못할 수 있다.

3.4. 무시 (Ignorance)

교착 상태가 매우 드물게 발생한다고 가정하고, 이를 처리하는 비용이 더 크다고 판단하여 아무런 조치도 취하지 않는 방법이다. '타조 알고리즘(Ostrich Algorithm)' 이라고도 불린다.

• 장점: 교착 상태 처리에 드는 오버헤드가 전혀 없다.
• 단점: 교착 상태 발생 시 시스템이 멈추거나 비정상 종료될 수 있으며, 복구는 전적으로 사용자나 관리자의 몫(재부팅 등)이다.
• 적용: Windows, macOS, Linux 등 대부분의 범용 운영체제가 이 방식을 채택하고 있다. 교착 상태 예방/회피/탐지로 인한 성능 저하가 사용자 경험에 더 큰 악영향을 미친다고 보기 때문이다.

4. 계층 구조로 본 교착 상태

사용자 프로그램의 잘못된 코드가 어떻게 커널 수준의 교착 상태로 이어지는지 추적해보자. (두 스레드가 두 개의 뮤텍스를 교차 요청하는 경우)

1. 사용자 애플리케이션 계층:
   • 스레드 1: lock(M1); ... lock(M2);
   • 스레드 2: lock(M2); ... lock(M1);
   • 프로그래머가 '락 순서 지정' 규칙을 위반하여 교착 상태의 원인을 제공한다.
2. 라이브러리 계층 (e.g., Pthreads):
   • 스레드 1이 lock(M1)에 성공. 스레드 2가 lock(M2)에 성공.
   • 스레드 1이 lock(M2)를 호출. M2는 스레드 2가 점유 중이므로, pthread 라이브러리는 스레드 1을 대기시키기 위해 커널에 진입해야 한다.
3. 시스템 콜 인터페이스 계층:
   • 라이브러리는 커널에 스레드를 대기시키기 위해 futex(FUTEX_WAIT, ...)와 같은 시스템 콜을 호출한다. Futex는 락이 경합 상태일 때만 커널을 호출하는 효율적인 동기화 메커니즘이다.
4. 커널 계층 (OS 스케줄러):
   • 커널은 futex 호출을 받고, 스레드 1의 상태를 RUNNING에서 WAITING(또는 BLOCKED)으로 변경한다.
   • 스레드 1을 M2 뮤텍스의 대기 큐(wait queue)에 넣는다.
   • 곧이어 스레드 2가 lock(M1)을 호출하고, M1은 스레드 1이 점유 중이므로 똑같은 과정을 거쳐 M1의 대기 큐에 들어간다.
   • 교착 상태 발생: 커널의 관점에서 스레드 1과 2는 모두 WAITING 상태다. 이들은 자신이 기다리는 자원이 해제되기 전까지 절대 RUNNABLE 상태로 돌아갈 수 없다. 커널은 기본적으로 이 상황이 '순환 대기'라는 것을 인지하지 못한다. 단지 두 스레드가 각자 다른 이벤트를 기다리고 있다고만 판단한다.
5. 회복 계층 (DBMS의 경우):
   • 만약 이것이 DBMS 내부였다면, 별도의 교착 상태 탐지기(detector) 스레드가 주기적으로 내부의 '대기 그래프(waits-for graph)'를 분석한다.
   • 그래프에서 '스레드 1 -> 스레드 2 -> 스레드 1' 사이클을 발견하면, 회복 정책에 따라 둘 중 하나(예: 스레드 2)를 희생양으로 선택하고 트랜잭션을 롤백시킨다.
   • 롤백 과정에서 M2 락이 해제되고, 커널에 futex(FUTEX_WAKE, ...)를 통해 M2를 기다리던 스레드(스레드 1)를 깨우라고 알린다.
   • 커널은 스레드 1을 RUNNABLE 상태로 만들고, 스케줄러는 언젠가 스레드 1을 다시 실행시켜 작업을 계속하게 한다.

5. 요약

 교착 상태는 간단히 말해, 둘 이상의 프로세스나 스레드가 서로가 가진 자원을 놓아주기를 기다리면서 영원히 멈춰버리는 '무한 대기' 상태입니다. 예를 들어, 스레드 1이 자원 A를 가진 채 자원 B를 기다리고, 스레드 2는 자원 B를 가진 채 자원 A를 기다리는 상황이죠.

이런 교착 상태가 발생하려면 네 가지 조건이 동시에 만족되어야 합니다. 바로 상호 배제, 점유와 대기, 비선점, 그리고 환형 대기입니다. 이 중 하나라도 깨뜨리면 교착 상태를 막을 수 있습니다.

 그래서 교착 상태를 다루는 방법도 크게 네 가지로 나뉩니다.
 첫째, 예방(Prevention) 은 이 네 가지 조건 중 하나를 원천적으로 막는 겁니다. 가장 실용적인 방법은 '환형 대기'를 막는 것인데, 모든 자원에 순서를 정하고 그 순서대로만 자원을 획득하도록 강제하는 '락 순서 지정(Lock Ordering)' 기법이 대표적입니다.
 둘째, 회피(Avoidance) 는 자원을 할당해 주기 전에, 이 할당이 미래에 교착 상태를 유발할지 '은행원 알고리즘' 같은 걸로 미리 계산해보는 겁니다. 안전할 때만 할당해주는 거죠. 하지만 계산이 복잡해서 잘 쓰이진 않습니다.
 셋째, 탐지 및 회복(Detection & Recovery) 은 일단 교착 상태가 발생하도록 내버려 둔 다음, 주기적으로 시스템을 검사해서 교착 상태를 찾아내고, 발견되면 관련된 프로세스 중 하나를 강제 종료해서 해결하는 방식입니다. 데이터베이스 시스템이 이런 방식을 주로 사용합니다.
 마지막으로 무시(Ignorance) 가 있습니다. 교착 상태는 드물게 발생하니까 그냥 무시하고, 문제가 생기면 사용자가 알아서 끄거나 재부팅하라는, 이른바 '타조 알고리즘'입니다. 놀랍게도 윈도우나 리눅스 같은 대부분의 범용 운영체제가 이 방식을 씁니다. 처리 비용이 더 크다고 보기 때문이죠.

 시스템 계층 구조에서 보면, 유저 프로그램이 잘못된 순서로 락을 요청하면 교착 상태가 발생합니다. 스레드 1이 커널에게 '자원 B를 달라'고 요청하면, 커널은 'B는 스레드 2가 쓰고 있으니 기다려'라며 스레드 1을 대기 상태로 만듭니다. 반대도 마찬가지고요. 커널은 그저 두 스레드가 각자 자원을 기다린다고만 알지, 이게 순환적인 교착 상태인지는 기본적으로 알지 못하고 신경 쓰지 않습니다. 그래서 두 스레드는 영원히 깨어나지 못하게 되는 겁니다.

 결론적으로, 교착 상태는 다중 프로그래밍 환경의 근본적인 문제이며, 시스템의 목적에 따라 각기 다른 전략으로 대응합니다. 일반적인 애플리케이션 개발자는 '락 순서'를 철저히 지켜서 교착 상태를 '예방'하는 것이 가장 중요한 임무라고 할 수 있습니다.