[Operating System] 교착상태(DeadLock)

교착상태(DeadLock)

다중 프로그래밍 시스템에서 프로세스가 결코 일어나지 않을 사건(또는 못하는 사건)을 기다리는 상태를 교착 상태(DeadLock)에 빠졌다고 한다. 즉, 시스템 자원에 요구가 뒤엉킨 상태로 두 프로세스가 사용하는 '비공유 자원'을 서로 기다리는 상태를 뜻한다.

교착상태 발생 조건

• 상호 배제 : 최소 하나의 자원이 비공유 자원이어야 한다. 한 번에 하나의 스레드만 사용할 수 있으며 다른 스레드가 사용하기 위해서는 사용 중인 스레드가 자원 해제해야 한다.
• 보유 및 대기 : 최소 하나의 자원을 보유(할당)한 상태로 동시에 다른 스레드가 사용하고 있는 자원을 요청해 대기하는 스레드가 존재해야 한다.
• 비선점 : 자원을 강제로 뺏을 수 없다. 즉, 선점(ex.메모리) 자원이 아닌 비선점(ex.프린터) 자원이어야 한다.
• 순환대기 : 다음과 같은 스레드 집합이 있어야 한다.
  • 스레드 T0는 자원 R0를 보유하고 자원 R1 보유를 기다린다.
  • 스레드 T1는 자원 R1를 보유하고 자원 R2 보유를 기다린다.
  • 스레드 T2는 자원 R2를 보유하고 자원 R0 보유를 기다린다.

발생 조건 4가지 중 3가지만 만족해도 교착상태에 빠지는 이유??

발생 조건 4가지 중 순환 대기 조건을 제외한 나머지 3가지 조건을 만족해도 교착 상태에 빠질 수 있다. 순환대기 조건은 나머지 3가지 조건을 만족하면 자연스레 발생할 수 있는 조건이기 때문이다.

교착상태 해결 방법

• 예방(Prevention)

  • 교착상태 발생 조건 4가지 중 최소 1가지 이상 성립하지 않도록 해 교착상태를 예방한다.
    • 상호배제 제거 : 모든 자원을 공유하면 되지만, 뮤텍스 락 같은 자원은 본질적으로 공유가 불가능해 상호배제 조건을 무조건 제거할 수는 없다.
    • 점유 및 대기
      1) 모든 자원을 한 번에 요청하고 점유한 상태로 시작한다. 하지만 자원은 필요한 시점에 동적으로 요청되기 때문에 비현실적이다.
      2) 소유한 모든 자원을 반납한 상태에서 요청한다. 현실적인 방안이지만 자원 활용률이 저하되고 기아 현상이 발생할 수 있다.
    • 비선점 : 새로운 자원을 요청했을 때 즉시 획득할 수 없다면, 소유한 모든 자원을 반납한다.
    • 순환대기 : 비교적 실현할 수 있는 해결책으로 모든 자원에 순서를 부여하고 자원 요청은 오름차순으로만 허용한다.
  • 예방 방법은 장치의 효율성과 시스템 처리량을 저하시킨다.

• 회피(Avoidance)

  • 리소스 요청에 대한 추가 정보를 요구하여 교착 상태 발생 가능성을 판단해서 적절하게 회피한다. 이때 중요한 점은 회피하는 것이지 교착상태를 제거하는 것이 아니다.
    • 프로세스의 시작 중단 : 프로세스 요구가 교착상태 발생 가능성이 있다면 프로세스의 시작을 중단시킨다.
      1) 안정상태 : 모든 스레드의 자원 최대한도까지 적절한 순서대로 할당해도 교착상태가 발생하지 않는 상태
      2) 불안정상태 : 안정상태가 아닌 상태, 이 상태일 때는 교착상태가 발생할 가능성이 존재한다.

      불안정상태 != 교착상태

      불안정상태일 때 항상 교착상태가 일어나는 것이 아니다. 하지만 교착상태가 발생했을 때는 불안정상태다.

    • 자원할당 거부 : 요청한 자원을 할당했을 때 교착상태가 발생할 수 있다면 요청한 자원을 할당하지 않는다.
      1) 은행가 알고리즘

• 감지(Detection)

  • 교착상태 예방 또는 회피하지 않으면 회복(복구) 알고리즘이 필요한데 이를 위해서는 교착상태의 감지가 선행되어야 한다.
  • 감지 알고리즘을 자주 실행하면 시스템 성능이 저하되지만, 교착 상태에 빠진 프로세스를 빨리 발견해 자원 유휴 상태를 방지할 수 있다.

• 회복(Recovery)

  • 운영자/사용자가 수동으로 해결하거나 시스템의 자동 복구 기능을 통해 회복할 수 있다.
    • 시스템의 자동 복구
      1) 하나 이상의 프로세스를 강제로 종료시켜 순환대기를 끊어버린다. 이 방식은 여태 작업한 결과를 전부 폐기하고 다시 처음부터 연산해야 해서 비효율적이다.
      2) 프로세스를 하나씩 중단시키고 감지 알고리즘을 통해 교착상태가 여전한지 확인한다. 이 방식은 감지 알고리즘을 반복 실행해 오버헤드가 크다.

  현대 OS에서 교착상태를 처리하지 않는 이유?

  대부분의 시스템에서는 교착상태가 한 달의 1번 꼴로 매우 드물게 발생한다.
  하지만 감지/예방 알고리즘은 시스템 자원을 매우 소모하기 때문에 발생 빈도 수가 적은 교착상태를 무시하는 게 비용적 측면에서 좋고, 실제로 발생했을 때 수동 조치(재시작 등)를 하는 게 더 간편하고 비용이 싸다.

학습하며 정리한 글이기 때문에 혼용된 표현 또는 잘못된 내용이 있을 수 있습니다.
만약, 발견하신 경우 댓글을 통해 알려주신다면 진심으로 감사드립니다.