[운영체제] 5. 교착 상태(Deadlock)

OS? Oh Yes! 책을 바탕으로 학습한 내용입니다.

교착 상태(Deadlock)

둘 이상의 프로세스가 각자가 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고 있는 상황을 말한다. 기아(Starvation)와는 다르게 외부적 조치가 없이는 벗어날 수 없다.

자원의 분류

• 선점 가능성
  • Preemptible
    선점 당한 후 돌아와도 문제가 발생하지 않음 ex) 프로세서, 메모리
  • Non-Preemptible
    선점 당한 후 돌아오면 문제가 발생 ex) 디스크 드라이브
• 할당 단위
  • Total allocation
    자원 전체를 한 프로세스에 할당 ex) 프로세서, 디스크 드라이브
  • Partitioned allocation
    자원을 분할하여 할당 ex) 메모리
• 동시 사용 가능성
  • Exclusive allocation
    한 순간에 한 프로세스만 사용 가능 ex) 프로세서, 메모리, 디스크 드라이브
  • Shared allocation
    여러 프로세스가 동시에 사용 가능 ex) 프로그램, 공유 데이터
• 재사용 가능성
  • Serially reusable
    시스템 내에 항상 존재, 사용이 끝나면 다른 프로세스가 사용 ex) 프로세서, 메모리, 디스크 드라이브, 프로그램
  • Consumable
    한 프로세스가 사용 후 사라짐 ex) 메세지, 시그널

교착 상태의 원인

교착 상태는 4가지의 원인으로 발생하며 이 중 하나라도 부정할 수 있다면 교착 상태에 빠지지 않는다.

• 자원의 배타적 사용(Mutual Exclusion Condition)
  배타적 사용이 요구되는 자원이 있으면 교착 상태가 발생할 수 있다.
• 자원의 부분 할당(Partial Allocation, Hold and Wait)
  프로세스는 필요한 시점에 필요한 자원을 부분적으로 확보하기에 어느 시점에 필요한 자원을 할당받지 못하지만 확보한 자원은 놓치 않게 되어 교착 상태가 발생할 수 있다.
• 자원의 선점 불가능성(Non Preemption)
  자원이 선점 불가할 경우 교착 상태가 발생할 수 있다.
• 자원에 대한 환형 대기(Circular Wait)
  자원을 보유한 채로 서로의 자원을 요청하게되면 교착 상태가 발생할 수 있다.

교착 상태의 해결

• 예방(Prevention)
  교착 상태의 원인이 되는 조건 중 하나를 없앰으로써 교착 상태 발생을 방지하는 방법, 교착 상태를 확실히 제거할 수 있지만 심각한 자원 낭비와 특정 프로세스의 무한 대기 가능성이 있다.

  • 자원의 배타적 사용을 배제
    배타적 사용이 필요한 자원을 공유할 경우 큰 문제를 야기할 수 있다. 따라서 배제할 수 없다.
  • 자원의 부분할당을 배제
    자신이 필요한 모든 자원을 미리 할당받아 실행하게끔 하는 방법으로 심각한 자원 낭비를 초래하고 무한 대기에 빠질 수 있다.
  • 자원의 선점 불가능성을 배제
    모든 자원이 선점 가능할 경우 비정상적인 프로세스 종료로 인한 자원 낭비와 무한 대기에 빠질 수 있다.
  • 자원의 환형 대기 상황을 배제
    자원에 대한 우선 순위를 책정하여 프로세스가 이 우선순위를 지켜 요청하도록 하는 방법, 마찬가지로 자원의 낭비와 무한 대기를 겪을 수 있다.

• 회피(Avoidance)
  특정한 알고리즘을 통해 시스템의 상태가 지속적으로 안전 상태를 유지할 수 있도록 조절하는 방법, 안전 상태는 교착 상태가 발생할 수 없는 상태를 의미한다. 대기 상태가 길어질 수 있지만 예방보다 자원의 낭비를 감소시킬 수 있다.

  • 은행가 알고리즘
    은행가 알고리즘이 정상적으로 작동하기 위해서는 다음과 같은 전제가 필요하다.
    • 시스템 내의 프로세스 수가 고정되어 있어야 한다.
    • 자원의 수가 고정되어 있어야 한다.
    • 각 프로세스가 요구할 자원의 최대 개수를 알아야 한다.
    • 각 프로세스는 할당받은 자원을 사용한 후 반드시 반납해야 한다.
    프로세스의 자원 요청이 있을 때 마다 요청에 따른 할당이 안전 상태를 유지할 수 있는지 확인한다. 안전 상태의 판단은 현 상태에서 모든 프로세스가 정상적으로 종료할 수 있는 길이 적어도 하나 이상 있는가다.

• 탐지(Detection)
  교착 상태가 발생하였을 때 그를 탐지하여 조치(복구)를 취하는 방법이다. 탐지를 위해서는 현 시스템의 상황을 알아야하는데 자원 할당 그래프(Resource Allocation Graph, RAG)로 나타낸다.

  • 그래프 제거법
    싱크(나가는 간선이 없는 프로세스 노드, 활동이 가능한 프로세스)로부터 시작하여 들어오는 모든 간선을 제거한다.(가지고 있던 자원의 반납) 모든 싱크에 대해서 같은 작업을 수행했을 때 간선이 남아있으면 교착 상태다.
  • 그래프 탐색법
    대기 상황을 나타내는 간선을 따라 진행했을 때 싱크가 발견되면 교착 상태가 없으며 모든 경로를 탐색해도 싱크가 발견되지 않는다면 교착 상태가 있는 것이다.
    사이클은 모든 자원이 한 개씩 있을 때만 교착 상태를 나타낸다.

• 복구(Recovery)

  • 프로세스의 종료(Process Termination)
    특정 프로세스를 종료시켜 자원을 확보하는 방법으로 프로세스를 종료시킬 때 종료 비용을 최소화하는 것이 관건이다.
    • 종료 비용이 가장 저렴한 하나의 프로세스를 종료시키는 방법
      하나를 종료시킬 때 마다 교착 상태가 제거되었는지 확인해야한다.
    • 모든 부분 집합을 만들어 종료 비용이 가장 저렴한 하나의 부분 집합을 모두 종료시키는 방법
      모든 부분 집합에 대한 비용을 계산하기가 복잡하고 힘들다.
  • 자원의 선점에 의한 방식
    자원을 선점시켜 교착 상태를 해소하는 방법으로 선점으로 인한 복구 비용을 최소화하는 것이 관건이다.
    • 검사점 지정(Checkpointing)
      프로세스의 실행 중간 중간에 결과값을 저장해두어 복구시 검사점으로 복구