[멀티 쓰레드] 교착 상태(Dead Lock)와 해결 방법
이 포스트는 개인 학습을 기록한 내용을 담고 있어 추후 수정될 수 있습니다.
교착 상태란
쓰레드란 프로세스 안에서 존재하는 하나의 실행 단위입니다.
이 실행 단위는 실행 중인 프로그램 안에서 최소 1개 이상이 존재하며
복수의 쓰레드가 동시에 실행될 수 있습니다.
쓰레드는 고유의 스택을 갖고 있기 때문에 함수의 호출로 생성되는 정보들을 저장하고
함수 내에서 선언되는 지역 변수들 또한 고유 스택에 자장할 수 있습니다.
그러나 쓰레드는 고유의 힙 영역이 없고 프로세스의 힙 영역을 공유하기 때문에
전역 변수의 경우, 모든 쓰레드가 한 가지 변수를 공유합니다.
그러나 CPU의 실행 시간은 응용 프로그래머가 직접 조작하거나 미리 예측할 수 없고
운영체제가 언제 어떤 쓰레드에 연산 장치 사용권을 부여할지 결정합니다.
때문에 한 전역 변수에 여러 쓰레드가 동시에 접근하여 수정하면
응용 프로그래머의 의도와 다른 값이 출력될 수 있습니다.
따라서 응용 프로그래머는 의도한 값을 출력하기 위해 뮤텍스와 같은 점유를 사용하여
데이터의 유효성을 지킬 수 있습니다.
여기서 교착 상태가 등장합니다.
교착 상태는 두 개 이상의 쓰레드가 각자 자원을 점유하고 있을 때,
상대방의 자원의 점유를 획득하고자 무한정으로 대기하는 상태를 의미합니다.
교착 상태의 발생 조건
교착 상태는 총 4가지의 발생 조건이 존재합니다.
4가지 조건이 모두 충족된 상태에서만 교착상태가 발생한다는 특징이 있습니다.
- 상호 배제 (Mutual Exclusion)
- 한 리소스는 한 번에 한 쓰레드만 사용
- 한 쓰레드가 점유 중인 자원을 다른 쓰레드가 사용하려면 점유가 종료될 때까지 대기
- 점유와 대기
- 다른 쓰레드에 할당된 자원을 점유하기 위해 대기하는 쓰레드가 존재
- 비선점 (No Preemption)
- 이미 점유된 자원을 다른 쓰레드가 강제로 빼앗을 수 없음
- 자원을 이용한 작업이 끝나고 점유가 끝날 때 까지 대기
- 환형 대기 (Circular Wait)
- 대기 중인 쓰레드의 관계가 서로의 점유가 종료되기를 기다리는 형태
위 4가지 조건을 정리하면
한 쓰레드가 한 자원을 사용이 끝날 때 까지 독점하는 상황에서
동일한 상황의 또 다른 쓰레드가 독점하고 있는 자원을 얻기 위해 대기하면서
무한히 대기하는 상황을 의미합니다.
교착 상태 해결 방법
교착 상태를 해결하는 방법으로는 크게 3가지 방법이 존재합니다.
- 처음부터 교착 상태가 발생하지 않도록 예방(Prevention)
- 교착 상태 발생 가능성이 있음을 인정하고 적절하게 그 가능성을 회피(Avoidance)
- 교착 상태를 허용하지만, 상태를 탐지(Detection)하여 회복
교착 상태 예방하기
교착 상태를 예방하는 방법은 위에서 언급한 4가지 발생 조건을 모두 충족되진 않도록 하는 것입니다.
- 상호 배제 조건 방지
- 한 자원에 여러 쓰레드가 동시에 접근하도록 허용
- 점유 대기 조건 방지
- 쓰레드가 실행 중 필요한 자원을 미리 요구하여 한 번에 처리
- 비선점 조건 방지
- 쓰레드 마다 우선순위를 매겨 높은 순위가 먼저 선점
- 순환 대기 조건 방지
- 순환 형태로 대기하지 않도록 하기 위해서, 단방향으로 자원 요청
그러나 위와 같은 방법을 사용할 경우,
공유되는 자원의 동기화, 낮은 우선 순위 쓰레드의 무한 대기 상태 등
교착 상태만큼 심각한 문제를 초래할 수 있다는 단점이 존재합니다.
교착 상태 회피하기
이 방법은 예방하는 방법과 다르게 교착 상태 발생 가능성을 인정하고 교착 상태 발생을 적절하게 회피하는 방법입니다.
회피하는 방법은 자원을 할당할 때, 이 할당으로 인해 교착 상태가 발생할 가능성이 있다면 자원을 할당하지 않고
자원이 할당된 후에도 시스템이 항상 thread safe한 상태를 유지할 수 있도록 하는 것이 특징입니다.
회피는 주로 다익스트라 제안한 은행원 알고리즘에서 사용됩니다.
탐지 및 회복
이 방법은 이름처럼 교착 상태를 탐지하여 정상적이도록 회복하는 방법입니다.
교착 상태의 탐지는 교착 상태 발견 알고리즘과 자원 할당 그래프 등을 활용하여
교착 상태에 있는 쓰레드와 자원을 찾는 역할을 합니다.
그리고 회복에서는 교착 상태를 발생시킨 쓰레드를 종료시키거나 할당된 자원을
선점하여 교착 상태를 끝낼 수 있도록 합니다.