[운영체제(OS)] 데드락(Deadlock) - (2) 데드락 해결 방법

0.🚶들어가며

이전 글에서 데드락이 무엇인지에 대해 알아보았습니다. 이번 글에서는 데드락을 해결하는 방법에 대해 알아보겠습니다.

데드락을 해결하는 방법을 크게 네 가지로 나눠 소개해볼 예정입니다.

• 데드락 예방
• 데드락 회피
• 데드락 검출과 회복
• 데드락 무시

위 네 가지 방법이 각각 무엇인지, 장단점은 무엇인지를 위주로 설명드리도록 하겠습니다.

---

1.🤚데드락 예방 (Deadlock prevention)

이전 글에서 데드락을 일으키는 조건에는 네 가지가 있다고 했습니다. 네 가지 중 하나라도 충족하지 않으면 데드락은 발생하지 않는 것이죠. 데드락 예방은 네 가지 조건 중 하나라도 충족시키지 못하게 하여 데드락이 발생하지 않도록 하는 해결방법입니다. 각 조건을 하나씩 보면서 내용을 알아보도록 하죠.

1. 상호 배제 예방

시스템 내에 있는 상호 배타적인 자원을 없애버리는 방법입니다. 애초에 시스템 내의 모든 자원을 공유할 수 있다면 데드락은 발생하지 않겠죠. 하지만 프로세스 동기화에서도 봤듯 공유 자원에 대한 상호 배제 처리를 하지 않는다면 그에 따르는 문제가 추가됩니다. 따라서 이는 현실적이지 않은 방법입니다.

2. 비선점 예방

비선점 예방을 한다면 자원을 할당받은 프로세스에게서 자원을 빼앗을 수 있도록 처리해야 합니다. 하지만 임계 구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없습니다. 설령 자원을 빼앗더라도 어떤 기준으로 빼앗을지, 빼앗은 시간 중 얼마나 사용할지 등의 결정이 어렵습니다. 또한 이런 방법이 Starvation을 일으킬 수 도 있죠. 따라서 비선점 조건을 무력화시키는 것 역시 비현실적인 방법입니다. 

3. 점유와 대기 예방

점유와 대기 예방은 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리는 상황을 없애는 방식입니다. All or Nothing 방식으로 자원을 배분하는 것이죠. 필요한 모든 자원을 얻을 수 있을 때만 프로세스를 시작하는 것입니다. 하지만 이러한 방식은 자원의 활용성이 떨어진다는 큰 단점이 있습니다.

4. 원형 대기 예방  

원형 대기 예방은 자원에 번호를 매기는 방식으로 구현할 수 있습니다. 낮은 번호의 자원을 사용하는 프로세스가 높은 번호의 자원을 요청하는 것은 허용하지만 그 반대는 허용하지 않는 식이죠.  하지만 이러한 방식은 프로세스 작업 진행에 유연성을 떨어뜨리며 자원의 번호를 어떤 방식으로 부여할 것인지에 대한 문제가 발생합니다. 

---

지금까지 데드락 예방에 대한 내용을 살펴보았는데요. 데드락 예방 방식은 자원에 대한 이용률을 대단히 감소시킵니다. 데드락은 기본적으로 자주 생기는 문제가 아닙니다. 그럼에도 불구하고 이를 위해서 하는 데드락 예방 방식은 Overhead가 너무 커 실효성이 적다고 볼 수 있습니다.  

---

2.📗데드락 회피 (Deadlock Avoidance)

데드락 회피는 프로세스가 사용하는 자원에 대한 추가적인 정보를 이용해서 데드락을 막는 방식입니다. 자원 할당이 데드락으로부터 안전한지 그렇지 않은지를 동적으로 조사해 안전한 경우에만 할당해주는 방식이죠. 프로세스마다 요구할 최대 자원 정보를 얻고 이를 바탕으로 해당 프로세스가 자원을 요구할 때 데드락 가능성을 파악한 뒤 자원 할당을 결정합니다. 

 

데드락으로부터 안전한 지에 대한 판단이 무엇일까에 대해 간단한 예시를 통해 들어보겠습니다.

 

라면 10인분과 김밥 20인분을 준비한 음식점이 있다고 가정해봅시다. 이 음식점이 예약 손님을 받을 때 10명이 예약한다면 문제가 없을 것입니다. 하지만 15명이 예약한다면 어떨까요? 30인분의 음식이 있음에도 불구하고 15명이 모두 라면을 시킬 상황을 고려하여 해당 예약은 거절하게 되는 것이 데드락 회피 방식입니다. 좀 더 정확한 알고리즘에 대해 궁금하시다면 Banker's Algorithm에 대해 찾아보시면 좋을 것 같습니다.

 

