교착상태 (DeadLock) 와 기아상태 (Starvation)

잘 기억은 안나지만 2022년 여름 주말이었는데 지인들끼리 다같이 모여서 쿠팡이츠로 점심을 시켜먹으려고 했는데 서버가 내려가 주문이 안된 사태가 있었습니다. 

 

여자친구가 당시 쿠팡이츠에서 일하고 있었고 사내톡으로 해당 문제가 교착상태 (DeadLock) 때문에 발생한 문제라고 판단하고 이내 두시간정도에 걸쳐서 문제를 해결했던 일이 생각납니다. 

 

가장 매출이 잘 나오는 주말 점심에 이런 일이 터졌기 때문에 고객들은 부정적인 고객경험과 경쟁사에 고객을 뺏기는 상황이 발생했죠. 

 

이처럼 데드락, 교착상태는 서비스를 운영함에 있어서 큰 문제가 될 수 있는 상황입니다. 오늘 시간에는 교착상태에 대해서 알아보고 왜 교착상태가 일어나는지, 해결하려면 어떻게 해야하는지에 대해서 알아보도록 하겠습니다. 

 

 

교착상태

교착상태 (이하 데드락) 은 하나 이상의 프로세스가 자원을 잡고 있는 상태에서 다른 자원을 획득하기위해 기다리고 있는 상황때문에 생기는 블락현상입니다. 

 

프로세스가 한번 실행되고 나면 잡고있던 자원을 해제하게 되는데 많은 프로세스가 한번에 실행되게 되면 실행에 필요한 자원을 갖기위해 끊임없이 경쟁하는 상태에 돌입하게 됩니다. 

 

데드락을 위한 네가지 상황

• 상호 배제 (Mutual Exclusion) : 상호 배제는 프로세스 동기화 포스팅에서도 소개해드린 개념입니다. 오직 하나의 프로세스만 임계구역에서 작업할 수 있고 나머지 프로세스는 임계구역에 들어가기 위해서는 기다려야 한다는 개념이었습니다. 
• 점유 대기 (Hold ans Wait) : 하나의 프로세스가 한번에 적어도 하나의 자원을 잡고있는 중에 다른 프로세스가 잡고있는 다른 자원을 획득하기위해 기다리는 상태를 말합니다. 
• 비선점 (No Preemption) : 다른 프로세스가 자원의 사용을 끝낼 때 까지 자원을 뺏을 수 없습니다.
• 순환 대기 (Circular Wait) : 일련의 프로세스가 각각의 다른 순환참조에의해 기다리고 있는 상황을 말합니다. 예를 들어서 일련의 프로세스 P0, P1, P2, P3가 있다고 가정해봅시다. P0는 P1에 의존하고 P1은 P2에 의존하고 P2는 P3에 의존하고 P3는 다시 P0에 의존하는 상황을 말합니다. 

위와같은 그림이 순환 대기를 보여주는 예시입니다. 프로세스 1이 자원  1을 쥐고있고 자원 2를 요구합니다. 프로세스 2는 자원2를 쥐고있고 자원 1을 필요로합니다. 

 

이런 상황이 바로 데드락을 유발하는 상황입니다. 이 때 두개의 프로세스 모두 실행이 되지 않는 상황이 생겨버리죠. 상호배제에 의해 자원은 공유되지 않기 때문에 이러한 상황이 생깁니다. 

 

 

데드락을 피하기 위한 네가지 방법

• 예방 : 데드락이 발생하려면 앞서 설명한 네가지 조건을 모두 만족해야 합니다. 그렇다는 얘기는 하나라도 만족하지 않으면 데드락이 발생하지 않는다는 얘기인데요. 때문에 데드락을 예방하기 위해서는 넷을 모두 만족하지 않은 시스템을 만들면 됩니다. 
• 회피 : 데드락이 발생하려는 조짐이 보이더라도 데드락을 회피하는 방법이 있습니다. 바로 알고리즘을 만들어서 데드락을 회피하는 방법입니다. 
• 감지 그리고 회복 : 데드락이 발생했을 때 데드락을 감지하는 알고리즘에 의해 데드락을 감지하고 회복하기 위해 뒤이어 설명할 세가지 방법을 통해 데드락에서 시스템을 회복시킬 수 있습니다. 
  • 데드락에 걸린 모든 프로세스를 중지시킨다. 
  • 데드락으로부터 시스템 회복까지 한번에 하나씩 프로세스를 중지시킨다. 
  • 자원의 비선점 때문에 발생한 문제를 자원을 선점시킴으로써 데드락 문제를 회복시킨다. 이때 데드락을 회복할 때 까지 우선순위가 높은 프로세스에 자원을 할당하는 방법입니다. 
