DeadLock (교착 상태)

DeadLock

일련의 프로세스들이 서로가 가진 자원을 기다리며 block 되어 더 이상 진행이 될 수 없는 상태

deadlock 예시

( * LiveLock : 스레드가 정체된 상태는 아니지만 계속 시도해도 진행이 안되는 경우 )

 

Deadlock Characterization

: deadlock이 일어나기 위한 4가지 필요조건으로, deadlock이 일어난 경우 아래 조건을 모두 만족한다!

 

1. Mutual exclusion (상호 배제)

: 단독으로 사용해야하는(공유가 불가능한) 자원이 적어도 하나 존재

 

2. Hold and wait (점유 대기)

: 어떤 자원을 획득한 상태에서 다른 자원을 기다리는 상태

 

3. No preemption (비선점)

: 본인인 스스로 더 이상 진행되지 않음에도 불구하고 가지고 있던 자원을 놓지 않는 상황

 

4. Circular wait (순환 대기)

: 서로 상대방이 놓기를 기다리는 상황

ex) 프로세스 {p0, p1, ... , pn} 이 있을 때 p0는 p1을, p1은 p2를, ... , pn은 p0을 기다림

 

 

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

프로세스 간의 관계를 그래프로 도식화해 보면 deadlock이 발생할지 예상할 수 있음

• no cycle → no deadlock
• deadlock → cycle
• cycle → may or may not deadlock

resource allocation의 사례이면서 deadlock인 상황

 

• single instance : cycle과 deadlock은 필요충분조건
• multiple instances : cycle은 deadlock이 일어나기위한 필요조건

cycle이 존재하지만 deadlock은 아닌 상황 ( T4가 언제가 종료되면 R2의 resource가 T3에 할당될 수 있음 )

 

Methods for Handling Deadlocks

(deadlock을 아예 처음부터 방지하는 방법)

1. Deadlock prevention

: 필요조건 4개 중 적어도 하나 이상 성립이 안되도록 하는 방식

 

1) Mutual Exclusion

• 공유 자원이 너무 많아서 이 조건을 막는 것은 어려움
• 모든 자원을 다 공유할 수 있도록 공유할 수 없는 자원을 다 없애버려야 함
• But, 하나의 스레드만 들어가야 하는 상황도 많음 ex) mutex-lock

 

2) Hold and Wait

• 시작하기 전에 필요한 자원을 한꺼번에 할당
• 잡고 있는 자원이 없을 때만 자원을 요청
• 조건이 너무 까다로워서 굶주릴 가능성이 많고, 자원 활용도도 떨어짐

 

3) No Preemption

• 자원 할당이 불가능하면 가지고 있는 자원을 다 내 놓음
• 대기 중인 프로세스의 자원을 반납하게 함
• 자원을 다 할당 받을 수 있을 때 프로세스를 다시 시작함
• 구현이 어려움,,

 

4) Circular Wait

• 가장 현실적인 방법
• 모든 resource type 에 고유 번호를 매기고, 스레드는 total ordering에 근거해서 자원 요청

 

2. Deadlock avoidance

: 필요한 자원에 대한 정보를 이용하는 방식

( = deadlock이 일어나는 길이 있으면 안 일어나는 길로 돌아가는 것 !)

 

1) Single Instance

• cycle = deadlock
• claim edge (Pi ---> Rj) : Pi가 앞으로 Rj를 요청할지도 모른다
• assignment edge (Pi → Rj) : 리소스가 프로세스에 할당
• cycle이 생기지 않는 경우에만 요청을 받아줌

 

2) Multiple Instance (Banker’s Algorithm)

: 어떤 스레드에 resource 요청을 허용해도, 그 시스템이 안전한 상태가 된다면 허용하는 알고리즘

( * 안전한 상태 : 시스템에 있는 모든 프로세스가 각자 필요한 자원을 사용할 수 있는 실행 순서가 존재하는 경우 )

• safe state → no deadlocks
• unsafe state → possibility of deadlock (어쩌면 deadlock이 발생할 수도 있음)
  → 시스템이 항상 안전한 상태에 남아 있도록 유지
   = 시스템이 안전한 상태를 유지할 수 있을 때만 자원을 할당
• cylcle != deadlock (판단이 어려우므로, Banker’s Algorithm 사용!)
• 각 프로세스(스레드)가 특정 resource에 대해 최대 몇개를 요청할 것인지에 대한 사전 정보가 필요함

 

* Request <= Need (요청이 need(최대 - 가지고 있는 것) 보다 클 수 x, 처음에 max만큼 필요하다 했던 게 거짓말,,)

* Request <= Available (남아있는 자원보다 더 많은 것 요청하면, 할당 불가)

 

 

 

(deadlock이 일어나면 문제를 해결하는 방법)

3. Detection (Allow) & Recovery

: 일단은 deadlock을 허용하고, 주기적으로 검사해서 deadlock이 일어났으면 문제를 해결하는 방식

 

* 현실적으로 모든 프로세스가 자신이 resource를 얼만큼 사용할지 알기 어려움

 = Deadlock Avoidance 구현 어려움 .. !

 → detection해서 deadlock이 발견되면 그 때 해결 !

 

1) Single Instance

: wait-for graph를 주기적으로 검사해서 cycle이 존재하면 deadlock이 있는 것 !

( * wait-for graph : Resource-allocation graph에서 resource를 뺀 것 )

 

2) Multiple Instance

• Banker’s Algoritim과 매우 유사
• Max가 없는 대신(사전 정보 필요 x) 현재 Request를 Need로 간주하고 Banker’s 알고리즘을 실행
• unsafe state이면 deadlock으로 판정
• 더 이상 자원이 필요하지 않을 것이라는 낙관적 가정을 전제함

 

4. Recovery (Ignore)

• deadlock을 무시하는 방식 (일어나면 사용자가 해결)
• 관리모드로가서 deadlock이 걸린 프로세스를 abort 시켜야 함
• 모든 프로세스 abort or 하나씩 abort (Deadlock = circular waiting → 하나만 풀려도 잘 풀리는 경우 많음)
• 하나씩 abort 하는 경우, 어떤 순서로 abort 시킬지! ex) 우선순위, 지속 시간, 필요한 자원 수 등등