[OS] Chapter 6 교착 상태

1. 교착 상태의 개요

1.1 교착 상태의 정의

• 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하기 못하는 상태를 교착 상태라고 한다.
• 아사 현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제이고, 교착 상태는 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제이다. → 운영체제가 감사히다가 교착 상태가 발생하면 강압적으로 해결해야 한다.

1.2 교착 상태의 발생

• 시스템 자원 - 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다.
• 공유 변수
• 응용 프로그램

1.3 자원 할당 그래프

• 자원 할당 그래프 - 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다라고 있는지 방향성이 있는 그래프로 표현한 것이다.
• 프로세스는 원으로, 자원은 사각형으로 표현한다. 자원을 사용하고 있는 경우는 자원으로부터 프로세스로 향하는 화살표로 표시하고, 반대로 프로세스가 자원을 기다리는 경우 프로세스로부터 자원으로 향하는 화살표로 표시한다.
• 식사하는 철학자 문제 - 철학자 4명이 둥그런 식탁에 둘러앉아 식사를 하는데 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다. 이때 모두 굶어죽는다.

2. 교착 상태 필요조건

2.1 교착 상태 필요조건

• 4가지 조건을 모두 충족해야지만 교착 상태가 발생한다.
  • 상호 배제 - 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
  • 비선점 - 한 프로세스가 사용 중인 자원을 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
  • 점유와 대기 - 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
  • 원형 대기 - 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.
• 상호 배제와 비선점 조건은 자원의 특징을 나타내고, 그리고 점유와 대기, 원형 대기 조건은 프로세스가 어떤 행위를 하고 있는지를 나타낸다.

2.2 식사하는 철학자 문제와 교착 상태 필요조건

• 상호 배제 - 포크는 한 사람이 사용하면 다른 사람이 사용할 수 없는 배타적인 자원이다.
• 비선점 - 배타적인 자원을 사용한다고 할지라도 자원을 빼앗을 수 있담녀 교착 상태가 발생하지 않을 것이다.
• ⇒ 상호 배제와 비선점 조건은 임계구역과 관련이 있다. 임계구역을 보호하기 위해 잠금 장치를 사용하면 상호 배제와 비선점 조건이 보장되 교착 상태가 발생할 수 있다.
• 점유와 대기 - 한 프로세스가 자원을 점유한 상태에서 다른 프로세스의 자원을 기다리면 서로 진행을 방해하는 상태가 되므로 교착 상태가 발생한다.
• 원형 대기 - 점유와 대기를 하는 프로세스들이 원을 이루면 서로 진행을 방해하는 상태가 되므로 교착 상태가 발생한다.
• ⇒ 중요한 점은 교착 상태와 아사 현상이 다르다는 것이다. → 교착 상태는 아사 현상과 다르게 잘못이나 오류가 없어도 자연적으로 발생한다.

3. 교착 상태 해결 방법

3.1 교착 상태 해결 방법

• 교착 상태를 해결하는 방법은 예방, 회피, 검출있고, 추가적으로 회복을 하는 방법도 있다.
  • 교착 상태 예방 - 교착 상태를 유발하는 네 가지 조건을 발생하지 않도록 무력화하는 방식이다. → 실효성이 적어 잘 사용되지 않는다.
  • 교착 상태 회피 - 자원 할당량을 조절하여 교착 상태를 해결하는 방식이다. 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것이다. → 보장이 없어서 실효성이 적다.
  • 교착 상태 검출과 회복 - 제약을 가하지 않고 자원 할당 그래프를 모니터링 하면서 교착 상태가 발생하는지 살표보는 방식이다. → 교착 상태가 발생하면 ㅗ히복이 진행된다. → 현실적인 접근 방법이다.

3.2 교착 상태 예방

• 교착 상태 예방은 네 가지 조건 중 하나라도 막는 것으로 4가지 방법이 있다.

3.2.1 상호 배제 예방

• 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 아예 없애버리는 방법이다. → 현실적으로 모든 자원을 공유할 수 없으며 상호 배제를 적용해서 보호해야 하는 자원이 있다.

3.2.2 비선점 예방

• 모든 자원을 빼앗을 수 있도록 만드는 방법이다. → 못한다. 설사 가능하게 하더라도 준이나 시간을 설정하기 어렵다. 아사 현상을 일으킬 수 있다. → 이는 에이징으로 해결하기도 어렵다.

3.2.3 점유와 대기 예방

