[OS] 교착 상태 (Dead Lock) 📌

교착 상태(Dead Lock) 란?

• 운영체제에서 데드락이란, 시스템 자원에 대한 요구가 뒤엉킨 상태이다
• 즉, 두 개 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황
• 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다
• 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제로, 문제 해결을 위한 일반적인 방법은 아직 없다

 

 

 

교착 상태가 발생하는 조건

데드락이 발생하기 위한 필요 조건은 4가지로, 여기서 하나라도 충족되지 않으면 데드락이 발생하지 않는다

그러나 4가지 조건을 모두 충족했다고 무조건 교착상태가 발생하는 것은 아니다!

아래의 조건 중 순환대기는 점유대기와 비선점을 만족해야 성립하기 때문에, 서로 완전히 독립적인 것은 아니다

 

 

1. 상호 배제 (Mutal Exclusion)

• 한번에 프로세스 하나만 해당 자원을 사용할 수 있다
• 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다

 

2. 점유 대기 (Hold and Wait)

• 어떤 프로세스가 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다

 

3. 비선점 (Non-preemption)

• 이미 할당된 자원을 강제로 빼앗을 수 없다
• 프로세스가 태스크를 마친 후 리소스를 자발적으로 반환할 때까지 기다린다

 

4. 순환 대기 (Circular Wait)

• 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다

 

 

 

 

교착 상태의 해결법

데드락의 해결법은 크게 3가지로 구분된다

 

1. 데드락이 발생하지 않도록 예방(Prevention)하기
2. 데드락 발생 가능성을 인정하면서도 적절하게 회피(Avoidance)하기
3. 데드락 발생을 허용하지만 데드락을 탐지(Detection)하여, 데드락에서 회복하기

 

 

 

예방 기법(Prevention)

교착 상태 예방 기법이란 교착 상태가 발생하지 않도록 사전에 시스템을 제어하는 방법이다

교착 상태 발생의 4가지 조건 중에서 어느 하나를 제거함으로써 수행된다

이는 자원 낭비가 가장 심한 기법이다

즉, 예방 기법은 시스템의 처리량이나 효율성을 떨어뜨리는 단점이 있다

 

1) 상호 배제(Mutal Exclusion) 부정

• 한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다

 

2) 점유 및 대기 (Hold and Wait) 부정

• 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없앤다
• 또는 자원이 점유되지 않은 상태에서만 자원을 요구한다

 

3) 비선점 (Non-preemption) 부정

• 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납한다
• 그 후 요구한 자원을 사용하기 위해 기다린다

 

4) 환형 대기 (Circular Wait) 부정

• 자원을 선형 순서로 분류하여 고유 번호를 할당한다
• 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤, 어느 한 방향으로만 자원을 요구하도록 한다

 

 

 

 

회피 기법 (Avoidance)

Safe sequence / Safe state

교착 상태 회피 기법은 교착 상태가 발생할 가능성을 배제하지 않고, 교착 상태가 발생하면 적절히 피해나가는 방법

주로 은행원 알고리즘(Banker's Algorithm)이 사용된다

 

 

은행원 알고리즘 (Banker's Algorithm)

1. 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법이다
2. 각 프로세스에게 자원을 할당하여 교착 상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전 상태, 교착 상태가 발생할 수 있는 상태를 불안전 상태라고 한다
3. 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다
4. 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장한다

 

 

 

 

발견 기법 (Detection)

교착 상태 발견 기법은 시스템에 교착 상태가 발생했는지 점검하여 교착 상태에 있는 프로세스와 자원을 발견하는 것을 말한다

 

• 교착 상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다

 

 

 

 

회복 기법 (Recovery)

교착 상태 회복 기법은 교착 상태를 일으킨 프로세스를 종료하거나 교착 상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미한다

 

1) 프로세스 종료

• 교착 상태에 있는 프로세스를 종료하는 것이다
• 교착 상태에 있는 모든 프로세스를 종료하는 방법
• 교착 상태에 있는 프로세스들을 하나씩 종료해가며 교착 상태를 해결하는 방법

 

2) 자원 선점

• 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법
• 우선 순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점한다

 

💡 자원 선점 시 고려사항
1. 자원을 선점할 프로세스 선택 : 최소의 피해를 줄 수 있는 프로세스를 선택한다
2. 자원을 선점한 프로세스의 복귀 : 자원이 부족한 상태이므로 대부분 일시 중지시키고 다시 시작하는 방법을 사용한다
3. 기아 현상 : 한 프로세스가 계속하여 자원 선점 대상이 되지 못하도록 고려해야 한다

 

 

---

참고 자료)

https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=dktmrorl&logNo=222287365901 

[IT정보] 교착상태(Deadlock) 개념

https://velog.io/@junu0516/%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-%EB%B0%A9%EC%A7%80%EA%B8%B0%EB%B2%95

교착상태 방지기법

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

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

https://chanhuiseok.github.io/posts/cs-2/

[운영체제] 데드락(Deadlock, 교착 상태)이란?