교착상태(Deadlock)

: 둘 이상의 프로세스(쓰레드)가 서로의 작업을 끝나기만을 기다리는 무한 대기 상태

발생조건

: 4가지 조건 모두 성립시 교착상태 발생 가능(AND 조건)

  1. 상호배제(Mutual Exclusion) : 한번에 한개의 프로세스만 공유자원 사용 가능
  2. 점유와 대기(Hold and Wait) : 이미 자원을 가진 상태로 다른 자원 요구
  3. 비선점(No Preemption) : 할당된 자원이 끝날때까지 뻇을수 없음
  4. 순환대기(Circular Wait) : 순환적으로 다음 프로세스가 차지한 자원 요구
    • P0 -> P1이 가진 자원요구 + P1 -> P2가 가진 자원요구 + Pn -> P0이 가진 자원요구

해결방법

1. 예방(Prevention)

image

  • 발생조건 4가지 중 하나라도 제거해 safe상태로 만들어 데드락이 발생하지 않도록 함
  • 단점 : 병행실행 아예 불가, 기아현상 발생
  1. 상호배제 조건 제거 : 임계 영역 제거
  2. 점유와 대기 조건 제거 : 한번에 모든 필요 자원 점유 및 해제
  3. 비선점 조건 제거 : 선점으로 변경
  4. 순환대기 조건 제거 : 자원 부여에 순서를 부여해 순환이 생기지 않도록 함
    • ex) 모든 프로세스는 1번 자원을 얻어야만 2번 자원을 얻을 수 있음

2. 회피(Avoidance)

  • 발생 가능성이 없는 경우에만 자원 할당해서 데드락이 발생하지 않도록 함
  • 순환대기 조건 제거
  • 프로세스가 평생 동안 사용할 자원을 미리 알려 데드락이 발생할 상황을 회피할 수 있다
    • 최악의 경우를 생각
  1. 자원 할당 그래프 알고리즘
    • 점선을 포함해 cycle이 생기지 않는 경우에만 요청 자원을 할당한다 image
    • R1 -> P1 : R1이 P1에게 할당됨
    • P1 -> R1 : P1이 R1을 요청
    • 점선(Claim edge) : 프로세스가 해당 자원을 미래에 요청할 수 있음을 표시
  2. 은행원 알고리즘 : 운영체제가 안전상태를 유지할 수 있는 요구만 수락, 안전상태의 요구는 안전상태를 만족될 수 있을때 까지 거절

3. 발견(Detection)

  • 데드락 발생을 허용하고 발견시 회복시킴

  • 회복방법

    1. 프로세스 중단
      • 모든 프로세스를 죽이던가 하나씩 죽여 데드락이 풀리는 지 확인해 나감
    2. 자원할당 제거(선점)
      • 피해가 최소화일 프로세스의 자원을 빼았음
      • 기아현상 발생가능 : 자원을 빼았은 프로세스가 그 자원을 다시 할당하면 발생

4. 무시(Ignorance)

  • 예방과 회피기법의 경우 성능에 영향을 끼칠 수 있기에 별다른 조치를 취하지 않음.
  • 대부분의 OS가 채택하고 있음