Deadlock

  이전 글에서 synchronization(동기화)을 이루기 위해 lock을 사용하였었다. 하지만 간단한 예제가 아닌 실제 상황에서는 performance의 큰 저하 없이 lock으로 병렬성(동시성)을 만들어내는게 쉽지 않은 걸 알았다. 만약 lock을 촘촘하게 한다면 병렬성은 올라가도 오버헤드도 증가하기 때문에 성능이 감소할 수도 있고 구조가 복잡해지면 deadlock이 발생할 수도 있었기 때문이다.

  이 글에서는 deadlock에 대해 더 알아보고, 컴퓨터 시스템의 deadlock을 예방하거나 피하기 위해 사용하는 방법들도 살펴볼 것이다.

System Model

  여기서는 다음과 같은 모델을 사용한다.

• 시스템은 cpu, memory, I/O device 등의 자원(resource)으로 이루어져 있다.
  • 단순화를 위해 R1, R2, ...로 표현한다.
• 각각의 자원들마다 인스턴스를 가지는데 동시에 여러명이 사용할 수 있는 인스턴스와 그렇지 않은 싱글 인스턴스가 있다.
• 각 프로세스는 request -> use -> release의 순서로 자원을 활용한다.

 

Deadlock Characterization

  deadlock은 다음 4개의 조건을 만족할 때 발생할 수도 있다.

• Mutual exclusion
• Hold and wait
• No preemption
• Circular wait

 

Resource-Allocation Graph

  자원을 할당받는 과정을 vertices(V)과 edges(E)으로 이뤄진 유향그래프를 이용하여 나타낼 수 있다. V는 P(P1, P2, ...)와 R(R1, R2, ...) 두가지 유형으로 나뉘는데 각각 시스템의 프로세스들과 자원을 나타낸 것이다. 그러므로 간선은 다음을 의미한다.

fig 1

• request edge: P -> R
• assignment edge: R -> P

Example

fig 2

  fig 2와 같은 상황에서는 deadlock이 발생할 수 있을까? 위에서 deadlock이 발생하는 조건을 살펴보면 circular wait가 발생하지 않는 것을 확인할 수 있다. 그러므로 P3가 R3를 내려놓으면 P2가 R3를 받고 P2가 R1을 내려놓으면 P1이 R1을 받는 식으로 모든 프로세스가 자원을 사용할 수 있게된다.

fig 3

  fig 3는 fig 2와 달리 circular wait가 있는 것을 확인할 수 있다. 그렇기 때문에 서로 자기가 필요로하는 자원을 상대방이 가지고 있어 지금 가지고 있는 자원을 내려놓지 못하는 deadlock이 발생할 수도 있게 된다.

fig 4

  fig 4도 얼핏보면 circular wait가 있어서 deadlock이 발생할 수 있는 상황처럼 보인다. 하지만 R2가 2개의 인스턴스를 가지기 때문에 P4가 R4를 내려놓게 되면 P3가 해당 인스턴스를 취하면 되기 때문에 circular wait가 깨지게 된다.

Basic Facts

  위의 그래프를 사용해 알아본 결과,cycle이 없다면 deadlock이 발생할 수 없었다. 만약 cycle이 있을 때 자원 당 하나의 인스턴스만 있게된다면 deadlock이 발생하게 되고 자원 당 몇개의 인스턴스가 존재한다면 deadlock이 발생할 수도 있게 된다.

 

Methods for Handling Deadlocks

  시스템은 절대로 deadlock 상태로 들어가면 안되기 때문에 deadlock prevention/avoidance처럼 시스템이 deadlock 상태에 진입할 수는 있지만 그렇게 될 때 다시 recover하는 방법이 있고, 아니면 문제를 무시하여 시스템에서 deadlock이 발생하지 않은 척하는 방법이 있다. unix나 윈도우 등 대부분의 OS에서는 후자를 택했다고 한다. 왜냐하면 전자의 방법은 프로세스가 얼마만큼의 자원을 요구하는지를 다 알고 있다는 가정하에 이뤄지기 때문에 실제 상황에 적용시키기 쉽지않기 때문이다. 그럼에도 이 글에서는 deadlock을 발견하고 prevention/detection하는 방법에 대해 알아볼 것이다.

Deadlock Prevention/Avoidance

  deadlock을 prevention한다는 것은 deadlock이 일어날 수 있는 조건 4가지 중 하나를 만족시키지 못하게 하는 것이다.

  deadlock을 avoidance한다는 것은 프로세스가 얼마만큼의 리소스를 필요로 하는지를 알고 있는 상황에서 deadlock을 피해가는 방법인데, 각각의 자원 타입마다 자신이 필요로하는 자원의 양을 선언하는 것이다. 이를 바탕으로 프로세스가 여러개 있을 때, 어떤식으로 스케줄링해야 deadlock을 피할 수 있는지 파악하는 것이다.

