Deadlock

대기 중인 프로세스들이 요청한 자원들이 다른 프로세스들에 의해서 점유되어 있고 그들도 모두 대기 상태에 있는 상태.

교착상태가 되기 위한 조건들은 네 가지가 있다.

 1) 상호 배제(mutual exclusion) : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 프로세스만이 그 자원을 사용할 수 있다.

 2) 점유하며 대기(hold-and-wait) : 프로세스는 최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.

 3) 비선점(no preemption) : 자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후 그 프로세스에 의해 자발적으로 방출될 수 있다.

 4) 순환 대기(circular wait) : 대기하고 있는 프로세스의 집합들이 원형으로 자원을 대기한다. P1은 P2가 점유한 자원을 대기하고, P2는 P3를, Pn은 P0가 점유한 자원을 대기한다.

Deadlock Prevention

Deadlock prevention algorithms ensure that at least one of the necessary conditions (Mutual exclusion, hold and wait, no preemption and circular wait) does not hold true.

1. Mutual Exclusion : Not always possible to prevent deadlock by preventing mutual exclusion (making all resources shareable) as certain resources are cannot be shared safely.

2. Hold and Wait : A resource can get all required resources before it start execution. This will avoid deadlock, but will result in reduced throughputs as resources are held by process even when they are not needed. They could have been used by other process during this time.

3. No preemption : If a process request for a resource which is held by another waiting resource, then the resource may be preempted from the other waiting resource.

4. Circular wait : To avoid circular wait, resources may be ordered and we can ensure that each process can request resources only in an increasing order of these numbers.