[운영체제/OS] 데드락(DeadLock, 교착상태)의 개념, 발생 조건, 처리방법

데드락의 개념

데드락 이란 ?

• 두개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해 다음 처리를 하지 못하는 상태
• '교착 상태'라고도 부르며, 시스템적으로 한정된 자원을 여러곳에서 사용할때 발생
• '외나무 양끝에서 두사람이 서로 비켜주기만 기다리는'것과 같으며 아래의 예시를 참고해보자!

• 프로세스 1과 2가 리소스1과 2를 모두 얻어야 한다고 가정하자
  • 프로세스1이 자원1을 얻은경우 프로세스2는 자원1을 얻을수없고, 프로세스2가 자원2를 가지고 있으므로 프로세스1은 자원2를 얻을 수 없다.
  • 두 프로세스는 무한정 wait 상태에 빠지게되며, 이게바로 DeadLock

데드락의 발생 조건

발생 조건	설명
상호배제(Mutual Exclusion) = Mutex	한번에 하나의 프로세스만이 공유자원 사용가능한 상태
점유하며 대기(Hold and Wait)	프로세스들이 현재의 자원을 점유하며 다른 자원을 요구하는 상태
비선점(Non-Preemption)	각 프로세스에 할당된 자원은 사용 완료될때까지 강제로 해제할 수 없는 상태
순환대기(Circular Wait)	서로 다른 프로세스 간의 자원요구가 연속적으로 반복되는 상태

데드락 처리방법

예방(Prevention)

• 위의 4가지 발생 조건을 제거(막아)하여 미리 예방하는 방법
  • 상호배제 부정, 점유대기 부정, 비선점 부정, 순환대기 부정

회피(Avoidance)

• 데드락 발생조건을 제거하지 않고 적절하게 피하는것
  • 은행원 알고리즘
    • 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데에서 착안
    • 프로세스의 자원 요구시, 자원할당 후에도 안정상태로 남아 있는지 사전에 검사하여 데드락을 회피
    • 안정상태를 유지하면 자원할당, 아니면 다른 프로세스들이 자원 해지까지 대기

탐지(Detection)

• 데드락 발생을 허용하여 자원할당 그래프나 탐지 알고리즘 등을 통해 유발 프로세스를 찾아내 해결

회복(Recovery)

• 교착상태의 프로세스를 종료하거나 할당 자원을 해제함으로서 회복
  • 프로세스 종료
    1. 교착상태의 프로세스를 모두 중지
    2. 교착상태가 제거될때까지 한 프로세스씩 중지
  • 자원 선점. 즉, 데드락이 깨질때까지 프로세스로부터 자원을 계속 선점, 이들을 다른 프로세스에 주는 것
    1. 교착 상태의 프로세스가 점유하는 자원을 선점하여 다른 프로세스에 할당, 해당 프로세스를 일시 정지
    2. 우선순위가 낮은 프로세스를 위주로 프로세스 자원 선점