Safe State

  프로세스가 이용가능한 자원을 요청했을 때, 이 자원을 할당하더라도 deadlock이 발생하지 않는 상태를 safe state라고 한다. 다시 말하면, 프로세스들이 실행될 때 모든 프로세스들이 자신이 필요로하는 자원을 다 할당받고 종료할 수 있는 sequence <P1, P2, ,,,>가 존재할 때 시스템은 safe state에 있다고 하는 것이다.

Basic Facts

fig 5

  정리하자면 시스템이 safe state에 있다면 deadlock이 발생하지 않고, 만약 unsafe state에 있다면 deadlock이 발생할 수도 있다는 것이다. 그리고 deadlock avoidance는 시스템이 unsafe state 상태로 들어가지 않게끔 만들어주는 것이다.

 

Avoidance Algorithm

  리소스 타입이 싱글 인스턴스를 가지는 경우에는 위에서 본 resouce-allocation graph를 통해 deadlock이 걸리는 상황을 판별할 수 있다. 만약 리소스 타입이 multiple 인스턴스를 가지는 복잡한 경우라면 Banker's algorithm을 사용하여 해결한다.

Resource-Allocation Graph Scheme

  들어가기 전 위에서 언급한 그래프에 몇가지 요소를 더 추가해보자. claim edge(P->R)는 프로세스가 리소스에 자원을 요청해야 한다는 의미이며 점선으로 표시한다. 이후 해당 프로세스가 그 자원을 요청하게 되면 claim edge는 request edge로 변하고 실선으로 표시된다. 그리고 해당 자원이 할당되면 assignment edge로 변한다. 이후 자원을 다 사용하여 release하게 되면 assginment edge는 claim edge로 변하게 된다. 앞서 말했듯이 이는 시스템이 미리 어떠한 리소스가 요구되는지 알고 있기에 가능한 것이다.

fig 6-1

 

fig 6-2

  fig 6-1의 상황은 현재 P1에 R1이라는 자원이 할당되어 있고 R2가 필요하다고 요청할 예정이다. 그리고 P2는 R1을 기다리고 있는 동시에 R2가 필요하다고 요청을 보낼 예정이다. 이때 fig 6-2같은 상황이 된다면 cycle이 생기게 되고 deadlock이 발생하게 된다. 이러지 않고 R2를 P1에 할당했다면 P2는 R1을 사용할 수 있게되니 cycle이 발생하지 않게되므로 deadlock도 발생하지 않게된다.

  그러므로 request edge를 assginment edge로 변환하는 것을 cycle이 만들어지지 않을 때만 가능케하면 deadlock을 발생하지 않게끔 할 수 있는 것이다.

Banker's Alogorithm

  이번에는 자원 타입이 여러개의 인스턴스를 가질 때 사용할 수 있는 Banker's Algorithm에 대해 알아보자. 선행 조건은 다음과 같다.

• 각 프로세스들은 얼마만큼의 자원을 사용할지 미리 claim하고 있어야하고, 가지고 있는 자원보다 더 많은 자원을 요청할 수는 없다.
• 프로세스가 자원을 요청할 때에는 wait를 한 다음 시스템이 safe state로 갈 수 있을지 판단한 뒤 그렇지 않다면 계속 wait한다.
• 프로세스가 리소스를 받으면 유한시간 내에 이를 반환해야 한다.

  n개의 프로세스가 있고, m개의 자원 타입이 있다고 하자. 여기서는 다음의 자료구조가 사용된다.

• Available: 길이 m의 벡터이다. 만약 [j]=k라면 리소스 타입 Rj의 k개의 인스턴스가 현재 사용가능하다는 뜻이다.
• Max/Allocation/Need: n*m 크기의 행렬이다. 만약 'Max/Allocation/Need[i, j] = k'라면 프로세스 Pi는 Rj의 k개의 인스턴스를 최대로 필요/현재 할당 중/필요로 한다이라는 뜻이다.
  
  • Need[i, j] = Max[i, j] - Allocation[i, j]

Example of Banker's Algorithm

fig 7-1

