학습 목표 및 학습 내용

학습 목표

• 데드락의 개념을 설명할 수 있다.
• 데드락의 발생 조건을 설명할 수 있다.
• 데드락의 처리 방안을 설명할 수 있다.

학습 내용

• Deadlock concept
• Deadlock characterization
• Methods for handling deadlocks
• Deadlock prevention
• Deadlock avoidance
• Deadlock detection and recovery

What is deadlock?

A semaphore usage example

Deadlock

• For a set of blocked processes, each is holding a resource and waiting to
  acquire a resource held by another process in the set.

Deadlock Characterization

System modeling

• Processes: P1, P2, … Pn.
• Resource types: R1, R2, …, Rm
  • CPU cycles, memory space, I/O devices, files, etc.
• Each resource type Ri has Wi instances.
• Each process utilizes a resource as follows.
  • request
  • use
  • release

Deadlock Characterization

Deadlock can arise if four conditions hold simultaneously.

• Mutual exclusion
  • Only one process at a time can use a resource.
• Hold and wait
  • A process holding at least one resource is waiting to acquire additional resources held by other processes.
• No preemption
  • A resource can be released only voluntarily by the process holding it.
• Circular wait
  • There exists a set {P0, P1, …, P0} of waiting processes such that
    • P0 is waiting for a resource that is held by P1,
    • P1 is waiting for a resource that is held by P2,
    • …,
    • Pn–1 is waiting for a resource that is held by Pn, and
    • Pn is waiting for a resource that is held by P0.

데드락(deadlock)은 여러 프로세스가 서로 필요한 자원을 소유하고 있어, 어떤 프로세스도 진행하지 못하는 상태를 말합니다. 이는 시스템의 공유 자원에 대한 경쟁 때문에 발생하며, 일반적으로 모든 프로세스가 무한정 대기 상태에 빠지게 됩니다.

그림에서는 세마포어를 사용하여 동기화된 프로세스 간의 자원 공유를 설명하고 있습니다. 세마포어는 운영체제의 핵심 기능 중 하나인 동시성 제어를 위한 도구로, 프로세스간의 상호 배제(mutual exclusion)를 보장하는데 사용됩니다. 이런 동기화 메커니즘이 없으면 여러 프로세스가 동일한 자원에 동시에 접근하여 데이터 불일치와 같은 문제가 발생할 수 있습니다.

데드락의 특성화는 시스템 모델링을 통해 이루어집니다. 여러 프로세스(P1, P2, … Pn)와 자원 유형(R1, R2, …, Rm)이 있고, 각 자원 유형 Ri는 Wi 인스턴스를 가집니다. 자원 유형에는 CPU 주기, 메모리 공간, I/O 장치, 파일 등이 포함될 수 있습니다. 각 프로세스는 요청, 사용, 해제의 순서로 자원을 활용합니다.

데드락은 다음 네 가지 조건이 동시에 충족될 때 발생할 수 있습니다.

상호 배제(Mutual Exclusion): 한 번에 한 프로세스만이 자원을 사용할 수 있습니다. 이는 두 프로세스가 동시에 동일한 자원에 액세스할 수 없음을 의미합니다.

보유 및 대기(Hold and Wait): 자원을 이미 보유하고 있는 프로세스가 다른 프로세스가 보유하고 있는 추가 자원을 획득하기 위해 대기하고 있습니다.

비선점(No Preemption): 자원은 그것을 보유하고 있는 프로세스가 자발적으로만 해제할 수 있습니다. 다른 프로세스가 그 자원을 강제로 빼앗을 수 없습니다.

원형 대기(Circular Wait): P0, P1, …, Pn의 대기 프로세스 집합이 존재하여 P0는 P1이 보유한 자원을, P1은 P2가 보유한 자원을 기다리고, 마지막으로 Pn은 P0가 보유한 자원을 기다

Deadlock Characterization

• Resource allocation graph
  • V is partitioned into two types.
    • P = {P1, P2, …, Pn}, set of all processes in the system.
    • R = {R1, R2, …, Rm}, set of all resource types in the system.
  • E is also partitioned into two types.
    • Pi → Rj : request
    • Rj → Pi : assignment
• Examples
  • Pi requests an instance of Rj
    
  • Pi is holding an instance of Rj
    

Deadlock Characterization

• Deadlock examples with resource allocation graph
  
  (a)deadlock(X) ↑
  
  (b)deadlock(O) ↑
  
  (c)deadlock(X) ↑

