데드락(Deadlock)의 이해

on OS

[공룡책 정리] 데드락의 이해: Chapter 8. Deadlocks (Part 1) 참고
- https://www.inflearn.com/course/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B3%B5%EB%A3%A1%EC%B1%85-%EC%A0%84%EA%B3%B5%EA%B0%95%EC%9D%98/lecture/65282?tab=curriculum - https://www.youtube.com/watch?v=FXzBRD3CPlQ

데드락(Deadlock)의 이해

데드락(Deadlock)이란?

프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로 대기중인 쓰레드 또는 프로세스들이 다시는 그 상태를 변경시킬 수 없으면( 요청하는 자원이 다른 프로세스나 쓰레드에 의해 점유되어 있고 그들 도 다 대기상태에 있기 때문) 이런 상황을 ‘교착 상태’라고 한다. 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생합니다.

데드락 발생 조건

데드락은 아래의 4가지 조건을 모두 만족할 때 발생한다.

상호배제(Mutual exclusion)

  • 최소한 하나의 자원이 비공유 모드로 점유되어야 한다.

점유하며 대기(Hold-and-wait)

  • 자원을 최소한 하나 점유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.

비선점(No preemption)

  • 자원들을 선점할 수 없어야 한다. 즉 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 작업을 종료한 후 그 프로세스에 의해 자발적으로만 방출될 수 있다.

순환대기(Circular wait)

  • 대기 프로세스의 집합이 순환 형태로 대기하고 있어야 한다.

데드락의 해결법

데드락의 해결법을 크게 3가지로 분류할 수 있습니다.

  • 데드락이 발생하지 않도록 예방(prevention)하기
  • 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance)하기
  • 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기
  • 데드락 무시하기

데드락 예방

데드락은 발생 조건 4가지를 모두 만족하는 경우 발생하기 때문에 이 4가지 조건 중 하나만 발생하지 않도록 막아도 데드락을 예방할 수 있다. 교착상태가 발생하지 않는것이 무조건 좋지만 발생하지 않는 환경을 만들어 버린다면 자원을 효율적으로 사용할 수 없어 현대시스템에서는 이 예방 방법을 잘 사용하지 않는다.

  • 자원의 상호배제 조건 방지 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.

그러나 일반적으로 상호배제 조건 방지로 교착상태를 예방하는 것은 불가능하다. Mutex lock과 같이 어떤 자원들은 근본적으로 공유가 불가능하기 때문이다.

  • 점유 대기 조건 방지 : 한 프로세스가 자신이 필요한 자원을 모두 사용할 수 있을 때만 작업을 시작한다.

  • 비선점 조건 방지 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.

  • 순환 대기 조건 방지 : 자원을 순환 형태로 대기하지 않도록 일정한 한쪽 방향으로만 자원을 요구할 수 있도록 한다.

데드락 회피

교착 상태를 인정하고 피해가는 방법이다. 대표적으로 은행원 알고리즘이 있다.

교착 상태가 발생할 것 같을 때 탐지하고 복구하는 탐지 및 복구 방법과 비교해 회피 방법은 자원을 요청할 때마다 회피 알고리즘을 수행해 오버헤드가 훨씬 심하다는 단점이 있다. 현대 시스템에서는 이런 회피의 오버헤드를 감당할 수 있는 시스템이 거의 없어 잘 사용되지 않는다.

데드락 탐지 및 복구

교착상태가 자주 발생하는 시스템에서 일반적으로 사용하는 방법이다. 교착 상태 존재 여부 및 연관된 프로세스와 자원을 알아낸 후 복구한다. 주로 순환 대기 존재 여부에 초첨을 맞추고 탐지한다. 대표적으로 자원할당 그래프를 소거하며 탐지하는 방법이 있다.

탐지 알고리즘도 회피 알고리즘과 같이 오버헤드가 발생하기 때문에 얼마나 자주 얼마나 자주 탐지알고리즘을 호출하는지가 중요하다. 시스템마다 교착상태가 일어나는 빈도가 다르기 때문에 각각 다른 기준으로 알고리즘을 호출해야 한다.

  1. 일정한 기간으로 주기적으로 호출하는 방법 ex) 3일에 1번, 일주일에 1번, 1달에 1번 등등
  2. 자원을 할당했을 때 자원이 즉시 할당이 되지 않을 때
  3. CPU 이용률이 기준 이하로 떨어졌을 때 ( 교착상태가 발생하면 프로세스들이 대기하면서 이용률이 떨어지기 때문 )

탐지에서 순환 과정을 찾아낸다면 순환대기를 깨서 교착 상태로부터 회복한다. 복구 알고리즘을 사용 시 프로세스가 작업중인 걸 일부 손실되는 것을 감당해야 한다.

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

데드락 무시

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

  • 윈도우와 유닉스를 포함한 대부분의 운영체제가 데드락을 무시하는 방법을 사용한다고 한다.

  • 교착상태가 드물게 발생하는데 교착상태를 해결하기 위해 많은 비용이 발생한다면 효율적이지 않기 때문에 교착상태가 일어나지 않는다고 가정하고 무시한다.

  • 만약 교착상태가 발생해 문제가 발생한다면 사용자가 직접 프로세스를 죽이거나 재부팅하는 방법을 통해 교착상태를 해결한다.