교착상태(Dead lock)

교착상태(Dead lock)

데드락(DeadLock) 또는 교착상태란 Multi processing 환경에서 다수의 프로세스가 작업을 진행하지 못하고 특정자원의 할당을 무한정 기다리고 있는 상태이다.

교착 상태와 기아현상(Starvation)의 차이

교착상태 : 여러 프로세스가 동일 자원 점유를 요청할 때 발생하며 리소스가 프로세스에 의해 차단된다.
기아상태 : 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때 발생하며 우선 순위가 낮은 프로세스가 차단되고 우선 순위가 높은 프로세스가 진행됩니다.

교착 상태로 인해 프로세스가 기아 상태가 될 수있는 한편, 기아로 인해 프로세스가 교착 상태에서 벗어날 수 있습니다.

발생 유형

• 시스템 자원
  임계 구역으로 보호되는 프린터, 스캐너, CD 레코더 등 동시에 같이 사용 할 수 없는 시스템 자원을 할당 받은 후 양보하지 않는 경우 발생

• 공유 변수
  한 변수를 할당 받은 상태에서, 다른 변수를 무한정 기다리기만 할 때 교착 상태가 발생

• 응용 프로그램
  예를 들어, 여러 프로세스가 하나의 데이터베이스에 저장된 데이터를 사용 할 때엔 일관성을 유지하기 위해 잠금을 사용.

교착 상태 발생 조건

4가지 모두 성립해야 교착 상태가 발생하며 하나라도 성립되지 않으면 교착 상태가 해결 가능하다.

1. 상호 배제(Mutual exclusion)
   한 프로세스가 사용하는 자원은 다른 프로세스와 공유 할 수 없는 배타작언 자원으로 임계 구역으로 보호된다.

2. 점유 대기(Hold and wait)
   다른 프로세스가 필요로 하는 자원을 점유하고 있으면서, 또 다른 자원을 기다리는 상태가 되어야 한다.

3. 비선점(No preemption)
   한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.

4. 순환 대기(Circular wait)
   점유와 대기를 하는 프로세스 간의 관계가 순환 형태를 이루어야 한다.

교착 상태 해결 방법

예방, 회피, 검출, 회복 4가지가 있다.

1. 교착 상태 예방

데드락이 성립하는 4가지 요건중 하나를 제거하므로서 데드락을 예방한다.

• 상호 배제 예방
  모든 자원 공유를 허용할 수 있다. 하지만 동시에 자원을 사용하므로서 동기화 문제가 발생한다.

• 점유 대기 예방
  프로세스가 필요로 하는 자원을 일시에 요구하고 할당한다.
  단점으로는,
  실행 후 자원이 추가적으로 필요 할 수도 있기 때문에, 프로세스가 자신이 사용하는 모든 자원을 자세히 알 수 없다.
  독점으로 인해 필요하지 않는 순간에도 자원을 소유해 자원 낭비가 발생
  많은 자원을 필요로 하는 프로세스는 기아 상태에 빠질 가능성이 있다.

• 비선점 예방
  모든 자원에 대해 선점을 허용할 수 있다. 기존에 자원을 가진 상태라면 기존 자원을 해체하고 요청한 자원과 같이 다시 할당받는다. 즉, 기존에 사용중이던 프로세스는 작업 내용을 잃을 수 있다.
  또한 어떤 기준으로 뺏을지, 얼마나 사용 할 지 등의 설정이 어려우며 기아 상태를 일으킬 수 있다. 기아 상태를 위해 에이징을 사용하면 교착 상태에 들어갈 수 있다.

• 순환대기 예방 : 자원들에게 순서를 부여하여 프로세스는 순서의 증가 방향으로만 자원 요청을 가능하게 한다. (숫자가 작은 자원을 잡은 상태에서, 큰 숫자를 잡는것은 허용하지만, 큰 숫자의 자원을 잡은 상태에서 작은 숫자의 자원을 잡는것은 허용 하지 않는 방식)
  순서에 맞지않는 자원을 할당받을 수 없어 데드락이 발생하지 않는다. 하지만 자원의 번호를 부여하는 기준 설정의 어려움과 자원이 사용 가능해도 순서로 인해 작업이 진행되지 않는 상황이 발생할 수 있다.

prevention은 자원의 효율성을 떨어트리고 비용이 많이드는 방법이다. 또한, 기아 상태 같은 다른 문제를 야기할 수 있다.

2. 교착 상태 회피

운영체제(OS)는 자원의 상태를 계속 감시하면서 프로세스가 일정기간 내에 성공적으로 종료될 수 있는 안전한 상태에서만 자원 요청을 허용하는 방법

대표적으로 은행원 알고리즘이 있다.
각 프로세스에 할당된 자원의 수는 '할당 자원'에 표시된다. 각 프로세스마다 자신이 선언한 최대 자원에서 현재 할당된 자원의 수를 빼면 '기대 자원'이 된다. 또한 전체 자원에서 각 프로세스에 할당되고 남은 자원의 수가 '가용 자원'이다.

각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다.

교착상태 회피를 하기 위해서는 다음과 같은 가정이 필요

• 프로세스 수가 고정되어 있어야 한다.
• 자원의 종류와 수가 고정되어 있어야 한다.
• 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
• 프로세스는 반드시 자원을 사용 후 반납해야 한다.

교착상태 회피 방법은 이러한 가정들이 필요하기 때문에 현실성이 부족하다. 또한 자원 요청이 있을 때마다 교착상태 회피 알고리즘을 사용한다 것은 상당한 오버헤드이다.

