교착 상태

교착상태

• 다른 작업이 끝나기만을 기다리며 작업을 더 이상 진행하지 못하는 상태를 말한다.(프로세스가 살아있으나 작업할 수 없는 상태) 한정된 자원에서 여러 프로세스가 작업을 하다보면 자연적으로 발생할 수 있다.

• 컴퓨터 시스템에서 시스템 자원을 사용하거나 잠금을 사용할 때 교착상태가 발생할 수 있다.

1. 시스템 자원 사용 도중 발생한 교착상태
   • P1 프로세스 : 스캐너 -> 프린터를 사용해야 하는 프로세스
   • P2 프로세스 : 프린터 -> 스캐너를 사용해야 하는 프로세스

2. 잠금(Lock) 때문에 발생하는 교착상태

   • 임계 구역 2개를 lock1, lock2로 관리된다고 가정하면,
   • 임계 구역에 프로세스가 진입하면 lock = ture 로 바뀐다.
   • 두개의 프로세스가 두개의 임계 구역을 순서만 다르게 쓰는 경우
   • 위에 시스템 자원을 사용하는 도중 발생한 교책상태 처럼 계속 무한 대기하는 결과가 초래된다.

3. DB와 같은 응용프로그램의 교착상태

   • DB의 경우 데이터 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착상태가 발생 할 수 있다.

교착 상태 필요 조건

• 교착상태는 상호 배제, 비선점, 점유와 대기, 원형 대기의 4가지 조건을 동시에 만족해야만 교착 상태가 발생한다

1. 상호 배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야한다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다.
2. 비선점 : 프로세스가 사용중인 자원을 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야한다.
3. 점유와 대기 : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다. 다른 프로세스의 작업 진행을 방해하는 교착 상태가 발생하기 위해서는, 다른 프로세스가 필요로 하는 자원을 점유하면서 또 다른 자원을 기다리는 상태가 되어야한다.
4. 원형 대기 : 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야한다. 즉 프로세스가 다른 프로세스의 진행을 방해하는 방향이 원을 이루어야한다.

   자원의 특징과 프로세스의 행위로 인해 교착상태가 발생한다.

   • 사용하는 자원을 동시에 공유할 수 없고 중간에 빼앗을 수 없다면 자원을 가진 프로세스가 자원을 반환할 때 까지 무작정 기다려야한다.
   • 프로세스가 자원을 점유 및 대기하고 있는 상태에서 다른 프로세스를 방해하는 방향이 원을 이루면 서로 양보하지 않기 때문에 교착 상태가 발생한다.

식사하는 철학자 문제

• 교착상태를 설명하기위한 예시로 식사하는 철학자 문제를 살펴보자.
  

  철학자 5명이 둥근 식탁에 둘러 앉아 식사를 하기 위해서는 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다. 포크는 공유할 수 없으며, 아무도 사용하지 않는 포크만 잡을 수 있다.

• 왼쪽의 포크를 잡는것 까지는 모든 철학자가 성공하지만, 오른쪽의 포크를 잡으려고 할때 오른쪽 포크는 다른 철학자가 점유한 상태가 된다. 이로인해 철학자 누구도 식사를 마칠 수 없다.

1. 상호 배제 -> 포크를 공유할 수 없다. 포크는 배타적인 자원이다.
   2.비선점 -> 사용중인 포크는 빼앗을 수 없다.
2. 점유와 대기 -> 왼쪽에 있는 포크를 점유한 후 오른쪽의 있는 포크를 기다린다.
3. 원형 대기 -> 철학자들이 다른 철학자의 식사를 방해하는 방향은 왼쪽이며, 원형 식탁에 앉아있으므로 해결되지 않는 문제가 된다. (사각 식탁의 경우 교착상태가 발생하지 않는다.)

교착상태 해결 방법

교착상태를 해결하는 방법은 예방, 회피, 검출이 있으며 추가적으로 교착 상태가 발견된 후 자원을 회복하는 방법이 있다.

교착상태 예방

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

• 그러나 이 방법은 실효성이 적음
• 왜냐하면 자원을 보호해야 하기 때문에 상호 배제 예방과 비선점 예방을 사용하기 어렵고 점유와 대기 예방, 원형 대기 예방은 프로세스 작업 방식을 제한하고 자원을 낭비한다는 문제점이 있다.

1. 상호배제 예방

독점적으로 사용하는 자원을 모두 없애버리는 방법
시스템 내의 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않는다.
시스템 내에는 공유할 수 없는 자원이 있기 때문에, 현실적으로 어렵다.

2. 비선점 예방

모든 자원을 빼앗을 수 있도록 만드는 방법
어떤 기준으로 빼앗을지, 빼앗아서 얼마나 사용할지 결정하기 어렵다.
아사 현상을 일으킬 수 있다. 아사 현상을 막기위해 에이징을 사용하다보면 결국 비선점 자원이 생기기 때문에 비 선점 조건을 무력화하기 어렵다.

3. 점유와 대기 예방

