운영체제(8), Deadlocks

Deadlocks

 

락이 죽어서 영원히 풀리지 않는 락이다.

 

 

 

 

화살표를 한 시점에서 쓰레드들이 각각 wait이 된다면 두 쓰레드의 상태는 계속 waiting 상태가 된다. 결국 P0와 P1은 영영 스케줄할 수 없게 된다.

 

Deadlock이 발생될 필요 조건 4가지

a -> b는 a가 참이면 b는 항상 참이고, 이에 따라 a는 b의 충분 조건이 된다. 데드락이 발생하면 위의 네가지 조건이 항상 참이 된다. 즉, 위의 네가지 조건에 만족했다고 해서 무조건 데드락이 발생하는 것은 아니다.

 

mutual exclusion: 한 시점에서 하나의 프로세스만 자원에 접근한다. 이는 해결할 수 없다.

 

Hold and wait: 하나의 프로세스가 홀드한 상태에서 wait한 상태이면 deadlock에 걸릴 가능성이 있다. 이는 개발자가 해결할 수 있는 조건이다. 필요한 shared resourse를 한번에 가지도록 할 수 있다.

 

No preemption: 본인이 접근한 리소스를 계속 가지고 있는다. 사용할 수 없으면 shared data를 반납하는 식으로 구현한다. 이는 개발자가 해결할 수 있는 조건이다.

ex) 배고픈 철학자 문제에서 젓가락을 놓으면 deadlock이 발생하지 않지만 이를 놓지 않는다. 

 

Circular wait: 서로가 서로를 기다리는 상황으로 이 또한 해결할 수 없다.

 

네가지 조건이 만족하면 데드락이 발생할 수 있다.

 

Handling Deadlock

 

 

Deadlock prevention

데드락이 발생할 가능성을 원천 봉쇄한다. 이는 개발자가 고려해야한다.

 

Deadlock avoidance

운영체제가 shared resource를 줄 때 데드락이 발생할 가능성을 체크한 뒤에 이를 할당한다. 매우 많은 오버헤드가 발생한다. 운이 나쁠 때 데드락이 발생하게 되기에 기회비용이 높다.

 

Deadlock detection and recovery

운영체제가 shared resource를 일단 주고 주기적으로 데드락에 빠졌는지 안빠졌는지 검사한다. 이후 데드락에 빠지면 이전 상태로 복구한다. 주기적으로 확인하기에 오버헤드가 높다.

 

Deadlock ignorance

현재 운영체제가 하는 방법으로 데드락에 빠지는 것에 대해 딱히 다루는 것이 없다. 

Ostrich: 낙타, 낙타는 해결할 수 없으면 머리를 모래속에 넣고 잊어버리고자 한다. 즉, 우리는 개발자의 입장에서 Deadlock prevention을 해야한다. 이때 위에서 봤던 deadlock을 발생시킬 4가지 필요조건 중에 하나라도 만족하지 않으면 deadlock이 발생하지 않기에 이를 가지고 처리한다.

 

해당 코드는 위의 네가지 조건이 만족했기에 데드락에 빠질 가능성이 생긴다. 이에 따라 이를 아래와 같이 수정해야한다.

 

이는 hold and wait 조건을 수정한 것이다.