교착 상태(Deadlock)

목표

교착 상태 개념을 설명할 수 있다.
교착 상태가 발생하기 위한 필요충분조건을 이해할 수 있다.
교착 상태 해결 방법을 설명할 수 있다.

교착 상태란?

교착 상태란 두 개 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미합니다. 결과적으로 아무것도 완료되지 못하는 상태를 가리킵니다.

 

교착 상태 필요충분조건

상호배제(Mutual Exclustion)	한번에 한개의 프로세스만 공유 자원을 사용할 수 있어야 한다.
점유와 대기(Hold and Wait)	최소한 하나의 자원을 점유한 상태에서 이미 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야합니다.
비선점(Non-preemption)	다른 프로세스가 선점한 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없습니다.
환형 대기(Circular Wait)	대기하는 프로세스들이 원형을 이루며 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 합니다.

교착 상태 해결 방법

교착 상태를 해결하는 방법은 예방, 회피, 발견 및 회복, 무시 기법 총 4가지 있습니다. 순서대로 알아보도록 하겠습니다. 

 

예방 기법(Prevention)

교착 상태가 발생하지 않도록 사전에 프로세스를 제어하는 방법입니다. 교착 상태 필요충분조건 중 어느 하나를 제거함으로써 수행되며 자원 낭비가 가장 심한 기법입니다.

• 상호 배제 부정: 한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 합니다.
• 점유 및 대기 부정: 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 합니다.
• 비선점 부정: 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 요청한 자원을 사용할 수 있는지 검사한 후 만약 사용 가능하다면 점유하고 있는 자원을 반납하고 요구한 자원을 사용하기 위해 대기합니다.
• 환형 대기 부정: 자원을 선형 순서로 분류하여 고유 번호를 할당합니다. 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 합니다.

회피 기법(Avoidance)

- 교착 상태가 발생할 가능성을 배제하지 않고 교착상태가 발생하면 적절히 회피하는 기법입니다.

- 대표적으로 은행원 알고리즘이 있습니다. (Banker's Algorithm)

 

은행원 알고리즘

• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법입니다.
• 각 프로세스에게 자원을 할당했을 때 교착 상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안정 상태, 교착 상태가 발생할 수 있는 상태를 불안정 상태라고 합니다.
• 프로세스의 요구로 자원을 할당하여 교착 상태가 발생할 수 있다면 요청한 자원을 할당하지 않습니다.
• 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 합니다.

 

발견 및 회복 기법(Detection & Recovery)

• 자원 할당 그래프를 통해 교착 상태를 탐지할 수 있습니다. (프로세스 O, 자원 □)
• 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복할 수 있습니다.
• 교착 상태를 일으킨 프로세스를 종료하는 방법은 교착 상태의 프로세스를 모두 종료하거나 교착 상태가 제거될 때까지 한 프로세스씩 중지하는 방법이 있습니다.
• 할당된 자원을 해제하는 방법은 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법입니다. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점합니다. 추가적으로 기아 현상, 피해 정도를 고려하여 할당된 자원을 해제합니다.

 

무시 기법(Ignorance)

교착 상태 자체를 무시하고 특별한 조치를 취하지 않습니다. 교착 상태의 발생 확률이 낮은 상황에서 효율적입니다. 대부분 운영체제가 무시 기법을 사용하고 있습니다.