데드락(DeadRock, 교착상태)

안녕하세요
오늘은 데드락에 대해서 배워보겠습니다…..

우우..

햄드러요

그래도어떠케

해야지.

---

데드락(DeadRock, 교착상태)

 

: 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해 제대로 된 작동이 되지 않고 무한한 대기상태에 빠지는 현상

자원이 한정적인데 비해 자원이 필요한 프로세스나 스레드의 개수가 자원의 개수에 비해 많은 경우에 교착 상태가 발생합니다.


데드락이 일어나는 경우의 예를 간단하게 들어봅니다.

프로세스가 2개가 있고, 각각의 프로세스는 자원 a와 자원 b를 모두 필요로 합니다.

프로세스1은 자원1을 얻습니다.

프로세스2는 자원1을 프로세스1이 가지고 있으므로, 자원1을 얻지 못하고 자원2를 얻습니다.

두 프로세스는 각각의 자원을 하나씩 지니고 있지만 추가로 필요한 자원이 자기자신이 아닌 상대방에게 있는 상태입니다.

프로세스가 종료되지 않았기 때문에 두 프로세스는 모두 자원을 반납하지 않고 하염없이 필요한 남은 하나의 자원이 사용가능해질 때까지 기다리게 됩니다.

= 결과적으로 두 프로세스가 자원을 얻지 못해 무한한 대기 상태에 빠지게 됩니다.

데드락의 발생 조건

데드락은 네가지의 조건이 모두 성립해야만 데드락이 발생합니다. 

상호 배제(Mutual exclusion)

: 자원은 한번에 한 프로세스만 사용할 수 있음

이전시간에 배운 뮤텍스입니다. 데드락이 발생하기 위해서는 이 뮤텍스가 사용되고 있어야 합니다.

점유 대기(Hold and wait)

: 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함
아까 예시와 같습니다. 하나의 자원을 가지고 있는데, 다른 추가적인 자원을 점유하고자 하는 자원이 바로 점유대기상태에 있는 프로세스라고 합니다.

비선점(No preemption)

: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

말 그대로 비선점입니다. 우선순위가 높다고 해서 하나의 프로세스에 할당되고 있는 자원을 함부로 빼앗을 수 없습니다.

순환 대기(Circular wait)

: 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

예시의 프로세스1이 프로세스2가 보유한 자원2를 원하고, 프로세스2가 프로세스1이 보유한 자원1을 원하는 것처럼 서로 원하는 자원을 서로가가지고 있는 순환형태의 자원 대기가 이루어져야ㅍ합니다.

 

만약 이 조건들 중 하나라도 부합하지 않다면 데드락에서 빠져나올 수 있다고 합니다.

데드락을 해결하는 방법

데드락이 걸리게 되는 조건도 중요하지만 조건이 중요한 이유는 그 조건을 활용하여 데드락을 해결하기 위해서죠..

예방(prevention)

위에서 말한 네가지의 발생조건 중 하나를 제거합니다. 자연스럽게 데드락 문제에 대한 예방 처리를 하게됩니다.

데드락의 조건이 4개이기 때문에 데드락의 예방방법 또한 4가지로 볼 수 있습니다.

 

상호배제 부정 : 여러 프로세스가 공유 자원 사용하도록 합니다. 공유 가능 자원으로 설계할 수도 있습니다.
점유대기 부정 : 프로세스 실행전 모든 자원을 할당하도록 합니다. 하나라도 자원을 가지지 못한다면 아무것도 가지지 않은 상태에서 자원을 기다리도록 합니다.
비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납하여 자원을 강제로 빼앗을 수 있는 규칙을 만들어줍니다
순환대기 부정 : 자원에 고유번호를 할당하고 순서대로 자원을 요구하도록 작성합니다.

 

회피(avoidance)
데드락이 발생할 가능성을 실시간으로 점검하고, 데드락 발생 시, 회피합니다. 

이 회피법에서 진행되는 것은 은행원 알고리즘으로 유명한 알고리즘이라고 합니다.

 

은행원 알고리즘(Banker's Algorithm)
은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래.

프로세스가 각각 자원을 요청할 때마다 최대 자원을 사전에 파악하여 시스템이 자원을 할당하고 나서도 항상 안정상태로 남아있을 수 있는지 사전에 검사합니다. 그리고, 여기서 안정상태라면 자원을 할당하고, 아니라면 다른 프로세스들이 자원을 해지하여 안전상태를 유지할 수 있는 상태가 될 떄까지 자원 요청을 거부하고 대기시킵니다.

 

 

탐지(Detection) 및  회복(Recovery)

데드락이 발생하도록 놔두고, 데드락이 발생하는 순간을 직접 탐지한 후에 복구합니다. 탐지 -> 복구 의 순서로 두가지 절차를 통해 이루어집니다.

 

탐지단계에서는 "자원 할당 그래프" 라는 것을 통해 데드락을 감지합니다. 누군가 자원을 요청할 때마다 주기적으로 탐지 알고리즘을 통해 시스템 상태를 점검하기에 탐지 알고리즘 실행에 따른 오버헤드가 발생한다는 특징이 있습니다.

회복단계에서는 탐지된 데드락을 해결하기 위한 방법을 선택하여 실행합니다. 

이 해결방법은 간단하게 3가지의 방법이 있습니다.

 

• 프로세스 종료: 데드락 상태를 포함하고 있는 프로세스를 강제로 종료시킵니다. 교착상태가 제거될 때까지 하나씩 프로세스를 중지합니다.
• 자원회수: 일부 프로세스에서 자원을 회수하여 다른 프로세스에 할당시킵니다. 해당하는 프로세스는 일시정지되고, 우선순위가 낮거나 수행 횡수가 적은 프로세스들에게 프로세스 자원 선점의 기회가 주어집니다.
• 프로세스 롤백: 프로세스를 이전 상태로 되돌립니다.

 

무시(Ignore)

데드락이 발생하여도 큰 해결법없이 그냥 무시하는 방법입니다.

방법이라고 하기에는 애매합니다.

리눅스 운영체제에서는 데드락을 감지 및 방지하지 않고 있으며, 데드락이 발생하게 되면 시스템 관리자나 사용자가 문제를 해결하도록 하게 되어있다고 합니다.

 

 

이렇게 데드락에 대해서 알아보았습니다.

여기서 간단하게 설명한 "은행원 알고리즘"과 "자원할당그래프"에 관해서는 제가 시간이 날 때 조금 더 구체적으로 덧붙여보도록 하겠습니다.

그럼 오늘은 여기서 20000

---

참고 자료

https://gyoogle.dev/blog/computer-science/operating-system/DeadLock.html

데드락 (DeadLock, 교착 상태) | 👨🏻‍💻 Tech Interview

https://namu.wiki/w/%EB%8D%B0%EB%93%9C%EB%9D%BD