교착상태(DeadLock)

• 둘 이상의 프로세스가 자원을 점유하고 있지만 서로의 자원을 필요로하여 무기한 대기에 빠진 상태를 의미한다.
• 발생 조건
  • 상호 배제(Mutual Exclusion)
    • 한 자원은 한 번에 한 프로세스만 사용할 수 있어야한다.
  • 점유 대기(Hold and Wait)
    • 최소 하나의 자원을 점유하고 있으면서, 다른 프로세스의 자원이 필요로 하여 대기하고 있는 프로세스가 존재해야 한다.
  • 비선점(No Preemption)
    • 프로세스가 점유하고 있는 자원은 사용이 끝날때 까지 강제로 뺏을수 없다.
  • 순환 대기(Circular Wait)
    • 프로세스의 집합이 순환 형태로 서로의 자원을 필요로 하고 있어야한다.
• 교착상태 예방(Prevention)
  • 발생 조건 중 한가지를 부정하여 방지 할 수 있다.
    • 상호 배제 부정
      • 여러 프로세스가 자원을 공유하여 사용
    • 점유 대기 부정
      • 프로세스 실행 전 모든 자원을 요구하고 할당
    • 비선점 부정
      • 다른 자원이 필요로 할때 현재 할당 받은 자원을 반납하고 해당 자원 대기
    • 순환대기 부정
      • 자원에 고유번호를 할당하여, 번호 순서대로 자원을 요구
• 교착 상태 회피(Avoidance)
  
  • 안정 상태(safe state) 프로세스가 요청한 자원을 데드락을 발생시키지 않으면서 모두 할당 해줄 수 있는 상태 
  • 불안정 상태(unsafe state) 자원을 할당해 줘도 교착상태가 발생할 수 있는 상태를 의미
  • 은행원 알고리즘
    
    • 안정 상태로 계속 남을 수 있도록 프로세스를 찾아서 자원을 할당해주는 방식
    • 자원의 종류와 수가 일정해야하며 항상 불안정 상태는 방지해야 하므로 자원이 효율적이지 못한다.
    • 또한 자원 요청이 있을 때마다 확인해야하므로 비효율적이다.
• 교착 상태 탐지 & 회복(Detection & Recovery)
  • 교착 상태를 허용하도록 한 후 교착 상태 탐지 후 회복 시키는 방법
  • 탐지 기법
    • 자원 할당 그래프를 통해 교착 상태 탐지
    • 자원 요청 시 마다 탐지 알고리즘이 수행 되어 비효율적
  • 회복 기법
    • 프로세스 종료 방법
      
      • 교착 상태의 모든 프로세스 종료
        • 연산 중이던 결과를 폐기하는 단점이 존재
      • 교착 상태가 해제 될 때가지 하나씩 종료
        • 매번 탐지 알고리즘을 수행해야해서 부담이 큼
    • 자원 선점 방법
      • 교착 상태의 프로세스의 자원을 선점해 다른 프로세스에게 할당
      • 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스를 위주로 자원 선점