If graph contains no cycles, no deadlock.
If graph contains a cycle, if only one instance per resource type, deadlock.
If graph contains a cycle, if several instances per resource type, possibility of deadlock.

데드락의 특성화는 자원 할당 그래프(Resource Allocation Graph)를 통해 시각화될 수 있습니다. 이 그래프는 시스템 내의 프로세스와 자원 간의 관계를 표현하며, 자원 요청과 자원 할당에 대한 정보를 제공합니다.

자원 할당 그래프에서는 정점(V) 집합이 두 부분으로 나눠집니다:

1. P = {P1, P2, …, Pn} : 시스템 내의 모든 프로세스 집합
2. R = {R1, R2, …, Rm} : 시스템 내의 모든 자원 유형 집합

마찬가지로, 간선(E) 집합도 두 부분으로 나눠집니다:

1. Pi → Rj : 프로세스 Pi가 자원 유형 Rj를 요청
2. Rj → Pi : 자원 유형 Rj가 프로세스 Pi에 할당

이 그래프의 예를 들면, Pi가 Rj의 인스턴스를 요청하는 경우에는 Pi에서 Rj로 화살표가 그려지고, Pi가 Rj의 인스턴스를 보유하고 있는 경우에는 Rj에서 Pi로 화살표가 그려집니다.

데드락이 발생한 경우도 이 그래프를 통해 확인할 수 있습니다. 데드락이 발생하지 않은 경우(그래프에 사이클이 없는 경우), 데드락이 발생한 경우(자원 유형당 인스턴스가 하나만 있고 그래프에 사이클이 있는 경우), 그리고 데드락이 가능성이 있는 경우(자원 유형당 여러 인스턴스가 있고 그래프에 사이클이 있는 경우)를 구별할 수 있습니다.

이러한 데드락 상황은 시스템의 성능을 저하시키며, 그래프 알고리즘, 데드락 방지 정책, 데드락 회피 알고리즘 등 다양한 방법으로 해결하려는 많은 연구가 진행되고 있습니다.

Methods for Handling Deadlocks

• Prevention
  • The system will never enter a deadlock state.
  • It ensures that at least one of four conditions cannot hold.
• Avoidance
  • The system will never enter a deadlock state.
  • It requires a priori information about how each process will utilize resources.
• Detection and recovery
  • It allows the system to enter a deadlock state and then recover.

Deadlock Prevention

• Ensures that at least one of four conditions cannot hold.
• Mutual Exclusion
  • is impossible to deny the mutual exclusion.
• Hold and Wait
  • requires process to request and be allocated all its resources before it begins execution.
• No Preemption
  • If a process holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.
  • Process will be restarted only when it can regain its old resources as well as the new ones that it is requesting.
• Circular Wait
  • imposes a total ordering of all resource types, and requires that each process requests resources in an increasing order of enumeration.
    

데드락을 처리하는 방법에는 주로 세 가지가 있습니다: 예방(Prevention), 회피(Avoidance), 그리고 탐지 및 복구(Detection and Recovery).

1. 예방(Prevention): 이 방법은 시스템이 데드락 상태에 진입하는 것을 막습니다. 데드락의 네 가지 조건 중 적어도 하나가 만족되지 않도록 보장합니다.

2. 회피(Avoidance): 이 방법 또한 시스템이 데드락 상태에 진입하는 것을 막습니다. 이 방법은 각 프로세스가 자원을 어떻게 활용할지에 대한 사전 정보가 필요합니다.

3. 탐지 및 복구(Detection and Recovery): 이 방법은 시스템이 데드락 상태에 진입하는 것을 허용하고, 그 후 복구합니다.

데드락 예방의 기본 전략은 데드락의 네 가지 필수 조건 중 하나 이상이 충족되지 않도록 하는 것입니다:

상호 배제(Mutual Exclusion): 이 조건을 부정하는 것은 불가능합니다. 자원은 동시에 두 개 이상의 프로세스에 의해 공유될 수 없습니다.

보유 및 대기(Hold and Wait): 이 조건을 부정하려면, 프로세스가 실행을 시작하기 전에 필요한 모든 자원을 요청하고 할당받아야 합니다.

비선점(No Preemption): 이 조건을 부정하려면, 프로세스가 보유하고 있는 일부 자원을 요청하고 즉시 할당받지 못하는 경우, 현재 보유하고 있는 모든 자원을 해제해야 합니다. 프로세스는 이전에 보유하고 있던 자원과 새롭게 요청한 자원을 모두 재획득할 수 있을 때만 재시작됩니다.

