5. 교착상태

교착상태(deadlock)이란?

• 2개 이상의 프로세스가 다른 프로세스의 자원을 기다리며 더이상 작업하지 못하는 무한대기 상태에 빠지는 것을 말한다.

교착상태의 4가지 조건

• 4가지 조건을 모두 만족하여야 교착상태이다.

1. 상호 배제: 사용하는 자원이 공유할 수 없는 자원이여야 한다.
2. 비선점: 하나의 프로세스가 다른 프로세스를 선점할 수 없어야 한다.
3. 점유와 대기: 각 프로세스는 어떤 자원을 할당받고 대기상태에 있어야한다.
4. 원형대기: 대기하는 방향이 원형을 이루어야한다.(사이클)

교착상태와 아사현상은 다르다

• 아사 현상은 정책적인 오류로 인해 작업이 이루어지지 않는 것을 말한다. 에이징등을 통해 해결할 수 있지만 교착상태는 자연스럽게 발생한다.

교착상태 해결법

1. 예방 - 4가지 조건중에 하나를 무력화 하는 방법이다
   • 상호배제 예방: 현실적으로 모든 자원을 공유할 수는 없으며 자원 공유시 데이터 일관성이 어긋날 수 있다.
   • 비선점 예방: 프로세스를 선점형식으로 만들면 시스템 프로세스를 건드릴 수도 있고 아사현상에 빠질 수 있다. 에이징을 해결하여도 다시 아사현상에 빠지게 된다.
   • All or Nothing: 모두 부여하거나 아예 부여하지 않는 방식
     • 모든 프로세스가 어떤 자원을 쓰는지 초기에 알기 어렵다.
     • 자원의 활용성이 줄어든다. (노는 자원이 많아진다)
     • 많은 자원을 사용하는 프로세스는 아사현상에 빠지게 된다.
     • 한번에 해야하기 때문에 일괄적으로 작업하게 되며 효울이 떨어진다.
   • 원형대기 예방: 자원에 번호를 부여하고 작은쪽에서 큰쪽으로만 할당되게 하는 방식
     • 유연성이 떨어지며 납득이 어렵다.(프린터 → 마우스는 되는데 반대가 안되면 사용자 입장에서는 납득이 어렵다)
     • 번호를 부여하는데 신중하여야한다.
   ⇒ 즉 예방 방법은 모두 실효성이 떨어진다.
2. 회피 - 자원을 할당하다가 교착상태의 가능성이 있으면 중단한다.
   • 30명의 테이블을 받을 수 있는 레스토랑에 20개의 파스타 분량뿐이라면 20명만 예약을 받는 방식이다.
   • 나머지 10테이블이 낭비된다. 또한 프로세스가 할당할 자원을 미리 알고있어야한다.
   ⇒ 마찬가지로 실효성이 떨어진다.
3. 검출과 회복 - 자원할당 그래프를 보며 회복 <= 현실적인 방법이다.
   • 타임아웃을 이용(가벼운 교착상태 검출)
     • 프로세스가 아무동작도 하지 않고 있다면 교착상태로 간주하여 종료하는 방식
     • 대기를 하고있는 엉뚱한 프로세스가 종료될 수 있다.
     • 분산형 시스템(분산 데이터베이스 등)에서는 네트워크 문제로 타임아웃이 발생할 수도 있으므로 적용하기가 어렵다.
   • 자원할당 그래프를 이용한 검출(무거운 교착상태 검출)
     • 사이클이 발생하면 교착상태로 본다 ⇒ 하지만 아닐수도있다. (뒤에서 다룸)
     • 프로세스를 계속해서 검사하면 오버헤드가 증가한다. 이를 위해 일정시간마다 검사하는 방법도 있다.
   • 교착상태의 회복
     • 프로세스를 모두 종료 ⇒ 다시 실행할 때 어떤걸 먼저 실행할지 기준이 필요하다. (재발생의 가능성이 있다)
     • 프로세스 하나를 종료
       • 우선순위가 낮은 프로세스
       • 같다면, 시간이 적게 걸리는 프로세스
       • 둘다 같다면 자원을 많이 쓰는 프로세스

다중 자원 - 사이클이 있어도 교착상태가 아닐수 있는 경우

하나의 자원을 2개이상의 프로세스가 쓸수 있다면 사이클이 발생하여도 교착상태라고 볼수 없다.

이를 해결하기 위한 방법으로 대기 그래프를 사용한다.

• 대기 그래프 - 프로세스와 프로세스 사이의 기다리는 관계만을 나타낸다.
• 감소 그래프 - 대기 그래프에서 끝날 가능성이 있는 방향을 지운다
• ⇒ 그래도 사이클이 존재한다면 교착상태로 볼 수 있다.