• 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 전부 할당하거나 아예 할당하지 않는 방식을 적용하는 것이다.
• 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다는 점에서 의미가 있다.
• 단점
  • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
  • 자원의 활용성이 떨어진다.
  • 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다. ← 동시에 많은 자원의 확보가 어렵다. → 아사 현상 발생 가능
  • 결국 일괄 작업 방식으로 동작한다. → 시스템 효율이 떨어진다.

3.2.4 원형 대기 예방

• 점유와 대기를 하는 프로세스들이 원형을 이루지 못하게 막는 방법이다. 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것이다.
• 단점
  • 프로세스 작업 진행에 유연성이 떨어진다.
  • 자원의 번호를 어떻게 부여할 것인지가 문제이다.

3.2.5 교착 상태 예방 정리

• 자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어려우며 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없다.

3.3 교착 상태 회피

3.3.1 교착 상태 회피의 개념

• 교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나눠어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법이다.
• 시스템의 운영 방식에 변경을 가하지 않기 때문에 교착 상태 예방보다 좀더 유연하다.
• 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.
• 할당된 자원이 늘어날 수록 불안정 상태가 커진다.

3.3.2 은행원 알고리즘

• 교착 상태 회피를 구현하는 방법은 여러 가지 인데 그 중 하나가 은행원 알고리즘이다. 은행이 대출을 해주는 방식과 비슷해서 이런 이름이 붙었다.
• 은행원 알고리즘의 변수
  • 전체 자원 - 시스템 내 전체 자원의 수
  • 가용 자원 - 시스템 내 현재 사용할 수 있는 자원의 수
  • 최대 자원 - 각 프로세스가 선언한 최대 자원의 수
  • 할당 자원 - 각 프로세스가 현재 할당된 자원의 수
  • 기대 자원 - 각 프로세스가 앞으로 사용할 자원의 수
• 자원을 할당할 때의 변수
  • 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다.
  • 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않는다.

3.3.3 교착 상태 회피의 문제점

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다. → 정확하게 선언하는 것이 어렵다.
• 시스템의 전체 자원 수가 고정적이어야 한다. → 새로운 자원이 추가되는 일이 빈번하고 고장이 빈번하기 때문에 이 수는 유동적이다.
• 자원이 낭비된다. → 모든 불안정 상태가 교착 상태가 되는 것은 아님에도 불구하고 자원을 할당하지 않는 것은 자원 낭비이다.

3.4 교착 상태 검출

3.4.1 교착 상태 검출의 개념

• 교착 상태 검출이 가능 현실적인 방법이다.
• 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법이다.
• 타임아웃을 이용하는 방법과 자원 할당 그래프를 이용하는 방법이 있다.

3.4.2 타임아웃을 이용한 교착 상태 검출

• 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다.
• 단점
  • 엉뚱한 프로세스가 강제 종료될 수 있다.
  • 모든 시스템에 적용할 수 없다. → 원격지에 있는 프로세스의 응답이 없는 것이 교착 상태인지, 네트워크 문제인지, 처리가 늦어지는 것인지 구분할 수 없다.
• 단점이 있어도 타임아웃을 데이터베이스와 운영체제에서 많이 선호한다.
• 타임아웃은 가벼운 방법이라 가벼운 교착 상태 검출이라 부른다. 자원 할당 그래프를 이용하는 방법은 무거운 교착 상태 검출이라 부른다.
• 타임아웃으로 데이터의 일관성이 깨지는 문제를 해결하기 위해 데이터 베이스에서는 체크 포인트와 롤백을 사용한다.
  • 체크포인트 - 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시이다.
  • 롤백은 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것을 말한다.

3.4.3 자원 할당 그래프를 이용한 교착 상태 검출

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

3.5 교착 상태 회복

• 교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 하는데 이를 교착 상태 회복이라고 한다. 교착 상태를 유발한 프로세스를 강제로 종료한다.
• 종료 방법
  • 교착 상태를 일으킨 모든 프로세스를 동시에 종료 → 동시에 작업을 시작하면 또 문제 발생 가능성이 있다. 순서대로 실행해야 한다.
  • 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법이다.
    • 우선순위가 낮은 프로세스 중에서 작업 시간이 짧고 자원을 많이 사용하는 프로세스를 먼저 종료한다.
• 프로세스 종료 뿐만 아니라 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야 한다. 시스템 복구는 명령어가 실행될 때마다 체크 포인트를 만들어 가자장 최근의 검사 시점으로 돌아기는 식으로 한다. → 시스템에 부하를 줘서 선택적으로 사용해야 한다.