7. Deadlock

The Deadlock Problem

A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.

💡

mutual하게 쓸 수 없는 자원이 현재 다른 프로세스가 가지고 있어서 block된 상황인데, 해당 process 또한 mutual하게 쓸 수 없는 자원을 원함으로써 block된 상황이다.

process가 resource의 부족으로 인해 block됨 → 해당 resource를 사용할 수 있을 때까지 block됨

근데, 2개의 서로 프로세스가 서로 원하는 경우에는 계속 block되는 상태 (물론 2개 이상의 프로세스가 꼬리를 물어도 dead-lock은 발생한다.)

이러한 문제는 자원이 한정됨 으로 인해서 발생

💡

Deadlock은 machine들 사이에서 일어날 수도 있고, process들 사이에서 일어날 수도 있다. (즉, deadlock은 단일 컴퓨터에서도 나타날 수 있다.)

특히 semaphore를 잘못쓰게 되면 dead-lock problem이 발생함.

Example : Improper usage of a semaphore

Example : Bridge Crossing

Livelock

Deadlock과 구분해서 정리해야 한다. Deadlock의 경우 한정된 공유자원을 여러 쓰레드가 동시에 사용하려고 할 때 무한정 대기하면서 발생하는 문제라면, livelock은 스레드들이 동시에 실행되면서 lock의 해제와 휙득을 반복적으로 하면서 정상적으로 동작하는 것처럼 보이나, 사실상 아무것도 못하고 무한 동작중인 상황을 말한다.

예를 들어, deadlock을 피하기 위해 프로세스가 lock을 휙득하지 못한 경우 대기 상태로 빠지지 않도록 하고, 자신이 휙득한 lock을 해제시켜서 다른 프로세스가 자신이 점유하고 있던 자원에 접근할 수 있도록 처리를 하고 다시 시작을 한다. 다른 프로세스와 이러한 과정이 순환적으로 일어나게 되면 livelock이 발생하게 된다. (이들은 block된 것은 아니지만, 더이상 진행을 하지 못하고 있다)

💡

2개 이상의 쓰레드가 진행하는 것을 막는다는 점에서 deadlock과 유사하지만, 다른 원인에 의해서 진행이 되지 않는다는 것을 반드시 기억해야 한다.

💡

Deadlock에 비해서는 자주 일어나는 문제는 아니다.

Formal Model of Deadlock

• Components of any resource allocation problem

  1. set of processes

  2. set of resources

Paradigm of resource usage by process

Resource Allocation Graph

💡

P type : Process

R type : Resource

Example

Deadlock occurs case

Theorem 1

If a graph doesn’t contain a cycle then no processes are deadlocked.

💡

cycle은 dead lock이 발생하기 위한 necessary condition이다. (즉 필요조건) 즉 사이클이 존재한다고 반드시 dead lock이라고 할 수 없음.

Cycle이 존재해도 deadlock이 발생하지 않는 예시

Theorem 2

If there is only a single instance per resources type, then a set of processes are deadlocked iff the processes and resources form a cycle in the resource allocation graph.

💡

If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred.

💡

각 resource의 여유분이 1개이고, 서로 꼬리를 물고 있을 때 deadlock의 필요충분조건이 된다.

즉 각 resource type이 여러 instance를 가지는 경우에는, 반드시 사이클이 deadlock를 의미하지 않는다.

사이클이 존재하지만 deadlock이 발생하지 않는 예시

Necessary Conditions for a Deadlock

1. Mutual exclusion : only one process at a time can use a resources

2. Hold and wait : a process holding at least one resource is waiting to acquire additional resources held by other processes.

3. No preemption : a resource can be released only voluntarily by the process holding it

4. Circular wait

💡

4가지 조건이 동시에 다 만족해야함. (단, 충분조건이 아님)

💡

추가적으로 4가지 조건이 independent한 것은 아니다. 예를 들어 circular wait은 hold and wait를 의미한다.

Sufficient condition이 아님을 보여주는 예시

Methods for Handling Deadlocks

Types

Deadlock Prevention or Avoidance

→ Ensure that the system will never enter a deadlock state

• problem

  효율성이 많이 떨어짐 (system이 전반적으로 under utilize될 확률이 높음)

💡

prevention이 조금 더 strong한 접근 방법이다.

Deadlock Detection and Recovery

