데드락(Deadlock, 교착상태)이란?
둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 말합니다.
데드락의 발생조건 4가지
다음 네 가지 조건을 모두 만족하면 교착상태가 발생합니다.
- 상호 배제
- 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.
- 점유 대기
- 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야한다.
- 비선점
- 프로세스에게 이미 할당된 자원이 사용이 끝나기 전까지는 강제로 뺏을 수 없다.
- 순환 대기
- 프로세스들이 서로 사용하고 있는 자원에 대해 순환 형태로 대기하고 있다.
데드락의 예방 방법
데드락의 발생 조건 4가지 중 하나라도 발생하지 않도록 하는 방법입니다. 자원 사용에 대한 효율성이 떨어지고 비용이 많이 드는 단점이 있습니다.
- 자원의 상호 배제 조건 방지 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 합니다.
- 그러나 추후 동기화 관련 문제가 발생할 수 있습니다.
- 점유 대기 조건 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 합니다. (자원의 효율성이 떨어짐, 프로세스들이 어떤 자원을 필요로하는지에 대해 알아야하는 오버헤드)
- 비선점 조건 방지 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 합니다. (작업하던 프로세스의 상태를 잃을 수 있음)
- 순환 대기 조건 방지 : 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 합니다. (프로세스에 오름차순이나 내림차순으로 번호를 할당하고 특정 방향으로만 자원 요구)
데드락의 회피 방법
은행원 알고리즘
안정 상태 : 프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서 차례대로 모두에게 할당해줄 수 있는 상태
안전 순서 : 데드락이 발생하지 않도록 자원할당, 실행 및 종료 할 수 있는 순서
불안정 상태: 데드락 발생 가능성이 있는 상태
- 프로세스가 자원 요청 시, 자원을 할당한 후에도 안정 상태로 남아있는지 사전 검사
- 안정 상태라면 자원을 할당
- 불안정 상태라면 다른 프로세스가 자원을 해지할 때까지 대기
자원을 요청할 때마다 시스템 상태를 검사하는 만큼 오버헤드가 큼 은행원 알고리즘의 경우 전제조건이 큼
데드락 탐지 및 회복
교착 상태를 허용하지만 교착 상태의 존재 여부와 교착 상태에 연관된 프로세스와 자원을 알아내는 방식. 순환 대기 존재 여부에 초점을 맞춥니다.
탐지
은행원 알고리즘 방법과 마찬가지로 알고리즘을 주기적으로 실행함으로써 시스템에 발생한 데드락을 체크하고 회복하는 방법. 주기, 자원 즉시 할당 여부, CPU 이용률 등을 고려
회복
교착상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제
- 프로세스 종료
- 교착 상태의 프로세스를 모두 중지
- 교착 상태가 제거될 때까지 한 프로세스씩 중지
- 자원 선점
- 교착 상태가 제거될 때까지 프로세스가 점유한 자원을 선점해 다른 프로세스에게 할당
회복 고려 사항
희생자 선택
프로세스가 어느정도 구동되었는지, 어느 정도의 자원을 가지고 있는지 등을 고려해 희생자를 선택한다.
(MySQL 같은 경우에는 가장 작은 트랜잭션을 롤백한다.)
기아 상태(Starvation)
프로세스 종료 시 비용이 적게드는 방향이 좋아 보이지만 이러한 방법은 기아 상태를 유발시킬 수 있으니 다양한 파라미터, 가중치를 고려해서 선택을 해야한다.
후퇴(Rollback)
프로세스를 완전히 Rollback 하는지 또는 데드락이 해결될 정도만 Rollback을 하는지 등 어느정도 수준으로 Rollback을 할 것인지를 고려해야합니다.
데드락 무시
교착 상태 자체를 무시하고 특별한 조치를 취하지 않는 방법. 교착 상태의 발생 확률이 낮은 상황에서 주로 사용합니다.
프로세스 자체를 종료하거나 시스템을 재부팅하여 교착상태를 해결합니다.