Deadlock

데드락은 프로세스가 리소스를 점유하고 놓아주지 않거나, 어떠한 프로세스도 리소스를 점유하지 못하는 상태가 되어 프로그램이 멈추는 현상을 말한다.

Deadlock 조건

• Mutual exclusion(상호 배제) : 여러 프로세스 중 하나만 critical section에 진입할 수 있을 때, 다른 프로세스들이 자원 사용 불가, 한번에 한 프로세스만이 자원 사용 가능
• Hold and wait(점유와 대기) : 프로세스 하나가 리소스를 잡고 있고, 다른 것은 대기중일 때. 즉 어떤 공유된 자원을 가진 상태에서 또 다른 것을 요구할 때
• No preemption(비선점) : OS가 작동중인 프로세스를 임의로 중단시킬 수 없을 때. 자원들은 그들이 점유하고 있는 프로세스로부터 도중에 해체되지 않음. 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
• Circular wait(순환 대기) : 프로세스가 순환적으로 서로를 기다릴 때, 각 프로세스는 순환적으로 다음 프로 세스가 요구하는 자원을 가지고 있다.

Deadlock 해결 방법

데드락을 제어하는 데는 크게 두가지 방법이 있다. 하나는 데드락을 방지하는 것이고 하나는 데드락을 피하는 것이다.

Deadlock Prevention

데드락을 방지한다는 것은 데드락 발생 조건 중 하나를 만족시키지 않음으로써 데드락이 발생하지 않도록 하는 것이다.

• Mutual Exclusion : 두 개 이상의 프로세스가 공유 불가능한 자원을 사용하니 발생하는 것이므로 공유 자원을 사용할 수 있도록 한다.
• Hold and wait : 한 프로스세가 실행되기 전 모든 자원을 할당시키고, 이후에는 다른 프로세스가 자원을 요구하도록 한다. 자원 과다 사용으로 인한 효율성, 기아 상태의 문제가 생길 수 있다.
• No preemption : 리소스를 점유하고 있는 프로세스가 다른 리소스를 요청했을 때 즉시 리소스를 사용할 수 없다면 점유하고 있던 리소스를 release 한다.
• Circular wait : 리소스 타입에 따라 순서를 매긴다.

Deadlock Avoidance

데드락을 피하는 것은 데드락이 발생할 것 같을 때는 아예 리소스를 할당하지 않는 것이다. 여기서는 시스템이 unsafe 상태가 되지 않도록 해야 하며, 만약 unsafe 상태가 되면 최대한 빨리 safe상태로 복구한다. 데드락 가능성은 포인터로 자원 할당 그래프를 구현해 판단한다. 만약 리소스 타입이 여러개면 은행원 알고리즘을 사용한다.

은행원 알고리즘(Banker’s algorithm)

은행원 알고리즘은 Dijkstra가 고안한 데드락 회피 알고리즘이다. 은행에서 모든 고객의 요구가 충죽되도록 현금을 할당하는 데에서 유래한 기법으로, 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기함으로써 교착 상태를 회피하는 기법이다.

Deadlock 회복

만약 시스템이 데드락을 방지하거나 회피하지 못했고, 데드락이 발생했다면 데드락으로부터 복구되어야 한다. 이때는 어떤 프로세스를 종료시킬지 정하는 것이 중요해진다.

판단 기준

1. 프로세스의 중요도
2. 프로세스가 얼마나 오래 실행됐는가
3. 얼마나 많은 리소스를 사용했는가
4. 프로세스가 작업을 마치기 위해 얼마나 많은 리소스가 필요한가
5. 프로세스가 종료되기 위해 얼마나 많은 리소스가 필요한가
6. 프로세스가 batch인가 interactive 한가

Resource Preemption

데드락을 해결하기 위해 리소스 선점 방식을 사용할 때는 다음과 같은 이슈가 있다.

1. Selecting a victim : 어떤 프로세스를 종료시킬 지 결정한다.
2. Rollback : 데드락이 발생하기 전 상태로 되돌린다.
3. Starvation : 계속 같은 프로세스가 victim이 될 수 있다. 이 경우 기아(Stravation) 문제가 발생한다.

출처:

https://parksb.github.io/ [공룡책으로 정리하는 운영체제]