운영체제 Ch8 - 데드락

데드락이란?

데드락: 자원을 다른 대기 스레드가 점유하고 있어서 대기 스레드가 다시는 자신의 상태를 변화하지 못하는 상태.

데드락의 특성

4가지 필수조건

1. 상호배제

2. 점유와 대기: 스레드가 실질적으로 자원을 점유하고 있어야 한다.

3. 비선점: 자원이 선점 불가능할 때만 데드락이 일어날 수 있다.

4. 원형대기

RAG(Resource Allocation Graph)

RAG: 데드락을 정확히 표현하기 위해 나타낸 directed graph.

 

- request edge
T -> R로 나타내며 스레드가 자원을 요청한다는 뜻이다.

 

- assignment edge

R -> T로 나타내며 자원을 할당받은 상태를 나타낸다. 

 

아래의 그림과 같이 RAG를 그려봄으로써 데드락을 시각적으로 쉽게 확인할 수 있다.

하지만 사이클을 가지고 있다고 무조건 데드락인 것은 아니다. 아래의 RAG와 같이 다수의 인스턴스를 가지고 있다면 사이클을 가지고 있어도 데드락이 일어나지 않을 수 있다.

데드락 핸들링 방법

Deadlock Prevention

Deadlock prevention: 데드락이 일어나지 않게 미리 예방함으로써 데드락을 다루는 방법이다. 위에서 살펴본 데드락 필수조건 4가지 가운데 하나만 막아도 데드락을 예방할 수 있다.

 

상호배제, 점유와 대기, 비선점을 막을 수도 있지만 불가능하기도 하고 굉장히 비효율적이기 때문에 원형대기를 막는 방법이 그나마 가장 효과적이다. 원형대기는 모든 자원에 순서를 부여하여 사이클이 생기지 않게 막는다. 하지만 이것 조차도 데드락을 막는 것을 완전히 보장할 수 없고 시스템으로 비효율적이다. 따라서 예방보다는 회피를 사용하는 방향이 효과적이다.

Deadlock Avoid

Deadlock Avoid: 리퀘스트를 받아주기 전에 미래의 데드락을 막기 위해 스레드를 잠시 대기시킨다. 선행 정보로 데드락을 예측하고 이를 회피하는 것이다. 선행 정보에는 최대 자원 개수, 가용 자원 개수, 할당 자원 개수가 있다. 이를 이용하여 데드락이 발생하는지 미리 알아보고 일어나지 않는다면 리퀘스트를 받고, 일어난다면 회피하는 것이다.

Safe State

만약 시스템이 데드락을 피해서 모든 리소스를 할당해줄 수 있는 순서가 존재한다면 safe하다고 말한다. 그러한 safe sequence를 찾는 것이 핵심이다.

 

아래 그림에서 보다시피 safe 영역에 있다면 데드락은 절대 일어나지 않는다. 하지만 주의할 것은 unsafe하다고 무조건 데드락이 일어나는 것이 아니다. unsafe하지만 데드락이 일어나지 않을 수도 있다.

우리는 데드락을 보장하기 위해서 항상 안전지대에 존재하도록 해야 한다.

RAG를 이용한 데드락 회피

Claim edge: 리퀘스트를 미리 보내서 데드락이 일어나는지 확인하는 edge.

 

claim edge를 미리 RAG에 넣어보고 만약 사이클이 발생하지 않으면 승인하고, 사이클이 발생한다면 사이클 디텍션을 통해 데드락을 회피한다.

claim edge를 이용한 safe 상태 확인

하지만 인스턴스가 여러 개 있는 복잡한 시스템에서는 이러한 방법을 이용할 수 없다. 따라서 Banker's Algorithm을 이용한다.

Banker's Algorithm

은행원 알고리즘은 이론으로만 보기엔 너무 복잡하고 이해할 수 없어서 직접 문제를 해결해보며 이해하는 것이 좋다. 기본적으로 4가지 구조를 가지고 있다.

 

- Available: 가용 자원 개수

- Max: 각 스레드가 필요한 최대 자원 개수

- Allocation: 스레드에 할당된 자원 개수

- Need: 각 스레드가 남은 필요 자원 개수

 

Safety Algorithm

Safety Algorithm은 말 그대로 safe한지 알아보는 알고리즘이다. 

 

예를 들어 5개의 스레드와 3개의 자원이 있고, A, B, C 각 인스턴스가 10, 5, 7개 있다고 해보자.

safe 알고리즘을 간략하게 정리해보면 다음과 같다.

 

1. work를 available과 똑같이 초기화한다. (3 3 2)
각 스레드의 finish를 모두 false로 만든다. (f f f f f)
2. finish=false && need <= work 인 것에 대해
3. work = work + alloc 하고 해당하는 스레드의 finish를 true로 만든다.
4.  2, 3번을 계속 반복하고 finish가 모두 true가 되면 안전상태가 된 것이다.  

 

Resource-Request Algorithm

Resource-Request Algorithm은 어떤 리퀘스트가 주어졌을때 요구 자원이 필요 자원과 가용 자원보다 적은지 판단하고  safe 알고리즘을 통해 safe하면 승인하고 아니면 승인하지 않는다.

 

1. Request <= Need라면 2번으로 이동.

2. Request <= Available이라면 3번을 수행.

3. Available = Available - Request

Allocation = Allocation + Request

Need = Need - Request

Deadlock Detection

예방도 그렇지만 회피 또한 일일이 데드락 상태를 점검해야 하고 또한 점검하여도 아닐 가능성이 있다(unsafe 상태라고 무조건 데드락인 것은 아니니까). 이는 시스템에 굉장히 부담을 줄 수 있다. 따라서 정말 데드락 문제가 중요한 시스템이 아니라면 그냥 감시하고 감지되면 해결하는게 나을 수 있다.

 

Detection Algorithm

Detection Algorithm은 기본적으로는 Safety Algorithm과 비슷하다.

 

1. work를 available과 똑같이 초기화한다. (3 3 2)
각 스레드의 finish를 모두 false로 만든다. (f f f f f) 하지만 Allocation이 0이라면 true로 한다.
2. finish=false && Request <= work 인 것에 대해
3. work = work + alloc 하고 해당하는 스레드의 finish를 true로 만든다.
4.  2, 3번을 계속 반복하고 finish가 모두 true가 되면 안전상태가 된 것이다. 

 

Detection 알고리즘을 언제 발생시켜야 하는지는 데드락이 얼마나 자주 일어나는 시스템인지, 스레드가 얼마나 많은지에 따라 다르다. 데드락이 자주 일어나는 시스템일수록 자주 디텍션을 해주어야 한다(사실 자주 일어난다면 애초에 시스템 자체를 잘못 만든 것). 또한 스레드가 많을 수록 데드락이 일어날 확률이 높아지므로 스레드의 개수에 비례하여 디텍션 알고리즘을 실행한다.

Deadlock Recovery

- 프로세스(스레드)를 강제 종료

상황에 따라 모두 종료할 수도 있고, 하나만 종료할 수도 있다.

 

- 자원 선점

가장 비용이 낮은 스레드를 선점시킬 수도 있다. 하지만 이렇게 하면 기아 문제가 발생할 수 있으니 선점할 수 있는 횟수를 제한하여 이를 막을 수 있다.