교착 상태 (Deadlock)

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 진행하지 못하는 상황을 의미한다.

 

Deadlock 필요조건

아래의 4가지 조건이 모두 충족되는 경우 교착 상태가 발생한다.

• 상호 배제
  한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함.
• 비선점
  한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
• 점유와 대기
  프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함.
• 원형 대기
  점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함.

 

즉, 위 4조건 중 하나라도 충족되지 않으면 교착 상태는 발생하지 않는다.

 

교착 상태 예방

- 상호 배제 예방

시스템 내에 독점적으로 사용할 수 있는 자원을 없애버린다.

하지만, 사실상 모든 자원을 공유할 수 없기에 사실상 이를 달성하기는 불가능하다.

 

- 비선점 예방

모든 자원을 빼앗을 수 있도록 구현한다.

하지만, 특정 프로세스가 모든 자원을 빼앗을 수 있다면 아사 현상의 원인이 된다.

이는 교착 상태 만큼 치명적이다.

 

- 점유와 대기 예방

프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 한다.

즉, 전부 할당하거나 아예 할당하지 않는 방식을 적용한다.

하지만, 자원의 활용성이 떨어지며, 일괄 작업 방식이 되어버리기에 성능에 치명적인 문제가 된다.

 

- 원형 대기 예방

점유와 대기를 하는 프로세스가 원형을 이루지 못하도록 한다.

이를 달성하는 방법은 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하게 하는 것이다.

하지만, 번호를 부여하는 방법에서 문제가 발생하고, 작업의 유연성에 영향을 주게 된다.

 

교착 상태 회피

교착 상태를 예방하는 것은 시스템, 혹은 성능상의 제약이 따르기에 사용하기 부담스럽다.

하지만 교착상태는 프로그래밍에 주의를 기울이면 그 빈도가 줄어든다.

즉, 한정된 자원을 할당하는 양이 많아질 수록, 불안정해지며, 교착 상태에 접어들 확률이 올라간다.

따라서 프로세스의 기대 자원보다 가용 자원이 많아질 경우에만 자원을 할당한다면

교착 상태를 피할 수 있다.

 

하지만, 이 경우에는 프로세스의 기대 자원을 알아야 한다.

기대 자원을 정확히 알 방법은 런타임이 아닌, 컴파일 타임에서 본인이 사용할 자원을 미리 정해놓는 수 밖에 없다.

또한 가용 자원을 파악하기 위해서는 시스템 전체 자원 수가 고정적이어야 한다는 한계가 존재한다.

 

따라서 교착 상태를 회피 하려는 노력도 중요하지만,

교착 상태의 발생을 파악하고, 이를 회복하기 위한 구현 또한 매우 중요하다.

 

교착 상태 검출 및 회복

교착 상태를 검출하는 대표적인 방법은 타임아웃(Time-out)이다.

즉, 일정 시간 이상 작업이 진행되지 않는 프로세스는 교착 상태에 진입했다고 판단하는 것이다.

 

다른 방법으로는 자원 할당 그래프(Graph)를 이용하는 것이다.

즉, 자원 할당 관계를 그래프 자료구조로 저장하는데, 여기서 cycle이 존재한다면 교착 상태라고 판단하는 것이다.

 

교착 상태에 있는 프로세스들은 다음의 우선순위를 기준으로 종료시키며 상태를 회복시킨다.

1. 우선순위가 낮은 프로세스 우선 종료
2. 작업 시간이 짧은 프로세스 차선 종료
3. 자원 할당이 많은 프로세스를 차차선 종료