데드락
프로세스가 자원에 대한 허용권을 얻지 못해서 다음 진행을 하지 못하고 계속 멈춰있는 상태를 의미
발생 조건
- 상호 배제(Mutual Exclusion) : 여러 프로세스 중 하나만 Critical Section에 진입할 수 있을 때
- 점유 대기(hold and Wait) : 프로세스가 자원을 점유하고 있으면서, 다른 자원을 기다릴 때
- 비선점(No Preemption) : 이미 할당된 자원을 선점할 수 없다.
- 순환 대기(Circle wait): 프로세스가 순환적으로 서로를 기다릴때
위 조건 중 하나만 만족되지 않아도 데드락은 발생하지 않는다.
Resource Allocation Graph
프로세스간의 관계를 그래프로 도식화해보면 데드락이 발생할지 예상할 수 있다.
만약 그래프에 순환 고리가 있다면 데드락의 위험이 있다는 의미이다. 순환고리가 있다고 해서 무조건 데드락이 발생하는 것은 아니다. 하지만 순환 고리가 없다면 데드락은 절대 발생하지 않는다
Deadlock 제어 방법
데드락을 제어하는 방법은 방지하는것과 피하는 것이 있다.
Deadlock Prevention
데드락을 방지하는 것은 데드락 발생 조건 중 하나를 만족시키지 않음으로써 데드락이 발생하지 않도록 하는 것이다.
- Mutual Exclusion : Critical section Problem을 해결하기 위해선 이 조건이 반드시 만족해야하므로, 공유 자원은 이 조건을 만족시킬 수 밖에 없다.
- Hold and Wait: 한 프로세스가 실행되기 전 모든 자원을 할당시키고, 이후에는 다른 프로세스가 자원을 요구하도록 한다. starvation문제가 생길 수 있다.
- No preemption : 리소스를 점유하고 있는 프로세스가 리소스를 요청했을 때, 즉시 리소스를 사용할 수 없다면 점유하고 있던 자원을 release한다.
- Circle wait: 리소스의 타입에 따라 프로세스마다 일대일 함수로 순서를 지정해준다.
데드락을 방지하는 것은 장치 효율과 시스템 성능을 떨어트리는 문제가 있다
Deadlock Avoidance
데드락이 발생할 것 같을 때 아예 리소스를 할당하지 않는 것이다. unsafe 상태가 되지 않도록 해야 하며, unsafe가 되었을 때, 최대한 빠르게 safe 상태로 복구해야 한다.
포인터로 자원 할당 그래프(Resource allocation graph)를 구현하여 판단한다. 만약 리소스 타입이 여러개라면 banker’s algorithm을 사용한다.
Banker’s Algorithm
다익스트라가 고안한 데드락 회피 알고리즘이다. 프로세스가 리소스를 요청할 때 마다 수행되며, 만약 리소스를 할당했을 때 데드락이 발생하는지 확인하는 시뮬레이션이다.
safe상태에서만 자원을 할당하고 unsafe인 상태에선 자원을 할당하지 않는다.
4가지 조건을 유지하며 프로세스를 운영하기에 예방보다는 자원 활용성에서 유연하지만, 교착 상태와 발생과의 연관성을 파악하는 것에 현실적인 어려움이 있다.
Recovery from Deadlock
만약 시스템이 데드락을 방지하거나 회피하지 못했고, 데드락이 발생했다면 데드락으로부터 복구되어야 한다. 이때 어떤 프로세스를 종료할지 정하는 것이 중요하다.
- 프로세스의 중요도
- 프로세스를 얼마나 오래 실행했는가
- 얼마나 많은 리소스를 사용했는가
- 프로세스가 작업을 마치기 위해 얼마나 많은 리소스가 필요한가
- 프로시스가 종료되기 위해 얼마나 많은 리소스가 필요한가
- 프로세스가 batch인가 interactive인가
Resource Preemption
데드락을 해결하기 위해 리소스 선점(Preemption) 방식을 사용할 때는 다음과 같은 이슈가 있다.
- Selecting a victim : 어떤 프로세스를 종료시킬 지 결정한다
- Rollback : 데드락이 발생하기 전 상태로 되돌린다.
- Starvation: 계속 같은 프로세스가 victim이 될 수 있다. 이 경우 기아(starvation)이 발생할 수 있다.
