[CS] 데드락

데드락(교착 상태)

두 개 이상의 프로세스 혹은 쓰레드가 서로가 가진 리소스를 기다리는 상태

 

데드락을 만드는 네 가지 조건

1. 상호 배제(Mutual exclusion): 리소스를 공유해서 사용할 수 없다.
2. 점유와 대기(hold and wait): 프로세스가 이미 하나 이상의 리소스를 취득한 상태(hold)에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다린다(wait).
3. 비선점(No preemption): 리소스 반환은 오직 그 리소스를 취득한 프로세스만 할 수 있다.
4. 원형 대기(Circular wait): 프로세스들이 순환하는 형태로 서로의 리소스를 기다리는 상태

운영체제(OS)의 데드락 해결 방법

1. 데드락 방지
2. 데드락 회피
3. 데드락 감지와 복구
4. 데드락 무시

---

데드락 방지(Deadlock prevention)

네 가지 조건 중 하나가 충족되지 않게 시스템을 디자인

즉, 네 가지 조건 중에 하나라도 만족시키지 않게 디자인

 

상호 배제: 리소스를 공유 가능하게 함

• 현실적으로 불가능

 

점유와 대기: 사용할 리소스들을 모두 획득한 뒤에 시작 (리소스를 전혀 가지지 않은 상태에서만 리소스 요청)

• 리소스의 활용률을 낮출 수 있는 방식이다.
• 만약 리소스가 인기가 너무 많아 여러 곳에서 사용한다면 출발 자체를 못할 수도 있다.

 

비선점: 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 한다.

• 모니터 방식과 비슷하다.
• 모든 자원이 선점 가능한 것은 아니다.

 

원형 대기: 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 요청

• 리소스에 번호를 붙이고 오름차순으로 할당하면 원행 대기는 발생하지 않음
• 데드락 방지를 위한 네 가지 접근 중에 가장 많이 쓰이는 방식

---

데드락 회피(Deadlock avoidance)

실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피하는 것

추가적인 정보는 현재 사용 가능한 리소스들, 이미 누군가에게 할당된 리소스들, 미래에 있을 리소스 요청이나 반환 등에 관한 정보

 

Banker Algorithm

• 리소스 요청을 허락해줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 안전할 때 까지 계속 요청을 거절하는 알고리즘
• 안전 순서열이 존재
• 안전 순서열대로 할당하면 모든 프로세스 할당 가능

---

데드락 감지와 복구

데드락을 허용하고 데드락이 발생하면 복구하는 전략

 

복구 전략

1. 프로세스를 종료한다. (지금까지 진행된 작업을 잃을 수 있다)
2. 리소스의 일시적인 선점을 허용한다.

 

데드락 무시

아몰라 개발자가 알아서 하겠지 하는 방식

---