[운영체제(OS)] 데드락(Deadlock) - (1) 데드락 개념과 발생 조건

0.🚶들어가며

프로세스 동기화에 대해 배우다 보면 나오는 개념 중 상호 배제라는 개념이 있습니다. 공유 자원에 대한 상호 배제 메커니즘을 구현하다 보면 발생하게 되는 문제가 있습니다. 바로 데드락이죠. 이번 글에서는 데드락이 무엇인지와 어떤 조건하에 데드락이 발생하는지에 대해 알아보도록 하겠습니다.

---

1.💀데드락이란?

일상생활의 데드락 예시

위 사진의 교통체증이 보이시나요? 이번 글에서 설명할 데드락은 현실세계에서 위와 같은 상황에 빗대어 볼 수 있습니다. 데드락이 무엇인지에 대해 알아보도록 하죠.

 

프로세스들이 서로가 가진 자원을 기다리며 작업을 더이상 진행하지 못하는 상태를 데드락이라고 합니다. 여기서 자원이라 함은 시스템 자원, 공유 변수 같은 소프트웨어, 하드웨어적인 자원 모두를 말합니다.

 

이전 글에서 소개한 사진의 일부인데요. 위 상황을 살펴보시면 데드락이 무엇인지 감이 잡히실 겁니다. 현재 Q, S라는 세마포어 자원이 있고 P0는 S를 차지, P1은 Q를 차지한 상황입니다. 그 이후 P0와 P1은 Q와 S를 각각 요구하고 있죠. 하지만 서로 차지한 자원을 양보하지 않는 이상 P0와 P1은 원하는 자원을 할당받을 수 없고 이후의 과정도 진행시킬 수 없습니다.

 

이 상황이 바로 서로가 가진 자원을 기다리며 작업을 더이상 진행하지 못하는 상태. 바로 데드락입니다.

---

2.💢데드락 발생의 4가지 조건

데드락이 발생하기 위해서는 반드시 4가지 조건이 충족되어야 합니다. 이 중 하나라도 충족되지 않았다면 데드락은 발생하지 않죠. 4가지 조건에 대해 바로 알아보겠습니다.

1) 상호 배제

상호 배제는 매 순간 하나의 프로세스만이 자원을 사용할 수 있음을 말합니다. 자원이 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 하는 것입니다. 프로세스 동기화에서 살펴본 임계 구역으로 보호된 공유자원은 대표적인 배타적 자원입니다. 이러한 상호 배제 메커니즘이 없다면 애초에 데드락 발생 이유도 없을 것입니다.

2) 비선점

비선점이란 프로세스가 자원을 스스로 내놓기 전까지는 강제로 빼앗기지 않음을 뜻합니다. 어떤 프로세스가 사용 중인 자원을 빼앗을 수 있다면 데드락은 걸릴 이유가 없겠죠?

3) 점유와 대기

점유와 대기는 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 점유하며 대기하는 것을 말합니다. 데드락이 발생하는 이유도 점유하며 대기하기 때문입니다.

4) 원형 대기

원형 대기란 자원을 기다리는 프로세스 간에 사이클이 형성되는 것을 말합니다. 점유와 대기를 한다고 모두 데드락이 걸리는 것은 아닙니다. 점유와 대기 구조가 프로세스 간에 원형으로 형성되어 있어야 데드락이 걸리는 것이죠. 

 

여기까지 데드락 발생의 4가지 조건을 알아보았습니다. 개념들이 아직 뚜렷하게 와닿지 않으실 수도 있을 것 같은데요. 예시를 보며 이에 대해 조금 더 자세하게 설명해보도록 하겠습니다. 

---

3.🧑‍🤝‍🧑데드락 발생 예시 - 식사하는 철학자 문제

데드락 발생 예시로 많이 언급되는 식사하는 철학자 문제에 대해 살펴보겠습니다.

식사하는 철학자

식사하는 철학자 문제에서는 식사를 하는게 목적이며, 아래와 같은 과정을 거쳐서 식사를 하게 됩니다.

• 왼쪽 포크를 사용할 수 있을 때까지 대기하며, 사용 가능해질 시 왼쪽 포크를 집어든다.
• 오른쪽 포크를 사용할 수 있을 때까지 대기하며, 사용 가능해질 시 오른쪽 포크를 집어든다.
• 양쪽 포크를 모두 잡으면 일정 시간 식사를 한다.
• 오른쪽 포크를 내려놓는다
• 왼쪽 포크를 내려놓는다.

이때 모두가 동시에 왼쪽 포크를 잡는다면 어떨까요? 누구도 오른쪽 포크를 잡지 못하는 상황이라 아무도 식사를 할 수 없습니다. 바로 데드락 상황이죠. 식사하는 철학자 상황에 맞춰 데드락 발생 4가지 조건을 과연 만족하는지 알아보겠습니다.

✅상호 배제

식사하는 철학자 문제에서 포크는 다른 사람과 같이 사용할 수 없는 배타적인 자원입니다. 데드락은 배타적인 자원을 여러 프로세스가 사용하려 할 때 발생한다고 했습니다. 이처럼 포크를 여러 명이 사용하려다 보니 데드락 조건 하나가 만족된 것입니다.

✅비선점

철학자들이 서로 포크를 빼앗을 수 있다면 데드락이 발생하지 않았을 것입니다. 비선점 요소 역시 데드락이 걸릴 조건 중 하나가 됨을 알 수 있습니다.

✅​점유와 대기

상호 배제와 비선점만으로도 데드락이 걸릴까에 대해 생각해봅시다. 만약 누군가 포크 두 개를 들었다고 생각해봅시다. 이 때는 누군가는 식사를 하고 누군가는 자신의 차례를 기다리는 중이 되겠죠. 이는 서로의 식사를 방해한다는 개념으로 보기보단 각자 자신의 식사 순서에 선후 관계를 정하고 기다리는 상황이라고 보는 게 더 적절합니다. 즉, 데드락 상황이 아닙니다. 하지만 모두가 포크를 한 개 든 상황은 자신이 든 포크를 점유하고 남이 놓기만을 대기하는 상황, 즉 서로의 식사를 방해하는 상황입니다. 이런 상황이 충족되어야 데드락의 조건 중 하나가 만족됩니다. 

✅​원형 대기

식사하는 철학자들은 둥근 식탁에서 식사를 합니다. 서로서로가 자신의 오른쪽 사람이 포크를 놓기를 기다리며, 그 끝을 따라가다 보면 자신의 왼쪽 포크를 놓기를 원하는 사람이 존재하게 되는 것이죠. 이러한 원형 대기 상황이 데드락을 유발합니다.

---

4.💨나가며

이번 글에서는 데드락이 무엇인지와 데드락 발생 조건에 대해 알아보았습니다.

다음 글에서는 데드락 해결방법에 대해 알아보도록 하겠습니다.