[CS] 교착상태(DeadLock)

교착상태

교착상태(DeadLock)은 두 개 이상의 프로세스(쓰레드)가 서로가 가지고 있는 자원을 기다리는 상황이 발생해 무한정 대기하는 상태를 의미한다. 교착상태가 발생하는 상황을 그림으로 나타내면 아래 그림과 같다.

위 그림에서 Process1은 Resource1 - Resource2 순서로 접근하고 Process2은 Resource2 - Resource1 한다고 하자. Process1과 Process2가 거의 동시에 실행된다면, 두 번째 Resource를 할당받기 위해 상대 프로세스가 가지고 있는 Resource가 할당될 때까지 기다릴 것이다.

교착상태가 발생하면 프로세스가 작동을 멈추고 서버의 경우 클라이언트의 응답을 할 수 없다.

정보처리기사책에 표기되어 있는 교착상태의 정의는 '둘 이상의 프로세스들이 자원을 점유하고 있는 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상'이다.

1. 발생하는 이유, 조건

흔히 말하는 교착상태의 필요조건 4가지라는 것이 존재하는데 4가지는 다음과 같다.

• 상호 배제(Mutual Exclusion): 한 번에 한 프로세스(쓰레드)만 자원을 사용할 수 있다.
• 점유 대기(Hold and Wait): 프로세스가 하나의 자원을 점유하면서 다른 프로세스가 점유하고 있는 자원을 요청해 대기하는 상황
• 비선점(No Preemption): 프로세스가 할당을 해제할 때까지 해당 자원을 선점할 수 없다.
• 순환 대기(Circular Wait): 할당받고자 하는 자원을 가지고 있는 프로세스를 방향그래프로 나타냈을 때 Circle이 생긴다.

위의 4가지 상황중 하나라도 해당하지 않는다면 교착상태가 일어나지 않는다.

2. 해결하는 방법

교착 상태를 해결하는 기본적인 방법은 예방, 회피, 발견, 회복으로 총 4가지가 존재한다.

• 예방(Prevention): 교착상태의 필요조건 중 최소 하나의 조건을 제거함으로 교착상태가 발생하지 않도록 하는 방법이다.
• 회피(Avoidance): 교착상태가 발생하면 적절히 피해가는 방법으로 가장 일반적인 방법은 은행원 알고리즘(Banker's Algorithm)이 있다.
• 발견(Detection): 교착상태가 발생했는지 주기적으로 검사하는 방법으로, 교착상태 발견 알고리즘이나, 자원할당그래프를 통한 Cycle검사로 교착상태를 발견할 수 있다.
• 회복(Recovery): 교착상태를 일으긴 프로세스(쓰레드)를 종료하거나 할당된 자원을 선점해 교착상태를 해결하는 방법이다.

은행원 알고리즘은 모든 프로세스가 한 번에 요구해도 할당할 수 있는 충분한 양의 자원을 만들어 놓아 공급하는 알고리즘이다.

참고문헌

1. 길벗알앤디. 정보처리기사 필기 - 시나공. 길벗, 2021