[CS] 교착 상태란

교착 상태를 해결하는 것 또한 운영체제가 맡는 중요한 임무 중 하나이다. 교착 상태란 무엇이며, 그를 표현하는 자원 할당 그래프와 교착 상태의 발생 원인을 알아보자

교착 상태(deadlock)

• 두 개 이상 프로세스가 각자 자원을 점유하고, 서로의 자원을 요구할 때에 더 이상 프로세스 진행이 불가해진다.
• 서로의 종료만을 기다리며 진행이 멈춰버릴 때 교착 상태가 발생한다.

식사하는 철학자 문제(dining philosophers problem)

• 교착상태를 잘 설명하는 예시이다.
• 철학자는 프로세스 또는 쓰레드, 포크는 자원, 생각하는 행위는 자원을 기다리는 것으로 이해할 수 있다.
• 포크는 한 번에 한 스레드에만 접근할 수 있으니 임계 구역으로 생각할 수 있다.

식사하는 철학자 문제 과정

1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6. 다시 1번부터 반복한다.

언뜻 보기에는 아무런 문제가 없어 보인다. 실제로 한 두명의 철학자가 식사할 때는 문제가 발생하지 않는다. 하지만? 여러명의 모든 철학자가 동시에 포크를 집어 식사한다면? 이 상태를 교착 상태라고 한다.

교착 상태의 발생 예시

• 뮤텍스 락에서도 교착상태는 발생할 수 있다.
• 각 프로세스가 lock 1과 2를 잠구고(lock1,2 = true;) 서로의 lock이 풀리기 만을 기다리면 교착 상태가 발생한다.

lock 1 = true;                                   lock 2 = true;
while(lock2 == true)                             while(lock1 == true)
;                                                ;

// 임계 구역 진입                                  // 임계 구역 진입
lock1 = false;                                   lock2 = false;

교착 상태의 해결

• 교착 상태 발생 상황을 정확히 표현할 수 있어야 한다.
• 교착 상태가 일어나는 근본적 원인을 알아야 한다.

---

자원 할당 그래프(resource-allocation graph)

• 각 프로세스가 어떤 자원을 사용하고, 어떤 자원을 기다리는지 간단히 표현한 그래프
  교착 상태는 자원 할당 그래프를 통해 단순히 표현될 수 있다.

자원 할당 그래프 작성 규칙

1. 프로세스는 원으로, 자원은 사각형으로 표현한다.

2. 사용할 수 있는 자원 개수는 자원 사각형 내 점으로 표현한다.

3. 프로세스가 어떤 자원을 사용 중이라면 자원에서 프로세스를 향해 화살표 표시한다.
   프로세스가 자원 사용을 종료하면 화살표는 삭제된다.

4. 프로세스가 어떤 자원을 기다리면 프로세스에서 자원으로 화살표를 표시한다.

자원 할당 그래프 예시

• SSD는 자원 개수가 3개, CPU는 2개, 프린터는 1개이다.
• 프로세스 A는 SSD를 사용한다.
• 프로세스 B와 C는 CPU를 사용하고, 프로세스 F는 CPU 사용을 요청한다.
• 프로세스 D는 프린터를 사용하고, 프로세스 E는 프린터 사용을 요청한다.

철학자 문제 자원 할당 그래프로 이해하기

또 다른 교착 상태를 자원 할당 그래프로 이해하기

• 교착 상태는 자원 할당 그래프가 원의 형태를 띌 때 발생한다.

---

교착 상태 발생 조건

• 교착 상태 발생 조건은 다음 네 가지가 있다.
  1. 상호 배제
  2. 점유와 대기
  3. 비선점
  4. 원형 대기

• 조건들이 모두 만족할 때 교착 상태 발생 가능성이 생긴다. 하나라도 만족하지 않으면 교착상태는 발생하지 않는다.

1. 상호 배제(mutual exclusion)

• 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상황에서 발생할 수 있다.
• 자원 할당량을 프로세스가 모두 사용하고, 작업이 끝나지 않으면 교착 상태가 발생할 수 있다.

2. 점유와 대기(hold and wait)

• 프로세스가 자원을 할당 받은 상태에서 다른 자원의 할당을 기다리는 상태에서 발생할 수 있다.
• 다른 프로세스의 작업이 끝나지 않으면 자원을 무한히 기다리게 된다.

3. 비선점(nonpreemptive)

• 자원을 이용하는 프로세스가 작업이 끝나야만 이용할 수 있는 자원을 비선점 자원이라고 한다.
• 어떤 프로세스도 다른 프로세스에 할당된 자원을 뺏지 못하면 교착상태가 발생할 수 있다.

4. 원형 대기(circular wait)

• 프로세스들이 원형 형태로 자원을 대기하는 상태를 뜻한다.
• 자원 할당 그래프가 원 형태로 그려지면 교착상태가 발생할 수 있다.
• 자원 할당 그래프가 원의 형태로 그려지면 교착 상태가 발생할 '수' 있다고 표현한 이유가 있다. 자원 할당 그래프가 원의 형태를 띄지 않는다면 교착 상태는 발생하지 않으나, 원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아니다.