테코톡의 케빈의 Deadlock을 보고 주관적으로 정리한 내용입니다.
개념
- 두 개 이상의 프로세스 혹은 스레드가 한정된 자원을 얻지 못해 다음 처리를 진행하지 못하는 상태
Deadlock 발생 조건
- 상호 배제 (mutual exclusion) - 하나의 공유 자원에 두 개 이상의 프로세스가 동시에 접근할 수 없음
- 점유 대기 (hold and wait) - 하나의 자원을 점유하고 있는 프로세스가 있고 해당 프로세스가 다른 프로세스에서 자원을 얻기 위해서는 요청을 하고 대기해야 함
- 비선점 (no preemption) - 특정 프로세스가 자원을 사용하고 있을 때, 그 자원을 뺏을 수 없음
- 순환 대기 (circular wait) - 프로세스들이 서로 사용하고 있는 자원에 대해 순환적으로 대기하고 있는 형태 (cycle 형태)
- 이 모든 조건을 만족하면 deadlock이 발생
Deadlock 해결 방법
- 예방
- 회피
- 탐지 및 회복
- 무시
예방
- 네 가지 발생 조건 중 하나를 제거함으로써 해결
- 하나의 공유 자원에 대해 동시에 접근 허용 - 현실적으로 불가능
- 프로세스가 작업을 수행할 때, 해당 작업에 필요한 리소스들을 먼저 요청하고 할당 받음 - 자원의 효율성이 떨어지고 프로세스들이 어떤 자원을 필요로 하는지 파악하기 위해 추가적인 오버헤드 발생
- 프로세스가 다른 프로세스의 자원을 요청하기 위해서는 자신이 할당 받았던 자원을 반납 - 여태까지 작업했던 프로세스의 상태를 잃을 수 있음
- 각각의 자원에 고유번호를 할당하고 특정 프로세스 내 자신이 할당받은 자원에 번호를 기준으로 오름차순/내림차순으로만 요청을 할 수 있도록 하는 방식 - 이것에 대해서는 단점을 설명하지 않았다 왜일까?
회피
- 교착 상태 발생 가능성을 검사해서 발생 가능성이 있다면 사전에 회피하는 형식
- 자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)
- 은행원 알고리즘 (Banker's algorithm) - 여러가지 전제조건들이 많이 존재를 하기 때문에 현실적으로 사용하기 어려움
- 데드락 회피 방법의 전반적인 플로우는 아래와 같음
- 프로세스가 자원 요청 시, 자원을 할당한 후에도 안정 상태로 남아있는지 사전 검사
- 안정 상태라면 자원을 할당
- 불안정 상태라면 다른 프로세스가 자원을 해지할 때까지 대기
- 자원을 요청할 때마다 시스템 상태를 검사하는 만큼 오버헤드가 큰 게 단점
탐지 및 회복
- 교착 상태를 허용하지만 상태를 탐지하고 회복하는 방식
- 알고리즘을 주기적으로 실행함으로써, 시스템에 발생한 Deadlock을 체크하고 회복
- 알고리즘을 어느 주기로 실행 해야할 지 결정을 잘 해야 함 - 너무 자주하면 오히려 비효율적
- 데드락을 탐지했을 경우, 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복
- 프로세스 종료
- 교착 상태의 프로세스를 모두 중지 - 작업했던 내용이 날라갈 수 있음
- 교착 상태가 제거될 때까지 한 프로세스씩 중지 - 교착 상태가 제거 되었는지 주기적으로 파악하기 위해 오버헤드가 큼
- 자원 선점
- 교착 상태가 제거될 때까지 프로세스가 점유한 자원을 선점해 다른 프로세스에게 할당
회복 고려 사항
- 희생자 선택 - 보통 비용적인 측면을 고려해 희생자를 선택함. 하지만 기아 상태가 발생하기 쉬워짐
- 후퇴 (Rollback)
- 기아 상태 (Starbation)
무시
- 교착 상태 자체를 무시하고, 특별한 조치를 취하지 않는 방법
- 교착 상태의 발생 확률이 낮은 상황에서 주로 사용
- 운영체제에서 많이 사용
https://youtu.be/Ry_gB34cvwc [10분 테코톡] 🚴♂️ 케빈의 Deadlock
