11. Deadlock

 

 

데드락(deadlock)은 프로그램이 만들어야 하는 적정한 progress를 만들지 못하는 현상을 말합니다. 데드락에 대한 연구는 굉장히 많이 진행되어 solution들이 다수 존재합니다. 하지만 이 solution들은 비용이 굉장히 비싸기 때문에 실제로는 거의 사용이 되지 않습니다.

 

데드락은 두 개 이상의 프로세스가 동작할 때 발생하며 프로세스들이 waiting state에 빠져 어떤 동작도 하지 못하게 됩니다. 왜 이런 일이 발생하냐면 서로가 서로에게 점유되어있는 리소스를 기다리기 때문입니다. 데드락 외에도 라이브락(livelock)이라는 현상이 있는데 라이브락의 경우 데드락과 다르게 CPU 사이클을 낭비하기 때문에 시스템에 주는 악영향이 더 큽니다.

 

라이브락은 spin lock을 통해서 발생할 수 있습니다. 데드락은 서로 얻지 못하는 것을 얻을 때까지 waitiging state에 들어가 서로 CPU를 양보하는 것이라면 라이브락은 서로 얻지 못하는 것을 얻을 때까지 spin lock을 돌며 CPU 사이클을 사용하는 것입니다. 

 

이렇게 프로세스가 꼬여서 발생하는 문제 중 무기한 연기(indefinite postponement)라는 문제가 존재합니다. 무기한 연기는 프로세스가 시스템 자원 스케줄링 정책 상 일어나지 않는 이벤트나 아니면 상당한 시간이 흐른 후 발생하는 이벤트를 기다리는 상태를 말합니다. (ex. 프로듀서가 수행이 종료되었지만 컨슈머가 데이터를 기다리는 현상 등)

 

 

 

데드락이 발생하려면 2개 이상의 프로세스 중 한 개가 어느 정도의 리소스를 점유하고 있는 상태에서 다른 프로세스가 점유하고 있는 리소스를 원해야 합니다. 이 과정에서 누구도 양보하지 않고 서로의 리소스를 원하는 상황이 데드락의 기본적인 형태가 됩니다.

 

위 사진은 프로세스0이 홀드한 세마포어 sema X가 x 리소스를 보호하고 있고 프로세스1이 홀드한 sema Y가 y 리소스를 보호하고 있습니다. 프로세스 0은 sema Y를 원하고 프로세스1은 sema X를 원하는 상황이 발생한 모습입니다..

 

프로세스는 직사각형, 리소스는 타원, 화살표는 할당된 프로세스를 가르키고 점선은 해당 리소스를 원하다는 것을 의미합니다. 프로세스와 리소스를 표현한 그래프를 resource allocation graph라고 부릅니다. 그래프 상에서 화살표들이 사이클을 이루면 데드락에 빠져있다고 합니다.

 

이렇게 그래프를 그리는 것을 통해서 바이너리 세마포어에 대한 데드락은 검출할 수 있습니다. 사이클이 발생하더라도 x 리소스가 여러 개의 인스턴스를 가진다면 사용할 수 있는 리소스 여분이 있기 때문에 데드락이 발생하지 않습니다. 데드락은 셀 수 없는 리소스에 대해서도 발생할 수 있습니다. 메인 메모리의 일부를 서로 점유하고 있는 상태에서 나머지 부분을 원할때도 데드락이 발생합니다.

 

 

 

데드락이 자동차 브레이크나 제어 장치에 발생한다면 큰 문제가 되기 때문에 해결 방안에 대한 연구가 많이 진행되었고 크게 두 가지 카테고리로 발전이 되었습니다. 첫 번째는 데드락이 발생하지 않게 방지하는 prevention, 두 번째는 데드락이 발생하게 하는 대신에 발견이 된다면 빠르게 조치를 취하는 detection & recovery 이렇게 2가지 방식으로 dead lock handling이 진행됩니다.

 

데드락이 발생하기 위해서는 4가지 필요조건이 만족되어야 합니다. 4가지 중 하나라도 만족하지 못한다면 데드락이 발생하지 않습니다. mutual exclusion과 no preemption은 리소스 속성에 대한 것으로 두 개 이상의 프로세스가 같은 리소스를 동시에 사용하거나  다른 프로세스가 강제로 리소스를 뺏으면 안된다는 것입니다. 데드락 방지를 위해 preemption을 하는 경우도 조심해야 합니다, 프린트를 할 때 첫 장 인쇄 중에 두 번째 장을 인쇄하기 위해서 리소스를 뺏으면 첫 장과 두 번째 장 내용이 섞여 출력물이 쓸모 없어지듯 preemption이 일어나면 안되는 경우도 존재합니다.

 

프로세스는 우리가 제어할 수 있지만 리소스의 속성까지는 제어할 수 없기 때문에 이 두 항목은 해소할 수 없는 필요조건이 됩니다. 나머지 두 개에 대해서도 알아보겠습니다. 프로세스들이 데드락을 만들려면 반드시 Hold and wait을 해야합니다. 리소스를 hold 하고있는 상황에서 wait을 해야 데드락이 발생합니다. 리소스가 없는데 wait을 해봤자 데드락은 발생하지 않습니다. (프로세스가 필요로 하는 모든 리소스를 한꺼번에 할당시키면 wait할 필요가 없어지기에 이 조건이 발생하지 않지만 이 방법은 굉장히 비싸기 때문에 현실적이지 못합니다.)

 

마지막은 circular wait으로 이전에 resource allocation graph에서 봤듯이 리소스를 가지고 있는 상태에서 다른 프로세스가 점유한 리소스를 원하고 그 프로세스도 다른 리소스를 원해 사이클이 생기는 것을 말합니다. circular wait을 해결하기 위한 standard allocation이라는 방법이 존재합니다. standard allocation은 리소스에 번호를 매깁니다. 그리고 모든 프로세스는 리소스를 항상 낮은 번호에서 높은 번호로 할당받게 됩니다. (이렇게 리소스에 번호를 매기는 것도 프로그래머에게 지나친 불편함을 제공합니다.)

 

 

 

데드락의 해결책은 2가지가 존재하는데 그 중 prevention은 데드락이 발생하는 4가지 필요조건 중 하나를 해결하는 것이였습니다. 하지만 4개 중 2개는 리소스 속성에 대한 것으로 해소가 불가능하고 나머지 2개는 지나치게 비싸거나 불편한 방법이기 때문에 현실성이 없었습니다.

 

그래서 이 방법 대신에 뱅커스 알고리즘(The Banker's Algorithm)을 통해서 해결합니다. 뱅커스 알고리즘은 프로세스의 리소스 요청을 받으면 그 리소스 요청을 들어줬을 때 데드락에 빠질 가능성이 있는지 확인해보고 가능성이 있다면 들어주지 않는 방식으로 동작하게 됩니다. 이렇게 조심스럽게 resource allocation을 진행하는 것이 prevention 기법입니다.