Deadlocks

What is Deadlock?

deadlock 이란, 두 개 이상의 프로세스들이 서로가 원인이 되어 서로를 무한히 대기하는 현상을 의미한다.

  P[0]					P[1]
wait(S);              wait(Q);
wait(Q);              wait(S);
...                   ...
signal(S);            signal(Q);
signal(Q);            signal(S);

위의 코드에서는 P0와 P1이 각각 S와 Q를 가져간 이후에 서로를 기다리면서 고착 상태에 빠지게 된다.

P[0]는 S를 가져가고, P[1]은 Q를 가져간 상태에서 서로의 Q와 S를 기다리는 구조이다.

이전 포스트에서도 설명했듯이 Dining Philospher 문제에서 철학자가 모두 하나씩의 젓가락을 먼저 집는다면 (일관된 방향으로), deadlock이 발생하게 된다.

OS에서는 deadlock을 예방하는 기능들을 제공하지 않으며 deadlock을 예방하고 deadlock이 없는 프로그램을 개발하는 것은 순전히 개발자의 몫이다.

Necessary Conditions

: deadlock은 다음의 4가지 조건을 모두 만족해야 발생한다.

System Model
1. Resource (CPU cycles, Files, I/O Devices)
2. Instance (해당 resource의 개수)

1. Mutual Exclusion

: 하나의 쓰레드는 오직 하나의 리소스만 이용할 수 있다.

2. Hold and Wait

: 하나의 쓰레드가 하나의 리소스를 홀딩(사용)하면서 동시에 하나의 리소스를 기다리고 있어야 한다.

3. No Preemption

: 리소스는 사용이 다 끝난 쓰레드에 의해서만 릴리즈될 수 있다.
(리소스의 양보가 불가능하다.)

4. Circular Wait

: 서로가 서로의 리소스를 기다리고 있어야 한다. (cycle 형성)

Resource Allocation Graph

• Resources
  R1, R2, R3 and R4

• Intances
  One instance of R1
  Two instances of R2
  One intance of R3
  Three instances of R4

• Threads

1. T1이 R2의 리소스를 하나 홀드하고 있고, 동시에 R1 리소스를 기다리고 있다.
2. T2가 R1과 R2의 리소스를 하나씩 홀드하고 있고, R3의 리소스를 기다리고 있다.
3. T3가 R3의 리소스를 하나 홀드하고 있다.

1. 만약 그래프가 cycle을 포함하고 있지 않다면 deadlock은 발생하지 않는다.

2. cycle이 존재하지만 리소스의 인스턴스가 여러개 존재한다면 deadlock이 발생할 수도 있고 그렇지 않을 수도 있다.

3. cycle 존재하면서 리소스의 인스턴스가 하나라면 deadlock이 발생한다.

오른쪽의 그림에서는 T2가 R1 사용이 끝난 시점에서 T1이 R1을 할당 받을 수 있기 때문에 deadlock은 발생하지 않는다.

Deadlock Prevention

deadlock의 4가지 필수 조건 중 한가지를 무력화함으로써 deadlock 발생을 예방한다.

• Mutual Exclusion
  : 데이터의 수정이 없다면 리소스를 여러 개의 쓰레드가 접근할 수 있도록 한다.

• Hold and Wait
  : 리소스를 사용하는 동안은 다른 리소스를 기다릴 수 없도록 한다.
  -> low resource utilization, starcation (not good!)

• No Preemption
  : 리소스를 양보할 수 있도록 한다.

일반적으로 위의 방법들을 deadlock prevention의 방법으로 사용하지는 않는다.

Circular Wait

: 일반적으로 cirular wait을 무력화시킨 방법을 많이 사용한다!

간단한 방법으로는 가져가는 리소스의 순서를 정하는 것이다.
ex) R1 > R2 > R3

해당 방법을 사용하기 위해서는 개발자가 리소스를 가져가는 순서를 무조건 지켜야한다.

Deadlock Avoidance

: deadlock prevention의 방법으로는 request의 순서를 제한해야 하기 때문에 device utilization과 system througput이 낮아지게 된다.

따라서 deadlock avoidance에서는 추가적인 정보를 이용하여 deadlcock 발생을 회피한다.

resource allocation graph의 현재 상태, 앞으로의 상황 등을 활용

