✅ DeadLock
🎈 데드락이란 ?
: 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해 다음 처리해야할 사항을 진행하지 못하는 상황으로, 무한히 다음 자원을 기다리게 되는 상태를 의미한다.
< 위 그림과 같이 차량이 서로 지나가길 기다리고 있는 상황을 의미 >
앞서 학습한 semaphore를 예시로 들어보면, 변수 A, B가 있고 프로세스 P1이 P(A), P(B)를 순서대로 호출하고 P2가 P(B), P(A)를 호출한다고 하면 각 프로세스는 서로 변수를 기다리는 상태가 되어버리는데, 이를 데드락 상태라고 한다.
💡 프로세스가 자원을 사용하는 절차
- REQUEST: 자원 요청, 만일 타 프로세스가 해당 자원 사용 중인 경우 대기
- ALLOCATE : 자원 할당 받음
- USE : 프로세스가 받은 자원 사용
- RELEASE : 프로세스가 자원 놓아줌
이때, 데드락은 모든 프로세스가 REQUEST 상태가 되어있는 상황을 의미💡 주로 발생하는 경우
- 멀티 프로그래밍 환경에서의 한정된 자원 사용
- 대기 상태로 들어간 프로세스들이 실행상태로 변경 불가능 할 때
🎈 DeadLock Characterization
데드락이 발생하기 위해선 다음 4가지 조건을 모두 만족해야 한다.
- Mutual Exclusion
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
- Hold and wait
- 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유한 자원을 release하지 않고 계속 보유
- No preemption
- 프로세스는 OS에 의해 강제로 자원을 빼앗기지 않는다.
- Circular wait
- 자원을 기다리는 프로세스 간 사이클이 형성되어야 함
🎈 Resource-Allocation Graph
: 프로세스 간 관계를 도식화한 그래프로, 데드락 발생여부를 확인할 수 있다.
- R은 자원을 의미, P는 프로세스를 의미, 자원 내 검은 동그라미는 인스턴스를 의미한다.
- 자원 -> 프로세스 edge : 해당 자원을 프로세스가 Allocation 중
- 프로세스 -> 자원 edge : 프로세스가 해당 자원을 Request
자원 당 하나의 인스턴스만 존재하면 DeadLock이고 여러 인스턴스가 존재하는 경우 DeadLock 여부를 판단해야 한다. (프로세스 간 사이클이 왼쪽 그래프에만 존재하기 때문)
🎈 DeadLock Solution
앞서 DeadLock 용어 해석, 발생 조건을 살펴보았다. 그렇다면 어떻게 데드락을 피할 수 있을까?
💡 1. DeadLock Prevention
- 용어 그대로 미리 예방하는 방법. 자원 할당 시 DeadLock 조건 4가지 중 어느 하나가 만족되지 못하도록 하는 방식
- 효율성과 처리량을 감소시키고, starvation이 발생할 수 있음 (자원 낭비가 심함)
💡 2. DeadLock Avoidance
- DeadLock이 발생할 가능성 있는 경우에 아예 자원 할당하지 않는 방식
ex) 가장 단순한 방식으로, 프로세스들이 필요로 하는 자원 별 최대 사용량 미리 선언- 시스템이 unsafe state에 들어가지 않는 것을 보장하는 것
safe sequence : 프로세스 내 순서 중 Pi의 자원 요청이 순차적으로 충족되는 경우
safe state : 시스템 내 프로세스들에 대해 모두 safe sequence가 존재하는 경우- Avoidance 알고리즘 종류
2-1) Resource Allocation Graph Algorithm
: 프로세스에서 자원을 요청하는 (request edge)가 자원을 할당받는 순간 방향이 반대되는 (assignment edge)로 변경 될 때 모든 edge에 대해 사이클이 생기지 않는 경우에만 요청된 자원을 할당
2-2) Banker's Algorithm
다익스트라가 고안한 알고리즘으로, 프로세스가 자원을 요청할 때마다 수행된다.
기본 개념으로, 자원 요청 시 safe 상태를 유지하는 경우에만 할당하며 총 요청 자원 수가 남은 자원 수보다 적은 프로세스만을 선택하며 수행하고 그런 프로세스가 없다면 unsafe 즉, 데드락이 발생할 수 있는 상태인 것으로 판단💡 3. DeadLock Detection
- 자원 할당 그래프를 통해 DeadLock 탐지
- 자원 요청 시, detection algorithm을 실행시켜 그에 대한 오버헤드 발생
💡 4. DeadLock Recovery
- DeadLock 일으킨 프로세스를 종료 or 할당 자원을 해제시켜 회복
- < 프로세스 종료 방법 >
DeadLock 상태의 프로세스 모두 중지
DeadLock 상태 제거될 때까지 하나씩 프로세스 중지- < 자원 선점 방법 >
DeadLock 상태의 프로세스가 점유하고 있는 자원 선점해 타 프로세스에 할당
우선 순위 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점
+) deadlock 발생 이전으로 rollback 후 프로세스를 재시작하는데, 동일 프로세스가 지속적으로 선택되면 starvation이 발생할 수 있어 rollback된 횟수를 저장해 해결💡 5. DeadLock Ignorance
- DeadLock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방식
DeadLock 자체가 매우 드물게 발생하기에 이에 대해 조치를 취하는 행위 자체가 더 큰 overhead일 수 있다. 따라서 시스템이 비정상적으로 작동하는 것을 사람이 느끼고 프로세스를 수동적으로 직접 죽이는 방법으로 대처하는 방식- UNIX, Windows 등 대부분의 범용 OS가 채택하는 방식
참고 자료
To be a DataScientist