+) safe sequence : 교착 상태를 발생 시키지 않고 프로세스에게 자원을 할당하는 순서, safe sequence가 존재하면 safe state라고 할 수 있다.
+) Unsafe state : 교착상태가 될 수 있는 상태, 불안정 상태라서 반드시 교착상태가 발생하는 것은 아니다. -> safe state 상태여야만 자원을 할당하기에 활용도가 떨어진다.

3. 교착 상태 검출

운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식이다.

교착상태에 대해서 예방은 현실적으로 힘들고 회피는 자원의 낭비가 크다. 현실적으로 가장 적합한 것은 교착 상태를 검출하고 회복하는 것이다.

타임 아웃을 이용한 교착 상태 검출
일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법

DB의 경우, 타임아웃으로 데이터의 일관성이 깨질 수 있기 때문에 스냅샷 / 롤백을 통해 일관성을 유지한다.
윈도우 OS의 경우도 시스템 복원을 통해 스냅샷 / 롤백 사용 가능하다.

문제점

• 타임아웃 시간동안 작업이 진행 되지 않은 모든 프로세스가 교착 상태에 빠진 것은 아니기 때문에, 엉뚱한 프로세스가 강제 종료 될 수 있다.
• 분산형 DB의 경우엔, 하나의 OS에서 모든 프로세스가 진행되는 것이 아니기 때문에, 타임아웃이 발생 했을 때 교착상태 때문인지, 네트워크 오류 때문인지 명확하게 알기 어렵다.

자원 할당 그래프를 이용한 교착 상태 검출
시스템의 자원할당 그래프로 교착상태를 검사하는 알고리즘으로 교착 상태를 정확하게 파악 할 수 있다는 것이 장점이다.
자원할당 그래프는 노드와 edge로 구성되어 있으며, 사이클이 존재 하면 교착 상태라고 판단한다.
-> 다중 자원일 경우에는 사이클이 있어도 교착 상태가 아닐 수 있다.

자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가적인 작업이 오버헤드를 유발한다.

+) 타임아웃 방법은 문제점이 있지만 대부분의 DB와 운영체제에서 많이 선호된다. 자주 발생하지 않는 교착 상태를 찾기 위해 자원 할당 그래프를 유지하면서 모든 자원을 감시하기란 비용이 너무 크다. 그래서 타임아웃을 이용하는 방법을 가벼운 교착 상태 검출이라 부르고, 자원 할당 그래프를 이용하는 방법을 무거운 교착 상태 검출이라 부른다.

+) 회피와 검출의 차이점은 회피는 미래에 발생할 최악의 경우를 고려해서 deadlock이 발생하지 않게 해준다면 검출은 현재상태만을 고려하여 deadlock 발생시 recovery한다.

다중 자원에서의 교착 상태 검출

하나의 자원을 여러 개의 프로세스가 동시에 사용 할 수 있는 경우에는 교착 상태 검출이 복잡 (사이클이 있다고 해서 모두 교착상태가 되는 것은 아니다.)
그래서, 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾는다.

• 대기 그래프 : 자원 할당 그래프에서 프로세스와 프로세스간 기다리는 관계만 나타낸 그래프
• 그래프 감소 : 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와, 관련 프로세스의 화살표를 지워 나가는 작업

즉, edge가 모두 제거되면 모든 프로세스는 자원을 할당 받을 수 있는 상태며 edge가 남아있다면 하나 이상의 프로세스가 deadlock 상태라 판단할 수 있다.
노드의 수가 증가할수록 검사가 복잡해진다.

교착상태 회복

deadlock을 검출한 뒤 해결하는 과정이다. 데드락에 빠진 프로세스중 하나를 종료하거나 할당된 자원을 해제시켜 데드락을 해결할 수 있다. 어떤 프로세스를 종료시킬지가 정해져야하는데 우선순위, 총 수행시간, 남은 수행시간등 cost를 고려하여 결정할 수 있다.

프로세스 종료 방법

• 교착 상태의 프로세스를 모두 동시에 중지
  - 종료된 프로세스들이 동시에 시작된면 다시 교착상태에 빠질 수 있기에 다시 실행 할때는 순차적으로 실행해야 한다.
  
• 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법
  - 우선순위가 낮은 프로세스 부터 종료
  - 우선순위가 같은 경우 작업 시간이 짧은 프로세스부터 종료
  - 위 두 조건이 같은 경우 자원을 많이 사용하는 프로세스 부터 먼저 종료

자원 선점 방법

• 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당, 해당 프로세스는 일시정지
• 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

식사하는 철학자 문제 (Dining Philosophers)

교착 상태의 대표적인 예시이다.

5명의 철학자가 원탁에 앉아서 식사를 한다.
철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

만약 모든 철학자들이 자신의 왼쪽포크를 잡는다면, 모든 철학자들이 오른쪽 포크가 사용 가능해질 때까지 기다려야한다.

1. 철학자들은 포크를 공유할 수 없다. (상호 배제)
2. 자신의 왼쪽에 앉은 철학자가 포크를 놓을 때까지 기다린다.(점유 대기)
3. 철학자들은 왼쪽 철학자의 포크를 빼앗을 수 없다.(선점 불가)
4. 각 철학자들은 원형 테이블에 앉아 있다. (순환대기)

해결법

• 4명까지만 식탁에 앉도록 하는 방법
• 한번에 포크를 하나만 들 수 있게 하는게 아니라 동시에 왼쪽 오른쪽 포크를 들게 한다.(점유 대기 / 순환 대기 제거)]
  -> 각 푸로세스 별로 세마포어를 하나씩 갖는다.