[운영체제]교착상태(Dead Lock)

교착상태(Deadlock)

• 2개 이상의 프로세스 or 스레드가 서로가 가진 리소스(자원)를 기다리는 상태
• 무한정 기다리며 벗어나지 못함

데드락 만드는 필요충분 조건

1. Mutual Exclusion : 리소스를 공유해서 사용할 수 없음
2. Hold and Wait : 프로세스가 이미 하나 이상의 리소스를 갖고 있는 상태(hold)에서 다른 프로세스가 사용 중인 다른 리소스를 추가로 기다리는 것(wait)
3. No Preemption : 리소스 반환은 오직 그 리소스를 취득한 프로세스만 가능. 강제로 자원을 뺏을 수 없음
4. Circular Wait : 프로세스들이 순환 형태로 리소스를 기다리는 것

 

해결 방법

1️⃣ 방지/예방(Prevention)

• 4가지 조건 중 하나가 충족되지 않게 시스템 디자인
• 자원 낭비가 가장 심한 방법
• 시스템의 처리량이나 효율성 떨어트릴 수 있음

1. Mutual Exclusion
   • 리소스 공유 가능하게 함
   • 단점) 여러 프로세스가 자원을 공유하기 때문에 의도치 않은 결과 얻을 수 있음
2. Hold and Wait
   • 사용할 리소스 모두 획득한 뒤 시작(대기 없애기) or 리소스 전혀 없는 상태에서만 리소스 요청 가능
   • 단점) 자원이 오랫동안 할당되고 사용되지 않으면서 낭비될 수 있음
3. No Preemption
   • 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 함
   • 단점) 공유 자원에 대한 동기화(상호배제) 의미가 없어짐
4. Circular Wait
   • 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스 요청(선형 대기로 만들기)

2️⃣ 회피(Avoidance)

• 실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피 하는 것
• 자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 할당을 허용하는 것
• Safe State(안정 상태) : 시스템의 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있을 때 (↔ 불안정 상태)
• Safe Sequence(안정 순서) : 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서
• 데드락은 불안정 상태에서 발생할 수 있음

 

Banker's Algorithm

• 리소스를 허락해줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 안전할 때까지(safe state에 드는지 확인) 계속 요청을 거절하는 알고리즘
• 대기중인 다른 프로세스들의 활동에 대한 교착 상태 가능성 미리 조사하는 것
• 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것 보장

🔴 단점

1. 자원 사용률이 굉장히 낮음(안정 상태 유지해야 해서)
2. 미리 최대 자원 요구량을 알아야 함
3. 자원의 양과 프로세스 수가 일정해야 함

3️⃣ 감지&복구(Detection & Recovery)

• 데드락 허용하고 감지되면 복구
• 감지
  • Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색 (with 현재 시스템의 자원 할당 상태)
  • 교착상태 발견 알고리즘과 자원 할당 그래프 사용할 수 있음
• 복구 전략(순환 대기에서 벗어나기 위함)
  1. 프로세스 종료
     • 교착상태에 있는 프로세스 모두 종료 : 부분 결과가 폐기될 수 있음
     • 하나씩 종료해가며 교착상태 해결 : 매번 탐지 알고리즘을 사용해야 하기 때문에 부담이 큼
  2. 리소스의 일시적인 선점 허용
     • 교착상태에 있는 프로세스가 가진 리소스를 다른 프로세스에 할당
     • 우선순위 낮은 or 수행된 정도가 적은 or 사용되는 리소스가 적은 프로세스를 위주로 해당 프로세스의 리소스 선점

참고
https://youtu.be/ESXCSNGFVto
https://coding-factory.tistory.com/311
https://chanhuiseok.github.io/posts/cs-2/