Deadlock

Deadlock이란?

set of blocked processes

- each holding a resource 

- waiting to acquire a resource held by another process in the set

Process 0:                Process 1:

  wait(A);                   wait(B);

  wait(B);                   wait(A);

한 시스템은 2개의 disk drive Process 0,1을 가졌고 각각은 하나의 디스크를 hold 하면서 다른 것을 필요로 한다

따라서 둘 다 자원을 이용할 수 없는 상태

System Model

- 시스템은 경쟁하는 Process들 사이에 분배되어야 할 유한한 수의 Resource자원(다수의 유형)들로 구성되어 있으며 각각의 유형들은 동등한 다수의 instance로 구성되어 있다.

  Each resource type Ri has Wi instances

- Resource types - R1, R2... : CPU cycles, memory space, I/O devices...

한 시스템이 두 개의 CPU를 가지면 resource type CPU는 두 개의 instance를 가진다

- Each process utilizes a resource as follows:

* Request 요청하는 프로세스는 자원을 획득할때까지 기다려야 하며 획득되지 않으면 할당하지 않는다

* Use 요청이 받아들여지면 자원을 사용한다

* Release 사용이 끝나면 자원을 반납한다

 사용 전 반드시 요청, 사용 후 반드시 방출(반납)해야 하며 Task수행을 위해 필요한 만큼의 자원을 요청한다

Deadlock Conditions발생조건

- 아래 4가지 조건을 다 만족하면 Deadlock이 발생할 수 있다(무조건 일어나는 것이 아님! 가능성이 있는 것)

1 Mutual Exclusion

Only one process at a time can use a resource

자원은 여러 프로세스들이 동시에 사용할 수 없다 (1프로세스 1타임)

2 Hold and Wait

A process holding at lease one resource is waiting to acquire additional resources held by another processes

자신이 하나의 자원을 가지고 있으면서 blocked process의 자원을 기다리고 있다

3 No Preemption

A resource can be released only voluntarily by the process holding it, after that process has completed its task

자원은 자원을 가지고 있던 프로세스에 의해, 프로세스의 작업이 끝났을 때 자발적으로만 반납될 수 있다

4 Circular Wait

set {p0, p1...pn}이 있을 때 p0은 p1이 가진 자원을 기다리고 있고, p1는 p2가 가진 자원을 기다리고 있고...... pn은 p0이 가진 자원을 기다리고 있는, hold and wait조건으로 cycle이 생겼을 때

- Resource-Allocation Graph

* set of vertices V and set of edges E

V는 두 가지 타입으로 나뉜다

P={P0, P1...} : set consisting of all the processes in the system

R={R0, R1...} : set consisting of all resource types in the system

Request edge : Pi에서 Ri로의 다이렉트 엣지 (->)

Assignment edge : Ri에서 Pi로의 다이렉트 엣지(->)

* P1이 R1의 자원을 요청하는 다이렉트 엣지를 볼 수 있다. 

* 각각의 R안에는 W라는 instance가 있다

* R2안에 있는 점이 P2를 가리키는 것은 R2의 자원 하나가 P2에 할당되었다는 것을 의미한다

1 똑같은 자원이 다른 프로세스에 할당되지 않는다

2 P1, P2을 보면 P1은 P2가 사용중인 자원을 기다리고 있다

3 이 그림에서 알 수 없다

4 X 사이클이 발생하지 않는다

= deadlock이 발생하지 않는다

1 한 자원을 여러 프로세스가 사용하지 않는다

2 P1은P2가 사용중인 자원이 반납되길 기다리고 있고, P2는 P3이 사용중인 자원이 반납되길 기다리고 있다. 또한 P3은 P1, P2가 사용중인 자원이 반납되길 기다리고 있다

3 그림으로 알 수 없다

4 P1->R1->P2->R3->P3->R2->P2,P1 로 사이클이 발생한다

= 3이 참이라고 가정하면 이러한 그래프에서는 deadlock이 발생할 수 있다

1 한 자원을 여러 프로세스가 사용하고 있지 않다

2 P1은 P2가 사용중인 자원을 요청하고 있고, P3은 P1이 사용중인 자원을 요청하고 있다

3 그림으로 알 수 없다

4 P1->R1->P3->R2->P1로 사이클이 형성되지만 ..!!!

P2와 P4를 보면 자원의 instance가 여러개일 때 Cycle을 하지 않는 상태에서 자원을 반납할 수 있다 =>breaking the cycle

* 만약 Resource Allocation graph가 cycle이 없다면 system은 deadlocked state가 아님

