[OS] 운영체제 Deadlock

교착상태인 Deadlock에 대해서 알아보자.

교착상태

그림과 같이 차가 도로에서 너무 막혀서 가고 싶은 곳으로 갈수가 없다. (어떠한 차도)
프로세스 관점에서 본다면 차가 프로세스이고 가고싶은 도로가 자원이면 프로세스들이 자원을 할당받지못해 작업을 수행하지 못하는 상태를 의미한다.

이것이 교착상태, deadlock이다.

교착상태 개념

• 프로세스 상태전이도에서 blocked/asleep상태의 프로세스는 프로세서를 할당받아 작업을 수행중 어떠한 자원이 또필요하여, (혹은 이벤트가 필요하여) 프로세서를 반납하고 자원을 대기하는(이벤트를 대기하는) 상태의 프로세스인데 이 때 영영, 영원히 자원을 받을 가능성이 없는 프로세스를 교착상태에 빠졌다 한다.
• 교착상태에 빠진 프로세스가 있는 시스템을 시스템이 deadlock상태에 있다고 한다.

starvation vs deadlock

그럼 기아현상과 비슷한데?
아니다. 기아현상은 운이 없어서 계속 자원을 할당받지 못해 우선순위가 뒤로 밀리는 프로세스의 상태를 의미한다.
그러나 deadlock은 영원히 자원을 할당 받을 가능성이 없는 프로세스이다.

프로세스 상태전이도 관점에서도 차이가있다.
기아상태의 프로세스는 ready상태의 프로세스이고 교착상태의 프로세스는 asleep/blocked상태의 프로세스이다.

할당받기를 기다리는 자원의 종류에도 차이가 있다.
기아상태의 프로세스는 프로세서(cpu)를 할당받기를 기다리는 프로세스이고 (그러나 운이없어서 할당을 계속 못받고있는...) 교착상태의 프로세스는 프로세서 이외의 자원을 할당받기를 기다리는 프로세스(그러나 받을 가능성이 전혀 없는 ...)이다.

(기아상태의 프로세스와 교착상태의 프로세스의 차이 in 프로세스 상태전이도)

교착상태는 기아현상과 마찬가지로 자원과 밀접한 관련이있다.(자원을 할당받지 못하므로...) 어떤 자원은 교착상태에 빠트릴수있고, 어떤 자원은 교착상태에 빠트릴 가능성이 없다.

자원의 분류

• 일반적인 분류
  hardware resource vs software resource
• 교착상태와 관련된 분류
  선점 가능여부에 따른 분류
  할당 단위에 따른 분류
  동시 사용 가능 여부에 따른 분류
  재사용 가능 여부에 따른 분류

선점 가능 여부에 따른 자원의 분류

• Preemptible resource
  선점을 당한 후 돌아와도 문제가 발생하지 않는 자원 ex)프로세서(context switching), 메모리
• Non-preemptible resource
  선점을 당하면 이후 진행에 문제가 발생하는 자원 ex)disk

할당 단위에 따른 자원의 분류

• Total allocation resource
  자원 전체를 프로세스에게 할당 ex)프로세서(하나의 core)
• Partitioned allocation resource
  하나의 자원을 여러개로 분할하여 여러 프로세스에게 할당 ex)메모리

동시 사용 가능 여부에 따른 자원의 분류

• Exclusive allocation resource
  한번에 한 프로세스만 사용이 가능한 자원 ex)프로세서(one core, if it's not multicore), disk
• Shared allocation resource
  여러 프로세스가 동시에 사용 가능한 자원 ex)한글파일, shared data(여러 프로세스가 동시에 읽을 경우)

재사용 가능 여부에 따른 자원의 분류

• SR(Serially-reusable Resources)
  시스템 내에 항사존재하는 자원, 한 프로세스가 사용한뒤 다른 프로세스가 사용 가능한 자원 (재활용 가능한 자원) ex)프로세서, 메모리
• CR(Consumable Resources)
  한 프로세스가 사용후 사라지는 자원(재활용 불가능한 자원) ex)signal, message

Deadlock을 일으킬 가능성이 있는 자원들

1. Non-preemptibleresource : 해당 자원을 기다리는 프로세스가 있을 경우 해당 자원을 먼저 사용한 프로세스가 있으면 기다리는 프로세스는 deadlock 상태가 됨
2. Exclusive allocation resource : 한번에 한 프로세스가 자원을 할당받아 사용하는 경우 프로세스가 할당받으려 하면 deadlock상태의 가능성이 있음
3. SR, CR : 두개다 한번에 하나의 프로세스만 사용이 가능한 자원이므로 Exclusive와 같은 이유로 deadlock을 일으킬 가능성이 존재함.

