교착상태와 해결법

운영체제에서 발생할 수 있는 중요한 문제인 교착상태에 대해 알아보자!

 

교착상태란?

교착상태란 두 개 이상의 프로세스가 서로의 자원을 기다리며 무한정 멈춰있는 상태를 말한다.

예를 들어, 자동차 교차로에서 네 대의 자동차가 각각 서로의 길을 막으며 무한히 기다리는 상황을 상상해 보자.
각 자동차는 다른 자동차가 지나가야만 자신이 움직일 수 있으므로, 모두가 멈춰 있게 되는 현상이 교착상태이다.

 

 

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

교착상태는 다음의 네 가지 조건이 적용되었기 때문에 발생한 것이다.
하나라도 충족되지 않으면 교착상태가 발생하지 않는다.

 

1. 상호 배제(Mutual Exclusion)

자원은 한 번에 한 프로세스만 사용할 수 있기 때문이다.
ex) 한 칸에 한 명만 들어갈 수 있는 화장실은 상호배제를 잘 지킨 것이다.

 

2. 점유와 대기(Hold and Wait)

최소한 하나의 자원을 점유한 상태에서 다른 자원을 요청하며 기다릴 수 있기 때문이다.
ex) 자동차가 교차로의 일부를 점유한 상태에서 다른 차선이 비기만을 기다리는 상황이다.

 

3. 비선점(Non-preemption)

한 번 할당된 자원은 강제로 빼앗을 수 없기 때문이다.
ex) 교차로에 진입한 자동차는 뒤로 물러서거나 강제로 나갈 수 없게 된다.

 

4. 순환 대기(Circular Wait)

자원을 사용하기 위해 대기하는 프로세스들이 원형을 이룬 채 대기하고 있기 때문이다.

ex) 첫 번째 자동차가 두 번째 자동차를 기다리고, 두 번째 자동차는 세 번째 자동차를 기다리며, 마지막 자동차가 첫 번째 자동차를 기다리는 형태

 

교착상태 해결법

교착상태 해결법에는 크게 예방, 회피, 발견 및 복구 기법이 있다.

크게 4가지로 분류하지만 발견 및 복구는 묶어서 이해하는 것이 편할 것 같다.

 

예방 기법 (Prevention)

교착상태를 예방하기 위해서는 발생 조건 중 하나를 제거해야 한다. 이를 교착상태 예방 기법(Prevention)이라고 하며, 자원 낭비가 심할 수 있으나 교착상태를 사전에 차단할 수 있다.

 

1. 상호 배제 부정

여러 프로세스가 자원을 동시에 사용할 수 있도록 한다.

 

2. 점유 및 대기 부정

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

 

3. 비선점 부정

자원을 점유한 프로세스가 다른 자원을 필요로 할 때 기존 자원을 반납하게 한다.

 

4. 순환 대기 부정

자원에 고유 번호를 할당하고 선형 순서로 분류하여, 각 프로세스가 점유한 자원의 앞이나 뒤 순서로만 자원을 요구하게 한다.

 

 

회피 기법 (Avoidance)

교착상태를 완전히 막을 수는 없지만, 적절히 피해 가는 방법으로 대표적으로 은행원 알고리즘(Banker's Algorithm)을 사용한다.

 

은행원 알고리즘

시스템을 안전 상태 / 불안정 상태로 구분하고 불안전 상태일 때 대기시키는 방법이다.
이 알고리즘을 적용하려면 할당할 자원 수와 프로세스 수를 고정해야 하는 등 많은 조건이 필요하다.

다익스트라가 제안한 알고리즘으로 은행에서 고객에게 대출할 때 모든 고객의 대출 요구가 안전하게 충족될 수 있도록 자원을 관리하는 방식에서 유래되었다.

 

 

발견(Detection) 및 복구 기법 (Recovery)

 

발견 기법

교착상태가 발생했는지 점검하여 문제가 있는 프로세스와 자원을 찾아내는 기법이다.
발견 후에 교착상태 복구(Recovery) 작업을 수행하므로 발견기법과 회복기법을 함께 쓴다.

 

복구 기법

순환 대기가 깨질 때까지 프로세스를 종료하거나 순환 대기에 포함된 프로세스의 제어권을 뺏고 롤백하는 기법(자원 선점)을 말한다.

 

프로세스 종료
프로세스 종료엔 2가지 방법이 있다.

• 모든 교착 상태 프로세스를 종료한다. -> 단순하지만 비용이 크다.
• 한 번에 한 프로세스씩 종료 -> 각 프로세스가 중지될 때마다 교착상태를 확인해야 되므로 상당한 오버헤드를 유발한다.

 

자원 선점
자원을 점유한 프로세스를 선점해 다른 프로세스에 할당하여 교착상태를 해소한다.

• 희생자 선택: 선점할 자원과 프로세스를 선택할 때 비용을 최소화하는 방법을 고려한다.
• 롤백 (Rollback): 선점된 프로세스를 이전 상태로 되돌리거나 다시 시작하는 방법이다. 가장 안전한 방법은 프로세스를 처음부터 다시 실행하는 것이다.
• 기아 상태 (Starvation): 특정 프로세스가 계속 자원을 선점당해 영원히 실행되지 못하는 상황이 발생할 수 있다. 이를 방지하기 위해 우선순위를 설정하거나 롤백 횟수 제한을 둔다.

 

프로세스의 희생양은 시스템의 우선순위에 따라 다른데 MySQL의 경우에는 트랜잭션의 작업 양이 가장 적은 트랜잭션을 롤백한다.

 

 

 

 

 

참고
10분 테코톡 🥁둔덕의 교착상태
CS-study