*                                                        있다면 only one instance per resource type->deadlock

                                                                   several instances per resource type-> possibility of deadlock

(조건을 다 만족해야 데드락 가능성이 생기는건데 왜 사이클+1인스턴스면 데드락이다, 라고 하는건지는 잘 모르겠다..)

- Methods of Handling Deadlocks

* Ensure that the system will never enter a deadlock state : deadlock prevention & deadlock avoidance

  시스템이 데드락에 빠지지 않게 한다

* Allow the system to enter a deadlock state and then recover

  시스템이 데드락에 빠지게 한 뒤 복구한다

* Ignore the problem and pretend deadlocks never occur in the system (Used by most OS including Unix)

  문제를 무시하고 데드락이 일어나지 않은 것처럼 행동(대부분의 운영체제에서 이용. 만약 데드락에 빠진다면 이는 사용자가 발생시킨 것!)

Deadlock Prevention

- By ensuring that at least one of the conditions cannot hold, the occurrence of a deadlock can be prevented 적어도 하나의 조건이 만족되지 않게 하여 데드락 발생 가능성이 예방됨

1 Mutual exclusion

* Not required for shared resources; must hold for nonsharable resources

* We cannot prevent deadlocks by denying the mutual exclusion condition because some resources are intrinsically nonsharable.

  공유될 수 없는 자원만을 요청하는 것인데, 본질적으로 어떤 자원들은 본질적으로 공유될 수 없으므로 이 조건을 불만족시키는 것만으로는 deadlock을 예방할 수 없다(사실 무슨 소린지 잘 모르겠다)

2 Hold and Wait

* Must guarantee that whenever a process requests a resource, it does not hold any other resources

* Require processes to request and be allocated all of its resources before it begins execution, or allow process to request resource only when the process has none

  프로세스가 자원을 요청할 때, 그 프로세스는 다른 어떤 자원도 갖고 있지 않다 = 프로세스는 실행하기 전 필요한 모든 자원들을 요청, 할당받은 상태여야 하거나, 프로세스가 자원이 전혀 없을 때 다른 자원을 요청할 수 있도록 한다

* Low resource utilization + starvation possible

  자원 사용율이 낮거나, 자주 쓰이는 자원을 여러개 필요로 하는 프로세스는 필요한 자원 중 최소 하나가 항상 다른 프로세스에게 할당되어 있으므로 무한정 대기해야 할 수도 있다

3 No Preemption

* If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released

* Process will be started only when it can regain its old resources as well as the new ones that it is requesting

  프로세스가 자원을 점유중이고 당장 할당될 수 없는 다른 자원들을 요청할 때, 현재 점유중이었던 자원들을 모두 반납한다. 프로세스는 점유중이었던 자원과 요청했었던 다른 자원들을 다시 얻었을 때 실행될 수 있다

4 Circular Wait

* Impose a total ordering of all resource types and require that each process requests resources in an increasing order of enumeration

* The process can request instances of resource type Rj if and only if F(Rj)>F(Ri) given that Ri the type of the instances that the process is currently holding

  자원에 order가 있다. 가진 것보다 높은 자원을 요구 할 수 있다

- 문제점: 장치 이용율 저하 + 시스템 처리율 throughput 감소

Deadlock Avoidance

- Requires that the system has some additional a priori information available 앞으로의 정보에 대해

* Resource currently available 현재 사용 가능 자원

* Resources currently allocated to each process 현재 사용 자원

* future requests and releases of each process 요청될/반납될 자원

- simplest and most useful model requires that each process declares the maximum number of each type that it may need

- Deadlock Avoidance algorithm dynamically examines the resource allocation state to ensure that there can never be a circular-wait condition

* resource allocation state is defined by the number of available and allocated resources, and the maximum demands of the process

- Safe State

* When a process requests an available resource, the system must decide if immediate allocation leaves the system in a safe state

* A system is in a safe state if there exists a sequence of all processes in the system such that for each process Pi the resources that Pi can still request can be satisfied by currently available resources+resources held by all the Pj with j<i

* System in a safe state-> no deadlock

                  unsafe    -> possibility of deadlock

  Deadlock avoidance -> ensure that a system will never enter an unsafe state

- Deadlock avoidance algorithms : http://woodforest.tistory.com/8

Deadlock Detection

- Allows systems to enter the deadlock state

- Deadlock detection algorithms : http://woodforest.tistory.com/9

- Recovery scheme (Process termination)

* Abort all deadlocked processes

* Abort one process at a time until the deadlock cycle is eliminated