[OS8] Deadlocks

Deadlock

데드락은 두 개 이상의 프로세스들이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. 아래와 같이 두 프로세스가 각각 S, Q 를 wait 한 상태에서는 S, Q 모두 signal 되지 않기 때문에 데드락에 빠진다.

Deadlcok 발생 필요조건

1. Mutual exclusion
   • 하나의 리소스에는 한 번에 하나의 스레드만 접근 가능하다.
2. Hold and wait
   • 필요한 자원들이 있으면 순서대로 자원을 얻고, 다른 자원을 기다려야하면 기존 리소스를 다 가진 채로 기다린다.
3. No preemption
   • 가진 자원들은 프로세스를 끝난 후에야 반납한다.
4. Circular wait
   • P0가 필요한 리소스는 P1이 들고 있고 P1이 필요한거는 P2, 다시 마지막 프로세스가 필요한 것은 P0 가 가지고 있는 순환 양이 존재한다.

Deadlock 처리

1. Deadlock prevention
   • 미리 예방하는 것. Deadlock 의 발생 가능성을 원천 봉쇄한다. 개발자가 할 수 있는 유일한 방법이다.
2. Deadlock avoidance
   • 운영체제가 하는 것. 프로세스가 쉐어드 데이터를 달라고 요청하면 데드락에 빠질 수 있는 것인가 체크한 후 데이터를 전달한다.
3. Deadlock detection and recovery
   • 운영체제가 하는 것. 자원을 달라고하면 달라는 대로 주고 주기적으로 데드락에 빠졌나 확인한다. 검사하고 데드락이면 이전 상태로 복구해준다.
4. Deadlock ignoance
   • 자기가 해결할 수 없는 문제가 주어지면 그냥 가만히 있는다. 현재의 운영체제가 데드락을 처리하는 방법이다. 데드락이 걸릴 확률이 너무 낮아서 대응하는 것이 비효율적이기 때문이다.

Deadlock prevention

발생 4가지 필요 조건 중에 하나라도 불만족 시키면 된다.

Mutual exclusion이 없다는 것은 race condition이 없다는 것이므로 없앨 수 없다. 또한 Circular wait 또한 조건이 주어지는 것이므로 바꿀 수 없다.

따라서 개발자하 할 수 있는 것은 Hold and wait, No preemption 을 제거하는 방법이다.

이는 필요한 것이 여러 개라면 하나씩 가지는 것이 아니라 한 번에 갖도록 하거나, 여러 쉐어드 리소스가 필요할 때 지금 당장 모두 가질 수 없다면 자신의 것을 모두 반납한 후에 기다리는 등으로 해결할 수 있다.