→ Allow the system to enter a deadlock state and then recover

예를 들어 프로세스가 많음에도 불구하고 idle상태에 오래 머물러 있는 경우에 deadlock 여부를 detection하고 recovery 절차를 진행함.

No policy

→ Ignore the problem and pretend that deadlocks never occur in the system.

대부분의 범용 OS는 이 케이스처럼 deadlock에 대한 정책이 없다. 즉 deadlock에 대한 문제를 고려하지 않음. 즉 deadlock에 대한 분제는 kernel이나 application 개발자에게 넘김

Deadlock Prevention

Key idea

4가지 deadlock necessary conditions중에 최소 1개가 발생시키지 않는 것을 보장함으로써, 절대로 dead-lock이 발생하지 않게끔하는 것이 아이디어

Mutual exclusion

• Problem

  일부 resource는 태생적으로 non-sharable한 것이 존재한다. 예를들어 mutex lock의 경우에는 동시에 여러 쓰레드에서 공유할 수 없다. 이러한 측면에서 mutual exclusion을 무시하는 방식으로 deadlock을 막을 수 없다.

Hold and wait

No wait : 이 정책에서 프로세스는 실행을 시작하기 전에 그것이 필요로 하는 모든 자원들을 한 번에 요청하게 됩니다. 따라서, 모든 필요한 자원들이 준비되어 있어야만 프로세스는 실행을 시작할 수 있으며, 그렇지 않은 경우 프로세스는 대기 상태에 머무르지 않고 롤백되거나 종료됩니다. 이렇게 함으로써, 프로세스가 실행 중에 추가적인 자원을 요청하거나 기다리는 상황을 방지하게 되고, 이는 결국 deadlock을 방지하는데 도움을 줍니다.

💡

프로세스가 미래에 사용할 모든 자원에 대해 사전에 알고 있어야 한다는 점 때문에 현실적인 해결방법이 아니다.

No hold : 이 정책은 프로세스가 새로운 자원을 요청할 때 이미 보유하고 있는 모든 자원을 먼저 release 해야 합니다. 이 역시 "hold and wait" 조건을 깨트리는 정책입니다. 프로세스는 필요한 다른 자원을 기다리면서 이미 보유한 자원을 'hold'하지 않습니다. 이 경우, 프로세스는 새로운 자원을 요청하기 전에 모든 자원을 해제하고, 필요한 모든 자원을 한 번에 요청합니다.

• Problem

  1. resource utilization이 낮음.

  2. starvation 문제가 발생할 수 있다.

No preemption

2가지 방식이 있음

1. 특정 process가 resource를 request했지만, 해당 resource를 바로 할당할 수 없는 경우, 해당 process가 가지고 있는 resource가 전부 release된다.

   💡

   no wait과의 차이가 무엇인가? : no wait은 시작을 안한 상태인거고, no preemption은 돌리고 있는 와중에 resource를 요구하고 있는 상황이라고 이해하면 됨.

   💡

   preempted된 process는 기존의 resource와 원하는 resource를 전부 다 사용할 수 있을때에만 재시작된다.

2. 특정 process가 resource를 request했지만, 해당 resource를 가지고 있는 process가 다른 resource를 wait하고 있는 경우, 기다리고 있는 프로세스로부터 해당 자원을 preempt시키고 요청한 process에 해당 자원을 할당한다. (만약 해당 resource를 가지고 있는 process가 wait상태가 아니라면 request한 process는 wait한다.)

• Problem

  Only can be applied to resources whose state can be easily saved and restored later

  ex) CPU registers, database transactions

  → 반대로 mutex lock이나 semaphore에는 적용하기가 힘들다.

Circular Wait

앞서 살펴본 3개의 deadlock prevention은 많은 상황에서 impractical하다. 반면 이 방식은 practical solution을 제시한다.

모든 resource type에 total ordering를 부여하고, 프로세스들이 증가하는 순서대로 해당 자료들을 쓰게끔 강제시킴으로써 위 문제를 해결하고자 함.

• Problem

  1. Ordering을 만든 것 만으로는 deadlock을 막을 수 없음. application developer가 해당 ordering을 따라야 한다는 문제점이 있음

  2. lock ordering을 만드는 것은 굉장히 어려움

💡

살펴본 것처럼, resource utilization과 throughput이 낮아짐. 그래서 등장한 개념이 Deadlock Avoidance

