[OS] 교착상태 (데드락, Deadlock)

1. 교착상태(데드락, Deadlock)란?

 

교착상태는 상호 배제에 의해 나타나는 문제점으로,

둘 이상의 프로세스나 스레드들이 자원을 점유한 상태에서

서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상이다.

 

이미지 출처: https://dkwjdi.tistory.com/248

 

---

 

2. 교착상태 발생 조건 Deadlock 

 

교착상태 발생의 필요충분조건은 네 가지가 있는데 이 네 가지 중 하나라도 충족되지 않으면 교착상태는 발생하지 않는다.

 

1) 상호배제 Mutual Exclusion

한 번에 하나의 프로세스만이 공유 자원을 사용하는 것

 

2) 점유와 대기 Hold and Wait

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기

 

3) 비선점 Non-Preemption

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

 

4) 환형대기 Circular Wait

공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 연결되어 있어

자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 함

 

---

 

3. 교착상태 해결방법

 

- 예방 Prevention

• 교착 상태 원인(상호 배제, 점유와 대기, 비선점, 환형 대기) 중 하나를 제거하는 방법
• 자원 낭비가 가장 심함

 

---

 

- 회피 Avoidance

• 교착 상태가 발생하려고 할 때 그 가능성을 피해가는 방법
• 리소스 할당의 측면에서 교착상태가 발생할 가능성이 있는 자원 할당(unsafe allocation)을 하지 않음
• 예) 은행원 알고리즘(Banker's Algorithm)

 

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

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

 

---

 

- 회복 Recovery

• 교착 상태를 일으킨 프로세스를 종료하거나, 교착 상태의 프로세스가 점유한 자원을 선점해서 다른 프로세스에 할당하는 기법
  👉 즉, 문제를 해결하기 위해 종료시켜버리는 것
• 프로세스 종료 방법
  • 교착 상태의 프로세스 모두 중지
  • 교착 상태가 제거될 때까지 한 프로세스씩 중지
• 자원 선점 방법
  • 자원을 빼앗긴 프로세스는 강제 종료 이후 재시작
  • 교착 상태에 빠진 프로세스가 필요로 하는 자원을 강제로 가져옴

 

---

 

참고

 

1. https://dkwjdi.tistory.com/248
2. https://velog.io/@ejung803/%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C%EC%99%80-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-%ED%95%B4%EA%B2%B0%EB%B0%A9%EB%B2%95
3. https://computer-choco.tistory.com/441