교착상태의 원리

• 교착상태 (dead lock)
  • 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태
  • 교착상태는 시스템 자원에 대한 경쟁 도중 발생할 수도 있고 프로세스 간 통신 도중에 발생할 수도 있음
  • 집합 내의 한 프로세스가 특정 사건의 발생을 기다리며 대기하고 있고, 이 사건이 집합 내의 다른 블록된 프로세스에 의해 발생될 수 있을 때 이 프로세스의 집합은 교착상태가 됨
  • 교착상태는 기다리던 사건이 결코 발생하지 않기에 영구적이다.
  • 교착상태는 두 개 이상의 프로세스들이 서로 충돌되는 자원 요구를 할 때 발생한다.
• 교착상태 해결 방안

접근 방법	자원 할당 정책	구체적인 기법	장점	단점
예방	보수적 (자원 할당이 가능하더라도 조건에 따라 할당하지 않는다)	모든 자원을 한꺼번에 요구	순간적으로 많은 일을 하는 프로세스에게 적합 선점이 불필요	효율이 나쁨 프로세스 시작을 지연시킬 가능성이 있음 프로세스는 사용할 모든 자원을 미리 알고 있어야 함
		선점 가능	자원 상태의 저장과 복구가 간단한 자원에는 적용하기 쉬움	선점 부하
		자원 할당 순서	컴파일 시접에 강제할 수 있음 시스템의 설계 시점에 문제를 해결했기 때문에 동적 부하가 없음	동적인 자원 할당이 불가
회피	예방과 발견의 중간 정도	교착 상태가 발생하지 않는 안전한 경로를 최소한 하나는 유지	선점이 불필요	운영체제는 자원에 대한 미래 요구량을 미리 알고 있어야 함 오랜 기간 지연 발생의 가능성 있음
발견	적극적 (자원 할당이 가능하면 즉시 할당)	주기적으로 교착 상태 발생 여부 파악	프로세스 시작을 지연시키지 않음 온라인 처리 가능	선점에 의한 손실 발생

• 교착 상태의 조건
  • 상호배제 (mutual exclusion)
    • 한 순간에 한 프로세스만이 한 자원을 사용할 수 있다. 
    • 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수 없다.
  • 점유대기 (hold and wait)
    • 자원을 기다리는 프로세스가 이미 자원을 할당하고 있다.
  • 비선점 (no preemption)
    • 프로세스에 의해 점유된 자원을 다른 프로세스가 강제로 빼앗을 수 없다.
  • 환형 대기 (circular wait)
    • 프로세스들간에 닫힌 연결 (closed chain) 이 존재한다. 즉, 자원 할당 그래프에서 환형이 만들어 진다.
  • 조건 1~3은 교착상태가 발생할 수 있는 필요조건
  • 조건 4까지 만족되면 교착상태가 발생할 수 있는 필요충분 조건
  • 조건 4는 조건 1~3의 결과에 의해 발생
    
    • 조건 1~3에 의해 해결할 수 없는 환형 대기 상태가 발생
    • 교착 상태의 정의가 해결할 수 없는 환형 대기 상태
    • 환형 대기가 해결될 수 없는 이유는 조건 1~3이 지켜지기 때문
    • 결국 위 4가지 조건이 교착상태가 발생할 수 있는 필요충분조건