Deadlock Avoidance

Key idea

Avoid deadlock by run-time checking and allocation of resources.

각 프로세스가 필요한 자원의 최댓값을 선언하고, 이에 대한 정보를 system이 가지고 있다고 전제한다. 위 내용을 바탕으로 deadlock을 피하기 위해서 특정 process가 wait되어야 하는지 여부를 system이 판단하게 된다.

💡

즉 priori information을 가지고 있다고 전제하는 것이다.

요구되는 정보의 양과 종류에 따라 다양한 알고리즘이 존재. 가장 간단하고 유용한 접근방법이 각 process(thread)로 하여금 각 resource type별로 사용할 수 있는 자원의 최댓값을 요구하는 것이다.

→ 이 정보를 통해 run-time으로 deadlocked state에 절대로 들어가지 않게끔하는 resource-allocation state를 판단하게 된다.

• Resource-allocation state는 어떻게 구성되는가?

  

  1. number of available and allocated resources

  2. maximum demands of resources for each process(threads)

  💡

  resource-allocation state와 resource-allocation graph를 구분할 것.

Safe State

프로세스가 available resource 를 request했을 때, 해당 allocation을 진행해도, system이 여전히 safe상태에 있는지 판단한다.

• 그래서 system이 safe state에 있다는 것의 의미가 무엇인가?

  모든 프로세스들에 대한 안전한 sequence가 있는 경우

  • 그래서 안전한 sequence라는 것은 무슨 의미인가?

    Sequence $<P_1, P_2, \dots, P_n>$ is “safe” if $\forall P_i,$ $P_i$’s request can be satisfied by initial available resources and resources held by all the $P_j$ ($j < i)$.

    💡

    즉, 해당 sequence 순서대로 자원 할당을 진행하게 되면 정상적으로 자원 할당이 무조건 가능하다는 의미이다.

Facts

unsafe하다고 deadlock이 발생하는 것은 아님. 단, system이 safe state에 있으면 deadlock이 절대로 발생하지 않는다.

💡

Avoidance의 목표는 그래서 system이 unsafe state에 들어가는 것을 막겠다는 것

Banker’s Algorithm

전제 : Maximum use에 대한 priori 를 가지고 있어야 한다.

해당 process에게 자원을 할당해주었다고 가정했을 때 safe sequence가 존재할 때만(safe할 때만) 실제로 자원을 할당해주겠다는 것.

Safety Algorithm

💡

안전한 상태란 프로세스가 요청하는 모든 자원을 할당해도 deadlock이 발생하지 않는 상태를 의미한다.

💡

현재 있는 자원만으로 끝낼 수 있는 process부터 먼저 다 끝내놓고, 자원을 돌려받는다. (이 과정에서 process가 이미 가지고 있는 자원이 있는 경우때문에 보유한 자원은 증가하거나 같다.) 이러한 과정을 반복해서 모든 process가 끝날 수 있는지 여부를 체크하는 것이다.

Example

5개의 process와 ABC 3개의 resource가 존재

MAX : 해당 process가 원하는 자원

ex) p_0는 A를 7개, B는 5개, C는 3개를 원하는 상황

Allocation : 해당 process가 가지고 있는 자원

Available : 안쓰고 있는 자원

지속적으로 need가 available한 process들을 처리시킴

Allocation과 MAX는 matrix, Available는 vector

Need : Max - Allocation

특히 22페이지 맨 마지막 state 주의 깊게 볼 것

→ Can request for (0, 2, 0) by p_0 be granted in above state?

The problem of Banker’s Algorithm

1. 사용할 수 있는 자원의 max값을 system에게 알려줘야한다는 가정이 필요하다. 이는 미래의 일을 알아야하는상황이기때문에 현실적이지는 않다.

2. maximum 값을 report한다는 점때문에 resource낭비가 되는 문제가 발생

Deadlock Detection and Recovery

Let the system deadlock and then deal with it

→ No a priori information on the resource request

Detection Algorithm

만약 모든 process가 Finish의 상태가 true이면, 현재의 상태가 safe라는 의미인데, 하나의 process라도 Finish의 상태가 false이면 현재 상태가 safe하지 않다는 의미이다.

💡

Allocation이 없는 process의 경우는 무시한다는 점을 주의해야 한다.

💡

