[Operating System] Deadlock
이번 포스팅에서는 Concurrency 하게 프로세스를 운영하면서 생길 수 있는 데드락 문제에 대해서 알아보겠습니다.
데드락이란 무엇인가?
사전 상으로 "교착 상태" 를 의미하며, OS 에서 이르는 데드락의 의미는 둘 이상의 프로세스가 서로를 기다리며 아무것도 할 수 없는 상태를 의미합니다. 다음 그림과 같은 상황이 그렇습니다.
위 상태를, 각 프로세스의 진행상황에 따라 어떤 상황이 발생할 수 있는지 그래프로 나타내면 다음과 같습니다.
회색 구역으로 진입하는 3, 4 번의 flow 는 deadlock 입니다. 서로가 서로에게 필요한 자원을 점유하고 있기 때문에 시간이 흐르더라도 각 프로세스는 더이상 진행할 수 없습니다. 그 외의 1,2,5,6 의 상황은 각 프로세스가 원하는 자원을 즉시 받지 못할 뿐, 기다리면 다시 자원을 받을 수 있는 정상적인 block 상태입니다.
데드락은 왜 발생하는가?
데드락의 정의에 대해 알아보았으니, 데드락이 발생하는 원인에 대해서 알아봅시다. 데드락이 발생하는 조건 4가지는 다음과 같습니다.
위 네가지 조건이 모두 충족될 때 데드락이 발생합니다.
데드락을 해결하는 방법
먼저, 데드락을 예방하는 방법부터 알아보겠습니다. 앞서 나와있듯이 이 방법은 Computational Overhead 가 커서 사용하지 않습니다.
데드락을 예방하기 위해서 데드락의 발생 조건 4가지를 깨뜨리는 방법을 고려할 수 있습니다. 하지만 위 그림에 나와있듯이 깰 수 없을만큼 치명적인 Side Effect 이 있거나, 매우 불편한 경우들이 대부분입니다.
이 외에도 Banker's Algorithm 등을 통해 데드락이 일어나지 않도록 프로세스를 운용하는 방법이 있지만, overhead 가 크거나, utilization 을 떨어뜨리거나, 특정한 제약 조건 내에서만 쓸 수 있는 한계로 인해 잘 사용하지 않습니다.
데드락이 발생한 경우 다음과 같은 방법을 통해 해결할 수 있습니다.
이와 같이 데드락을 예방하거나, 해소할 수 있는 방법이 없는 것은 아닙니다. 다만, 현대의 OS 에서는 데드락이 발생하는 확률이 극히 낮고, 이 때 수동으로 해결해주는 것이 더 빠르고 computational cost 가 적게 들기 때문에 데드락을 예방/해소하는 알고리즘을 사용하지는 않습니다.