Deadlock
- 프로세스는 실행을 위해 여러 자원을 필요로 한다
- CPU, 메모리, 파일, 프린터 .....
- 어떤 자원은 있으니 다른 자원은 없을 때(다른 프로세스가 사용 등) 프로세스 혹은 스레드는 대기해야 한다
- 두 개 이상의 프로세스 혹은 스레드가 필요로 하는 자원을 서로 가지고 있다면 무한히 대기하게 되어 결코 상태가 변할 수 없는 상황이 일어난다
- 이것을 deadlock 이라고 한다
- Blocked state
- 프로세스가 특정 이벤트를 기다리는 상태
- 프로세스가 필요한 자원을 기다리는 상태
- Deadlock state
- 리소스를 기다리는 프로세스(혹은 스레드)가 결코 상태가 변할 수 없는 상황
- 다른 대기중인 스레드(혹은 프로세스)가 해당 자원을 가지고 있기 때문
System Model
- 동일 자원은 여러 개 있을 수 있다(instance)
- ex) CPU2개, 프린터 3개 등등
- 프로세스(혹은 스레드)는 다음과 같은 흐름으로 리소스를 이용한다
- Request : 리소스를 요청한다. 만약 다른 프로세스가 리소스를 사용중이라서 리소스를 받을 수 없다면 대기한다
- Use : 프로세스는 리소스 위에서 수행된다
- Critical Section이라고 볼 수 있다
- 한 프로세스는 여러 리소스를 사용할 수 있다
- Release : 프로세스가 리소스를 놓아준다
Deadlock vs Starvation
- Deadlock
- 일어날 가능성이 없다
- Starvation
- 일어날 가능성이 있지만 무한정 대기하는 상태
Deadlock 발생 조건
Deadlock은 아래의 4가지 조건을 만족해야 발생한다. 하나라도 만족하지 않는다면 발생하지 않는다
- Mutual exclusion
- 여러 프로세스 중 하나의 프로세스만 Critical Section에 접근 가능
- 프로세스가 자원를 사용한다면 다른 프로세스는 해당 자원 사용 불가
- Hold and wait
- 점유하고 대기하는 스레드(혹은 프로세스)
- 스레드가 적어도 하나의 리소스를 가지고
- 다른 스레드가 가지고 있는 리소스의 사용을 기다리는 경우
- 스레드가 무한정 대기 중이더라도, 해당 스레드가 아무런 자원이 없다면 deadlock을 일으키지 않는다
- 해당 스레드는 starvation
- Non-preemptible resources
- 사용중인 자원은 선점될 수 없다
- Circular wait
- 프로세스가 순환적으로 서로를 기다릴 때
- 의존 그래프를 그려보면 순환
Resource-Allocation Graph
프로세스 간의 관계를 그래프로 도식화해 보면 데드락이 발생할지 예상할 수 있다. 만약 그래프에 순환 고리가 있다면 데드락 위험이 있다는 의미가 된다. 순환 고리가 있다고 무조건 데드락이 발생하는 것은 아니지만, 순환 고리가 없으면 절대로 데드락이 발생하지 않는다.
Deadlock 제어 방법
프로토콜이 deadlock을 예방하거나 회피하도록 하여 아예 발생하지 않도록 하거나, 발생하도록 놔두고 발생하면 탐지하여 회복하도록 한다.
Deadlock Prevention
deadlock 발생 조건 4가지 중 한가지만 막으면 되니, 하나 선택하여 예방해보자
Mutual Exclusion의 경우
- 모든 리소스를 공유 가능하게 만들면 deadlock이 발생하지 않는다
- 본질적으로 불가능 하다
- 공유할 수 없는 자원이 있다
Hold and Wait
- 스레드가 다른 자원을 요청할 때 자원을 가지고 있으니 문제가 생긴다
- 그러니까 자원을 요청할 때는 가지고 있던 자원을 전부 반납하도록 하자
- 실용적이지 않다
- starvation
- 자원 사용률 저하
No preemption
- 선점을 보장하는 프로토콜을 사용하자
- 선점이 불가능한 자원이 있다
- ex) print
- 혹은 스레드가 자원을 할당 받자마자 선점당할 수 있다
- 대부분의 애플리케이션에서 적용할 수 없다
Circular wait
- 자원 타입에 번호를 부여
- 자원을 요청할 때 자신이 보유한 자원보다 높은 번호를 가진 자원만 요청
- 이를 통해 circular wait를 방지할 수 있다
- 증명된 사실..!!
- starvation의 위험은 높아진다
- 자원의 활용율이 떨어진다
결론
deadlock을 예방하는 것은 부작용이 많다
장치 효율과 시스템 성능이 줄어든다.
그렇기 때문에 Multi-thread 를 통해 얻은 이점을 deadlock prevention이 다 상쇄시켜 버린다
미사일 시스템 등 Critical 한 시스템에서만 사용한다.
Deadlock avoidence
회피란 프로세스의 자원 할당 요청이 deadlock이 발생할 것 같은 때는 리소스를 할당하지 않는 것
- 스레드는 deadlock을 회피하기 위해 대기하게 된다
- deadlock 발생 여부를 예측하기 위해 추가적인 정보가 필요하다
- 할당되거나 할당이 가능한 자원들의 개수
- 스레드들이 요청할 수 있는 각 자원의 최대 개수
- safe state
- system이 각 스레드에 자원을 할당 가능한 상태
- 모든 프로세스가 정상적 종료 가능한 상태
- safe sequence 가 존재
- deadlock 상태가 되지 않을 수 있음을 보장
- unsafe state
- 자원 할당 순서에 따라 deadlock이 발생 가능한 상태
- 반드시 발생한다는 의미는 아니다
시스템이 safe한 상태라면 unsafe state로 넘어가지 않도록 함으로써 deadlock을 회피할 수 있다
시스템이 unsafe 즉 Deadlock 발생 가능성이 있는 상태라면 최대한 빨리 safe 상태로 복구한다
deadlock 발생 가능성은 자원 할당 그래프(Resource allocation graph)를 구현해 판단하거나, 리소스 타입이 여러 개라면 banker's algorithm을 사용하여 판단한다.
Banker's Algorithm
- Deadlock avoidance를 위한 간단한 이론적 기법
- 가정
- 한 종류의 자원이 여러 개라고 가정
- 시스템을 항상 safe state로 유지
- 현재 상태에서 안전 순서가 하나이상 존재하면 안전 상태, 하나도 못찾으면 unsafe 상태
- Banker's algorithm
- 만약 자원을 줬을 때 safe 상태라면 자원을 준다
- unsafe 하다면 주지 않는다
Recovery from Deadlock
만약 데드락이 발생했다면, 데드락으로부터 복구되어야 한다.
- deadlock이 발생했는지 탐지하고, 발생했다면 회복할 방법이 필요하다
- Banker's algoruthm 을 통해 탐지
어떤 프로세스를 종료시킬 지 정하는 것 몇가지 판단 기준이 있다
- 프로세스의 중요도
- 프로세스가 얼마나 오래 실행되었는가
- 얼마나 많은 리소스를 사용했는가
- 프로세스가 작업을 마치기 위해 얼마나 많은 리소스가 필요한가
- 프로세스가 종료되기 위해 얼마나 많은 리소스가 필요한가
- 프로세스가 batch인가 interactive 한가
Reference
https://www.inflearn.com/course/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B3%B5%EB%A3%A1%EC%B1%85-%EC%A0%84%EA%B3%B5%EA%B0%95%EC%9D%98/unit/65282
https://parksb.github.io/article/11.html