Seungho Jeong

Backend Problem Solver (feat. Python)

게시:

Deadlock(교착상태)이란 프로세스들이 서로가 가진 자원을 기다리며 Block된 상태를 말한다.

예를 들어 프로세스 A, B, C가 있고 자원[1] 1, 2, 3이 있을 때, 각각의 프로세스는 작업을 수행하기 위하여 지정된 2개의 자원이 필요하다고 가정하자. 이러한 조건속에서 A가 1을 가지고 있는 상태에서 2를 요청(Request)하고, B는 2를 가지고 있는 상태에서 3을 요청하고, C는 3을 가지고 있는 상태에서 1을 요청한다면 프로세스는 서로의 자원을 기다리며 멈추게 된다.

Deadlock 상태에 빠지면 어떤 프로세스가 먼저 희생(또는 종료)하지 않는 이상 끝나지 않는다.

Deadlock implementation in Real-world.
리얼 월드에서의 Deadlock

발생조건

Deadlock은 아래의 4가지 조건을 모두 만족해야 발생하며 어느 하나의 조건이라도 만족하지 않으면 Deadlock은 발생하지 않는다. 이는 Deadlock은 자주 발생하는 문제가 아니라는 의미이기도 하다.

  1. Mutual Exclusion(상호 배제): 매 순간 하나의 프로세스만이 자원을 사용할 수 있는 경우. 즉, 프로세스가 자원을 얻었을 때 다른 프로세스와 함께 쓰지 않고 독점적으로 사용하는 경우.
  2. No Preemption(비선점): 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는 경우. 자원을 가지고 있는데 빼앗길 수 있다면 당연히 교착상태는 발생하지 않을 것이다.
  3. Hold & Wait(보유대기): 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는 조건일 때. 즉, 이미 내가 가진 자원을 내어놓지는 않으면서 추가 자원을 요청하는 조건을 말한다.
  4. Circular Wait(순환대기): 자원을 기다리는 프로세스간에 사이클이 형성되는 경우. 각 프로세스가 필요로 하는 자원들이 꼬리를 물고 고리를 형성하는 경우를 말한다.
Resource-Allocation Graph
Resource-Allocation Graph

발생조건 1~3번을 만족한다고 가정하고 위의 이미지를 보았을 때 첫 번째 그래프에는 \(R_2\)에 자원이 2개 존재하므로 하나의 순환대기 사이클이 형성되면 Deadlock이 아니지만 해당 자원에 대하여 2개의 사이클이 형성되었기 때문에 Deadlock이다.

두 번째 그래프에도 \(R_1\)(또는 \(R_2\))의 2개의 자원에 대하여 이미 모두 Allocated되어 있다. 하지만 \(P_2\), \(P_4\)는 사이클과 무관한 프로세스이기 때문에 해당 프로세스는 언제든지 자원을 Release 할 수 있기 때문에 Deadlock이 아니다.

처리방법

Deadlock을 해결하는 방법으로는 ▲ Prevention(예방) ▲ Avoidance(회피) ▲ Detection & Recovery(탐색 & 회피) ▲ Ignorance (무시) 4가지가 있다.

Prevention

자원 할당 시 Deadlock 발생의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 방법이다.

Deadlock을 원천적으로 막을 수 있지만 자원의 이용률이 낮아지고 성능이 낮아지는(Throughput 감소) 문제가 있어 비효율적이고 Starvation 문제가 생길 수도 있다.

  1. Mutual Exclusion: 상호배제 조건을 만족시키지 않는 것은 불가능하다. 만약 가능했다면 근본적으로 Process synchronization 문제가 발생하지 않을 것이기 때문이다.
  2. No Preemption: 자원을 Preemption 할 수 있도록 하여 부분적으로 해결할 수 있다. 다만 Context switch가 가능한 CPU나, 쉽게 Save & Restore 할 수 있는 Memory 등의 자원에는 쉽게 적용할 수 있지만 그렇지 않은 자원은 곤란하다.
  3. Hold & Wait: 다음 두 가지 방법으로 해결할 수 있다.
    1. 프로세스 시작 시 필요한 자원을 모두 할당받게 한다.
      • 쓰지 않을 수도 있는 자원을 쓸데없이 독점하게 되므로 낭비이다.
    2. 자원을 요청할 때 보유한 자원을 모두 반환하도록 한다.
      • 자원을 얻는 과정이 지속적으로 반복되므로 비효율적이다.
  4. Circular Wait: 모든 자원에 할당 순서를 정하여 정해진 순서대로만 자원을 할당하여 해결한다.

Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 Deadlock의 가능성이 없는 경우에만 자원을 할당하는 방법이다. 프로세스가 시작될 때 평생 사용할 자원을 미리 선언(Declare)한 뒤 이 정보를 통하여 어떠한 프로세스가 자원을 요청할 때 다른 프로세스와 Deadlock이 발생할 가능성이 조금이라도 있으면 자원을 아예 할당하지 않음으로써 Deadlock을 방지한다.

