[운영체제] 데드락(DeadLock) 관련 면접대비 질문정리

💡  데드락에 대해 설명해주세요.

데드락이란, 시스템 자원에 대한 요구가 뒤엉킨 상태입니다.

둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 말합니다.

---

💡 데드락의 발생조건은 무엇이 있나요?

• 상호 배제
  • 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제 될 때까지 기다려야 한다.
• 점유 대기
  • 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
• 비선점
  • 이미 할당된 자원을 강제로 빼앗을 수 없다.
• 순환 대기
  • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

---

💡 데드락의 해결 방법은 무엇입니까?

1. 예방(방지)

• 데드락의 발생조건 4가지중 하나라도 발생하지 않도록 하는것
  • 상호 배제 방지 :  한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
    • 동기화 문제가 발생 할 수 있음
  • 점유 대기 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때 까지 작업을 보류해서 나중에 또 다른 자원을 점유하기 위한 대기조건을 성립하지 않도록 한다.
  • 비선점 방지 : 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
  • 순환 대기 방지 : 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구 할 수 있도록 한다.
• 예방(방지) 방법은 시스템의 처리량이나 효율성을 떨어뜨리는 단점이 발생 할 수 있다.

 

2. 회피 

• 회피는 교착 상태가 발생하기 전에 교착 상태를 예상하여 안전한 상태에서만 자원 요청을 허용하는 방법입니다.
• 안전 상태 : safe sequence가 존재하여 모든 프로세스가 정상적으로 종료할 수 있는 상태
  • safe sequence : 교착 상태를 발생 시키지 않고 자원을 할당하는 순서
• 사용하는 알고리즘
  • 자원 할당 그래프 알고리즘
    • 자원 유형마다 인스턴스가 하나 있는 경우에 사용 할 수 있는 알고리즘
  • 은행원 알고리즘
    • 자원 유형마다 다수의 인스턴스를 갖는 경우에 사용 할 수 있는 알고리즘

 

3. 탐지

• 예방이나 회피를 사용하지 않았을 때 데드락이 발생할 수 있으니 여기에서 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용하는 것
• Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색
• 사용하는 알고리즘
  • 대기 그래프
  • 은행원 알고리즘
• 교착 상태를 탐지했다면 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 복구
• 복구 방식
  • 프로세스 종료
    • 교착 상태의 프로세스를 모두 중지
    • 교착 상태가 제거될 때까지 한 프로세스씩 중지
  • 자원 선점
    • 희생자 선택 : 최소의 피해를 줄 수 있는 프로세스를 선택
    • 롤백
      • 선점 된 프로세스를 문제 없던 이전 상태로 롤백
      • 보통 가장 안전한 방법은 프로세스를 중지시키고 재시작 하는 것
  • 기아 상태
    • 우선 순위를 사용하여 선점 될 때마다 프로세스 우선순위를 높이는 것

---

💡 희생자 선택은 어떻게 결정합니까?

프로세스 종료의 비용을 최소화하기 위하여 비용을 계산합니다.

비용 요인으로는 교착상태 프로세스가 점유하고 있는 자원의 수, 프로세스가 지금까지 실행하는 데 소요한 시간들과 같은 매개변수들들 고려하여 결정합니다.

---

💡  데드락(DeadLock)와 기아(Starvation)는 같은건가요?

데드락과 기아는 자원 할당을 무한히 대기한다는 점에서는 같아보이나 차이점이 있습니다.

데드락은 여러 프로세스나 스레드가 절대 발생하지 않는 이벤트나 자원 할당을 위해 무한정 대기를 합니다.

데드락은 프로세스의 상태 중 blocked 상태에서 발생합니다.

 

기아는 프로세스가 CPU 자원의 할당을 무한히 대기합니다.

기아는 CPU 스케쥴링과 관련이 있습니다.

기아는 프로세스의 상태 중 ready 상태에서 발생합니다.