[8-1] Deadlocks - 1

[ Deadlocks ]

 

 

[ deadlock ]

2개 이상의 쓰레드(or 프로세스)가 서로 리소스를 획득하지 못하고 무한히 서로를 기다리고 있는 상태.

대기 중인 스레드는 요청했던 리소스가 다른 대기중인 쓰레드에 의해 점유되어 있기 때문에 결코 다시 빠져나올 수 없게 됨.

 

하나의 쓰레드는 resource를 다음과 같이 활용한다.

(Request → Use → Release)

 

Figure 8.1 Deadlock example

 

얼핏보면 이상하지 않게 보이지만,

thread_one이 first_mutex를 잡고, thread_two가 second_mutex를 잡은 상태라고 가정해보자.

그 다음, thread_one이 second_mutex를, thread_two가 first_mutex를 서로 잡을려고 시도하는 순간, 양측 쓰레드가 이미 잡고있는 lock을 추가로 잡아야 진입할 수 있기 때문에 deadlock이 걸리게 된다.

 

[ Four Necessary Conditions ]

1) Mutual Exclusion

At least one resource is held in a non-sharable mode.

여러 스레드가 read만 하고 있는 경우는 발생하지 않고, write가 끼어 들어서 non-sharable해야 mutual-exclusion, 즉 락을 잡아야하는 상태가 되어야 발생할 수 있다.

→ 가장 기본 조건

 

2) Hold and Wait

A theard holds at least one resource and waiting to acquire additional resources held by other threads.

한 쓰레드가 이미 "1개이상"의 리소스를 잡은 상태에서 다른 쓰레드가 잡고있는 추가적인 리소스를 획득할려고 할 때 발생할 수 있다.

 

3) No preemption

Resources cannot be preempted.

리소스가 선점 불가능 할 때만 발생가능.

 

4) Circular Wait

A set of waiting threads exist such that the dependency graph of waiting is circular.

대기하는 쓰레드들의 한 집합이, 대기하고있는 dependency graph의 형태를 봤을 때 순환하는 형태로 존재해야 발생할 수 있다.

 

[ Resource-Allocation Graph ]

Figure 8.3 : Figure 8.1의 graph 형태

Figure 8.1의 상황을 그래프로 나타낸다면, 물고 물리는 하나의 cycle이 생기는 것을 볼 수 있다.

 

 

또 다른 예제 Figure 8.4는 cycle이 없기 때문에 데드락이 구조적으로 발생할 수 없다.

8.5는 cycle이 있어 T1, T2, T3는 deadlock이 발생할 수 있다.

 

8.6은 cycle이 있으나 deadlock이 발생하지 않는다.

R1, R2는 2개의 인스턴스를 지니고 있는데다가, T4가 리소스를 반납한다면 T3는 리소스를 획득할 수 있기 때문이다.

 

[ An important observation ]

Resource-allocation graph가 cycle을 형성하지 않는다면, 데드락이 절대 발생할 수 없다는 사실을 알 수 있다.

반면에, cycle을 형성한다면 데드락이 발생할 가능성이 생기는 것이다.

 

 

[ Three was of dealing with the Deadlock Problem ]

1) Ignore the problem altogether

발생할 때까지 그냥 무시하기

 

2) Use a protocal to prevent or avoid deadlocks

발생하지 못하게 프로그램을 작성해서 예방하기

→ prevent는 매우 힘들고 비용이 비싸지만, avoid는 비싸더라도 적용할만 하다.

(prevention : $8.5, avoidance : $8.6, Banker's Alogrithm)

 

3) Allow the system to enter a deadlocked state,

then detect it, and recover it.

데드락이 발생할 수는 있는 구조지만, 발생했을 때 빠르게 발견해서 고치는 방법

(Deadlock Detection : $8.7, Recovery from Deadlock : $8.8)

 

[ Deadlock Prevention ]

4가지 조건 중 적어도 1개의 조건이 발생하지 못하게 막아보자.

 

1) Mutual Exclusion

→ 이 조건은 본질적으로 해결 불가능.

 

2) Hold and Wait

쓰레드가 리소스를 요청할 때, 기존에 잡고 있던 다른 리소스들을 놓은 후에 요청하려는 리소스를 잡게 한다.

→ 가능하지만, 실용적이지 못함.

 

3) No preemption

쓰레드가 리소스를 요청할 때, 해당 리소스를 다른 쓰레드가 잡고 사용 중이어도 강제로 뺏고 할당시켜 해보자.

→ 일반적인 프로그램에는 적용할 수 없음.

 

4) Circular Wait

때때로 실용적이다.

리소스들에 전부 순서를 부여해서, 각 쓰레드가 리소스를 요청할 때 증가하는 순서(increasing order of enumeration)로 요청하도록 해보자.

→ circular-wait condition이 발생하지 않는다는 것이 보장된다.

 

 

하지만, 만약 락이 동적으로 획득된다면 lock ordering 방식 또한 deadlock prevention을 보장할 수는 없다.

 

위 transaction 함수가 있을 때, 다음 함수처럼 상호간에 같이 호출하는 경우 발생할 수 있다.

 

 

 

Deadlock Prevention은 굉장히 힘들고 비싸지만, Avoidance는 실용적이다. (다음 챕터)