Deadlock을 회피할 수 있는 안전한 시퀀스(Safe sequence[2])가 존재하는 경우에만 자원을 할당한다. 즉, 시스템 State가 원래 State로 돌아올 수 있는 경우(Safe state[3]에만 자원 할당하여 모든 프로세스의 수행을 보장한다. 이 방식도 원천적으로 Deadlock을 막는다.

Avoidance Algorithm

  1. Resource-Allocation Graph Algorithm (Single instance인 경우)
    • 자원당 인스턴스가 하나 밖에 없는 경우에 사용한다.
    • Safe state를 그래프로 확인할 수 있다. 아래 그림에서 Request edge(실선)의 Assignment edge 변경 시 Cycle이 생기지 않는 경우에만 요청 자원을 할당한다.
    • Cycle 여부 조사(Graph Traversals)시 프로세스의 수가 \(n\)일 때 \(O(n^2)\) 시간 소요
    Resource-Allocation Graph
    자원으로부터의 점선 화살표(Claim edge)는 자원에 대한 잠재적인(미래의) 할당 가능성을 의미하며 요청 시 실선(Request Edge)으로 바뀐다.
  2. Banker’s Algorithm (Multiple instance인 경우)
    • 자원당 인스턴스가 여러 개인 경우 사용한다.
    • 최대 요청 가능 자원의 벡터에서 현재 할당된 자원 벡터를 뺀 뒤 가용 가능한 자원의 벡터를 할당했을 때 Deadlock을 회피할 수 있는 시퀀스가 존재하면 할당한다.
    Banker's Algorithm Table
    P1이나 P3는 현 상태에서 Max-allocation이 할당 가능한 자원 A(3), B(2), C(2)보다 적기 때문에 P1이나 P3에 할당하면 언젠가 프로세스 종료 후 자원을 반환할 것이다. 또한 이후 반환된 자원을 계산했을 때 P4나 P2에 할당하면 언젠가 종료되어 자원을 반납할 것이고 이후 마지막으로 P0에 할당하면 모든 프로세스를 종료시킬 수 있기 때문에 시스템은 Safe state이다.

Detection & Recovery

Deadlock 발생은 허용하되 Detection 루틴을 두어 Deadlock 발견 시 Recover하는 방식이다.

Detection Algorithm

  1. Wait-For Graph (Single instance인 경우)
    • Resource-Allocation Graph(자원 할당 그래프)의 변형으로 그래프에서 Cycle이 곧 Deadlock을 의미한다.
    • 그래프에 점선이 없어 자원의 최대 사용량을 미리 알릴 필요가 없어진다.
    • 자원 할당 그래프와 달리 프로세스만으로 Node를 구성한다.
    • Avoidance와 마찬가지로 Cycle이 존재하는지 확인하기 위해서는 그래프를 모두 순회해야 하므로 \(O(n^2)\)만큼의 Time complexcity가 필요하다.
    Banker's Algorithm Table
    더 심플하여 사이클을 찾기 쉽다.
  2. Banker’s Algorithm (Multiple instance인 경우)
    • Banker’s Algorithm과 같이 테이블을 그려서 확인한다.
    • 요청이 없는 프로세스는 자원을 반납할 것이라는 낙관적인 관점으로 해석한다. 즉, 당장 요청이 없는 프로세스의 자원과 할당 가능 자원을 합한 상태에서 Safe sequence가 존재하는지 확인하는 것이다.
    • 만약 Safe sequence가 존재한다면 현재 Deadlock이 없는 것으로 한다.
    Banker's Algorithm Table
    Banker’s Algorithm Table

Recovery

  • Process termination: Deadlock이 발견된 경우 Deadlock과 관련된 모든 프로세스를 종료시키는 방법이다.
  • Resource Preemption: Deadlock이 발견된 경우 Deadlock과 관련된 프로세스를 하나씩 종료시키는 방법이다. 비용을 최소화할 victim을 선정하여 자원을 하나씩 빼앗어 보는 방법이다. Safe state로 Rollback하여 프로세스를 재시작하여 Deadlock을 없앤다.
    • 동일한 프로세스가 계속해서 victim으로 선정되는 경우 Starvation이 발생할 수 있으므로 특정 프로세스만 선정되지 않도록 자원을 빼앗는 패턴을 조금씩 다르게 해야 한다. (Cost factor에 Rollback 횟수도 고려해야 한다.)

Ignorance

Deadlock이 일어나지 않는다고 전제하고 아무런 조치도 취하지 않는 방식이다.

Deadlock이 생기지 않게 하는 것 자체가 자원을 비효율적으로 쓰는 것이고 Detection routine도 O/H가 크기 때문에 Deadlock이 생기더라도 시스템이 책임지지 않고 가만히 놔두며, 만약 시스템에 Deadlock이 발생하여 시스템이 느려지거나 멈추는 등 시스템이 비정상적으로 작동하는 것을 사용자가 발견하면 직접 프로세스를 종료하는 것으로 대처한다.

UNIX, Windows 등 대부분의 범용 OS가 채택하고 있는 방식이다.

각주

1: 하드웨어는 물론 소프트웨어까지 포함하는 개념으로 CPU Cycle, Memory space, I/O Device, Semaphore 등이 있다. 요청(Request) → 할당(Allocate) → 사용(Use) → 반환(Release) 사이클로 사용한다.

2: 프로세스의 Sequence \(<P_1, P_2, ..., P_n>\)이 Safe하려면 \(P_1(1 \le i \le n)\)의 자원 요청이 “가용 자원 + 모든 \(P_j(j \lt i)\)의 보유 자원”에 의해 충족되어야 한다. 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장한다.

  • \(P_i\)의 자원 요청이 즉시 충족될 수 없으면 모든 \(P_i(j \lt i)\)가 종료될 때까지 기다린다.
  • \(P_i-1\)이 종료되면 \(P_i\)의 자원요청을 만족시켜 수행한다.

3: 시스템 내의 프로세스들에 대한 Safe sequence가 존재하는 상태

Reference

반효경, “반효경 [운영체제] 16. Deadlock 1”. KOCW. 2014년 4월 11일. video, http://www.kocw.net/home/cview.do?lid=a1bfe7f08156cb36
반효경, “반효경 [운영체제] 16. Deadlock 2”. KOCW. 2014년 4월 15일. video, http://www.kocw.net/home/cview.do?lid=7351cb56948b1c9a


OS 시리즈 모두보기 (펼치기)


댓글남기기