원형 대기(Circular Wait): 이 조건을 부정하려면, 모든 자원 유형에 대해 전체 순서를 부여하고, 각 프로세스가 열거 순서가 증가하는 방식으로 자원을 요청해야 합니다. 이는 자원을 요청하는 순서를 정하여 원형 대기를 방지하는 것입니다.

이런 방법들을 이용하면 데드락을 예방하거나 회피할 수 있지만, 완벽한 해결책은 아닙니다. 각 방법은 자원 사용의 효율성, 시스템 성능, 그리고 복잡성 등을 고려해야 하는 trade-off들을 가지고 있습니다.

예를 들어, 데드락 예방을 위해 모든 자원을 미리 요청하도록 강제하는 것은 실행 전에 모든 필요한 자원을 알 수 있어야 하므로, 프로그래밍이 더 복잡해질 수 있습니다. 또한, 필요한 모든 자원을 미리 할당받는 방식은 자원의 효율성을 저하시킬 수 있습니다. 왜냐하면 프로세스가 모든 자원을 사용하기 전에는 그 자원들이 놀게 되기 때문입니다.

비선점 방식을 사용하는 경우, 프로세스가 자원을 해제하고 재시작하는 데 필요한 비용이 커질 수 있습니다. 이는 특히, 그 프로세스가 많은 양의 계산을 수행한 후에 자원을 요청하고 이를 즉시 할당받지 못했을 때 문제가 될 수 있습니다.

마지막으로, 원형 대기를 방지하기 위해 자원에 전체 순서를 부여하는 방법은 프로그래밍 복잡성을 증가시키며, 모든 상황에서 적용할 수 있는 순서를 정하는 것이 어려울 수 있습니다.

따라서, 이들 방법 각각은 데드락 문제를 해결하기 위한 다양한 접근 방식을 제공하지만, 각각의 장단점을 고려하여 적절한 전략을 선택해야 합니다.

Deadlock Avoidance

• Deadlock avoidance algorithm
  • When a process requests an available resource, system must decide if the immediate allocation leaves the system in a safe state.
    • A state is in safe, if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock.
  • It requires that the system has some additional a priori information available.
• If a system is in safe state,
  • No deadlocks.
• If a system is in unsafe state,
  • Possibility of deadlock.

• Resource allocation graph
  • Claim edge Pi → Rj
    • Pj may request Rj.
    • It is represented by a dashed line.
  • Claim edge is converted to request edge,
    • when a process requests a resource.
  • Request edge is converted to assignment edge,
    • when the resource is allocated to the process.
  • Assignment edge is reconverted to claim edge,
    • when a resource is released by a process.
• [Note]
  • When multiple instances of a resource type, use the banker’s algorithm.
• Unsafe state example
  

데드락 처리에 대한 추가 전략으로는 회피(Avoidance) 와 탐지 및 복구(Detection and Recovery)가 있습니다.

데드락 회피(Deadlock Avoidance): 이 전략은 프로세스가 사용 가능한 자원을 요청할 때 시스템이 즉시 자원을 할당한 후에도 시스템이 안전 상태에 있는지 결정해야 합니다. 안전 상태란, 시스템이 데드락을 피하면서 어떤 순서로든 각 프로세스에 자원을 할당할 수 있는 상태를 말합니다. 이를 위해 시스템은 일부 추가적인 사전 정보가 필요합니다.

안전 상태에 있는 시스템에서는 데드락이 발생하지 않습니다. 반면, 불안전 상태에 있는 시스템에서는 데드락이 발생할 가능성이 있습니다. 하지만 불안전 상태는 반드시 데드락을 의미하는 것은 아닙니다.

자원 할당 그래프에서는 "Claim edge"라는 개념을 사용하여 데드락 회피를 돕습니다. Claim edge는 프로세스 Pi가 자원 Rj를 요청할 수 있다는 것을 나타냅니다. 이는 점선으로 표시됩니다. 프로세스가 자원을 요청하면 Claim edge는 Request edge로 변환되며, 자원이 프로세스에게 할당되면 Request edge는 Assignment edge로 변환됩니다. 프로세스가 자원을 해제하면 Assignment edge는 다시 Claim edge로 변환됩니다. 이러한 과정을 통해 시스템이 안전 상태를 유지할 수 있도록 돕습니다.

Deadlock Detection & Recovery

• Allow system to enter deadlock state.
• Detection algorithm.
  • Periodically invoke an algorithm that searches for a cycle in the graph.
    • If there is a cycle, there exists a deadlock.
  • [Note] When multiple instances of a resource type, use more complicated algorithm.
