6.교착 상태

교착 상태

---

• 교착 상태
  • 교착상태란(Dead Lock)
  • 교착 상태 발생의 필요 충분 조건
  • 교착 상태의 해결 방법
    • 은행원 알고리즘

---

교착상태란(Dead Lock)

둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

• 상호 배제에 의해 나타나는 문제점

자동차(프로세스)들이 현재 위치한 길(자원)을 점유함과 동시에 다른 차가 사용하는 길을 사용하려고 대기하고 있지만 다른 길을 사용할 수 없으며 현재 길에서도 벗어나지 못하는 상태이다.

교착 상태 발생의 필요 충분 조건

이 네 가지 조건 중 하나라도 충족되지 않으면 교착 상태가 발생하지 않는다.

• 상호 배제(Mutual Exclusion) : 한 번에 한 개의 프로세스만이 공유 자원을 사용
• 점유와 대기(Hold and Wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있다.
• 비선점(Non-preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없다.
• 환형 대기(Circular Wait) : 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어, 프로세스가 자신의 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구한다.

교착 상태의 해결 방법

교착 상태를 막으려면 위 4가지의 필요 충분 조건 중 한 가지를 제거하면 된다.

• 예방 기법(Prevention) :

  • 교착 상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로, 교착상태 발생의 네 가지 조건 중에서 어느 하나를 제거(부정)함으로써 수행된다.

  • 자원의 낭비가 가장 심하다

  • 상호 배제 부정 : 여러 프로세스가 동시에 하나의 공유 자원을 사용할 수 있게 한다.

  • 점유와 대기 부정 : 프로세스가 실행되기 전에 필요한 모든 자원을 할당함으로써 프로세스 대기를 없앤다. 또는 프로세스가 자원을 점유하지 않은 상태에서만 자원을 요구하게 한다.

  • 비선점 부정 : 자원을 점유한 프로세스가 다른 자원을 요구할 때 점유한 자원을 반납하게 한다.

  • 환형 대기 부정 : 자원을 선형 순서로 정렬해 고유 번호를 할당한다. 그리고 각 프로세스에서 요구할 수 있는 번호의 방향을 정해서 한쪽 방향으로만 자원을 요구하게 한다.

• 회피 기법(Avoidance) : 교착 상태가 발생할 가능성을 배제하지 않고 교착 상태가 발생하면 적절히 피해나가는 방법, 주로 은행원 알고리즘이 사용된다.

• 발견 기법(Detection) : 시스템에 교착 상태가 발생했는지 점검하여 교착 상태에 있는 프로세스와 자원을 발견하는 방법

• 회복 기법(Recovery) : 교착 상태를 일으킨 프로세스를 종료하거나 교착 상태의 프로세스에 할당된 자원을 선정하여 프로세스나 자원을 회복하는 것

은행원 알고리즘

운영체제가 안전한 상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족할 수 있을 때까지 계속 거절하는 알고리즘

• 안전 상태 : 시스템이 교착 상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해줄 수 있는 상태로 안전순서열이 존재하는 상태
  • 안전순서열 : 모든 고객들에게 돈을 빌려주고 은행이 다시 돈을 돌려받을 수 있는 상태
• 불안전 상태 : 안전순서열이 존재하지 않는 상태. 불안전 상태는 교착상태이기 위한 필요조건으로, 교착 상태는 불안전 상태에서만 발생하지만, 무조건적으로 발생하는 것은 아니다.