Deadlock

교착상태(Deadlock) ( = 무한대기)

다중 프로그래밍 환경에서 두 개의 프로세스가 서로 다른 프로세스가 가지고 있는 자원을 기다리고 있으며 자신이 차지하고 있는 자원을 내놓지 않는 현상으로 이 두 프로세스에게는 영원히 처리기를 줄 수 없게 된다.

가. 교착상태 필수조건

① 상호배제(mutual exclusion) : 어느 자원에 대해 한 프로세스가 이미 사용중이면 다른 프로세스는 기다려야 하는 것
② 점유와 대기(wait for) : 하나 이상의 자원을 할당받은 채로 나머지 자원을 할당 받기 위해 다른 프로세스의 자원이 해제되기를 기다리는 프로세스가 존재하는 경우
③ 비중단(no Preemption) : 자원을 할당받은 프로세스로부터 자원을 강제로 빼앗지 못하는 것
④ 환형대기(circular wait) : 자원 할당 그래프 상에서 프로세스의 환형 사슬이 존재하는 것

나. 자원할당 그래프
G = {E, V} E는 간선의 집합을 V는 프로세스의 집합을 말한다.
P={P1, P2, P3,...,Pn} : 프로세스의 집합
R={R1, R2, R3,...,Rm} : 자원의 집합

기호	뜻
원	프로세스
네모	자원
자원→프로세스	할당
프로세스→자원	요청

다. 교착상태 발견기법

① 자원할당 그래프에서 환형 대기를 나타내는 사이클(cycle)이 있으면 교착상태가 존재할 수 있다. (자원할당 그래프가 사이클을 포함하지 않으면 교착상태는 발생하지 않는다.)
② 사이클이 존재할 경우 그 사이클이 제거 될 수 있는지 검사한다.
(각 프로세스가 요구하는 자원을 모두 할당받았을 경우 제거 가능)
③ 사이클이 제거 될 수 있을 경우는 교착상태가 아니며, 제거 될 수 없을 경우는 교착상태이다.

라. 교착상태 예방 및 해결 방법

① 교착상태 예방(deadlock prevention) = 교착상태 필요조건의 부정

• 상호배제조건의 부정
  자원을 공유할 수 있도록 한다. 자원을 공유할 수 없는 자원인 프린터등은 상호배제조건 부정을 할 수 없다.
• 점유 및 대기조건의 부정
  프로세스가 수행을 하기에 필요한 모든 자원을 한꺼번에 요청하고 할당받는다.
• 비중단조건의 부정
  원래 갖고 있던 자원을 일단 반납하고 필요하다면 다시 그 자원이나 다른 자원을 요구한다.
• 환형대기조건의 부정
  각 자원 유형별로 고유번호를 부여하여 번호가 큰순으로 자원을 요구하도록 한다.

② 교착상태 회피(deadlock avoidance)
교착 상태가 발생할지 하지 않을지의 상태를 사전정보를 가지고 예측하여 안전하다고 판단될 경우 처리하는 방법이다. 이 경우 불안정하다고 판단이 되더라도 교착상태가 발생되지 않을 수도 있다.

• 안정상태(safe state): 전체자원의 상황이 작업을 완료할 수 있는 상태
• 불안전 상태 : 교착상태가 일어날 수 있는 상태.
  

③ 교착상태 발견(deadlock detection)
교착상태가 일어났는지를 자원할당 그래프를 이용하여 알아내는 과정이다.

④ 교착상태 복구(recovery from deadlock)
교착상태를 발견하고 교착상태에 있는 하나 이상의 프로세스들로부터 몇 개의 자원 선점(resource preemption) 시키는 것에 의해 복구 하는 방법으로 조작자에게 교착상태가 발생했음을 알려주어서 직접 수작업으로 처리 하도록 하거나 시스템으로 하여금 교착상태를 자동적으로 복구하도록 하는 방법이 있다.

• 선점 방법
  - 모든 교착상태 프로세스들을 종료하는 것 : 이것은 교착 상태 사이클을 분해시키지만 회복하는데 많은 비용이 소요된다.
  - 프로세스를 하나씩 종료하는 것 : 교착상태 사이클이 제거될 때까지 하나씩 종료하는 방식으로 상당한 오버헤드를 요구한다.
• 선점 프로세스(=희생자) 선택 기준
  회복시 필요한 비용이 가장 적은 것을 선점의 대상(=희상자)으로 선택한다.
• 복귀(rollback)
  프로세스로부터 자원을 선점한다면, 그 프로세스를 어떤 상태로 놓을 것인지를 결정해야한다. 그러나 정상적인 수행을 계속할 수 없을 때에는 그 프로세스를 안전한 상태로 되돌려 놓고, 그 상태로부터 재시작해야 한다.(예: 완전복귀)
• 기아상태(starvation)
  비용 요소에 기초를 두는 시스템에서 희생자 선택은 주로 동일한 프로세스가 매번 선택 될 수 있는데 이 경우 특정 프로세스가 반복해서 희생자로 선택될 경우 그 프로세스는 지정된 작업을 오랫동안 완료하지 못하는 상황이 되며, 이러한 상황을 기아상태라 한다