교착상태 (Dead Lock)

교착상태(Dead Lock) 이란?

둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 자원을 요구하며 무한정 기다리는 현상을 말합니다.

 

 

위의 사진은 교착상태가 발생하는 경우입니다. 다중 프로그래밍 환경에서 자원을 사용하기 위해 서로 경쟁하는 상황이 발생합니다.

경쟁상태

두개 이상의 프로세스 또는 스레드들이 하나의 공유자원에 접근할 때 접근된 순서 등이 결과값에 영향을 줄 수 있는 상태를 말합니다.

 

교착상태 발생의 필요충분 조건

아래의 네가지 조건이 모두 충족되어야 교착상태가 발생합니다. 교착상태는 프로세스 뿐만 아니라 스레드 또한 발생할 수 있습니다.

 

상호배제

한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야합니다.

점유와 대기

최소한 하나의 자원을 점유하고 있으며 다른 프로세스가 점유하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야합니다.

비선점

다른 프로세스가 점유한 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없어야합니다.

환형 대기

자원을 점유하며 다른 프로세스가 점유하고 있는 자원을 사용하기 위해 대기하는 프로세스(점유가 대기 중인 프로세스)들이 원형으로 자신의 앞 또는 뒤에 있는 프로세스가 점유한 자원을 요청해야합니다.

 

교착상태 예방 기법

교착상태 예방 기법은 교착상태가 발생하지 않게 사전에 시스템을 제어하는 방법입니다. 교착상태 발생 4가지 조건 중 하나를 제거하여 예방합니다.
자원의 낭비가 가장 심한 기법입니다.

상호 배제 부정

한번에 여러개의 프로세스가 공유 자원을 사용할 수 있도록 합니다.

점유 및 대기 부정

프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구합니다.

비선점 부정

자원을 점유하고 있는 프로세스가 다른 자원들을 요구할 때 점유하고 있는 자원을 반납하고 요구한 자원을 사용하기 위해 기다리게 합니다.

환형 대기 부정

자원에 고유번호를 할당하고 번호 순서대로 자원을 요구하도록 합니다.

교착상태 회피 기법

교착상태 회피 기법은 교착상태가 발생하면 적절히 회비해나가는 방법입니다.

은행원 알고리즘

은행에서 모든 고객이 만족할 수 있는 알고리즘에서 착안된 알고리즘입니다.
안전상태일 경우 프로세스에 자원을 할당해주고 불안전 상태일 경우 안전상태가 될때까지 거부합니다.

안전 상태 (Safe State)
시스템이 교착상태를 일으키지 않으며 각 프로세스가 요구한 최대 요구량 만큼 필요한 자원을 할당해 줄 수 있는 상태

불안전 상태 (Unsafe State)
불안전 상태는 교착상태 발생의 조건입니다. 불안전 상태에서만 교착상태는 발생하지만 불안전 상태일 경우 무조건 교착상태가 발생하진 않습니다.

 

교착상태 회복 기법

교착상태 회복 기법은 교착상태를 일으킨 프로세스를 종료하거나 프로세스에 할당된 자원을 선점하여 프로세스 혹은 자원을 회복하는 것을 말합니다.

프로세스 종료

교착상태의 프로세스를 종료하는 방법입니다. 교착상태의 모든 프로세스를 종료하는 방법과 교착상태의 프로세스를 하나씩 종료해가는 방법이 있습니다.

자원 선점

교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당합니다. 이때 기존에 자원을 점유하는 프로세스는 일시적으로 정지됩니다.

 

프로세스의 우선순위, 프로세스의 수행된 정도, 사용되는 자원의 수 등등이 고려되어 자원을 선점합니다.

 

이때 한 프로세스가 계속하여 자원의 선점 대상이 되지 못하는 상태를 기아상태라고 합니다. 이런 문제를 해결하기 위해 오래 기다린 프로세스의 우선순위를 높이는 방식등이 사용됩니다.