Deadlock Model

Graph Model

데드락상태의 프로세스와 자원을 그래프로 표현한 것

p1 프로세스는 R2자원을 할당받은 상태에서 R1자원을 요청하고있고
p2 프로세스는 R1자원을 할당받은 상태에서 R2자원을 요청하고있다.

두 프로세스는 영원히 자원을 할당받지 못하는 상태인 deadlock상태가 되었다.

State Transition Model

데드락 상태의 프로세스 자원을 상태로 표현한것

두 프로세스가 자원을 할당받았냐 요청하냐에 따라서 상태를 구분한것이다.
deadlock은 각자 자원을 할당받았으나 상대방의 자원을 요청하는 상태에서 발생한다.

Deadlock 발생 필요 조건

1. Exclusive use of resources(자원의 특성)
   한 프로세스만 사용가능한자원
2. Non-preemptible resources(자원의 특성)
   선점을 한번 당하면 자원에 변경이 생기는 자원
3. Hold and wait(프로세스의 특성)
   자원을 하나 hold하고 다른 자원을 요청
4. Circular wait(프로세스의 특성)
   deadlock 그래프 모델과 같은 circular wait상태

위 네개의 필요조건을 모두 충족ㅎ애ㅑ deadlock이 발생된다.

Deadlock Prevention(데드락 예방)

그렇다면 저 네개의 필요조건중 하나를 해결해주면 데드락을 예방할수 있겠네?

그렇다. 필요조건중 하나만 해결하더라도 데드락은 발생하지 않는다.
하나씩 조건을 없애서 데드락을 예방해보자.

모든자원에 대한 공유를 허용하자.

Exclusive use of resources 조건을 없애기 위해 모든 자원에 대한 공유를 허용하면 데드락을 예방할수있다. 그러나 이건 비현실적이다. 프로세서 하나의 코어를 여러 프로세스가 동시에 접근하도록 만드는 것은 현실적으로 불가능하다.

모든자원에 대해 선점을 허용하자.

Non-preemptible resources조건을 없애는 것인데, 선점을 허용하도록 하기 위해서는 선점 불가능한 자원을 요청한 경우 다시 처음부터 모두 작업을 시작하게 하여 비선점 조건을 없앨수 있다. 그러나 이것은 심각한 자원 낭비를 초래한다.

필요자원을 한번에 모두 할당하자.

Hold and wait조건을 없애기 위한 것으로 처음에 필요한 자원을 모두 할당받아서 작업이 끝날때까지 자원을 들고있는 것이다. 그렇다면 자원을 hold한 상태로 기다리지 않으므로 조건을 없애 데드락을 예방할수 있다. 그러나 이것또한 심각한 자원낭비를 초래한다. 필요자원을 모두 할당받은 프로세스가 작업이 모두 끝나기 까지 나머지 프로세스들은 계속해서 기다려야 하기 때문에 무한 대기 현상이 발생할수있다.

Circular wait 조건 제거

자원들에 순서를 부여하여 프로세스는 자원을 순서가 증가하는 순서대로만 요청할수 있도록 하면 된다. 이러면 Circular wait자체가 발생하지 않으므로 조건을 없앨수 있다. 그러나 이것 또한 심각한 자원 낭비를 초래한다. 한 프로세스가 다른 프로세스가 선행해서 요청해야할 프로세스를 할당받아 작업중이면 다른 프로세스들은 순서가 큰 자원을 할당받지 못하고 계속 기다리고 있다.

데드락 예방 결론

• 데드락이 발생할수 있는 조건 하나를 없애서 데드락을 해결하자는 것은 좋은 생각이지만 비현실적이기도하며, 심각한 자원낭비를 초래한다. 데드락 발생 필요조건을 없애는 데드락 예방은 데드락에 대한 좋은 해결책이 아니다.

Deadlock Avoidance(데드락 회피)

데드락 예방을 통해서도 데드락 해결이 not practical, 현실적이지 않으므로 좋은 해결방법이 아니었다.
이번엔 시스템 상태를 감시하다가 데드락이 발생할 가능성이 있으면 프로세스의 자원 할당요청을 보류하는 데드락 회피를 이용해보자.
데드락 회피를 통해서 시스템을 safe state로 유지할수있다.

safe state

safe sequence가 존재하는 상태이다.

safe sequence는 데드락이 발생하지 않음을 보장하는 프로세스에게 자원을 할당하는 순서를 의미한다.

unsafe state

