교착상태(Deadlock)

1. 교착상태를 설명하기 위한 시스템 개념(모델)
- 시스템은 제한된 개수의 자원으로 구성
- 프로세스는 자원을 경쟁적으로 사용

2. 정상상태에서의 프로세스 자원 사용 순서
(1) 요구
(2) 사용
(3) 해제(반납)

3. 교착상태가 존재하기 위한 4가지 조건
(1971년  E. G. Coffman의 논문에 최초 언급되어서 Coffman조건이라고도 알려져 있음)
(1) 상호배제조건(mutual exclusion)
  한 프로세스가 자원을 사용하고 있을 때, 다른 프로세스는 기다려야 함
(2) 대기조건(wait for)
  프로세스가 다른 자원을 기다리면서, 이미 자신에게 할당된 자원은 해제하지 않고 점유하고 있음
(3) 비중단조건(no preemption)
  자원 사용이 끝나기 전에 중도에 비자발적으로 해제될 수 없음
(4) 환형대기조건(circular wait)
  프로세스간 환형 사슬이 존재하여 각 프로세스는 다음 프로세스가 요구하는 자원을 가지고 있음

4. 교착상태 기술(Description)
시스템자원할당그래프(방향성 그래프)를 사용하여 기술함
G=(V, E)
V:꼭지점의 집합은 아래의 두 집합으로 구성됨
  - 프로세스의 집합 P={p1, p2, p3,,,pn}  (원으로 나타냄)
  - 자원의 집합 R={r1, r2, r3,,,rm} (사각형 내의 점으로 나타냄)
E:간선의 집합은 아래와 같은 두 가지의 순서쌍이 가능함
  - (pi, rj) : pi로부터 rj로 유향간선(directed edge)이 존재. pi가 rj를 요청하여 대기중인 상태.
                  요구간선(request edge)이라고 함.
  - (rj, pi) : rj로부터 pi로 유향간선(directed edge)이 존재. rj가 pi에 할당된 상태.
                  할당간선(assignment edge)이라고 함.
자원할당그래프에서 사이클이 존재하는 것이 교착상태의 충분조건은 아님.
사이클이 존재하지 않으면 교착상태는 존재하지 않음.
(각 유형의 자원이 여러 단위자원을 가지면 교착상태가 발생하지 않음)

5. 교착상태에 관한 연구대상
Coffman조건 4가지를 모두 만족해야만 교착상태이므로, 위의 4가지 조건 중 어느 한가지가 성립하지 않는 상황을 만들거나, 그런 상황이 되도록 조정함으로써 교착상태를 방지할 수 있게 된다.
(1) 교착상태 방지
(2) 교착상태 회피
(3) 교착상태 발견
(4) 교착상태 회복

참고문헌
1. ISBN89-20-90347-6
2. ISBN89-20-34416-7
3. wikipedia::Deadlock
  http://en.wikipedia.org/wiki/Deadlock