교착상태(DeadLock)

1) 교착상태의 개념

• 둘 이상의 프로세스가 실현 불가능한 상태를 무한정 기다리고 있는 상태를 말한다.
• 둘 이상의 프로세스가 하나의 자원을 서로 요구하는 상태를 말한다.

2) 교착상태가 발생할 수 있는 필요 충분 조건

(1) 상호 배제(Mutual exclusion) : 한 리소스는 한 번에 한 프로세스만이 사용할 수 있다.

(2) 점유와 대기(Hold and wait) : 어떤 프로세스가 하나 이상의 리소스를 점유하고 있으면서 다른 프로세스가 가지고 있는 리소스를 기다린다.

(3) 비선점(No preemption) : 프로세스가 작업을 마친 후 리소스를 자발적으로 반환할 때까지 기다린다.

(4) 환형 대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가진다.

3) 교착상태 해결 방안

(1) 예방(Prevention)

• 상호배제 부정 : 공유 자원에 동시 접근이 허용되므로 컴퓨터 시스템의 신뢰성 보장 불가능
• 비선점 부정 : 언제든 사용 중인 공유자원을 중단하거나 빼앗을 수 있는 가장 현실적인 예방 방식
• 점유와 대기 부정 : 자원을 일부 점유한 프로세스가 추가 자원의 요구를 실패하는 경우 기존 자원 반납 후 다시 요청
• 환형 대기 부정 : 자신이 가진 자원의 앞, 뒤 순서의 자원 요청을 금지시킴

(2) 회피(Avoidance)

• 안정적 상태를 유지할 수 있는 프로세스의 요청만 받아들이는 방식으로 교착상태가 발생할 가능성을 회피한다.
• 대표적으로 은행원 알고리즘(Banker’s Algorithm)이 있다.
  • 안전 상태와 불안정 상태로 구분
  • 자원의 양과 사용자의 수가 일정해야 함
  • 모든 요구를 유한한 시간 안에 수용해야 함
  • 대화식 프로그램에는 적용 불가능

(3) 발견(Detection)

• 컴퓨터의 중단 원인이 교착상태인지 다른 이유인지 파악하는 방법이다.
• 공유 자원과 프로세스의 관계를 인접 행렬로 표현하여 파악한다.

(4) 회복(Recovery)

• 교착상태가 발생한 프로세스 중 희생양(중단할 프로세스)을 정하여 자원을 빼앗는 방식이다.
• 희생양을 정하는 기준은 다음과 같다.
  • 우선순위가 낮은 프로세스
  • 진행률이 적은 프로세스
  • 자원을 적게 사용하고 있는 프로세스
  • 기아(무한 대기) 상태 등으로 수행이 불가능한 프로세스