# 교착 상태 (Deadlock)


- 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미

## 교착상태 예시

public class DeadlockExample {

    public static void main(String[] args) {
        Object resource1 = new Object();
        Object resource2 = new Object();

        MyThread1 t1 = new MyThread1(resource1, resource2);
        MyThread2 t2 = new MyThread2(resource1, resource2);

        t1.start();
        t2.start();
    }
}

class MyThread1 extends Thread {
    final Object resource1;
    final Object resource2;

    public MyThread1(Object resource1, Object resource2) {
        this.resource1 = resource1;
        this.resource2 = resource2;
    }

    public void run() {
        synchronized (resource1) {
            System.out.println("Thread 1: locked resource 1");
            try {
                Thread.sleep(100);
            } catch (Exception e) {
            }
            synchronized (resource2) {
                System.out.println("Thread 1: locked resource 2");
            }
        }
    }
}

class MyThread2 extends Thread {
    final Object resource1;
    final Object resource2;

    public MyThread2(Object resource1, Object resource2) {
        this.resource1 = resource1;
        this.resource2 = resource2;
    }

    public void run() {
        synchronized (resource2) {
            System.out.println("Thread 2: locked resource 2");
            try {
                Thread.sleep(100);
            } catch (Exception e) {
            }
            synchronized (resource1) {
                System.out.println("Thread 2: locked resource 1");
            }
        }
    }
}

- 위 코드는 두 개의 스레드가 서로 다른 두 개의 자원을 사용하려고 시도하는 상황을 나타낸다.
- 두 스레드는 서로 다른 자원을 사용하려고 시도하지만, 서로의 자원을 사용하려고 시도하고 있기 때문에 무한정 기다리게 되어 교착상태에 빠진다.

## 식사하는 철학자들


1. 원형 테이블에 철학자들이 앉아있다.
2. 각 철학자 사이에는 젓가락이 하나씩 놓여 있으며, 총 N개의 젓가락이 있다(N명의 철학자가 있다고 가정).
3. 철학자들은 생각하거나 식사를 할 수 있다.
4. 식사를 할 때, 철학자는 자신의 양 옆에 있는 두 개의 젓가락을 사용해야 한다.
5. 철학자는 생각한 뒤 식사를 하고, 식사를 마친 후에는 다시 생각한다.

이러한 상황에서 다음과 같은 문제가 발생할 수 있다.

- 교착 상태(Deadlock): 모든 철학자가 동시에 자신의 왼쪽 젓가락을 집으면, 오른쪽 젓가락을 집을 수 없어 모두 교착 상태에 빠진다.
- 기아 상태(Starvation): 한 철학자가 계속해서 젓가락을 얻지 못하고 기다리는 상황이 발생할 수 있다.
- 불공평한 자원 할당(Unfairness): 한 철학자가 자주 식사하는 반면 다른 철학자는 자주 기아 상태에 빠질 수 있다.

식사하는 철학자들은 컴퓨터 과학에서 멀티스레딩과 동기화 문제를 설명하기 위한 고전적인 예시로, 다수의 프로세스나 스레드가 공유 자원에 접근할 때 발생할 수 있는 교착 상태(deadlock), 병목 현상, 비동기 접근에 대한 이슈 등을 설명하기 위해 사용된다

식사하는 철학자 문제를 시스템에 적용해보면 다음과 같다

- 철학자: 프로세스
- 젓가락: 공유 자원
- 식사: 자원 사용
- 생각: 자원을 사용하지 않는 상태
- 교착 상태: 모든 철학자가 동시에 자원을 요청하여 무한정 기다리는 상태

식사하는 철학자에 대해서 해결방법으로 여러가지가 제시되어 있으며, 그 중 몇개는 다음과 같다.

- 젓가락의 수가 철학자의 수보다 많으면 된다.
- 누군가 한명이 반대 젓가락을 먼저 들면 된다.
- 철학자가 2개의 젓가락을 모두 집을 수 있을 때만 집게 한다.

## 교착상태 발생의 필요 충분 조건


- 상호 배제(Mutual exclusion): 자원은 한 번에 하나의 프로세스만이 사용할 수 있다.
- 점유 대기(Hold and wait): 프로세스는 하나 이상의 자원을 점유하고 있으면서 그와 동시에 다른 프로세스에서 점유 중인 자원을 추가로 점유하기 위해 대기하고 있어야 한다.
- 비선점(No preemption): 어떤 프로세스가 사용 중인 자원을 다른 프로세스가 요구하면 해당 프로세스는 자원의 사용이 끝날 때까지 기다려야 하며 강제로 빼앗을 수 없다.
- 순환 대기(Circular wait): 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

## 교착상태 해결방법

교착상태에 대한 해결방법에는 크게 다음과 같은 접근 방법이 있다.

