데드락 (Deadlock)

1. 데드락이란?

 

출처 : https://www.reddit.com/r/pics/comments/6qulze/traffic_deadlock/

 

위의 그림과 같은 상황에서 교통정리를 한다고 생각해보라.

 

아무리 생각해봐도 서로 너무나 강력하게 맞물려있어서 해결방법이 도저히 떠오르지 않을거다. 바로 이런 상황이 데드락(deadlock)이라고 하는 것이다.

 

이번에는 컴퓨터 관점에서 데드락을 생각해보자.

 

deadlock

 

위와 같은 흐름으로 동작하는 프로그램이 있다고 가정해보자.

 

쓰레드0은 B가 풀릴때까지 A를 잡고있을 것이고, 쓰레드1은 A가 풀릴때까지 B를 잡고있을 것이다. 결국 서로 아무런 진행도 하지 못한 채, 오도가도 못하는 상황에 빠지게 되는데 이것이 바로 데드락이다.

 

 

 

2. 데드락의 발생

 

그렇다면, 어떤 경우에 데드락이 발생할까? 데드락이 발생가능한 경우는 다음과 같다.

 

1) Task들이 서로 한개 이상의 리소스를 요청할 때.

2) 어떤 Task가 리소스를 잡고있는 상태에, 다른 task가 그 리소스를 기다리고 있는 경우에 발생.

 

아까 살펴보았던 예제 에서는 1) 쓰레드0이 A와 B 두개의 리소스를 요청했고, 2) 쓰레드0이 A를 잡고있는 상태에, 쓰레드1이 A를 기다리고 있었기 때문에 발생한 것이다.

 

이렇게 간단한 예제에서도 데드락이 발생하는데, 실제 더 복잡한 프로그램에서는 굉장히 빈번하게 데드락이 발생한다.

 

 

 

3. 데드락의 조건

 

데드락은 아래 4가지조건이 모두 성립하면 발생 가능하다.

 

1) Mutual exclusion

- 하나의 리소스는 하나의 task만 사용 가능하다.

 

2) Hold and Wait

- task는 다른 task가 사용중인 리소스를 기다릴 때, 자신이 잡은 채로 기다린다.

 

3) No preemption

- 리소스는 처리되기 전에 release 되지 않는다.

 

4) Circular wait

- task들이 circular하게 wait하는 경우.

 

 

 

4. 데드락 해결 전략들

 

이렇게 생기는 데드락을 해결하기 위한 전략으로는 크게 4가지가 있다.

 

1) Deadlock prevention

2) Deadlock avoidance

3) Deadlock detection and recovery

4) Just Ignore

 

1) 과 2) 방법은 데드락이 아예 발생하지 않도록 조절해주는 것이고, 3) 과 4) 방법은 데드락이 발생하더라도 그 후에 해결하도록 처리해주는 방법이다.

 

지금부터 하나씩 자세히 살펴보자.

 

 

• Deadlock prevention

데드락은 앞서 살펴본 4가지 조건들이 모두 만족해야만 발생가능하므로, 그 중 하나의 조건을 막아줌으로써 데드락을 방지하는 방법이다.

 

1) Mutual exclusion 조건 방지

- 리소스의 특성은 이미 정해진 것이라 바꾸기 힘들다.

 

2) Hold and wait 조건 방지

- 그 task가 필요한 리소스들을 미리 한번에 다 잡고, 다 잡히면 시작하는 방식 (하나라도 못잡으면 시작x)

- 나름 괜찮은 방법이나, resource utilization이 낮아지고, starvation이 발생 가능하다.

 

3) No preemption 조건 방지

- preemption 하게 동작시키면 되지만, 맘대로 바꾸기 힘들다.

 

4) Circular wait 조건 방지

- 각 task 마다 필요한 모든 리소스들을 특정 기준대로 줄을 세우고 (total ordering) 줄세워진 순서대로 처리하는 방식.

- 모든 task가 같은 조건으로 줄을 세웠기 때문에 서로 Circular하게 맞물리는 일이 방지된다.

 

이렇게 조건들 중 하나를 막아주는 방식으로 데드락을 방지할 수 있다.

 

이 때, 데드락이 발생하는지 판단하려면 witness라는 것을 이용하면 된다.

 

 

• Deadlock Avoidance

데드락이 발생할 것 같으면 리소스를 할당 해주지 않고, 데드락이 발생하지 않을 것 같으면 리소스를 할당해주는 방법.

 

safe & unsafe

 

위의 그림에서 알 수 있듯이, 데드락은 Unsafe한 구간에서만 발생한다. 즉, 데드락을 피하고 싶으면, Safe한 구간에만 리소스를 할당해주면 되는 것이다.

 

여기서 Safe 구간이란, 리소스를 각 task에게 할당해주었을 때, 모든 task가 요청을 완료할 수 있는 상태이다.

 

이 때, safe하게 리소스를 할당해주는 순서를 safe sequence 라고 한다. 만약 safe sequence가 하나라도 있으면 그 구간은 safe 하다고 할 수 있다.

 

그렇다면 safe sequence를 찾는것이 핵심인데, 대표적인 방법으로는 Banker's Alogrithm이 있다. 이 알고리즘은 다음에 자세히 알아보자. (구글링 해봐라)

 

 

• Deadlock Recovery

데드락이 발생하면, 알아내고 (witness 등 이용) 복구하는 방법이다.

 

1) 관련 프로세스를 다 죽이거나 2) Preemption을 시켜주는 형태로 복구를 해준다.

 

대충 들어봐도 알 수 있듯이 그냥 노답인 방식이라 잘 쓰이진 않는다.

 

 

• Ignoring Deadlock

그냥 데드락 발생해도 일일히 다 처리해주지 않고 그냥 쌩까는 방식이다. 

 

왠지 핵노답일 것 같은 방법이지만, 놀랍게도 대부분의 OS에서는 데드락을 그냥 무시해버린다. OS가 일일히 다 데드락을 처리해주다보면, 너무 할일이 많아지기 떄문에 그냥 아이 못해먹겠네 하고 던져버리는 것이다.

 

즉, 프로그래머가 '알아서' 데드락 발생 안하게 잘 짜야한다. (살려줘)

 

 

오늘 배운 내용을 정리해보면,

 

1. 데드락은 프로그램이 리소스를 잡고 푸는 과정에서 오도가도 못하게 꽉 막혀버린 상황이다.

 

2. 데드락이 발생하기 위한 조건으로는 4가지가 있다.

 

3. 데드락을 해결하기 위한 방법으로도 4가지가 있다.

 

 

본 내용은 공부하며 정리한 것으로, 오류가 있을 수 있습니다.