쉽게 배우는 운영체제 Chapter06 교착 상태

1. 교착상태의 개요

1.1 교착 상태의 정의

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 더 이상 작업을 진행하지 못하는 상태

1.2 교착 상태의 발생

시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생할 수 있다.

• 시스템 자원
  다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. 예를 들어 임계구역으로 보호되는 시스템 자원을 할당받은 후 양보하지 않는 경우 교착 상태가 발생할 수 있다.

• 공유 변수

  교착 상태를 발생시키는 임계구역 코드

  

• 응용 프로그램
  여러 프로세스가 데이터베이스에 저장된 데이터를 사용할 때는 데이터의 일관성을 유지해야 하는데 일관성을 유지하기 위해 잠금을 사용할 경우 교착 상태가 발생할 수 있다.

1.3 자원 할당 그래프

프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지 방향성이 있는 그래프로 표현한 것으로 프로세스는 원, 자원은 사각형으로 표현한다.

2. 교착 상태 필요조건

2.1 교착 상태 필요조건

교착 상태는 아래 네 가지 모두를 충족해야 발생한다.

• 상호 배제
  한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.

• 비선점
  한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.

• 점유와 대기
  프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.

• 원형 대기
  점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.

3. 교착 상태 해결 방법

교착 상태는 아사 현상과 비슷해 보이지만 차이점이 있다.
아사 현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제로 에이징으로 해결할 수 있지만, 교착 상태는 여러 프로세스가 작업을 진행하면서 자연적으로 일어나는 문제로 아사 현상보다 처리가 복잡한데 이를 해결하기 위한 방법은 다음과 같다.

• 교착 상태 예방
  교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화한다.

• 교착 상태 회피
  교착 상태가 발생하지 않는 수준으로 자원을 할당한다.

• 교착 상태 검출과 회복
  자원 할당 그래프를 모니터링하면서 교착 상태를 발견한다. 만약 교착 상태가 발생할 경우 교착 상태 회복 단계가 진행된다.

3.1 교착 상태 예방

1. 상호 배제 예방
   시스템 내에 독점적으로 사용할 수 있는 자원을 없애버리는 방법이다. 시스템 내의 모든 자원을 공유한다면 교착 상태가 발생하지 않는데 현실적으로 모든 자원을 공유할 수 없으며, 상호 배제를 적용하여 보호해야 하는 자원이 있기 때문에 현실적으로 어렵다.

2. 비선점 예방
   모든 자원을 빼앗을 수 있도록 만드는 방법이다.

3. 점유와 대기 예방
   프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 즉, 전부 할당하거나 아예 할당하지 않는 방법이다.
   이 방법은 자원에 대한 제약을 푸는 상호 배제 예방과 비선점 예방과 달리 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다.

4. 원형 대기 예방
   자원을 한 방향으로만 사용하도록 설정하여 원형 대기를 예방할 수 있다.

자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어렵고 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 교착 상태 예방은 현실적으로 어렵다.

3.2 교착 상태 회피

교착 상태 회피는 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시키는 방법이다.
프로세스의 작업 방식에 제약을 가하는 교착 상태 예방과 달리 교착 상태 회피는 시스템의 운영 방식에 변경을 가하지 않기 때문에 교착 상태 예방보다 유연하다.

• 은행원 알고리즘
  교착 상태 회피를 구현하는 방법 중 하나로 안정상태일 경우 자원을 할당하는 방법이다.

3.3 교착 상태 검출

교착 상태 예방은 실제로 구현하기 어렵고, 교착 상태 회피는 구현할 수 있지만 자원을 낭비하는 문제가 있다. 따라서 교착 상태 해결 방법 중 가장 현실적인 것은 교착 상태 검출이다.

• 타임아웃을 이용한 교착 상태 검출 - 가벼운 교착 상태 검출
  일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리
• 자원 할당 그래프를 이용한 교착 상태 검출 - 무거운 교착 상태 검출

3.4 교착 상태 회복

교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료한다.

• 교착 상태를 일으킨 모든 프로세스 동시에 종료
  종료된 프로세스들이 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 높기 때문에 강제로 종료한 후 다시 실행할 때는 순차적으로 실행해야 한다.

• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

  • 우선순위가 낮은 프로세스 먼저 종료
  • 우선순위가 같다면 작업 시간이 짧은 프로세스 먼저 종료
  • 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스 먼저 종료

출처

• 쉽게 배우는 운영체제 - 조성호 지음