간단하고 가장 효과적인 모델로는 요청할 수 있는 리소스의 maximum number 를 미리 선언하는 것이다.

현재 이용 가능한 리소스들과 최대 요청 가능한 리소스의 숫자를 이용해 resource - allocation state를 계산한다.

Safe State

deadlock이 발생할 가능성이 전혀 없는 상태를 safe state로 정의하고, deadlock 발생 가능성이 있다면 unsafe state로 정의한다.

따라서 쓰레드가 이용 가능한 자원을 요청할 경우, 할당했을 때 safe state가 유지되는지 검토해야 한다. (Immediate)

시스템의 모든 스레드에 대해서 <T1, T2, ... Tn>, 스레드에 특정한 순서가 존재하여 다음 조건을 만족하면 시스템은 안전한 상태에 있다고 판단한다.

각 스레드 Ti에 대해, Ti가 추가로 요청할 수 있는 자원을 현재 사용 가능한 자원과 그 이전 스레드들(Tj, j < i)이 가지고 있는 자원을 사용해서 충족할 수 있어야 한다.

좀 더 자세히 설명하자면,

• 현재 사용 가능한 자원
  : 현재 시스템에서 사용하지 않고 남아있는 자원

• 각 스레드 Ti가 추가로 요청할 수 있는 자원
  : 스레드 Ti가 앞으로 요청할 수 있는 자원의 최대량

• 이전 스레드들이 가지고 있는 자원
  : 현재 스레드 Ti보다 앞서 있는 스레드들(Tj, j < i)이 점유하고 있는 자원.

따라서, 시스템이 안전한 상태라면, 순서 <T1,T2, ... Tn>에 대해 다음 조건이 성립해야 한다.

• 스레드 T1이 앞으로 요청할 수 있는 자원은 현재 사용 가능한 자원으로 충족되어야 한다.

• 스레드 T1이 종료되어 자원을 반환하면, T2가 앞으로 요청할 수 있는 자원이 현재 사용 가능한 자원과 T1이 반환한 자원으로 충족될 수 있어야 한다.

• 마찬가지로, T2가 종료되어 자원을 반환하면, T3가 앞으로 요청할 수 있는 자원이 현재 사용 가능한 자원과 T1과 T2가 반환한 자원으로 충족될 수 있어야 한다.

• 이 과정을 모든 스레드에 대해 반복하면, 마지막 스레드 Tn까지 모든 스레드가 요청할 수 있는 자원을 충족할 수 있는 순서가 존재하게 된다.

위의 예제에서는 현재 3개의 사용 가능한 리소스가 있는 상태이다. 그리고 T0, T1, T2의 future needs resource 개수는 각각 5개, 2개, 7개이다. 따라서 2개를 T1에게 할당해 T1의 작업을 끝내고 리소스를 모두 회수하면 사용 가능한 리소스는 총 5개가 된다. 5개의 리소스로 T0의 작업을 끝내고 리소스를 회수하여 T2에게 리소스를 할당할 수 있다.

Resource Allocation Graph

Claim edge

: Claim edge란 스레드가 리소스를 request 할 수도 있는 경우를 점선으로 표시한 것이다. resource allocation graph를 이용해 deadlock avoidance를 하려는 경우 claim edge를 넣어보면서 데드락이 일어날 수 있는지 아닌지를 판단하게 된다. (cycle이 생기는지?)

Edge Conversion

• Claim edge
  : 미래에 해당 자원을 요청할 수도 있는 상태

• Claim to Request
  : 실제로 스레드가 자원을 요청한 상태

• Request to Assignment
  : 스레드가 요청한 자원을 할당받은 상태

• Assignment to Claim
  : 스레드가 자원을 다 사용한 후 릴리즈한 상태

Wait-for Graph

wait-for 그래프는 resource allocation graph에서 스레드 간의 대기 상태만을 표현할 수 있도록 압축한 그래프이다. 위의 그림에서는 T1 ~ T4가 서로를 기다리면서 deadlock이 발생한 상태를 나타낸다.

wait-for graph는 각각의 리소스가 single instance일 때 유효하다.

Recovery from Deadlock

Process Termination

• Abort all deadlocked threads

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

어떤 스레드를 종료시킬 것인지?
Selecting a victim - minimize cost
Rollback - return to some safe state, restart the thread for that state
Starvation - same thread may always be picked as victim