[OS] Deadlocks

System Model

---

---

Deadlock이란?

• 모든 프로세스가 대기하고 있는 상태
• 해당 상태를 못 바꾼다. 다른 프로세스를 통해서 상태를 바꿔야하기에.
• 쓰레드가 리소스가 필요할 경우 동작 방식
  • Request - Use- Release 이며, Use단계에서 임계영역이 고려된다.

Dead lock 발생할 때의 필요한 조건

• 상호배제가 필요할 때
• Hold and Wait - 점유하고 대기를 할 때
• No preemption - 자원을 못 뺏어오고, 선점이 불가할 때
• Circular Wait - dependency 그래프가 순환할 때

 

Deadlock Characterization

---

---

Resource-Allocation Graph

• T→R - T가 인스턴스 R을 요구한다
• R→T - R이 T에 할당되어있다
• 데드락의 전형적인 예제
• 사이클이 생성되면, 데드락이 발생하고 사이클이 없어야 한다.

 

Methods for Handling Deadlocks

---

---

데드락 문제를 어떻게 다룰까?

• 발생안하길 기도하면서 무시한다.
• 데드락을 방지하거나 피하자
  • 방지하는 것은 굉장히 힘들다
  • 피하는것은 Banker's Algorithm을 사용하자
• 데드락이 발생하면, Detect를 하고 Recover를 하자

 

Deadlock Prevention

---

---

한 가지만 무조건 막자

• 상호배제
  • 적어도 하나의 리스트는 공유하지말자, 하지만 애초에 공유를 안하면 데드락이 발생안한다
• Hold and Wait
  • request를 할 때는 항상 hold 해둔 자원을 놔주자 → 실효성이 없다
• No preemption
  • 다른 홀딩 자원을 뺏어오자 → 실효성이 없다, 뺏긴 쓰레드가 문제를 일으킴
• Circular Wait
  • 해당 문제를 막는 것이 가장 실효성이 있다.
  • 누군가 자원을 들고있으면 내려놓고 기다리자
  • Ordering lock
    • 데드락은 막을 가능성은 있지만, starvation 발생.
    • 하지만 데드락 완벽히 막는다고 보장은 못한다

 

Deadlock Avoidance

---

---

리소스 request를 할 때, 미리 데드락 위험이 있는 지 확인하기

• 프로세스가 요구할 수 있는 최대 자원의 개수를 미리 파악해놓기
• 가능한 리소스, 할당된 리소스, 최대 리소스 개수를 알아놓는 것

Safe State

• safe squence라면 최대 자원을 할당해 줄 수 있다.
• safe state란 데드락이 안일어나는 sequence 상태이다.
• safe state를 벗어나는 요청이 온다면, request를 거절한다
• cycle detection
  • RAG에 claim edge를 집어넣어서 사이클이 생기면 거절, 없다면 수락

Banker's Algorithm

• RAG를 이용한 판단은 다중 인스턴스가 있다면 사용할 수 없다.
• RAG에 비해 비효율적이고 복잡하다
• Data structures
  • 쓰레드 : n, 리소스 : m
  • available : 이용 가능한 리소스타입의 개수를 가지고 있는 벡터
    • available[m] → m개 타입의 리소스 타입 선언
    • available[j] == k → j타입의 이용가능한 리소스가 k개 있다
  • Max : 쓰레드가 요구할 수 있는 최대 값의 행렬
    • Max[nm] → nm개의 행렬 선언
    • Max[i][j] == k → 쓰레드 i에서 j타입 리소스를 최대 k개 요구 할 수 있다
  • Allocation : 현재 할당되어 있는 리소스 개수
    • Allocation[i][j]
  • Need : 앞으로 요청할 리소스 개수
    • Need[i][j] = Max[i][j] - allocation[i][j]

Safety Algorithm

[1]

Work벡터 초기화 - available 가져오기

Finish벡터 초기화 - false로 초기화

[2]

Finish = false && need ≤ work인 경우

work = work + allocation

[3]

Finish = true

모든 Finish가 true면, safe state이다.

[예시]

1. i=0, need = (7,4,3) ≤ work(3,3,2)를 만족못하므로 기각
2. i=1, need = (1,2,2) ≤ workd(3,3,2)를 만족하므로, work += allocation
3. work = (5,3,2), finish t1 = True
4. i=2, 기각
5. i=3, 승인, work = (7,4,3)
6. i=4, 승인, work = (7,4,5)
7. i=0로 돌아가기, 승인, work = (7,5,5)
8. i=1로 돌아가기, 승인, work = (9,5,5)

1→3→4→2→0 은 safe sequence이기에 safe state를 만족하는 sequence 이다.

새로운 request가 들어올 경우, Resource-Request Algorithm

• Request ≤ Need, Request ≤ Available를 만족해야된다.
• 승인된경우, Request만큼 Need, Available이 줄어들며 Allocation늘어난다

 

Deadlock Detection

---

---

Detection

• prevent or avoid를 하지않으면 데드락이 발생할 수 있지만, 멀쩡한 Request도 거절하므로 시스템 부담이 크다.
• 데드락 상태를 허용해주는 대신 감시를하고 데드락에 빠진다면 회복을하자
• Single instance일 때는 RAG에서 자원을 뺀 Corresponding wait그래프로 싸이클을 확인하자

• Several Instances일 경우 Banker's algorithm을 응용한다.
  • Need 대신 request로 바꿔서 활용하며, Finish가 전부 true로 안된다면 데드락이 발생하는 것
• 요청을 수락하도록 냅두고, 주기적으로 알고리즘을 적용해서 확인 하는 것이다.
• 주기는 너무 느리면, 어떤 사이클에서 발생하는지 모르므로 적당하게 해야된다.

데드락 조치 방법

• 프로세스를 종료 시킨다. (전체 혹은 의심스러운 일부를)
• 코스트가 적은 희생자를 하나 선정해서 자원을 뺐는다 → 계속 걸리는 경우 기아문제가 발생할수있다