[OS]데드락의 발생과 처리 방법

1. Deadlock이란?

프로세스들이 서로가 가진 자원을 기다리며 block된 상태이다.

1.1 자원이란?

• 하드웨어, 소프트웨어를 포함하는 개념
• I/O, CPU, Memory, Semaphore 등

2. Deadlock 발생 조건

4가지 조건 모두 만족할 때 deadlock 발생한다. 다시 말해 한 가지 조건을 해제하여 deadlock을 방지한다.

1. Mutual Exclusion, 상호 배제

• 하나의 프로세스가 자원을 독점적으로 사용

2. No Preemption, 선점 불가

• 자원을 강제로 빼앗을 수 없음

3. Hold and Wait

• 일을 수행하기 전까지 현재 가진 자원을 내어 놓지 않음

4. Circular Wait, 환형 대기

• 자원을 기다리는 프로세스간에 사이클이 형성됨

3. Deadlock 처리 방법

데드락을 방지하는 방법(prevention, avoidance) / 데드락을 해결하는 방법

3.1 Deadlock Prevention

데드락 발생 조건 중 하나가 만족되지 않도록 한다.

• Mutual Exclusion - 공유할 수 있는 자원이라면 데드락을 고려할 필요가 없었을 것이다.
• Hold and Wait - 프로세스가 자원을 요청할 때 다른 자원을 갖고 있으면 안된다.
  • 방법 1. 프로세스 시작 시 필요한 자원을 한 번에 할당받도록 한다. - (필요 없는 자원도 갖게 되므로 비효율적이다.)
  • 방법 2. 자원이 필요한 경우 보유한 자원을 모두 놓고 재요청
• No Preemption - 항상 해결할 수 있는 것은 아니다. 빼앗을 수 없는 자원들도 존재한다.
  • CPU 혹은 memory는 빼앗을 수 있다. (context를 저장하고 다시 불러와서 이용할 수 있다.) → 데드락이 발생하지 않는다.
• Circular Wait - 모든 자원에 할당 순서를 정해 순서대로만 자원을 할당한다.
  • 순서가 3인 자원을 갖고 있는 프로세스가 순서가 1인 자원이 필요하다면 우선 자원을 놓아야 한다.

throughput이 감소하고 starvation 문제가 발생한다.

3.2 Deadlock Avoidance

프로세스가 평생 사용할 자원을 미리 알고 있을 때, 현재 요청하는 자원을 할당하면 데드락이 발생할 지 안할 지 확인한 후 안전한 상태에서만(safe state) 자원을 할당한다.

Banker’s Algorithm

프로세스가 최대 자원 이하의 자원을 요청한 경우에도 가용 자원으로 최대 자원을 모두 충족하지 못한다면 자원을 할당하지 않는다.

• 추가 자원(최대 자원 - 할당된 자원)과 가용 자원만으로 계산을 한다.
• 가용 자원으로 프로세스 A가 요구한 자원을 모두 처리가 가능한 경우 프로세스 A는 자원을 할당받을 것이다.
• 프로세스 A는 일을 모두 끝내면 기존에 가지고 있던 자원까지도 모두 반납할 것이다.
• 늘어난 가용 자원으로 다른 프로세스 B,C,D 들에게 자원을 할당한다.

3.3 Deadlock Detection and Recovery

Detection

여유 자원이 있다면 할당한다. 데드락이 발생하면 감지할 수 있어야 한다.

• 자원을 요청하지 않는 프로세스는 자원을 반납할 것이라고 예측한다.
• 반납할 자원과 가용 자원을 합친 경우의 자원으로 다른 요청들을 처리할 수 있는 지 확인한다.
• 반복하며 safe sequence를 찾는다.

은행원 알고리즘과 다르게 미래는 보지 않고 현재만 고려한다.

Recovery

• Process termination
  • 데드락과 관련된 모든 process를 종료
  • 데드락과 관련된 process를 하나씩 종료
• Resource Preemption
  • 비용을 최소화할 수 있는 희생양에게서 자원을 빼앗음
  • starvation 문제 발생 - 동일한 프로세스가 계속해서 희생양이 되는 경우 / 희생양이 다시 자원을 가져가는 경우

3.4 Deadlock Ignorance

현대의 대부분 OS가 채택하는 방법이다.

데드락은 사실 매우 드물게 발생한다. 데드락에 대한 조치가 더욱 큰 오버헤드가 발생할 수 있다.

만약 시스템에 데드락이 발생하는 경우 사용자가 직접 프로세스를 죽인다.