예방(Prevention), 회피(Avoidance), 발견(Detection), 복구(Recovery), 무시(Ignore)이다.

### 예방(Prevention)

교착상태가 발생하지 않도록 시스템을 설계하는 것을 의미한다

교착상태가 발생하기 위한 네 가지 필수조건이 있는데 이 중 하나라도 제거하면 교착상태를 예방할 수 있다는 점에서 착안된 방법이다.

즉, 상호 배제, 점유 대기, 비선점, 순환 대기 중 하나 이상의 조건을 제거하는 방법이다.

하지만 교착상태의 조건을 하나라도 제거하는것은 현실적으로 어렵다.

#### 1. 상호 배제 제거

상호 배제(Mutual exclusion): 자원은 한 번에 하나의 프로세스만이 사용할 수 있다.

- 상호배제 조건을 제거하여 모든 자원을 공유 가능하도록 만드는 방식
- 하지만 모든 자원이 공유 가능한 것은 아니기 때문에 현실적이지 않다

#### 2. 점유 대기 제거

점유 대기(Hold and wait): 프로세스는 하나 이상의 자원을 점유하고 있으면서 그와 동시에 다른 프로세스에서 점유 중인 자원을 추가로 점유하기 위해 대기하고 있어야 한다.

- 프로세스 시작 시 필요한 자원을 모두 할당받게 하고, 그 이후에는 추가적인 자원 요청을 허용하지 않는 방식
- 자원의 활용도가 떨어져서 효율성이 크게 저하하는 단점이 있다.

#### 3. 비선점 제거

비선점(No preemption): 어떤 프로세스가 사용 중인 자원을 다른 프로세스가 요구하면 해당 프로세스는 자원의 사용이 끝날 때까지 기다려야 하며 강제로 빼앗을 수 없다.

- 운영체제가 필요한 경우 자원을 강제로 빼앗을 수 있는 방법을 제공하는 방식
- 프로세스의 실행에 영향을 줄 수 있고 예상치 못한 결과를 초래할 수 있다.

#### 4. 순환 대기 제거

순환 대기(Circular wait): 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

- 모든 자원에 번호를 붙이는 방식
- 프로세스는 자원을 요청할 때, 번호가 낮은 순서부터 요청하도록 강제하는 방식
- 특정 자원의 활용률이 떨어질 수 있다.

### 회피(Avoidance)


- 시스템이 교착상태를 지속적으로 검사하여 교착상태가 발생할 가능성이 있는 경우의 자원 할당을 회피하는 방법
- 자원 요청에 대해 교착상태를 예측하고, 예측된 상황을 피하는 방법
- 교착상태가 발생할 가능성이 있다면 자원을 할당하지 않는다.
- 현재 가용자원을 프로세스 요청시 바로 할당해 줄 것인지(안정 상태), 기다리게 할 것인지(불안전 상태)를 결정하는 문제와 같다.
- 대표적인 알고리즘으로 `은행원 알고리즘`이 있다.
- 은행이 대출을 시행한 후에 파산하지 않고 정상 유지되지는를 검사하여 안전하다고 판단될 때만 대출을 시행하는 것과 같은 개념

### 교착상태 발견(Detection) 및 복구(Recovery)

> R: 리소스 / P: 프로세스

- 시스템이 교착상태에 빠지는 것을 허용하되, 교착상태를 탐지하고 이를 해결하기 위한 메커니즘을 갖추는 방법
- 회피 및 예방에 비해 자원활용도가 높지만, 교착상태를 해결하기 위한 비용이 발생한다.

#### 발견(Detection)

- 특정 조건이 발생했을 때 시스템의 자원 할당 상태를 검사하여 교착상태를 확인한다
- 일반적으로 자원 할당 그래프를 사용하여 교착상태를 탐지한다
- 자원 할당 그래프에서 교착상태는 순환 경로(cycle)로 나타난다

#### 복구(Recovery)

- 교착상태가 탐지되면 시스템은 교착상태를 해결하기 위해 하나 또는 여러 프로세스를 종료하거낟 할당된 자원을 회수하는 등의 조치를 취한다
- 프로세스를 종료하는 방법에는 여러 가지가 있는데, 모든 교착상태에 연루된 프로세스를 종료하거나 교착상태 사이클을 제거할 수 있는 최소 수의 프로세스를 종료하는 방법이 있다.

### 무시(Ignore)

교착상태를 해결하는데는 비용이 많이 들고, 교착상태가 발생할 가능성이 적다. 즉 교착상태 해결을 위한 오버헤드가 교착상태로 인한 문제보다 더 큰 경우가 일반적이다.

따라서 많은 시스템에서는 교착상태를 무시하고 시스템을 운영하는 방법을 사용한다. 대신 교착상태 발생 시 사요자나 관리자가 수동으로 개입하여 시스템을 재시작하거나 문제를 해결할 수 있도록 한다.