즉, Banker’s Algorithm은 자원을 할당해주기 전에 판단하는 것이고, Dead lock detection은 현재 상태가 safe한지 여부만 판단하는 것이다.

Example

💡

resource-allocation-state와 다른 점은 allocation이 0인 process/thread에 대해서는 Finish를 true로 취급한다는 점에서 차이를 보이고 있다. 또한 need가 아니라 request로 바뀌어있다. (따라서 priori를 요구하지 않는다.)

Comparison between Banker’s Algorithm and Detection Algorithm

Deadlock detection 알고리즘의 주요 목표는 시스템에 이미 발생한 deadlock을 찾는 것입니다. Deadlock 상황은 다음 네 가지 조건이 동시에 충족될 때 발생합니다: mutual exclusion, hold and wait, no preemption, 그리고 circular wait. 이 중 "hold and wait" 조건은 프로세스가 최소한 하나 이상의 자원을 보유하면서 다른 자원을 기다리고 있음을 의미합니다.

이미 자원을 할당받지 않은 프로세스는 "hold and wait" 조건을 충족시키지 못하므로, 그러한 프로세스는 deadlock 상황의 일부가 될 수 없습니다. 그렇기 때문에 deadlock detection 알고리즘에서는 자원을 할당받지 않은 프로세스를 고려할 필요가 없습니다.

물론, 프로세스가 자원을 할당받지 않은 상태로 남아있는 경우, 그 자체로 다른 종류의 문제를 초래할 수 있습니다. 예를 들어, 시스템의 자원이 고갈되어 프로세스가 필요한 자원을 얻지 못하는 상황은 starvation 문제를 야기할 수 있습니다. 하지만 이런 문제는 deadlock과는 별개의 문제로, 별도의 해결 방법을 요구합니다.

Banker's Algorithm은 Dijkstra가 제안한 자원 할당 알고리즘으로, 자원을 할당할지 여부를 결정하기 위해 가상의 "은행원"의 입장에서 안전성을 검토합니다. 이 알고리즘의 주요 목적은 시스템을 안전한 상태로 유지하는 것이며, 안전한 상태란 프로세스가 요청하는 모든 자원을 할당해도 deadlock이 발생하지 않는 상태를 말합니다.

Banker's Algorithm에서는 자원을 할당하지 않은 프로세스를 고려하는 이유는 이러한 프로세스들이 미래에 자원을 요청하게 될 것이라는 예상 때문입니다. 즉, 프로세스가 현재 자원을 가지고 있지 않더라도, 그 프로세스가 미래에 요청할 수 있는 최대 자원 요청을 고려하여 안전한 상태를 판단합니다. 이렇게 함으로써 Banker's Algorithm은 미래에 발생할 수 있는 가능한 모든 상황을 예측하고 이에 대비하여 자원을 관리합니다.

따라서 Banker's Algorithm에서는 현재 자원을 할당받지 않은 프로세스도 고려하는데, 이는 시스템의 안전성을 보장하고 potential deadlock 상황을 미리 방지하는 데 중요합니다.

Detection Algorithm Usage

언제, 얼마나 deadlock detection algorithm을 수행할 것인지를 결정하는 것은 중요한 문제가 된다. 왜냐하면 자원을 request할 때마다 deadlock detection algorithm을 수행하면 굉장히 큰 overhead를 일으키기 때문이다.

Recovery from Deadlock

1. Process Termination
   1. Deadlock에 걸린 process를 다 종료시키고, 해당 process에 할당된 자원을 회수한다.
   2. Deadlock에 걸린 process들 중 하나씩 종료시키고, 자원을 회수하면서 deadlock이 풀릴때까지 해당 과정을 반복한다.

      → 그래서 누구부터 죽이는 것에 대한 기준이 필요함

      1. Priority of the process

      2. How long process has computed

      3. Resources the process has used

      4. Resources the process need to complete

💡

하지만, system이 inconsistent될 수 있다는 측면에서 쉬운 방법은 아니다.

2. Resource Preemption
   1. Selecting a victim

      → 어떤 process의 어떤 자원을 preempt시켜야할지를 결정해야 한다.

      → 일반적으로는 cost가 적은 것을 기준으로 한다.

   2. Rollback
   3. Starvation

      → 하지만 starvation에 대한 부분도 생각해야 한다. 동일한 process가 계속해서 victim으로 지정될 수 있기 때문이다.