다중 프로세스의 무한대기, 교착상태(Deadlock)

Intro

교착상태는 사실 교착상태라는 말보다는 Deadlock이라는 말을 훨씬 많이 사용하고 있으며, 개발자라면 한번 정도는 경험해볼만한 상황이기도 하다. 필자같이 데이터 분석가라면 대용량의 데이터를 처리하기 때문에 다른 사람들보다 이러한 상황을 자주 경험해봤다. 왜냐하면 다중 프로세스에서 발생하기 때문에 대용량을 처리하는 상황(최고의 속도를 위해서 수많은 Thread들과 마이크로서비스 등을 사용하기 때문)은 그야말로 최적의 상황이기 때문이다.

 

다중 프로세스 무한대기 상태, 교착상태의 개요

교착상태(Deadlock)의 개념

- 다중 프로세스(process) 환경하에 서로 다른 프로세스가 각자 자신이 소유한 자원을 포기하지 않고 상대 프로세스의 자원을 무한정 기다리고 있는 상태

- 교착상태에 있는 프로세스들은 실행을 끝낼 수 없으며, 시스템 자원이 묵여 있어서 다른 작업을 시작하는 것도 불가능

 

deadlock 상태

 

현실상황에서 자주 볼 수 있는 교착상태

가. 교차로에서 차들이 동시에 진입할 때

생각만해도 치가 떨리는 교통상황

나. 연인이 서로 상대방의 약점을 물고 늘어질 때

연인A : 너는 날 사랑하고 있는 것 같지가 않아
연인B : 네가 날 사랑하는 감정을 준다면 널 사랑할 수 있을 것 같애

다중 프로세스 상에서 상대방의 자원(즉 사랑)을 주지 않고 점유할려는 교착상태의 모습이다. 개발자들은 이럴 경우 "젠장~ 데드락에 빠졌네..."라는 이과스러운 농담을 던지곤 한다.

 

교착상태의 원인

상호배제(Mutual Exclusive)

- 프로세스가 자원을 배타적으로 점유하고 있기 때문에 다른 프로세스가 그 자원을 사용할 수 없음

 

점유와 대기(Block & Wait)

- 한 프로세스가 자원을 점유하고 있으면서 또 다른 자원을 요청하고 대기하고 있는 상태

 

비선점(Non Preemption)

- 한 프로세스가 점유한 자원에 대해 다른 프로세스가 선점할 수 없고, 오직 점유한 프로세스만이 해제 가능

 

환형대기(Circular wait)

- 다 중 프로세스간 자원의 점유와 대기가 하나의 원형을 구성한 상태

 

※ 한 시스템 내에서 모든 조건 만족 시 교착상태

 

교착상태의 해결방안

예방(Prevention)

- 교착 상태의 원인 조건(상호배제, 점유와 대기, 비선점, 환형대기)의 부정

 

회피(Avoidance)

- 은행원 알고리즘(Banker's Algorithm), wait-die, wound-wait 알고리즘

 

탐지(Detection)

- 시스템의 상태를 탐지 알고리즘을 통해 교착상태 검사

- 자원할당 그래프, wait for graph

 

회복(Recovery)

- 교착상태가 없어질 때까지 프로세스를 순차적으로 Kill 시킴

- 자원의 우선순위별 할당 : 희생자 선택, 기아상태

 

교착상태의 해결방안에 활용되는 은행가 알고리즘이나, wait-dai, wound-wait, 자원할당 그래프는 본 포스팅에 설명하기에는 내용이 길기 때문에 별도 포스팅 예정

 

교착상태를 설명하는 철학자들의 만찬(dining philosophers problem)

※ 한국어판 위키피디아나 나무위키에는 식사하는 철학자들 문제라고 나와 있음

 

철학자들의 만찬

교착 상태를 설명하는 예시로 사용되며 이미지만 봐도 직관적으로 알 수 있다.

 

다섯 명의 철학자들이 원탁에 앉아서 식사를 하려 하는데 각자 앞에는 스파게티가 있고 옆에는 포크가 하나씩 있다. 각각의 철학자들은 다른 철학자에게 이야기를 할 수 없으며 식사를 할 때 왼쪽 포크를 들고 다음에 오른쪽 포크를 드는 알고리즘을 가지고 있다고 가정을 한다.

이때 동시에 왼쪽 포크를 들었다면 모든 포크가 각각 철학자들에게 한 개씩 쥐어질 것이다. 이때 왼쪽 포크는 각각 철학자들(프로세스)이 선점한 자원이 될 것이고, 이들은 오른쪽 포크를 들려고 하나 이미 다른 철학자들이 들고 있어서 식사를 못 하는 교착 상태에 빠지게 된다.

이때 어떤 철학자가 포크를 빠르게 2개를 집을 경우, 우측에 있는 철학자는 기아 상태에 빠지게 되기도 한다.

이 철학자들의 문제를 듣고 "포크 하나로 먹을 수 있는데?"라고 생각하는 사람들을 위해서 젓가락으로 바꾼 버전도 존재한다.

 

키워드

상호배제, 점유와 대기, 비선점, 환형대기, banker's algorithm, 자원할당 그래프, wait-die, wound wait

 

참고자료

https://ko.wikipedia.org/wiki/%EC%8B%9D%EC%82%AC%ED%95%98%EB%8A%94_%EC%B2%A0%ED%95%99%EC%9E%90%EB%93%A4_%EB%AC%B8%EC%A0%9C