Deadlock

Deadlock은 굶어 죽을 때까지 풀리지 않는 교착 상태를 의미한다.

//Process1
mutex_lock(A); //a1
mutex_lock(B); //a2

//Process2
mutex_lock(B); //b1
mutex_lock(A); //b2

예를 들어 위와 같은 두 프로세스가 있다면, 평상 시에는 프로세스1이 A에 대해 락을 걸고 들어간 후, B에 대해 락을 걸고 들어가고, 프로세스2는 B의 락이 풀리기를 기다려서 들어갔다가 A의 락이 풀리기를 기다려서 들어가는 식으로 정상 동작한다.
그러나 운이 나빠서 진행 순서가 a1->b1->a2->b2가 된다면 문제가 발생한다. 이렇게 되면 이 두 프로세스는 Deadlock 상태가 되고, 커널 속 혹은 유저 속에서 죽어버리게 된다.

Dining Philosopher's Problem(식사하는 철학자 문제)

식사하는 철학자 문제는 데드락 상황의 대표적인 예시이다. 네 명의 철학자가 원형 테이블에 둘러앉아 식사를 하는데, 젓가락이 네짝 밖에 없는 경우, 한 명의 철학자는 우선 자기 젓가락을 손에 쥔 후, 식사를 하기 위해 다른 한쪽 젓가락을 들려고 하는데, 이 젓가락은 이미 다른 사람에 의해 점유된 상태이다. 이렇게 되면 네 명의 철학자는 모두 자원을 점유한 상태에서 다른 사람이 젓가락을 내려놓기를 기다리게 된다.

Deadlock의 4가지 필요 조건

위의 예시를 통해, 데드락의 필요 조건에 대해 생각해볼 수 있다.
데드락의 필요 조건은 다음 4가지이다.

1. Mutual Exclusion
   shared resource는 하나의 쓰레드(프로세스)만이 사용할 수 있다.

2. Hold and Wait
   resource 하나를 가진 후, 다른 resource 하나를 더 갖기 위해 기다린다.

3. Non-Preemption (자르지 않음)
   다른 쓰레드가 resource를 점유하고 있는 것을 뺏어오지 않는다.
   (반대로 생각하면, CPU라는 자원은 preemptive하기 때문에 데드락이 걸리지 않는 것이다.)

4. Circular Wait
   Circular하게 서로가 서로의 자원을 얻기 위해 기다려야한다.

Deadlock Handling

데드락을 해결하기 위한 방안은 크게 세가지가 있다.

1. Prevention(예방)
   데드락의 필요 조건 중 하나를 거부해버린다. 그러나 1과 3은 불가능하기 때문에 Hold and Wait 혹은 Circular Wait를 거부하는 식으로 예방한다.

• Hold and Wait Prevention : All or Nothing
  Hold and Wait을 예방하기 위해서는 All or Nothing 전략을 사용한다. 즉, A, B 두 자원이 필요하다면, 이 두 가지에 한번에 락을 걸어 점유하거나, 둘 다 점유하지 않는 것이다.
  그러나 All or Nothing 전략은 당장 사용하지 않는 자원을 차지하고 있는 것이기 때문에 효율이 떨어지고, starvation 문제를 야기할 수 있다.

• Circular Wait Prevention
  Circular Wait을 예방하기 위해서는 resource에 번호를 할당해줄 수 있다. 이렇게 번호를 할당해두면, 번호가 증가하는 방향으로 Lock을 거는 것은 허용하고, 번호가 감소하는 방향으로 Lock을 거는 것은 허용하지 않는 방식의 규칙을 통해 Circular Wait을 예방할 수 있다.
  그러나, 이 방식 역시, 1->3->2의 순서로 resource를 사용해야하는 경우에는 먼저 사용할 3번 리소스보다 2번 리소스를 먼저 할당받아야하기 때문에, 아직 사용하지 않는 자원을 미리 점유해야한다는 사실은 변하지 않는다.

2. Avoidance
   resource 요청이 system을 unsafe하게 만든다면, 이 요청을 거절한다.

3. Detection & Recovery
   이미 데드락 문제가 발생했을 때, 이를 조사하여 참여한 그룹을 찾아 그룹 내 프로세스를 모두 죽여버린다.