[CS 정리] 교착상태(Deadlock)

우아한 테크톡 관련된 유튜브 강의 정리 내용입니다.

정확한 내용을 학습하고 싶으면 강의 링크를 참고하시면 됩니다.

---

교착상태 (Deadlock)

상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미합니다.

 

 

교착 상태 4가지 필요 조건

1. 상호 배제 조건

한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 합니다.

 

2. 점유와 대기 조건

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

 

3. 비선점 조건

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

 

4. 순환 대기 조건

공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 합니다.

 

교착 상태 해결법

• 교착 상태 예방
• 교착 상태 회피
• 교착 상태 탐지 및 복구
• 교착 상태 무시

 

교착 상태 무시

- 교착 상태가 드물게 발생하는 시스템에서 일반적으로 사용하는 방법

 

교착 상태 탐지 및 복구

- 교착 상태가 자주 발생하는 시스템에서 일반적으로 사용하는 방법

 

- 교착 상태 탐지

교착 상태 존재 여부 및 교착 상태에 연관된 프로세스와 잔원을 알아봅니다..

순환 대기 존재 여부에 초점을 맞춥니다.

 

얼마나 자주 탐지 알고리즘을 호출??

 

교착 생태 복구

순환 대기를 깨서 교착 상태로부터 회복

• 순환 대기가 깨질 때까지 프로세스 종료
• 순환 대기에 포함된 프로세스의 제어권을 뺏고 롤백

어떤 프로세스를 희생양으로?

시스템마다 다른 기준으로 우선 순위를 정합니다..

 

 

교착 상태 예방

- 교착 상태는 필요악

 

• 상호 배제 부정
• 점유와 대기 부정
• 비선점 부정
• 순환 대기 부정

 

필요 조건 중 하나를 거부하고 예방 -> 점유와 대기 조건을 거부한다면?

자원을 효율적으로 사용할 수 없다..

 

교착 상태 회피

교착 상태를 인정하고 피해가자

 

은행원 알고리즘

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

- 시스템을 안전 상태 / 불안전 상태로 구분하고 불안전 상태일 땐 대기시킵니다.

- 할당할 자원 수 고정, 프로세스 수 고정, 제한된 시간안에 자원 반납 등 많은 조건 필요

 

교착 상태가 발생한 것 같을 때 탐지하고 복구하는 전략

vs

자원을 요청할 때 마다 시스템의 상태를 판단하고 회피하는 전략