교착 상태(Deadlocks)

안녕하세요 dely입니다:)

오늘은 교착 상태(Deadlocks)에 대해 정리해보겠습니다.

 

A는 실을 가지고 있고, B는 바늘을 가지고 있다고 할 때

A는 B에게 바늘을 달라고 요청하고,

B는 A에게 실을 달라고 요청하는 상황을 가정해봅니다.

서로 요청만 하다가 아무도 바느질도 못하고 마음이 상해버리겠죠.....(응?)

 

이처럼 한정된 자원을 여러 프로세스들이 사용하려고 서로 경쟁하다보면

필요한 자원을 서로 점유하고 있어 프로세스가 상태를 변경할 수 없는 상황이 발생하는데

이를 교착상태(deadlocks)라고 합니다.

 

그래서 이를 해결하기 위해

어떤 상황에서 교착상태가 일어나는지,

어떤 방법으로 해결할 수 있는지,

미리 예방할 수 있는지

알아보도록 하겠습니다.

 

1. 교착 상태의 특징

교착 상태는 한 시스템에 다음과 같은 네 가지 조건이 동시에 성립될 때 발생할 수 있습니다.

  1) 상호 배제(Mutual exclusion) : 한 번에 한 프로세스만이 자원을 사용할 수 있다.

     만약 다른 프로세스가 그 자원을 요청하면 요청 프로세스는 자원이 방출될 때까지 반드시 지연된다. 

 

  2) 점유하며 대기(Hold and Wait) : 최소한 하나의 자원을 점유한 채 다른 프로세스에 의해 점유된 자원을 추가로

    얻기 위해 대기하고 있는 프로세스가 반드시 있어야 한다.

 

  3) 비선점(No preemption) : 자원이 강제적으로 방출될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후

    그 프로세스에 의해 자발적으로만이 방출 될 수 있다.

 

  4) 순환 대기(Circular wait) : 대기하고 있는 프로세스의 집합에서 P0은 P1이 점유한 자원 대기, P1은 P2이 점유한 자원 대기,

    P2은 P3이 점유한 자원 대기, P3은 P0이 점유한 자원 대기... 이런식으로 원을 그리며 대기한다.

 

 

2. 교착 상태 예방

교착 상태를 예방하기 위해 위에서 언급한 교착 상태의 네 가지 조건 중 최소한 하나가 성립하지 않도록 보장함으로써

교착 상태의 발생을 예방할 수 있습니다.

 

  1) no 상호 배제(Mutual Exclusion) : 상호 배제 조건은 공유가 불가능한 자원에 대해서는 반드시 성립해야 합니다.

     따라서 교착 상태를 예방하기 위한 방법으로 읽기 전용 파일과 비동기화 메서드처럼 공유 가능한 자원들로 사용하는 방법이 있습니다.

     그러나 일반적으로 상호 배제 조건을 거부하므로 교착 상태를 예방하는 것은 불가능합니다.

 

  2) no 점유하며 대기(Hold and Wait) : 프로세스가 자원을 요청할 때는 다른 자원들은 점유하지 않을 것을 반드시 보장해야 합니다.

      그 방법으로는 다음과 같이 두 가지가 있습니다.

        (1) 각 프로세스가 실행되기 전에 자신의 모든 자원을 요청하고 할당받을 것을 요구하는 방법입니다.

        (2) 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 것입니다.

 

      하지만 이 방법에는 단점이 있습니다.

      - 많은 자원들이 할당된 후 오랫 동안 사용되지 않기 때문에 자원의 이용도가 낮을 수 있습니다.

      - 자주 쓰이는 자원들을 여러 개 필요로 하는 프로세스는 자신이 필요한 자원 중에서 최소한 하나가 항상

        다른 프로세스에게 할당되어 있기 때문에 끝없이 대기 해야할 수도 있습니다.

 

  3) no 비선점(No Preemption) : 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면,

      그 자원들이 묵시적으로 방출되게 합니다.

      그러나 이 방법은 CPU 레지스터나 메모리 공간처럼 그 상태가 쉽게 저장되고 후에 복원될 수 있는 자원에만 적용할 수 있습니다.

 

  4) no 순환 대기(Circular Wait) : 순환이 아닌 오름차순으로 자원을 요청하도록 요구하는 방법을 쓸 수 있습니다.

 

 

3. 교착 상태 회피(Avoidance)

위의 교착 상태 예방 방법은 요청 사항을 제약하여 교착 상태를 예방하게 됩니다.

그러나 이 방법은 장치의 이용률이 저하되고 시스템 처리율이 감소되며, 프로세스 기아 상태가 발생할 수 있습니다.

 

따라서 교착 상태를 회피하는 방법을 쓸 수 있는데,

프로세스가 자원이 어떻게 요청될 지에 대한 추가 정보를 제공하도록 요청하는 것입니다.

이는 각 프로세스의 요청과 방출에 대한 완전한 순서를 파악하고 있기 때문에

각 요청에 대해 프로세스가 대기해야하는지 여부를 결정할 수 있게 됩니다.

 

그래서 교착 상태 회피 알고리즘에서는 자원 할당 상태를 검사하게 됩니다.

자원 할당 상태는 가용 자원의 수, 할당된 자원의 수, 프로세스들의 최대 요구 수에 의해 정의됩니다.

 

 

4. 교착 상태로부터 회복(Recovery)

교착상태 회피, 예방 방법도 좋지만 또 다른 방법으로는 프로세스를 종료시키거나 자원을 선점하는 방법도 있습니다.

  1) 프로세스 종료(Termination)

    프로세스를 종료하는 방법에도 두 가지가 있습니다.

     (1) 한꺼번에 모두 중지 : 확실하게 교착 상태를 회복시킬 수 있지만 비용이 큰 방법입니다.

     (2) 하나씩 종료하면서 계속 교착 상태인지 확인 : 상당한 오버헤드를 유발합니다.

 

  2) 자원 선점(Resource Preemption)

     교착 상태가 깨어질 때까지 프로세스로부터 자원을 계속적으로 선점해 이들을 다른 프로세스에게 주게 됩니다.

     이 때 세 가지 사항들을 고려해야 합니다.

     (1) 선점 할 프로세스 선택(selection of a victim) : 교착 상태 프로세스가 점유하고 있는 자원의 수,

         교착 상태 프로세스가 지금까지 실행하는 데 소요한 시간과 같은 값들을 비교하여 순서를 결정해야합니다.

     (2) 되돌리기(rollback) : 교착 상태인 프로세스를 중지시키고 재시작합니다. 최대한 많은 정보를 유지해야하는 것이 필요합니다.

     (3) 기아 상태(starvation) : 선점 할 프로세스를 선택할 때 계속해서 같은 프로세스를 선택하게 된다면 교착 상태는 유지됩니다.

         그에 따라 기아 상태가 되는데, 이를 방지하기 위해서 선점 할 프로세스를 선택하는 비용 요소에

         되돌리기 횟수를 포함시키는 방법이 있습니다.