safe sequence가 존재하지 않는 상태이다.
unsafe state는 데드락이 무조건 발생하는 것이아니다. 자원을 요청하는 프로세스가 갑자기 자원을 요청하지 않을 수도있고 하므로, 데드락이 발생할 가능성이 존재한다는 것이다.

데드락 회피의 가정 (not practical한 원인이다.)

• 프로세스와 자원의 수가 고정되어야 한다.
• 프로세스가 요구하는 자원의 최대 수를 알고 있어야한다.
• 자원을 할당받은뒤 반납을 해야한다.(이건 당연한 거임)

데드락 회피 알고리즘

시스템을 항상 safe state로 유지하게 도와주는 알고리즘

1. Dijkstra Banker's 알고리즘
   데드락 회피를 위한 간단한 이론적 기법이다.
   자원의 종류는 하나라는 가정이 필요하다.

자원의 종류가 단 하나라는 가정하에, 현재 프로세스에게 할당가능한 자원의 수에 대하여 프로세스에게 자원을 적절하게 할당할수 있는 하나의 safe sequence가 존재하는걸 찾는 과정이다. safe sequence가 하나라도 존재하면 sfae state로 유지할수있지만 하나라도 없으면 unsafe state이다.

2. Habermann's 알고리즘
   Banker's 알고리즘과 다른 것은 자원의 종류가 여러개라는 가정이다.
   자원의 종류만 다양해졌지 근본적으론 Banker's 알고리즘과 동일하다.

시뮬레이션을 돌리다가 safe sequence가 하나라도 존재하면 safe state인 것이고, 없으면 unsafe state인 것이다.
(참고로 unsafe state라고 데드락이 무조건 발생하는게 아닌 데드락이 발생할수 있는 가능성이 현재로썬 존재한다는 의미이다. 나중에 프로세스가 필요로하는 자원이 줄어들수도 있으므로,,!!!! - 다시한번 복기하는 것, 위에서 한번 언급했었음)

데드락 회피 결론

• 데드락의 발생을 막을수 있다.
• 항상 시스템을 감시하고 있어야 하므로 그만큼 overhead가 발생한다.
• safe state를 위해서 자원을 사용할수 있지만 사용하지 않는 경우가 존재할수 있다. 자원 활용도가 떨어진다.
• 무엇보다도 데드락 회피에서 언급한 가정들 때문에(프로세스 수 , 자원수 고정, 프로세스가 필요로할 최대 자원의 수 미리 알고있음,,,) not practical, 즉, 데드락 예방과 같이 현실적이지 못한 부분도 존재한다.

데드락 해결을 위해 데드락 예방, 회피 모두 알아보았는데 모두 부족한 부분이있다. 어떻게 확실히 데드락을 해결할수 있을까

Deadlock Detection and Deadlock Recovery

데드락 예방, 데드락 회피로는 데드락 해결책으론 부족하다는걸 느꼈다.
이번엔 데드락을 탐지하는 방법과 데드락이 발생하면 복구하는 방법을 알아보자.

Deadlock Detecion

데드락 예방처럼 데드락 발생 때문에 사전 조치를 하지 않고 주기적으로 deadlock이 발생할수 있는지 탐지한다. 탐지하는 방법으로는 Resource Allocation Graph(RAG)를 사용한다.

Resource Allocation Graph(RAG)

• Deadlock Detection(검출)을 위해 사용하는 그래프이다.

• Directed(방향이있고), bipartite(두 노드간 간선으로 이어진) 그래프이다.

• 그래프는 G = (N, E)로, Node와 Edge로 이루어져있다.

• N(Node)는 N = {Np, Nr} 프로세스와 자원의 집합으로 이루어져있고 Np = {P1, P2, ... Pn}, Nr = {R1, R2, ...Rm}으로 각 프로세스들과, 자원들을 이루는 집합으로 이루어져있다.

• E(Edge)는 Np와 Nr사이에만 존재한다.
  

  

  
  (그림과 같이 간선은 프로세스에서 자원, 자원에서 프로세스로만 연결될수 있다.)

• Rk는 자원의 타입(종류)이고, Tk는 Rk자원의 수이다. 그리고 |(a, b)|는 (a,b)의 간선의 수이다.
  

  

• 아래 그림은 RAG의 한 예시이다.
  

  

RAG를 통한 Deadlock Dection(데드락 검출) - Graph Reduction

• RAG에서 간선을 하나씩 지운다.
• 모든 간선이 지워지면 Deadlock에 빠진 프로세스가 없다는 의미이다.
• 모든 간선이 지워질수 없으면 Deadlock에 빠진 프로세스가 존재한다는 의미이다.

