OS - 06. Deadlock

Preemptable and Nonpreemptable Resources

이벤트들은 작업에따라 resource를 필요로 한다.

1. Request the resource
2. Use the resource
3. Release the resource

Resource Acquisition

a: 하나의 리소스를 사용하는 경우. 리소스를 할당받기위해 semaphore을 설정하고 down > use > up을 통해 사용 후 반납한다.

b: 리소스 2개를 사용하는경우. 리소스를 둘 다 할당받은 후 사용 후 둘 다 반납한다.

a: deadlock free code. 자원의 할당 및 반납순서를 지켜 데드락이 발생하지 않는다.

b: code with a potential deadlock. pA가 resource1을 할당받고 pB가 resource2를 할당받게되면 서로 resource 2,1을 기다리게되므로 데드락이 발생할 수 있다.

Illustation

-> 데드락은 각각의 프로세스가 다른 프로세스의 작업이 수행완료될때까지 기다리는 경우 발생할 수 있다!

Conditions for Resource Deadlocks

1. Mutual exclusion condition
2. Hold and wait condition
3. No preemption condition
4. Circular wait condition

Deadlock Modeling

Strategies for deadlock

1. Just ignore the problem - 무시한다. 실제로 대부분의 시스템이 사용한다
2. Detection and recovery - deadlock을 확인하고 회복한다. 프로세스를 죽여서 할당할 수 있다.
3. Dynamic avoidance - deadlock 회피전략.
4. Prevention - deadlock일어나는 4가지경우 중 1가지 경우를 아예 없애버린다.

Deadlock Detection

Deadlock Detection; with One Resource of Each Type

어떤 자원이 어디에 할당되어있는지 resource graph를 그려 circle만 남겨서 데드락이 발생하는 b 경우를 파악한다.

- P1을 처리하면 사용가능한 자원은 2 3 1 로 p1을 끝낼 수 있다. 하지만 p4를 처리하면 사용 가능한 자원이 0 0 3이 남게되므로 처리가능한 프로세스는 존재하지 않기 때문에 deadlock이 발생한다.

- 이렇게 deadlock이 발생하는 경우를 회피해서 실행 순서를 정할 수 있다.

 

Recovery from Deadlock

• Recovery through preemption
• Recovery through rollback
• Recovery through killing processes

preemption을 뺏거나 프로세스를 rollback, killing하여 자원을 뻇어서 할당함으로써 recovery할 수 있다.

Deadlock Avoidance

Deadlock을 피해다니면서 할당한다.

b의 경우는 C를 끝낼 수 있으므로 deadlock이 발생하지 않지만, c는 끝낼 수 있는 프로세스가 존재하지 않으므로 deadlock이 발생한다.

Deadlock Prevention

Deadlock Prevention의 접근방법

Attacking Mutual exclusion, Hold and wait, No preemption, Circular wait의 4가지 경우 중 한 경우를 없애버리면 deadlock이 발생하지 않을 수 있다. 이 접근법에는 위의 그림과 같다.