운영체제 교착상태

 

 

교착상태 

여러 스레드가 한정된 자원을 사용하려 하고 사용할 수 없는 순간이 왔을 때 이 상태를 벗어날 수 없으면 교착 상태라 합니다.

교착 상태

 교착상태를 예방하는 도구가 있을 수도 있지만 보통은 제공하지 않습니다. 교착상태를 방지하는 것은 개발자의 몫입니다. 교착상태를 유발하는 여러 곳에서 발생할 수 있습니다. 자원으로 사용되는 모든 부분에서 발생합니다. 

 

교착상태의 특징

 

교착상태의 필수 조건

교착 상태는 다음 네 가지의 조건이 모두 성립할 때 발생됩니다.

1. 상호 배제 : 최소한 하나의 자원이 공유하지 않고 점유되어야 합니다. 다른 프로세스가 요청을 하더라도 현재 진행 중인 프로세스가 완료될 때까지 대기합니다.

2. 점유하며 대기 : 프로세스가 자원을 점유한 체 다른 자원을 얻기 위해 대기하며 현재 사용 중인 자원을 점유합니다.

3. 비선점 : 자원들을 선점하지 않습니다.

4. 순환 대기 : 대기하고 있는 프로세스끼리 서로서로 사용하는 자원을 서로 대기합니다.

 

교착상태의 해결

 교착상태를 해결하기 위해 다음 세 가지 방법을 들 수 있습니다.

• 가능성을 무시하고 교착상태가 절대 발생하지 않는다고 간주한다.
• 교착상태를 예방하거나 회피하는 시스템을 구성한다.
• 교착상태가 발생하더라도 복구한다.

 보통의 경우 첫 번째를 많이 사용합니다. 

첫 번째의 방법의 경우 처음 서두에 썼던 것처럼 개발자가 교착상태를 처리하거나 예방해야 합니다.

두 번째 방법은 위의 필수조건 중 4가지 중 하나라도 성립하지 않도록 보장하는 방법을 사용하여 예방할 수 있습니다. 회피의 경우 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 요구하도록 합니다.

마지막의 경우 교착상태를 허용하고 교착상태가 발생했을 경우 탐지하고 원래대로 복구하는 알고리즘을 사용하여 교착상태를 벗어나도록 합니다.

 

 

교착상태 탐지 및 회복

 교착상태 해결을 위한 세 가지 방안중 앞 두 가지가 아니라면 탐지와 회복 알고리즘을 사용해야 합니다. 응용된 알고리즘으로 은행원 알고리즘이 존재합니다.

교착상태의 탐지

1. 각 자원 유형이 한 개 식 있는 경우

 대기 그래프라 하는 자원 할당 그래프의 변형을 사용해 교착 상태 탐지 알고리즘을 적용할 수 있습니다.

 

교착상태의 회복

탐지 인스턴스가 교착상태를 탐지하면 교착상태를 회복해야 합니다. 교착상태가 발생한 것을 통보하여 수작업으로 처리하게 하거나 시스템이 프로세스를 중지시키거나 혹은 프로세스를 선점할 수 있도록 허용합니다.

 

프로세스, 스레드 중지

 1. 교착 상태 프로세스를 모두 중지

 교착상태를 완전히 벗어날 수 있습니다. 하지만 그동안의 프로세스가 실행한 결과들을 모두 버리게 되므로 다시 계산하는데 큰 비용이 발생할 수 있습니다.

2. 교착 상태에서 벗어날 때까지 하나의 프로세스만 중지

 프로세스가 중지될 때 교착상태 탐지 알고리즘을 실행하여 교착상태 탈출 여부를 확인합니다. 하지만 여러 번 탐지 알고리즘을 실행하기 때문에 오버헤드가 큽니다.

 

어느 선택지를 고르던 프로세스가 실행하는 도중에 중지시키는 건 큰 부담을 가지게 됩니다. 파일 작업 도중에 중지시키게 된다면 어느 상태에 놓여있는지 모르는 파일을 남기고 프로세스는 중지되게 됩니다. 최소의 비용으로 어떤 프로세스를 죽일지는 프로세스의 우선순위, 종료하는 데까지 필요한 작업시간, 사용한 자원 유형과 수등이 결정 요소로 적용될 수 있습니다.

 

자원 선점

 선점 방식을 이용해 교착상태 필수 조건중 하나를 성립하지 않도록 하여 교착상태를 탈출하는 방식입니다. 다음은 고려해야 할 부분입니다.

• 선점할 프로세스 선정

 어떤 자원을 이용하는 프로세스를 선점할 것인지 최소 비용을 달성할 수 있을지 여러 요소들을 고려하여 결정합니다.

• 롤백

선점 후에는 그 프로세스는 가용한 자원이 없기 때문에 정상적으로 다시 실행이 불가능하다. 그리고 안전한 지점까지 돌아가서 다시 프로세스를 실행해야 한다. 단순히 중지시키고 재시작하는 것도 한 방법이지만 이것은 비용 문제로 이어진다. 교착상태를 탈출할 수 있을 정도의 롤백을 시킨다면 매우 효과적이다. 하지만 더 많은 상태 정보를 유지해야 한다는 단점이 있다.

• 기아 상태

자원들이 동일한 프로세스로부터 항상 선점되지 않을 수 있다. 항상 똑같은 프로세스가 선점될 수 있다. 이것의 해결 책으로는 롤백의 횟수를 포함하는 방법이 있을 수 있다.