그럼 RAG에서 어떤 간선을 지워야하나?
---> Unblocked process의 간선을 모두 지워야한다.

Unblocked process란?

위 수식의 적합한 프로세스를 Unblocked process라고 한다.
이 의미는 한 프로세스에 대해서 모든 자원을 요청하는 모든 간선의 수가 해당 모든 자원이 할당된 모든 간선의 수보다 작거나 같아야 한다는 의미이다.
즉, 사용될수 있는 자원의 수 >= 요청하는 자원의 수 의 의미이다.
이 수식에 맞는 프로세스를 Unblocked process라 하며 해당 프로세스의 간선을 지워나가며 Deadlock Detection을 할수 있다.

1) Graph reduction결과로 모든간선이 지워짐 - 데드락에 빠진 프로세스가 없다.

P1이 unblocked process이므로 간선모두 지우고 -> p2도 unblocked process이므로 간선 모두 지우면 간선이 모두 지워져서 데드락에 빠진 프로세스가 없다는걸 알수있다.

2) Graph reduction결과로 모든 간선이 지워질수 없음 - 데드락에 빠진 프로세스가 있다.

P3가 unblocked process라 간선을 모두 지웠다. -> 그런데 unblocked인 프로세스가 없다. -> 모든 간선을 지울수없다. -> 데드락에 빠진 프로세스가 존재한다.(P1, P2프로세스)

이렇게 RAG에서 unblocekd process의 간선을 모두 지워나가며 데드락 탐지를 할수 있다.

Deadlock dection vs Deadlock Avoidance

데드락 탐지와 데드락 회피의 차이는? 둘다 프로세스의 상태(시스템의 상태)를 감시한다고 하지않았나? 그럼 똑같지않나?
데드락을 막으려는 정도의 차이가존재한다.

• Deadlock dectection
  데드락 탐지는 현재의 상태만 고려하며 최선의 상태를 생각하기에 최악의 경우 Deadlock이 발생할수도 있다. 이를위해서 Deadlock Recovery(데드락 복구)가 존재한다.

• Deadlock avoidance
  데드락 회피는 최악의 경우를 생각하기에 Deadlock이 발생할 가능성이 없다.

Deadlock Recovery

그렇다면 데드락이 탐지를 해도 데드락이 발생할수도 있는데, 데드락을 어떻게할까? 바로위에서 말한 것처럼 데드락을 복구하면된다.

복구하는 방법은 크게 두가지로

1. 프로세스 죽이기
2. 자원 선점하기
   가 존재한다.

프로세스 죽임으로써 데드락 복구

데드락이 발생중인 프로세스를 종료시킴으로써 데드락을 복구한다. 그러나 데드락에 빠진 프로세스가 여러개면 cost model을 기준으로 먼저 종료시킬 프로세스를 선택해야한다.

자원 선점함으로써 데드락 복구

이미 할당된 자원을 요청함으로써 데드락이 발생할 경우 해당 자원을 선점해서 뺏어옴으로써 데드락을 복구시킬수있다. 그러나 해당 자원을 이미 할당되어져있던 프로세스는 데드락에 빠지지않았는데 자원을 선점당하여 프로세스를 재시작해야하는 단점이 존재한다. 이 또한, 어떤 자원을 선점하느냐 는 자신만의 cost model을 토대로 먼저 선점할 자원을 선택할수 있다.

Checkpoint-restart method

프로세스를 강제 종료시키든, 자원을 강제로 선점하던 프로세스는 재시작을 해야하는데, 바로 재시작을 하면 너무 비효율적이므로 check point(특정 지점)마다 context를 저장하여 종료시킨다. 이러면 다시 재시작할때 해당 checkpoint에서 다시 실행할수있다.

데드락 결론

다중 프로그래밍에서는 여러 프로세스가 존재하고, 프로세스들은 자원을 할당받아야 작업을 수행하는데 자원을 영영 할당받지못하는 데드락 상태가 발생하기 마련이다. 자원의 특성 관점에서의 데드락을 발생시키는 원인과, 프로세스의 특징 관점에서의 데드락을 발생시키는 원인을 알아보았고 데드락을 해결하기 위해 예방, 회피, 탐지와 복구에 대해서 알아보았다. 데드락을 해결하는 방법은 매우 많은 방법이있으며 예방과 회피는 not practical하며 비효율적이므로 탐지 복구를 이용해 데드락을 해결해보자. 탐지와 복구를 이용해도, 자신에 맞는 복구법을 이용해서 데드락을 복구시킬수 있다는 사실도 알게되었다.

https://www.youtube.com/watch?v=xvoEsy2zJnc&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=19