---

Deadlock

✔️ Deadlock

쓰레드(or 프로세스)가 요청한 리소스가 다른 쓰레드(or 프로세스)에 점유되어 있고 다른 쓰레드 또한 리소스를 기다리는 상태를 변경할 수 없는 상황

✔️ Deadlock 필수 조건

Mutual Exclusion

최소한 하나의 자원은 비공유 모드로 점유되어야한다

Hold and wait

쓰레드는 최소한 하나의 자원을 소유한 상태에서 다른 쓰레드에 점유된 리소스를 추가로 얻기 위해 대기해야 한다

No preemption

리소스는 선점할 수 없어야 한다

Circular wait

대기하는 쓰레드는 의존성 그래프가 원형 상태여야 한다

그래프가 사이클을 포함하지 않으면 데드락이 아니다. 그래프가 사이클을 포함하면 데드락 일수도 있고 아닐 수도 있다. 사이클에서 리소스 인스턴스가 정확하게 하나의 인스턴스만 가지면 데드락이다. 사이클이 존재할 때 리소스 인스턴스가 여러개이면 반드시 데드락이 발생한다는 것은 아니다.

---

Deadlock Handling

✔️ Deadlock prevention

데드락 필수 조건 4가지 중 최소한 하나라도 발생하지 않도록 방지한다

• Mutual Exclusion -> 불가능

  • 모든 리소스를 sharable 하게 할 수 없다

• Hold and wait -> 불가능

  • 리소스는 유한하기 때문에 어떤 프로세스가 hold하면 다른 프로세스는 대기해야 한다.

• No preemption -> 불가능

  • 모든 리소스를 선점하게 할 수 없다

• Circular wait -> 가능

  • 리소스에 번호를 매겨서 쓰레드가 점유하고 있는 리소스의 번호보다 높은 리소스만 요청하도록 할 수 있다.
    • 락킹을 다양하게 획득할 수 있으면, 데드락 방지를 보장하지 않는다(동기화 문제)

단점

디바이스 효율을 떨어뜨리고 시스템 처리율을 줄인다

✔️ Deadlock avoidance

• 미래에 발생할 수 있는 데드락을 회피하는 방법이다
  • 해당 요청이 데드락을 발생하는 요청이라면 대기시키고, 데드락을 발생시키지 않는 요청이라면 받아들인다.
• 프로세스가 실행될 동안 사용할 자원에 대한 부가적인 정보가 필요하다

✅ Safe State

특정한 순서로 각각의 쓰레드에게 쓰레드가 필요로 하는 리소스를 할당할 수 있을때 데드락을 회피할 수 있다.

• 이 때의 특정한 순서를 safe sequence라고 하고, safe sequence가 존재할 때 safe state라고 한다
  • safe state 일 때는 데드락이 발생하지 않는다.
  • unsafe state 일 때는 데드락이 발생할 수 도 있다.
• 데드락을 회피하려면 safe state 임을 보장하면 된다
  • safe sequence를 결정할 수 있으면 요청을 받아들인다

✅ RAG

자원 인스턴스가 1개일 때는 RAG 그래프에서 claim edge(쓰레드의 미래 요청)를 그래프에 추가하여 Cycle Detection을 통해 데드락을 회피한다.

• RAG에서 Cycle Detection 하면 요청을 wait
• RAG에서 Cycle Detection 하지 않으면 요청을 grant

단점

RAG는 리소스의 인스턴스가 여러개일 경우 데드락 회피에 적용할 수 없다

✅ Banker's Algorithm

리소스의 인스턴스가 여러개일 경우 Banker's 알고리즘을 적용한다

자료구조

• Available = 가용한 자원 타입 개수 벡터

  • Available[j]==k = R(j)의 K개 인스턴스가 사용가능하다

• Max = 각각의 쓰레드의 맥시멈 요청 행렬

  • Max[i][j]==k = T(i)는 R(j)의 최대 k개 인스턴스가 필요하다

• Allocation = 현재 각각의 쓰레드에게 할당된 리소스 개수 행렬

  • Allocation[i][j]==k = T(i)는 현재 R(j)의 K개 인스턴스를 할당받았다

• Need = 각각의 쓰레드에게 필요한 리소스 개수 행렬

  • Need[i][j]==k = T(i)는 현재 R(j)의 K개 인스턴스를 필요로 하다

Safety algorithm

시스템 스냅샷이 safe한지 아닌지 판별하는 알고리즘

• 1. Initialize
  • Work 벡터 = Available
  • Finish[n] 벡터 = false (n=쓰레드)

• 2. Find i
  • Finishi[i]==false
  • Need(i)<=Work

• 3. Update Work
  • Work = Work + Allocation(i)
  • Finishi[i]=true
  • Go step 2
• 4. Check
  • if Finish[i] == true for all i
  • then system is safe state

Resource-Request algorithm

새로운 리소스 요청이 들어왔을 때 시스템 스냅샷이 safe한지 아닌지 판별하는 알고리즘

• 1. Check Request(i) <= Need(i)
• 2. Check Request(i) <= Available(i)
• 3. Request(i) 적용
  • Available = Available - Request(i)
  • Allocation(i) = Allocation(i) + Request(i)
  • Need(i) = Need(i) - Request(i)
• 4. Safety 알고리즘 적용

단점

• RAG 보다 덜 효율적이고 더 복잡하다
• 시스템에 부하를 준다

✔️ Deadlock detection and recovery

• 데드락이 발생하는 것을 허용하고, 발생했을 때 recovery하는 방식
• Detection을 매 요청마다 할 것인지 일정한 주기로 할것인지 선택해야 한다.

✅ Deadlock detection

리소스 인스턴스가 1개일 때

Wait-for-graph를 유지하고, 주기적으로 싸이클을 확인한다

Wait-for-graph

RAG에서 리소스를 제외한 Dependency graph

리소스 인스턴스가 여러개일 때

banker's 알고리즘과 비슷하게 수행한다.

✅ Deadlock recovery

• Process and Thread Termination

  • 데드락과 관련된 쓰레드를 모두 종료하거나
  • 데드락이 제거될 때까지 프로세스 하나씩 종료한다

• Resource Preemption

  • victim(선점될 쓰레드)을 선택한다

✔️ Ignore Deadlock

• 데드락이 발생 확률을 낮게 보고, 데드락 처리하는 것을 무시한다.