Operating System Concepts 8장 Deadlock

• A가 lock(x), B가 lock(y)인데 A가 lock(y)도 하고싶고, B가 lock(y)도 하고 싶을때 두 lock은 절대로 풀리지 않기 때문에 Deadlock이라고 한다.

A,B는 프로세스 x,y는 resource | x->A는 할당된거 A->y는 waiting하고 있는거

ㄴ> 위의 그림은 cycle graph이다.

 

1.DeadLock이 발생 안하게 하는 방법

• Prevention
• Avoidence

2.DeadLock 발생 후 해결하는 방법

• Detection & Recovery

 

 

8.3.1 Necessery Conditions (데드락이 발생하는 필요조건)

1. Mutual exclusion(상호 배제) - 자원은 한명밖에 접근 못해!
2. Hold & Wait : 하나의 자원을 잡고 있으면서 또다른 자원을 기다리고 있다.
3. No Preemption : 자원은 preemption 될 수 없다.
4. Circular Wait : cycle 그래프 형태로 waiting이 있다.

 

 

8.5 Deadlock Prevention

데드락을 예방하는 방법

1. Mutual exclusion : 얘는 예방 X
2. Hold & Wait : 만약에 두 자원을 lock을 하고 싶다면 다른 프로세스가 lock할 수 없게 동시에 두개의 자원을 lock한다.  ex) lock(x,y) , Dining 문제에서 처음부터 동시에 포크를 두개를 집어버리면 Dead lock이 발생하지 않는다. 

단점 : 성능 저하

1. No preemption : 얘도 예방 X
2. Circular Wait : Ordering 자원에다 번호를 붙인다. 그래서 3번 자원을 사용하면 3,4,5를 사용할 수 있는것. 번호대로 순차적으로 자원을 할당한다.

 

8.6 Deadlock Avoidance

데드락이 발생할 가능성이 존재하면 기다려라 => 회피

 

8.6.3.3 

 

Allocaion - A,B,C 자원에서 Tread한테 할당한 수 

Max -  작업을 끝내는데 필요한 자원의 수 => T3가 B 하나 C 하나만 필요하니까 T3에게 먼저 할당한다.

Available - 할당하고 남은 자원

 

A : 2+ 3+ 2+ 3 =10;

B : 1 + 1 + 3 = 5;

C : 2 + 1 + 2 + 2 =7;

 

 

8.7 Deadlock Detection

• Deadlock이 발생한걸 감지하면 해결시켜야줘야한다.

8.8.1

• 해결 방법은 두가지 

1. Abort all deadlocked processes - 모든 프로세스 abort
2. Abort one process at a time until the deadlock cycle is eliminated - 데드락 사이클이 제거될때까지 한 프로세스를 abort

ㄴ> 그러면 한 프로세스(희생자)를 어떻게 결정

8.8.2 Resource Preemption

1. 희생자를 정한다.
2. rollback 시킨다.

• 3. Starvation