• 무시 : 이 방법은 시스템이 데드락이 절대 발생하지 않는다고 가정한 상태에서 시작합니다. 데드락 상황이 자주 발생하지 않기 때문에 몇몇 시스템들은 아예 무시하는 방법을 선택하기도 합니다. OS 중 Unix와 Windows같은 것들이 선택하는 방법이죠. 만약 이런 상황에서 데드락이 발생한다면 재시작을 통해 데드락 상황을 자동적으로 해결하도록 설계되어있습니다. 
  • 무시와 같은 예제는 Ostrich 알고리즘의 한 예시입니다. 이 알고리즘은 극도록 드문 잠재겅니 문제를 무시하기위한 전략 중 하나입니다. 

 

기아상태

 

많은 분들이 교착상태와 기아상태에 대해 헷갈려 하시는 분들이 많은 것 같습니다. 제 주변인들도 이를 많이 헷갈려 하시더라구요. 둘은 비슷한듯 보이지만 약간 다른 차이점을 가지고 있습니다. 

 

기아 상태는 높은 우선순위가 계속 실행이 되서 낮은 우선순위가 실행되지 않는 상황을 말합니다. 군대 은어로 잼걸렸다고 하는 표현이 이와 같습니다. 실제로 영어로 된 문서에서 이와같은 현상을 Jammed 라고 표현하더라구요. 

 

기아상태는 보통 무한한 시간동안 프로세스가 딜레이되는 상황에서 주로 발생합니다. 

 

프로세스의 요청을 핸들링하기 위해 OS에서 필요한 자원들은 다음과 같습니다. 

 

• 메모리
• CPU 시간
• 디스크 저장공간
• Bandwidth of network
• I/O access to disk or network

이러한 자원들이 밀리고 밀리면서 우선순위가 낮은 프로세스가 실행되지 않는 상황이 바로 기아상태입니다. 

 

기아상태의 특징

• 낮은 우선순위의 프로세스가 영원히 기다리고 높은 우선순위의 프로세스가 끊임없이 동작하는 상황
• 낮은 우선순위의 프로세스는 자원과 영원히 상호작용하지 않기 때문에 데드락이 발생하지는 않습니다. 그러나 낮은 우선순위의 프로세스가 영원히 실행이 안된다는 문제가 발생합니다.
• 그러므로 기아상태는 정확히 실패한 방법입니다. 기아상태는 데드락을 일시적으로 해결해주는 방법이긴합니다. 
• 기아상태를 유발하는 가장 중요한 요인은 모든 자원들을 공급하는 충분한 리소스가 없기 때문입니다. 
• 기아상태는 자원이 자원 분배에 실패 때문에 프로세스의 실행을 위해 절대 공급되지 않는 상태에서도 발생할 수 있습니다. 

 

이러한 기아상태를 해결하기위한 방법도 존재하겠죠? 해결하는 방법에 대해서 한번 알아보도록 하겠습니다. 

 

기아상태 해결방법

• CPU에 자원분배를 맡긴다. 
• 프로세스를 선택하는 것을 랜덤 선택으로 바꾼다. 
• PriorityQueue와 같은 스케쥴링 알고리즘을 사용한다. 

 

이렇게 기아상태에 대해서 알아봤습니다. 그럼 교착상태와 기아상태의 차이에 대해서 한번 쭉 정리하고 마무리 짓도록 하겠습니다. 

 

마치며

여기까지 교착상태와 기아상태에 대해서 알아봤습니다. 오랜만에 쉬우면서 중요한 개념을 공부해보니 마음이 뿌듯하니 좋습니다. 긴 글 읽어주셔서 감사합니다. 오늘도 즐거운 하루 되세요~

 

 

참조

https://www.scaler.com/topics/operating-system/deadlock-in-os/

Deadlock in OS | Scaler Topics

https://www.geeksforgeeks.org/introduction-of-deadlock-in-operating-system/

Introduction of Deadlock in Operating System - GeeksforGeeks

https://www.scaler.com/topics/starvation-in-os-operating-system/