Deadlock

Deadlock이란?

• 여러개의 프로세스가 서로가 서로를 waiting하는데 signal을 해줄 프로세스가 없어서 멈추는 경우

  위의 상황에서 P0가 S를 wait하고, P1는 Q를 wait하므로 DeadLock발생

Deadlock Characterization

Mutual exclusion

wait signal을 쓰는 것은 Mutex가 당연히 전재되어야 함

Hold and wait

하나를 쥐고 다른 것을 기다리는 상황. 위 P0과 P1처럼 각각 S와 Q를 쥐었는데 다시 반납을 하지 않음

No preemption

하나를 쥐고 있기만 하고 내려놓지 않음. 스케줄러의 비선점적, 선점적 처럼 프로세스가 도중에 끝나지않아서 계속 쥐고 있음.

Circular wait

Dining Philosopher의 상황 처럼. 서로가 돌아가며 꼬리에 꼬리를 물며 대기하는 상황

• 위의 4가지가 모두 충족되는 상황에 Deadlock이 발생
• 하나라도 제거하면 Deadlock해결

Handling Deadlocks

• Deadlock prevention
  OS가 관리하면 오버헤드가 크고 알고리즘이 복잡해서 개발자가 잘 막아야 함

• Deadlock avoidance
  공유자원의 상태를 보고 (lock인지 unlock인지 확인) 일일히 Deadlock을 피하며 관리

• Deadlock detection and recovery
  OS가 Deadlock이 발생하는지 모니터링을 하다가 발견하면 복구

• Deadlock ignorance
  OS가 그냥 무시함. 그냥 걸리면 걸리는 거지~

Dining Pilosopher 해결

• 기존은 wait(chopstick[L]), wait(chopstick[R])로 Deadlock발생
• 세마포어를 젓가락의 사용 유무 상태가 아닌, 철학자의 상태로 접근을 달리해서 해결
• 중간 단계인 왼쪽을 hold하고 오른쪽을 봤는데 없으면 hold한 왼쪽을 다시 내려놓는 알고리즘도 존재