[OS]데드락이란?

[데드락이란?]

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

 

[데드락 발생 4대요소]

데드락 발생 4가지의 조건을 모두 만족해야 한다.

 

Multi exclusion(상호배제)

매순간 하나의 프로세스만이 자원을 사용할 수 있다.

No preemption(비선점)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.

Hold end wait(보유대기)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 갖고 있는다.

Circuler wait(순환대기)

자원을 기다리는 프로세스간에 사이클이 형성되어야한다.

 

[데드락 해결 방법 - 미리 예방하는 방법]

교착상태 예방(Deadlock Prevention)

교착상태 발생 요인 4가지 조건이 발생하지 않도록 하는 것이다.

• 상호배제 예방 : 공유해서는 안되는 자원의 경우 상호배제 조건은 반드시 성립해야한다. 👉 배제할 수 있는 조건X
• 비선점 예방 : 모든 필요한 자원을 얻을 수 있을 때 그 포르세스를 다시 시작한다
                        어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다.
                        👉 아사현상을 일으켜 비선점 조건을 무력화 하기는 어렵다.
• 점유와 대기 : 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야한다.
  • 프로세스 시작 시 모든 필요한 자원을 모두 놓고 다시 요청한다. 👉 비효율적 이다.
  • 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청한다.
    (단점)
    프로세스가 자신이 사용하는 모든 자원을 알기가 어렵다.
    자원의 활용성이 떨어진다.
• 원형 대기 예방 : 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.
  (단점)
  이용률 저하, 기아현상 문제, 처리량 감소가 있다.
  e.g.) 순서가 3인 자원 R1을 보유중인 프로세스가 순서가 1인 자원 R1을 할당 받기 위해서는 우선 R1을 release해야 한다.
  e.g.) 마우스를 할당 받은 상태에서 프린터를 할당받을 수 있으나 프린터를 할당 받은 상태에서 이전 순번인 마우스를 할당 받을 수 없다.

교착상태 회피(Deadlock Avoidance)

자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당한다.

가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는지 각 자원별 최대 사용량을 미리 선언하도록 한다.

• 적용 알고리즘
  • Single instance 👉 Resource Allocation Graph Algorithm
  • Multiple instance 👉 Bnaker's Algorithm

 

[데드락 발생 이후 대응 방법]

교착상태 검증과 회복(Deadlock Detection and Recovery)

교착 상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링 하면서 교착 상태가 발생하는지 살펴보는 방식으로 만약 교착 상태가 발생한다면 교착 상태 회복 단계가 진행 된다.

• 교착상태 검출 : 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식이다.
• 검출방법
  • 타임아웃 이용 👉 일정 시간동안 작업이 진행되지 않은 프로세스를 교착상태가 발생한 것으로 간주하여 처리한다.
  • 자원할당 그래프 이용 👉 자원할당 그래프 내에 사이클이 있으면 교착상태이다.
• 회복
  • Process termination : 교착상태와 연관된 모든 프로세스를 죽인다.
  • Resource Preemption : 비용을 최소화 할 victim의 선점
                                          safe state로 rollback하여 process를 재시작

데드락 무시(Deadlock Ignorance)

데드락이 일어나지 않는다고 생각하고 아무런 조치를 취하지 않는다.
사용자가 직접 교착상태를 강제 종료로 해결할거라는 전제를 갖고 무시한다.