[운영체제(OS)] 8-1) 교착상태(Deadlock)란?

---

1. 교착상태(Deadlock)

: 두 개 이상의 프로세스, 스레드가 서로 자원을 얻지 못해 다음 처리를 못하는 상태, 무한히 자원을 기다리는 상태를 말합니다. 

멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황에서, 한 프로세스가 자원을 요청했을 때 그 자원을 동시에 사용할 수 없는 경우 프로세스는 대기 상태에 들어갑니다. 이 대기상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 교착 상태가 발생합니다.

---

System Model 

: System은 유한한 수의 리소스로 구성이 되며, 정상적인 작동 모드에서 프로세스는 다음과 같은 순서로만 리소스를 사용할 수 있습니다.

1) 요청(Request) : 프로레스가 리소스를 요청하고, 얻을 때까지 대기합니다.

2) 사용(Use) : 프로세스가 리소스에 대해 작업을 수행합니다.

3) 방출(Release) : 프로세스가 리소스를 방출합니다.

 

만약 한 프로세스 집합 내에 있는 모든 프로세스가 리소스를 기다린다면 그 프로세스 집합은 교착상태(Deadlock)에 있다고 합니다.

---

2. 교착상태(Deadlock) 특징

: 프로세스들은 실행을 끝낼 수 없고, 시스템 리소스가 묶여있어서 다른 작업을 시작하는 것도 불가능합니다.

 

- Deadlock 발생 조건(4가지 모두 성립해야 발생)

1) 상호 배제(Mutual exclusion) : 최소한 하나의 리소스는 nonsharable mode(한 번에 한 프로세스가 하나의 리소스에 접근 가능)

2) 점유 대기(Hold and wait) : 프로세스는 최소 하나의 자원을 점유한 채 추가 자원(다른 프로세스가 점유중인)을 얻기 위해 대기.

3) 비선점(No preemption) : 자원들을 선점할 수 없음. 자원이 강제적으로 해제(방출)될 수 없고, 점유중인 프로세스가 task를 종료해야함.

4) 순환 대기(Circular wait) : 프로세스 집합에서 순환 형태로 자원을 점유하고 서로 대기하고 있어야 함.

 

- 자원 할당 그래프(Resource-Allocation Graph)

: P는 프로세스, R은 리소스.

즉, P -> R은 요청 간선(Request Edge)이고, R -> P는 할당 간선(Assignment Edge).

자원 할당 그래프에서 사이클이 없다면 어느 프로세스도 교착상태(Deadlock)가 생기지 않습니다.

반면 사이클이 있다면 교착상태가 발생할 수 있지만 100%는 아닙니다. 각 resource type이 여러개의 instance를 가지면 사이클이라고 해서 반드시 교착상태가 발생했을음 의미하지는 않습니다.