교착 상태

교착 상태

교착 상태의 개요

2개 이상의 작업이 동시에 이루어지는 경우 다른 작업이 끝나기만 기다리며 작업을 더 이상 진행 하지 못하는 상태를 교착 상태라고 한다.

아사 현상은 잘못된 프로세스 실행 정책으로 인해 프로세스가 실행되지 못하는 반면 교착상태는 여러 프로세스가 실행되다가  자연스럽게 이도저도 못하게 되는 상태이다. 따라서 교착상태가 발생하면 강압적으로 해결해야한다.

 

보통 교착 상태는 공유할 수 없는 자원을 사용할때 잠금을 사용할 때 주로 발생한다. 

 

교착 상태 필요조건

교착 상태는 네가지 필요조건이 존재한다.

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

상호배제: 한 프로세스가 자원은 다른 프로세스와 동시에 공유할 수 없으며 배타적인 자원으로 임계구역으로서 보호된다.

비선점: 한 프로세스가 사용 중인 자원을 중간에 다른 프로세스가 뺴앗을 수 없다.

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

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

 

즉 자원을 동시에 점유할 수 없으며 뺏을 수도 없고 A자원을 갖고 있으면서 B자원을 기다리는데 다른 프로세스에서는 B자원을 갖고 있으며 A자원을 기다리는 경우 교착 상태가 발생한다.

교착 상태 해결 방법 

교착 상태 해결

교착 상태 예방: 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화 하는 방식이다.  이 방법은 실효성이 적어 잘 사용 되지 않는다.

교착 상태 회피: 자원 할당량을 조절하여 교착 상태를 해결 하는 방식으로, 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하는 것이다. 하지만 자원 할당 양을 얼마만큼해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적다.

교착 상태 검출과 회복: 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식이다. 만약 교착 상태가 발생하면 회복 단계가 진행된다. 이 방식이 제일 현실적인 접근 방식이다.

 

상호배제 예방

시스템 내에 있는 상호 배타적인 모든 자원 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법이다.

독점적인 자원을 없앨 수는 있겠지만 그에 따를 사이드 이펙트가 너무 어마무시해서 사실상 어렵다.

 

비선점 예방 

모든 자원을 뺴앗을 수 있도록 만드는 방법이다. 

시스템의 모든 자원을 뺴앗는 것은 어려우며 빼앗을 수 있다하더라도 어떤 기준으로 뺏을 것이며 얼마나 사용할지 결정하기 어렵다. 시스템을 사용하다가 우선순위가 낮은 프로세스는 계속해서 자원을 사용하지 못해 오히려 우선순위가 낮은 프로세스가 사용하고 있는 데이터에 대해 교착 상태가 발생 할 수 있다. 

점유와 대기 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다.  자신이 사용하는 자원을 모두 한번에 다 사용하고 한번에 다 Free하는 방법이다. 

하지만 프로세스가 자신이 사용하는 모든 자원을 자세히 어렵고, 자원의 활용성도 떨어지고 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다. 결국 일괄 작업 방식으로 동작한다.

 

원형 대기 예방

프로세스의 자원점유를 원형이 아닌 단방향으로 가능하게 한다.
예를들어 키보드를 점유한 후 마우스를 점유할 수 있지만
마우스를 점유한 후 키보드에 요청을 보내면 거절되고 프로세스는 강제 종료된다.
이는 프로세스 작업 진행에 유연성이 떨어지고 어떤 기준으로 자원에 순위를 둘지 정하기 어렵다.

 

 

교착상태 회피

어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법이다.

자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다. 할당된 자원이 적을 수록 안정상태가 높으며 할당된 자원으 많을 수록 불안정 상태가 높아진다. 

불안정 상태가 교착상태는 아니며 불안정 상태가 커질수록 교착 상태가 발생할 확률이 높아진다.

은행원 알고리즘

은행원 알고리즘에서는 최악의 경우를 기준으로 삼음으로써 교착 상태를 막는다. 

자신이 사용할 자원의 최대 수를 운영체제에 알려준다. 

은행원 알고리즘은 전체자원 가용자원 최대자원 할당자원 기대자원으로 구성된다.
가용자원과 기대자원을 비교해서 가용자원으 크거나 같으면 자원을 배분한다.
가용자원이 기대자원보다 하나라도 큰 상태를 안정상태
가용자원이 어떤 기대자원보다도 크지 않으면 자원을 할당하지 않는다.
하나도 큰게 없다면 불안정 상태이다. 

프로세스가 자신이 사용할 모든 자원을 미리 선언해애햐고
시스템 자원수가 고정적이며
자원 할당에 제약을 두기 때문에 문제가 있다.

 

교착 상태 검출

교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착상태로 간주하여 프로세스를 검출하는 방법이다.

교착 상태 검출은 가벼운 교착상태 검출과 무거운 교착 상태 검출로 나눌 수 있다.

가벼운 교착상태 검출은 프로세스가 특정시간동안 진행되지 못하는 프로세스들을 찾아 교착상태로 검출하는 것이다.

무거운 교착상태 검출은 운영체제가 자원을 할당하거나 요청하는 프로세스가 있을 때마다 자원 할당 그래프를 업데이트해 교착상태가 있는지 없는지 확인하는 방법이다. 

 

먼저 가벼운 교착상태 검출은 교착상태 외의 다른 이유로 작업이 진행되지 못하는 모든 프로세스를 강제종료 시킬 수 있다. 또한 미사일 발사나 원자로 제어 시스템과 같은 곳에서 교착상태가 발생했다고 해서 타임 아웃 걸린 모든 프로세스를 죽이는 것은 문제가 될 수 있다.  

프로세스의 강제 종료로 인해 데이터의 일관성이 깨지는 것을 방지하기 위해 스냅샷을 사용한다. 

스냅 샷은 특정 체크 포인트 시점의 데이터로 교착상태가 발생해 문제가 생길 경우 스냅 샷으로 롤백이 가능하다. 

 

무거운 교착 상태 검출은 운영체제가 자원 할당과 요청이 있을 때마다 자원 할당 그래프를 업데이트하고 이를 관리해야하기 떄문에 오버헤드가 발생할 수 있다. 이를 해결하는 방법으로 특정 시간마다 자원 할당 그래프를 업데이트 하는 방식도 고려할 수 있다.

 

교착 상태 회복 

교착상태를 일으킨 모든 프로세스를 동시에 종료한다. 

이럴 경우 모든 프로세스가 회복되어서 동시에 작동하면 또 교착상태를 발생할 경우가 생길 수 있으므로 어떤 프로세르를 먼저 실행할 것인지 기준을 정해야 한다.

 

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

우선 순위가 낮은 프로세스를 먼저 종료하고 작업시간이 짧으며 자원을 많이 사용하는 프로세스를 먼저 종료한다.