Deadlock

Deadlock

• 프로세스들은 자원들을 필요로 한다.
  • 자원?
    • CPU, 메모리, 파일, 프린터
• 어떤 자원은 갖고 있으나 다른 자원은 갖지 못할 때 대기해야 한다.
• 다른 프로세스 역시 다른 자원을 가지려고 대기할 때 교착 상태가 발생할 수 있다.
• 교착상태 필요 조건
  1. Mutual exclustion : 상호배타
  2. Hold and wait : 보유 및 대기
  3. No Preemption : 비선점
  4. Circular wait : 환형 대기
• Deadlock은 흔하게 발생하지는 않는다

Deadlock 처리

1. 교착상태 방지 : Deadlock Prevention
2. 교착상태 회피 : Deadlock Avoidance
3. 교착상태 검출 및 복구 : Deadlock Detection & Recovery
4. 교착상태 무시 : Don't Car

Deadlock Prevention

• Deadlock이 발생하기 위해서는 총 4가지의 조건들이 충족해야 한다.

  1. Mutual exclusion
  2. Hold and wait
  3. No Preemption
  4. Circular wait

• 따라서 교착 상태를 방지 하기 위해서는, 위 조건 4개중 하나라도 만족하지 않도록 한다.

• 조건 1. Mutual exclusion

  • 자원을 공유하지 못하기에 상호배타가 발생한다. 그러면 자원을 공유하게 하면 Mutual exclusion이 발생하지 않을 수 있다.
    • 자원을 공유한다.... 현실적으로 불가능 하다.
      • Why? -> 프린터 자원을 A에서 사용하고 있는데 B에서 사용을 동시에 한다면 각기 다른 내용이 하나의 A4 종이에 출력 될 것이다.

• 조건 2. Hold and Wait

  • 자원A를 가지고 있는데 자원B도 필요로 하여, 자원 A를 가지면서 자원B를 기다릴 때, Hold & wait가 발생한다. 그렇다면 방법으로 해결할 수 있다.
    • B를 가질 수 없다면 A를 포기하고, 깔끔하게 둘다 동시에 사용가능할때 A와 B를 동시에 사용하자!
      • 단점 : 자원 활용률 저하 -> Starvation 발생
  • 정리 : 자원을 가지고 있으면서 다른 자원을 기다리지 않게 하자!

• 조건 3. No Preemption

  • 비선점에서 선점 방식으로 변경하면 해결할 수 있을것이다
    • 그러나 대부분에 경우에 안될것 같다 -> 예시) 프린터

• 조건 4. Circular wait

  • 자원에 번호를 부여하여, 오름차순으로 자원을 요청하면 해결할 수 있을 것이다.
  • 단점 : 자원 활용률 저하 발생

Deadlock Avoidance

• 자원 요청에 대한 잘못된 승인을 하지 않는것
• 잘못된 승인이란 무엇인가?
  • A, B, C 프로세스에 자원을 할당하는데 B는 실행 완료할 수 있지만, A와 C는 서로 미리 선점하고 있는 자원이 많아서 완료할 수 없는 것
• 운영체제는 자원을 할당할 때 불안전 할당이 되지 않도록 해야한다.
  • 불안전 할당 -> 교착상태
• 정리 : Avoidance 부분은 은행(OS)이 대출해줄때(자원 할당), 대출금(Process 실행 종료 후 반환되는 자원)을 받아서 다시 다른 사용자(Process)가 사용할 수 있는지 없는지를 판단하는것으로 생각하면 쉽다

Deadlock Detection & Recovery

• Deadlock이 일어나도록 허용
• 그러면 Deadlock이 발생할 수 있지 않나?
  • 주기적 검사를 통해 교착상태 발생 시 복구(Recovery)
• Detection : 검출
  • 주기적으로 교착상태 발생하는 지를 확인하는 검사를 하기 위해 overhead가 크다
• Recovery
  • 주기적으로 현재 상태를 기억하고 있어야 한다. 현재 상태를 기억하고 있어야지 교착상태 발생 전으로 돌아갈 수 있다.
  • 복구 방법
    • 프로세스 일부 강제 종료
    • 자원 선점하여 일부 프로세스에게 할당

Deadlock Don't Care

• 교착상태는 실제로 잘 일어나지 않는다.
• 위에서 알아보았던 교착상태의 4가지 필요 조건을 모두 만족하더라도 일어나지 않을 수 있다.
• 그러니까 그냥 교착상태를 무시