아무튼 예시를 보아도 상당한 자원 낭비가 예상됩니다. 자원이 있더라도 데드락이 무서워서 자원을 사용하지 못하는 모습이니까요.  이 역시 실효성이 적어 보입니다.

---

3.👀데드락 검출과 회복 (Deadlock Detection & Recovery)

데드락 검출과 회복은 이전에 예방, 회피 방식과는 다르게 데드락이 발생한 후 해결하는 방식입니다. 데드락 해결 방법 중 가장 현실적인 방법입니다. 데드락 검출은 운영체제가 프로세스의 작업을 관찰하면서 데드락 발생 여부를 계속 주시하는 방식입니다. 만약 데드락이 발생했다면 이를 해결하기 위해 회복 단계를 밟게 됩니다.

1) 검출 방식

우선 데드락이 발생했는지 여부를 검출할 수 있는 방식 두 가지를 소개하겠습니다.

(1) 타임아웃을 이용한 데드락 검출

데드락이 걸리게 되면 작업이 진행되지 않는다는 특징을 고려하여 일정 시간 동안 작업 진행이 되지 않은 프로세스를 데드락에 걸린 것으로 간주합니다. 하지만 이러한 방식은 문제가 조금 있습니다. 모든 프로세스가 데드락 때문에 작업이 이루어지지 않는 게 아니기 때문이죠. 다른 이유로 진행되지 않은 프로세스는 영문도 모른 채 데드락 판정을 받을 수 있게 됩니다. 하지만 단순한 구현 방식으로 인해 데이터베이스나 운영체제에서 선호되기도 합니다.

(2) 자원 할당 그래프를 이용한 데드락 검출

자원 할당 그래프라는 (프로세스~자원)의 할당, 요청 관계를 표현하는 그래프를 사용해 데드락을 검출하는 방식입니다. 자원의 성격에 따라 검출 방식은 다르지만 뮤텍스 자원을 가정하면 자원 할당 그래프에서 사이클의 존재 여부가 정확하게 데드락 발생 유무를 검출할 수 있게 됩니다.

 

2) 회복 방식

데드락이 검출되었다면 데드락으로부터 프로세스들을 풀어주어야 할 것입니다. 이를 위한 회복 방식에 대해 알아보겠습니다.

(1) 프로세스 종료

프로세스를 종료하면 자원을 반납하기 때문에 회복하는 방식 중 하나가 될 수 있습니다. 프로세스를 종료하는 방식은 또 두 가지로 나뉠 수 있는데요. 모든 데드락 프로세스를 종료시켜버리던지, 한 번에 하나씩의 프로세스를 종료해보면서 데드락 사이클이 사라지는지 확인하는 방식이 있습니다.

(2) 자원 빼앗기

데드락을 유발하는 이유는 자원이 모자라서입니다. 따라서 프로세스들이 사용하고 있는 자원들 중 비용을 최소화할 희생양을 하나 골라잡아 자원을 빼앗는 방식입니다. 이 과정에서 문제 발생 소지를 막기 위해 자원을 빼앗기기 전까지 했던 일들을 Rollback 해주는 과정이 필요합니다. 하지만 자원 선점 방식은 동일한 프로세스가 계속하여 자원 선점의 대상이 되어 Starvation 문제를 일으킬 가능성을 가지고 있습니다.

---

4.🔙데드락 무시 (Deadlock Ignore)

데드락 무시는 사실 데드락 해결 방법이라고 보기 어렵습니다. 데드락이 걸려도 시스템에서는 아무런 조치도 취하지 않는 방식이죠. 그럼에도 불구하고 현대 범용 운영체제는 대부분 데드락에 대한 처리를 하지 않습니다. 왜 그럴까요? 

 

데드락은 매우 드물게 발생하는 현상입니다. 위에서 살펴봤던 데드락 해결 방법들이 오히려 더 큰 Overhead일 수 있는 것이죠. 시스템에 데드락이 발생한 경우 이를 감지한 사용자가 알아서 Process를 Kill 하는 방식으로 대치합니다.

 

데드락에 대해 열심히 배웠는데 운영체제들이 결국 데드락 무시를 선택한 것이 조금 허탈하기도 합니다,, 

---

5.💨나가며

프로세스 동기화에서 배운 상호 배제 메커니즘으로 인해 이어지는 문제인 데드락에 대해 글을 정리해보았습니다.

 

데드락 해결을 위해 어떤 방식으로 노력을 해왔는가 흐름을 집어볼 수 있어 좋은 기회였던 것 같습니다.