[운영체제] 교착 상태

교착 상태의 정의

• 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태
• 교착 상태는 아사 현상과 비슷해 보이지만
  • 아사 현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제
  • 교착 상태는 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제

 

교착 상태의 발생

• 시스템 자원
  • 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생
• 공유 변수
  • 한 변수를 할당받은 상태에서 다른 변수를 기다리면 발생
• 응용 프로그램
  • 데이터베이스는 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착 상태가 발생 가능.

 

자원 할당 그래프

• 프로세스가 어떤 자원을 사용중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것.
• 프로세스 -> 원 / 자원 -> 사각형
• 여러 프로세스가 하나의 자원을 동시에 사용할 수 있는 경우 프로세스 수 -> 사각형 안에 작은 동그라미

 

 

교착 상태 필요 조건

• 상호 배제(Mutual Exclusion)
  • 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
  • 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없어 교착 상태가 발생한다.
• 비선점(non-preemption)
  • 한 프로세스가 사용중인 자원은 다른 프로세스가 뺏을 수 없는 비선점 자원이어야 한다.
• 점유와 대기(hold and wait)
  • 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
• 원형 대기(circular wait)
  • 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 

 

• 교착 상태는 위의 조건 모두를 충족해야 발생하고, 이 중 단 하나라도 충족하지 않으면 발생하지 않는다.
• 따라서 위의 네 가지 조건을 교착 상태 필요조건이라고 한다.

 

교착 상태 해결 방법

교착 상태 예방

• 상호 배제 예방
  • 시스템 내에 있는 독점적으로 사용할 수 있는 자원을 없애는 방법
  • 모든 자원을 공유하도록 하는 것인데, 시스템 내에는 공유할 수 없는 자원이 있다.
  • 따라서 상호 배제 예방은 사실상 어렵다.
• 비선점 예방
  • 모든 자원을 뺏을 수 있도록 만드는 방법
  • 임계구역 보호를 위해 잠금을 사용하면 자원을 뺏을 수 없고 기준 잡기가 어렵다
  • 아사 현상이 생길 수 있으므로 비선점 예방도 어렵다.
• 점유와 대기 예방
  • 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 all or nothing 방식을 적용
  • 이를 위해 프로세스는 시작 초기에 사용하려는 모든 자원을 한꺼번에 점유하거나 모두 반납해야 한다.
  • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
  • 자원의 활용성이 떨어진다.
  • 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
  • 일괄 작업 방식으로 동작한다.
• 원형 대기 예방
  • 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방한다.
  • 즉 모든 자원에 숫자를 부여해 숫자가 큰 방향으로만 자원을 할당하는 것이다.
  • 프로세스 작업 진행에 유연성이 떨어진다.
  • 자원의 번호를 어떻게 부여할 것인지 문제이다.

 

교착 상태 회피

• 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나눠주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나눠주는 방법
• 즉, 할당되는 자원의 수를 조절하여 교착 상태를 피하는 방법

 

• 자원의 총수 / 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나눈다.
• 시스템이 안정 상태를 유지하도록 자원을 할당한다.
• 안정 상태는 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말한다.

 

• 문제점
  • 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
  • 시스템의 전체 자원 수가 고정적이어야 한다.
  • 자원이 낭비된다.

 

교착 상태 검출

• 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식.

 

• 타임아웃을 이용한 교착 상태 검출
  • 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태로 처리하는 방법이다. 
  • 엉뚱한 프로세스가 강제 종료될 수 있다.
  • 모든 시스템에 적용할 수 없다.

•  
  • 그럼에도 불구하고 이 방법은 선호하는 방법이다.
  • 자원 할당 그래프를 이용하는 방법의 작업이 너무 많아 구현이 힘들기 때문이다.
  • 가벼운 교착 상태 검출 / 타임아웃 이용
  • 무거운 교착 상태 검출 / 자원 할당 그래프 이용

 

• 자원 할당 그래프를 이용한 교착 상태 검출
  • 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지 혹은 기다리고 있는지를 알 수 있다.
  • 교착 상태가 없는 자원 할당 그래프는 사이클이 존재하지 않고, 교착 상태가 있는 경우 사이클이 존재한다.
  • 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확히 파악할 수 있다는 것이 장점이다.
  • 추가 작업으로 인해 오버헤드가 발생하는 단점이 있다.

 

교착 상태 회복

• 교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는것
• 교착 상태를 유발한 프로세스를 강제로 종료하는 방법을 통해 회복한다. 두가지 방법이 있다.

 

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료
  • 이 방법은 종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 크다.
  • 따라서 종료 후에 순차적으로 실행한다.
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
  • 우선순위가 낮은 프로세스 먼저 종료
  • 우선순위가 같은 경우 작업 시간이 짧은 프로세스 먼저 종료
  • 두 조건 모두 같은 경우 자원을 많이 사용하는 프로세스 먼저 종료한다.