교착 상태(Deadlock)

교착 상태(Deadlock)의 개념

Blocked/Asleep State는 프로세스가 특정 이벤트, 필요한 자원을 기다리는 상태를 의미한다. 이렇게 프로세스가 이벤트 혹은 자원을

기다리는 상태 중에서 발생 가능성이 없는 이벤트, 자원을 기다리는 상태를 특별히 Deadlock State라고 한다.

교착 상태(Deadlock)와 기아 상태(Starvation)

교착 상태(Deadlock)는 Asleep State에서, 기아 상태(Starvation)는 Ready State에서 발생하며, 교착 상태가 기다리는 이벤트, 자원은

발생 가능성이 없으나, 기아 상태가 기다리는 이벤트, 자원은 발생 가능성은 있으나 우선순위 등에 밀리는 것을 의미한다.

 

교착 상태(Deadlock)와 자원(Resource)

자원은 일반적으로 하드웨어 자원, 소프트웨어 자원으로 구분할 수 있다. 이외에도 선점 가능 여부, 할당 단위, 동시 사용 가능 여부, 재사용 가능 여부에 따라 구분할 수 있다. 

 

1. 선점 가능 여부에 따른 분류

Preemptible Resource

선점당한 후, 돌아와도 문제가 발생하지 않는 자원으로 Processor와 Memory 등이 해당한다. Processor의 경우, Context Switching 시

Saving과 Restoring을 진행함으로써, Memory의 경우 Swap-Device를 이용함으로써 문제가 발생하지 않는다.

 

Non-Preemptible Resource

선점당하면, 이후 진행에 문제가 발생하는 자원으로 Rollback, Restart 등의 특별한 동작이 필요하다. Disk Drive가 해당한다.

 

2. 할당 단위에 따른 분류

Total Allocation Resource

자원 전체를 프로세스에게 할당하는 자원으로 Processor가 해당한다.

 

Partitioned Allocation Resource

하나의 자원을 여러 조각으로 나누어 여러 프로세스에게 할당하는 자원으로 Memory가 해당한다.

 

3. 동시 사용 가능 여부에 따른 분류

Exclusive Allocation Resource

한 순간에 한 프로세스만 사용 가능한 자원으로 Processor, Memory, Disk Drive 등이 해당한다. Memory의 경우 할당된 영역을 

동시에 여러 프로세스가 사용할 수 없다는 의미이다.

 

Shared Allocation Resource

여러 프로세스가 동시에 사용 가능한 자원으로 Program, Shared Data 등이 해당한다.

 

4. 재사용 가능 여부에 따른 분류

Serially Reusable Resource

시스템 내에 항상 존재하는 자원으로 사용이 끝나면 다른 프로세스가 사용 가능하다. Processor, Memory Disk Drive, Program

등이 해당한다.

 

Consumable Resource

한 프로세스가 사용한 후에 사라지는 자원으로 Signal, Message 등이 해당한다.

교착 상태(Deadlock) 발생 필요 조건

자원의 특성

Exclusive Use of Resources

Non-Preemptible Resources

 

프로세스의 특성

Hold and Wait(Partial Allocation)

Circular Wait

교착 상태 예방(Deadlock Prevention)

4개의 교착 상태 발생 필요 조건을 제거함으로써 교착 상태를 예방할 수 있다. 우선, 모든 자원을 공유 허용하거나 모든 자원에 대한 선점을 허용함으로써 Exclusive Use of Resources, Non-Preemptible Resources 조건을 제거할 수 있다. 그러나 현실적으로 불가능하다. 필요한

자원을 한번에 모두 할당(Total Allocation) 받음으로써 Hold and Wait 조건을 제거할 수 있다. 그러나 필요하지 않은 순간에도 자원을

가지고 있음으로써 자원 낭비가 발생하며, 특정 프로세스의 경우 Starvation 발생 가능성이 있다. 자원들에게 순서를 부여하고 프로세스는

순서의 증가 방향으로만 자원 요청 가능하게 할 경우 Circular Wait 조건을 제거할 수 있다. 그러나 이 역시 자원 낭비가 발생한다.

교착 상태 회피(Deadlock Avoidance)

교착 상태 회피란 시스템의 상태를 계속 감시하여 교착 상태가 될 가능성이 있는 프로세스의 자원 할당 요청을 보류, 시스템을 항상 Safe

Stae로 유지하는 것을 의미한다. 이때, Safe State란 교착 상태가 되지 않을 수 있음을 보장하는 Safe Sequence가 존재, 프로세스가

정상적으로 종료 가능한 상태를 의미한다. 교착 상태 회피는 프로세스의 수, 자원의 종류와 수가 고정되어 있고, 프로세스가 요구하는 자원 및 최대 수량을 알고 있으며, 프로세스는 자원을 사용 후 반드시 반납하는 것을 가정한다. 교착 상태의 발생을 막을 수 있다. 그러나 항상

시스템을 감시하고 있어야 하기에 부하가 높고, Safe State 유지를 위해 사용 되지 않는 자원이 존재하여 자원 효율이 낮다. 또한, 가정 역시

현실적이지 않다.

교착 상태 탐지 및 복구(Deadlock Detection and Recovery)

교착 상태 탐지

교착 상태 탐지란 교착 상태 방지를 위한 사전 작업을 하지 않고, 시스템이 교착 상태인지, 어떤 프로세스가 교착 상태인지 등을 주기적으로 확인하는 것을 의미한다. 이를 위해 Resource Allocation Graph(RAG)를 사용할 수 있다. 다만, Graph Reduction은 검사 주기와 Node의 수가 많은 경우 부하가 크며, 교착 상태 발생 시 복구 과정이 필요하다.

 

교착 상태 복구

교착 상태 복구는 크게 Process Termination과 Resource Preemption으로 나눌 수 있다. Process Termination의 경우, 교착 상태인

프로세스 중 일부를 종료하는 것을 의미한다. 이때, 어떤 프로세스를 종료할지는 Termination Cost Model에 따라 선택한다.

Resource Preemption은 교착 상태 해결을 위해 선점할 자원을 선택한다. 해당 자원을 가지고 있는