fig 7-2

  fig 7의 상황을 보자 5개의 프로세스 P0~P4가 있고 3개의 자원 타입 A, B, C가 각각 10, 5, 7개의 인스턴스를 가지고 있다. Allocation을 보면 A인스턴스 7개, B인스턴스 2개, C인스턴스 5개가 현재 할당 중이기 때문에 available은 총 A, B, C가 3, 3, 2인 것을 알 수 있다. 'Need[i, j] = Max[i, j] - Allocation[i, j]'를 이용하여 fig 7-2처럼 Need도 구해볼 수 있다.

  일단 P0이 available한 자원을 모두 들고 간다고 해보자. 그렇다면 총 '3 4 2'가 할당된다. 하지만 이것은 MAX에 미치지 못하기 때문에 P0는 수행되지 못한다. 이때 P0이 가져간 자원을 내려놓지 않는다면 다른 프로세스들도 MAX를 채우지 못하기 때문에 deadlock 상황이 발생할 수 있게 된다.

  그렇기 때문에 available을 갖고 수행이 될 수 있는 프로세스는 무엇인지 알아봐야 한다. fig 7-2에서 available을 가져가서 수행될 수 있는 프로세스는 P1과 P3이다. 만약 P1이 자원을 가져가게 되면 '2 1 0'이 새로운 available이 된다. 이때는 P4도 실행될 수 없다. 그러다가 P1이 완료된 후 자원을 내려놓게 되면 available은 '5 3 2'가 된다. 이렇게 되면 P3와 P4의 Max를 채워줄 수 있게 된다. P3가 필요한 자원을 가져간 뒤에 자원을 반납하면 available은 '5 4 3'이 된다. 이런 식으로 P4, P2, P0도 수행될 수 있다.

fig 8

  fig 8의 상황은 fig 7-1에서 P1이 (1,0,2)를 요청한 뒤의 상황이다. 위 처럼 생각을 해보면 <P1, P3, P4, P0 P2>의 순서로 필요로 하는 자원을 가져올 수 있게 된다.

 

Deadlock Detection & Recovery

  앞에서 살펴본 deadlock prevention/avoidance가 적용되지 않은 시스템은 deadlock이 발생할 수 밖에 없는데 여기서는 deadlock을 detect하고 recovery하는 방법에 대해 알아볼 것이다.

fig 9

  유향 그래프를 이용해서 resource-allocation graph와 유사한 corresponding wait-for graph를 나타낼 수 있다. Pi -> Pj는 Pi가 Pj를 기다리고 있다는 의미이다. 각 자원 타입마다 single 인스턴스를 가지고 있을 때는 이 wait-for 그래프를 그려본 뒤 cycle이 있는지 확인한 뒤 존재한다면 deadlock이 있다고 본다. 참고로 cycle이 있는지 확인하는 것에는 n^2만큼의 시간복잡도가 소요된다고 한다.

  자원 타입이 여러개의 인스턴스를 가질 때는 여지껏 봤듯이 available, allocation, request를 이용하여 detection을 한다.

fig 10

  fig 10의 상황을 보자. available이 '0 0 0'인걸 보아 모든 자원이 사용 중이라는 걸 알 수 있다. P0, P2는 요구하는 것이 없으니 내려놓게 되면 available은 '3 1 3'이 된다. 이를 이용하면 나머지 P1, P3, P4도 모두 필요한 자원을 가질 수 있게 된다.

  그런데 만약 P2가 '0 0 1'을 요청(request)하고 있었다면 어떻게 달라질까? 그렇게 되면 P0한테 되돌려받은 '0 1 0'만을 가지고는 다른 프로세스를 실행시킬 수 없게 되므로 deadlock이 발생하게 된다. 앞에서 본 banker's 알고리즘과 유사하다.

  물론 이러한 알고리즘을 자주 사용하면 deadlock을 신속히 발견하여 처리할 수는 있겠으나 당연히 오버헤드가 발생하므로 성능은 저하될 것이다. 그러므로 얼마나 자주 deadlock이 발생하는지, 얼마나 많은 프로세스가 roll back되어야 하는지 등을 고려하여 알고리즘의 사용빈도를 결정할 필요가 있다.

  deadlock의 recovery는 프로세스를 abort하거나 preemption을 하는 방법 등이 있다. 하지만 이런 방법을 많은 OS에서는 사용하지 않는다고 했다. 계속 언급하지만 실제 상황에서는 자원을 프로세스에 넘겨줄 때 얼마나 줘야할지 알 수 없기 때문에 deadlock을 발견하기 쉽지 않다. 때문에 프로그래머가 deadlock을 인지해서 고치는게 아닌 시스템적으로 OS가 deadlock을 풀기에는 무리가 있다.

---

• Operating System Concepts, Avi Silberschatz et al.
• Operating Systems: Three Easy Pieces
  • Remzi H.Arpaci-Dusseau andAndreaC.Arpaci-Dusseau
  • Available(withseveraloptions)athttp://ostep.org