6. 교착상태 (데드락)

교착상태 (Deadlock)

운영체제 (또는 소프트웨어)에서 자원을 사용할 때, 두 개 이상의 작업이 순차적으로 상대방의 작업이 끝나기를 기다리면서, 아무것도 진행되지 않는 상태를 말한다.

교착상태 발생 조건

교착상태는 다음 네 가지 조건이 모두 성립될 때 발생한다.

1. 상호 배제 (Mutual exclusion)

한 번에 하나의 프로세스만 공유 자원을 사용할 수 있다.

 

2. 점유 대기 (Hold and Wait)

각 프로세스가 하나의 자원을 점유하고 있으면서, 다른 프로세스가 사용하고 있는 자원을 추가로 점유하기 위해 대기한다.

 

3. 비선점 (No preemption)

각 프로세스는 다른 프로세스가 사용하고 있는 자원을 강제로 빼앗을 수 없다.

 

4. 순환 대기 (Circular wait)

각 프로세스는 순환적으로(원형 형태) 다음 프로세스가 요구하는 자원을 가지고 있다.

반응형

교착상태 해결 방법

예방 기법 (Deadlock Prevention)

교착상태가 발생되지 않도록 사전에 예방하는 방법이다.

교착상태 발생 조건 네 가지 중 적어도 하나가 성립하지 않게 만드는 방법이다.

순환대기를 막는 방법이 네 가지 중 가장 효율적이다. 자원에 순서를 부여하고, 각 프로세스가 오름차순으로 자원을 요청하도록 구현한다.

예방 기법은 일반적으로 자원 사용 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.

 

회피 기법 (Deadlock Avoidance)

교착상태가 발생하는 조건인지 확인하면서 적절히 회피하는 방법이다.

Circular wait가 발생하지 않도록 자원 할당 상태를 검사하면서, 시스템이 안전 상태 (Safe state)인지 확인한다.

1. 자원 할당 그래프 알고리즘 (Resource - Allocation Graph Algorithm): 자원 할당에 대한 그래프를 구성한 후, 그래프에 사이클이 없을 때에만 자원을 할당한다.

예를 들어 위와같이 P2가 R1,R2에게 자원 요구,  P1이 R2에게 자원을 요구하고 있고 R1이 P1에 업무를 할당한 경우 R2는 P1에 자원을 할당해야 P1이 작업를 마치고 R1,R2에 자원을 반환하고 P2가 R1,R2로 부터 자원을 할당받아 작업을 수행할 수 있게된다.

 

2. 은행원 알고리즘 (Banker's Algorithm): 자원 할당 그래프 알고리즘은 프로세스가 하나의 자원만 사용하는 시스템에서 사용된다. 이에 반해 은행원 알고리즘은 프로세스가 자원을 여러 개 사용하는 경우에도 사용할 수 있는 알고리즘이다.

 

탐지와 회복 기법 (Deadlock Detection & Recovery)

시스템에 교착 상태가 발생했는지 확인하기 위해 시스템의 상태를 검사한다.

탐지 후, 교착 상태를 일으킨 프로세스를 종료하거나, 교착상태의 프로세스에 할당된 자원을 선점하여 교착상태를 제거한다.

 

무시 기법 (Deadlock Ignorance)

교착상태 자체를 무시하고, 특별한 조치를 취하지 않는다. 교착상태의 발생 확률이 낮은 상황에서 효율적이다.

만약 교착상태가 발생한다면, 프로세스를 종료하거나 자원을 선점하여 회복한다.

UNIX, Windows 등 대부분의 운영체제가 이 방법을 사용한다.