OS - DeadLock

Deadlock

• 2개 이상의 프로세스가 동시에 semaphore/mutex에 접근함으로써 하나의 waiting상태의 프로세스로 인해 lock이 무한히 풀리지 않는 경우
  

dead lock 발생 필요조건

• 4가지 조건을 만족하면 dead lock이 발생할 수도 있다.
• dead lock이 발생했다면 4가지 조건이 모두 참이다.
• 대우 ) 4가지 조건 중 하나라도 만족하지 않으면 deadlock이 발생하지 않는다.

Mutual exclusion (문제 해결의 단서로 쓸 수 없다)

• 한 번에 하나의 프로세스만 resource를 사용할 수 있다

Hold and wait

• 하나의 shared resource를 hold한 상태에서 추가적으로 필요한 shared data를 다른 프로세스가 사용하고 있다면 waiting해야한다.
• 하나를 가지고 다른 하나를 기다리는 조건

No preemption

• 리소스는 프로세스가 작업을 완료한 후 이를 보유한 프로세스에 의해서만 자발적으로 방출될 수 있으나 방출하지 않으므로 발생된다.
• hold한 리소스를 사용하지 않을 때 반납하지 않고, 사용이 끝날 때만 반납한다.

Circular wait (개발자가 다룰 수 없는 조건이다)

• p0이 p1의 resource를 기다리고 p1은 p2의 resource를 기다리고 p2는 p0의 resource를 기다리는 상황
• 순환적으로 shared data를 사용을 기다리며 무한히 waiting하는 상태

Handling Deadlocks

Deadlock prevention

• 개발자의 알고리즘이 한다
• shared data에 대한 요청의 방법을 제한한다.
• 최소 하나 이상의 필수 조건이 유지되지 않는지에 대해 검사한다.

Deadlock avoidance

• OS가 deadlock여부를 테스트한다
• shared data에 대한 요청이 들어왔을 때 알고리즘을 통해 deadlock의 가능성을 검토한다
• 시간이 많이 걸리며, deadlock의 가능성이 낮으므로 overhead가 많이 발생한다.
• 리소스 요청 방법에 대한 추가적인 정보가 필요하다
• 요청에 대한 승인/미승인 여부를 즉석에서 결정한다.

Deadlock detection & recovery

• OS가 resource를 분배하고 주기적으로 deadlock에 빠졌는지에 대해 검사한다
• deadlock의 여부를 검사하고 발생했다면 발생 이전으로 복구한다.
• 시간이 많이 걸리며, deadlock의 가능성이 낮으므로 overhead가 많이 발생한다.

Deadlock ignorance

• OS가 Deadlock을 무시한다, 현재 OS가 채택한 방법)
• deadlock발생 가능성이 낮고 overhead가 커서 단순히 deadlock을 무시한다.
• The Ostrich(낙타) algorithm