데드락 (deadlock)

1. 정의

- 영원히 오지않는 event를 기다리는 것

- 예를 들면 A라는 프로세스는 B가 가진 자원이 있어야만 동작 가능하여 B의 작업이 끝나기를 기다리고

  있는데, B도 A가 가진 자원이 필요해 A가 끝나기를 기다리는 상태. 결국 두 작업은 영원히 끝날 수

  없게 된다.

- starvation은 어떤 한 작업의 차례가 오지 않아 영원히 기다리는 것이어서 무언가 생산적인 활동은

  일어나고 있는 반면(다른 프로세스는 동작하고 있기 때문에), deadlock은 작업 자체가 이루어지지 않아

  생산적인 활동 자체가 없다.

 

 

2. 발생 조건

4가지 조건을 동시에 만족하면 데드락이 일어날 수 있음

- Mutual exclusion ; 한번에 오직 1개의 프로세스만이 자원에 접근가능

- Hold and wait ; 최소한 한 개의 자원을 가진 프로세스가 다른 프로세스 소유의 자원을 기다리는 것

- No preemption ; 해당 작업이 완료되기 전까지는 자원이 반환되지 않는 것

- Circular wait ; 연쇄적으로 자원을 기다리는 형태

  (1은 2를 기다리고 2는 3을 기다리고 3은 1을 기다리는 것과 같은 상태)

 

 

3. Anti-deadlock

 

3.1 Ostrich Algorithm

- 시스템을 재시작한다.

- (+) 가장 빠르고 비용이 적게 든다.

- (-) deadlock의 발생 빈도가 높아질수록 효율이 극도로 나빠진다.

 

3.2 Deadlock Prevention

- 데드락의 발생 조건을 막아 데드락이 일어나지 않게 한다.

- mutual exclusion ; 동시에 여러 프로세스의 접근을 가능하게 한다.

  하지만 실제로 불가능하다.

- hold and wait ; 한 번에 모든 자원을 가지거나 아무것도 가지지 못하게 한다. (hold 방지)

  또는 실행 전에 자원을 미리 할당해버린다.(wait 방지)

  자원 활용도가 떨어지며, starvation이 발생할 수 있다.

- no preemption ; 한 개의 작업이라도 실패하면 모든 자원을 release한다.

- circular wait ; 자원 형태에 따라 순서를 매겨 프로세스가 리소스를 요청하면 해당 순서에

  따라 자원을 할당한다.

3.3 Deadlock Avoidance

- Dijkstra의 banker's Algorithm을 이용

- 각각의 프로세스가 OS에게 자신이 필요로하는 최대의 자원을 알려준다. OS는 오직 safe한

  상태를 가지는 프로세스에게만 자원을 할당한다.

- safe state ; 받은 자원을 통해 무사히 작업을 수행하고 반납할 수 있는 상태

- 지나치게 보수적이라서 safe state를 위해 병렬성을 감소시킨다.

- 또한, 프로세스가 알려줬던 요구량보다 더 많은 요구량이 발생할 수 있다.

3.4 Deadlock Detection

- 데드락 상태가 되는 것은 허용하지만, wait-for graph 또는 detection algorithm을 통해

  데드락을 유발하는 프로세스를 찾아낸다.

 

3.5 Deadlock Recovery

- 매 time slice마다 프로세스를 제거함과 동시에 회수해 더 이상 데드락이 발생하지 않을 때까지 한다.

  또는 체크 포인트를 만들어 데드락이 발생하면 체크 포인트 지점으로 rollback한다.

- rollback시 starvation이 발생할 가능성이 높다. (무한 rollback이 발생할 수도 있다)