• Recovery scheme.
  • Process termination
    • Abort all deadlocked processes.
    • Abort one process at a time until the deadlock cycle is eliminated.
  • Resource preemption
    • Preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken.

데드락 탐지 및 복구(Deadlock Detection and Recovery): 이 전략은 시스템이 데드락 상태에 진입하는 것을 허용하고, 그 후 복구하는 방법을 사용합니다.

데드락 탐지(Deadlock Detection): 이 알고리즘은 그래프 내에서 주기적으로 사이클을 찾는 알고리즘을 호출합니다. 만약 그래프 내에 사이클이 있으면 데드락이 존재한다는 것을 의미합니다. 이 알고리즘을 수행하는데에는 자원 및 시스템의 복잡성에 따라 시간이 걸릴 수 있습니다. 또한, 여러 개의 자원 인스턴스를 처리하려면 더 복잡한 알고리즘이 필요합니다.

데드락 복구(Deadlock Recovery): 데드락이 탐지되면 시스템은 데드락을 해결하기 위해 두 가지 주요 전략을 사용할 수 있습니다.

• 프로세스 종료(Process Termination): 이 접근법은 모든 데드락 프로세스를 강제 종료하거나, 데드락 사이클이 제거될 때까지 한 번에 하나의 프로세스를 종료하는 방법을 사용합니다. 이러한 접근법은 단순하고 명확하지만, 프로세스 종료는 사용자에게 불편을 줄 수 있고, 완료되지 않은 작업을 잃게 만들 수 있습니다.
• 자원 선점(Resource Preemption): 이 접근법은 데드락에 연루된 프로세스로부터 일부 자원을 선점(강제로 빼앗음)하고, 이러한 자원을 다른 프로세스에게 할당하여 데드락 사이클이 깨지도록 하는 방법입니다. 이 방법은 일부 프로세스가 진행을 계속할 수 있도록 해주지만, 자원을 선점하고 재분배하는데에는 비용이 들며, 또한 데드락을 완전히 제거하려면 여러 번의 선점 및 재분배가 필요할 수 있습니다.

이 두 가지 방법 모두 시스템의 특성과 요구사항, 그리고 이용 가능한 자원에 따라 다른 결과를 가져올 수 있으므로 주의해서 선택해야 합니다.

Summary

• Deadlock is a situation that processes are waiting indefinitely for event that is caused by waiting process.
• Deadlock can arise if four conditions; mutual exclusion, hold and wait, no preemption, and circular wait hold simultaneously.
• Deadlock prevention ensures that at least one of four conditions cannot hold.
• Deadlock avoidance ensures that a system will never enter an unsafe state.
• Deadlock detection and recovery allows system to enter deadlock state.

요약

데드락은 프로세스들이 대기하는 이벤트가 다른 대기 중인 프로세스에 의해 발생되어 무한히 대기하는 상황을 말합니다. 이것은 프로세스들이 필요한 자원을 얻지 못해 실행을 계속할 수 없게 되는 상태를 나타냅니다.

데드락은 4가지 조건이 동시에 충족될 때 발생합니다. 이 조건들은 상호 배제(mutual exclusion), 점유 및 대기(hold and wait), 비선점(no preemption), 그리고 순환 대기(circular wait)입니다.

데드락 예방(Deadlock Prevention)은 이러한 네 가지 조건 중 적어도 하나가 충족되지 않도록 보장함으로써 데드락을 방지하는 방법을 의미합니다. 예를 들어, 시스템은 프로세스가 자원을 요청할 때마다 그 요청이 데드락을 일으킬지 아닐지를 검사하고, 데드락이 발생할 가능성이 있다면 그 요청을 거부합니다.

데드락 회피(Deadlock Avoidance)는 시스템이 '안전하지 않은 상태(unsafe state)'로 진입하지 않도록 보장하는 것을 의미합니다. 여기서 '안전한 상태(safe state)'는 시스템이 데드락 없이 모든 프로세스를 계속 실행할 수 있는 상태를 의미합니다. 데드락 회피 알고리즘은 프로세스가 자원을 요청할 때마다, 그 요청을 승인하는 것이 시스템을 안전하지 않은 상태로 이끌지 않는지를 검사합니다.

데드락 탐지 및 복구(Deadlock Detection and Recovery)는 시스템이 데드락 상태에 진입하는 것을 허용한 다음, 데드락을 탐지하고 복구하는 방법을 사용합니다. 데드락이 발생하면 시스템은 데드락에 연루된 프로세스를 종료하거나, 필요한 자원을 선점하여 데드락을 해결합니다.