전부 할당하거나 아예 할당하지 않는 방식 필요한 자원을 모두 할당한 후 실행한다.
프로세스는 자원을 점유한 상태에서 다른 자원을 기다릴 수 없다.
자신이 사용하려는 모든 자원을 한번에 점유하거나, 그렇지 못하는 경우 모든 자원을 반납해야한다.

점유와 대기 예방은 다음과 같은 단점이 있다.

• 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
  프로세스가 작업동안 사용되는 모든 자원을 알기 어렵다. 작업 도중 추가되는 자원도 존재하기 때문이다.
• 자원의 활용성이 떨어진다.
  프로세스가 앞으로 사용할 자원까지 모두 선점한다는 것은 당장 사용하지 않을 자원을 선점한다는 것이기 때문에 자원이 낭비된다.
• 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
  많은 자원을 사용하는 프로세스는 동시에 많은 선점하기 어려운 조건이기 때문에, 작업이 지연될 수 있다.
• 결국 일괄 작업 방식으로 동작한다.
  다른 프로세스가 종료하고 자원을 반납할 때까지 해당 자원을 사용해야하는 다른 프로세스들 대기상태가 된다.

4. 원형 대기 예방

점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
자원을 한 방향으로만 사용하도록 설정하는것이다. 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당한다.

원형 대기 예방에는 다음과 같은 단점이 있다.

• 프로세스 작업 진행에 유연성이 떨어진다.
  큰 번호 자원을 사용하고 작은 번호 자원을 사용할 수 없기 때문에
  프로세스가 프린터를 사용하고 마우스를 할당 받을 수 없다.
  (예시) 위에 그림 참고!

• 자원에 번호를 어떻게 부여할지가 문제가 된다.
  큰 번호 자원을 사용하고 작은 번호 자원을 사용할 수 없기 때문에 자원에 번호를 붙일때 신중해야한다. 하지만 어떤 기준으로 부여할지 문제가 발생한다.

교착 상태 회피

• 자원 할당량을 조절하여 교착상태를 해결하는 방식
• 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단
• 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정상태와 불안정 상태로 나누고 안정상태를 유지하도록 한다.
• 그러나 얼마만큼 자원을 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적음

자원 할당 기준

• 자원을 할당하는 경우 (안정상태)
  • 각 프로세스의 기대 자원(프로세스가 대기하는 자원의 수)과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 뜻으로 안정 상태이다.
• 자원을 할당하지 않는 경우 (불안정 상태)
  • 가용 자원이 각 프로세스들의 기대 자원보다 크지 않으면 자원을 할당하지 않는다.이는 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이다. 즉 불안정 상태 이다.

교착상태 회피의 문제점

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

교착 상태 검출과 회복

• 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착상태가 발생하는지 살펴보는 방식
• 교착 상태가 발생하면 교착 상태 회복 단계가 진행
• 교착 상태를 해결하는 가장 현실적인 접근 방법

교착 상태 검출 방법

• 가벼운 교착 상태 검출 : 타임아웃 이용
  • 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하고 처리하는 방법
  • 일정 시간 동안 작업이 진행되지 않으면 해당 프로세스를 죽인다.
  • 예시) 윈도우에서 '프로그램이 응답이 없어 종료합니다.'라는 메시지의 경우 타임아웃을 이용하는 방법의 대표적인 예시
  • 문제점은 다음과 같다.
    • 엉뚱한 프로세스가 강제 종료 될 수 있다.
      교착상태가 아니여도 타임아웃으로 프로세스가 종료될 수 있다.
    • 모든 시스템에 적용 할 수 없다.
      분산 데이터베이스의 경우 네트워크로 각 시스템들이 연결되어있다. 원격지에 있는 프로세스의 응답이 없는 것이 교착 상태 때문인지, 네트워크 문제인지, 또다른 문제인지 알 수 없다.
• 무거운 교착 상태 검출 : 자원 할당 그래프 이용
  • 장점 : 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악 할 수 있다.
  • 단점 : 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 인해 오버헤드가 발생한다.

교착 상태 회복

교착 상태가 검출되면 교착 상태를 푸는 후속작업을 하는데 이를 교착 상태 회복이라고 한다. 교착 상태를 유발한 프로세스를 강제로 종료 한다.

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료한다.
  모든 프로세스를 강제로 종료한 후 다시 실행할 때는 순차적으로 실행해야한다. 이때 어떤 프로세스를 먼저 실행할 것인지 정해야한다.
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료한다.
  교착상태를 일으켄 프로세스들 중 하나를 골라 종료시킨다. 순서대로 종료하면서 나머지 프로세스의 상태를 파악한다. 프로세스 종료 순서를 정할 때는 다음과 같은 기준을 따른다.
  • 우선 순위가 낮은 프로세스를 먼저 종료한다.
  • 우선 순위가 같으면 작업 시간이 짧은 프로세스를 종료 한다.
  • 위의 두 조건이 같으면 자원을 많이 사용하는 프로세스를 먼저 종료한다.

프로세스를 강제 종료된 후 강제 종료된 프로세스가 실행되기전에 시스템을 복구해야한다.
시스템 복구는 명령어가 실행될 때 마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 식이다.