CS 공부 & 면접 맛보기 0x0E [운영체제] : 데드락(Deadlock)의 해결 방법

데드락(Deadlock)의 해결 방법

질문

데드락을 해결하는 방법은 무엇인가요?

면접 답변

데드락(Deadlock)은 교착상태 예방(Prevention), 회피(Avoidance), 발견(Detection), 회복(Recovery)의 네 가지 방법으로 해결할 수 있습니다.

---

1. 교착상태 예방(Prevention)

교착상태 발생의 4가지 조건(비선점, 순환 대기, 점유 대기, 상호 배제) 중 하나를 제거하여 해결하는 방법입니다.

• 상호 배제(Mutual Exclusion) 부정:
  • 여러 프로세스가 동시에 자원을 사용할 수 있도록 허용합니다.
  • 단, 이 경우 동기화 문제가 발생할 수 있습니다.
• 점유 대기(Hold and Wait) 부정:
  • 프로세스가 실행되기 전에 필요한 모든 자원을 할당합니다.
  • 자원을 비효율적으로 사용하는 문제가 발생할 수 있습니다.
• 비선점(No Preemption) 부정:
  • 자원을 점유 중인 프로세스가 다른 자원을 요구할 때, 현재 점유한 자원을 해제하고 대기하게 합니다.
• 순환 대기(Circular Wait) 부정:
  • 자원에 고유한 번호를 부여하고, 번호 순서대로 자원을 요청하도록 합니다.

---

2. 교착상태 회피(Avoidance)

• 교착상태 발생 가능성을 완전히 배제하지 않고, 발생할 경우 피해가는 방법입니다.
• 은행원 알고리즘(Banker's Algorithm)이 대표적으로 사용됩니다.
• 시스템이 자원을 할당하기 전에 안전 상태(Safe State)인지 검사하여, 교착상태 발생 가능성이 있는 경우 자원을 할당하지 않습니다.

---

3. 교착상태 발견(Detection)

• 시스템 내에서 교착상태가 발생했는지 점검하는 기법입니다.
• 자원 할당 그래프(Resource Allocation Graph)를 사용하여 순환 대기 여부를 검사합니다.
• 순환이 발견되면 교착상태로 판단합니다.

---

4. 교착상태 회복(Recovery)

• 교착상태를 해결하는 마지막 수단으로, 이미 발생한 데드락을 해결하는 방법입니다.
• 방법 1: 교착상태를 유발한 프로세스를 종료.
• 방법 2: 교착상태 프로세스의 자원을 선점하여 다른 프로세스가 사용할 수 있도록 합니다.

---

관련 개념 설명

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

• 자원을 할당하기 전에 안전 상태(Safe State)인지 검사하는 알고리즘입니다.
• 모든 프로세스가 자원을 할당받아도 교착상태가 발생하지 않을 때만 자원을 할당합니다.
• 주로 리소스 관리 시스템에서 사용됩니다.

자원 할당 그래프(Resource Allocation Graph)

• 자원의 할당 상태를 시각적으로 표현하는 그래프입니다.
• 노드: 프로세스와 자원
• 간선:
  • 프로세스 → 자원 (자원 요청)
  • 자원 → 프로세스 (자원 할당)
• 순환이 존재하는 경우 교착상태로 판단합니다.

---

결론

• 데드락은 예방, 회피, 발견, 회복의 4가지 방식으로 해결할 수 있습니다.
• 각 방식은 시스템의 성능, 자원 사용 효율, 복잡성에 따라 선택되어야 합니다.