데드락 문제 (Deadlock Problem)

Deadlock (교착상태)

두 개 이상의 프로세스나 스레드가 서로가 가진 자원을 기다리며 다음 일을 처리하지 못하는 상태를 말합니다.

 

프로세스 A와 B는 1번 자원과 2번 자원을 모두 획득해야 일을 끝낼 수 있는데

A는 1번을 B는 2번 자원을 각자 획득하고 상대방에게 할당된 자원을 무한정 기다리고 있다.

 

Deadlock 발생의 4가지 조건

데드락은 아래의 4가지 조건이 모두 성립해야 발생한다. 

따라서 아래 조건 중 하나라도 해결한다면 데드락 문제를 해결할 수 있다.

1. Mutual Exclusion (상호배제) 
   • 자원은 한번에 하나의 프로세스만 사용할 수 있다.
2. No preemption (비선점)
   • 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없다.
3. Hold and wait (점유 대기)
   • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지않고 계속 갖고 있다.
4. Circular wait (순환 대기)
   • 자원을 기다리는 프로세스간에 사이클이 형성되어 있다.

 

Deadlock 해결 방법

1. Prevention (예방)

Deadlock 발생의 4가지 조건 중 하나라도 제거하여 문제를 해결하는 방법이다.

• Mutul exclusion 을 방지할 수 없다.  만약 공유해서 사용할 수 있는 자원이 었다면 데드락 문제가 발생하지 않았을 것이다.
• Hold and Wait 를 방지하기 위해서는 프로세스가 필요한 자원을 모두 획득 했을 때만 자원을 할당받고 획득하지 못하면 자원을 모두 내려 놓는 방식을 해결할 수 있지만 너무 자원이 낭비된다는 단점이 있다.
• No Preemption : 자원을 빼앗는 것을 허용하게 된다면 CPU나 메모리 같은 경우에는 상태를 쉽게 save하고 resotre 할 수 있지만 모든 자원이 그렇지 않기 때문에 해결하기 어렵다.
• Circular Wait 은 모든 자원에 할당 순서를 정해놓고 순서대로만 할당하는 방식을 사용할 수 있다.

 

2. Avoidance (회피)

자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전한 지 조사 후 안전할 경우에만 할당한다.

 

은행원 알고리즘

• 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 한다.
• 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자 수가 일정해야 한다.
• 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.

3. Detection and recovery ( 탐지 및 회복)

deadlock이 발생하도록 놔두고 발생시 찾아내서 해결하는 방법이다.

 

탐지

자원 할당 그래프를 이용하여 시스템에 deadlock이 발생했는지 점검한다. 

자원을 요청할 때마다 탐지 알고리즘을 실행하는 것은 큰 오버헤드가 발생한다.

 

회복

deadlock을 탐지했다면 deadlock을 일으킨 프로세스를 종료하거나 할당된 자원을 뺏어 회복시킨다.

 

 

 

출처

https://chanhuiseok.github.io/posts/cs-2/

https://velog.io/@ejung803/%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C%EC%99%80-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-%ED%95%B4%EA%B2%B0%EB%B0%A9%EB%B2%95