데드락

정의

프로세스들이 서로가 가진 자원을 기다리며 무한정 기다리고 있는 상태

 

발생 조건

다음의 4가지 조건 모두 만족해야한다.

Mutual exclusin(상호배제)

매 순간 하나의 프로세스만이 자원을 사용할 수 있다.

No preemption(비선점)

프로세스는 자원을 스스로 내려놓을 수 있지만 강제로 빼앗기지 않는다.

Hold and wait(점유 대기)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다.

Circular wait(순환 대기)

자원을 기다리는 프로세스간에 사이클이 형성되어야 한다.

 

해결 방법

예방

교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)

• 상호배제 부정
  • 동시에 여러 프로세스가 자원을 접근할 수 있게 한다. 다만 공유해서는 안되는 자원의 경우에는 불가능.
• 점유대기 부정
  • 다른 프로세스가 자원을 선점할 수 있게 허용한다.
  • 다만 선점당할 때 모든 작업이 날아가므로 상태를 저장하고 다시 복구할 수 있는 cpu나 memory같은 자원에서 주로 사용
• 비선점 부정
  • 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
• 순환대기 부정
  • 자원에 고유번호 할당 후 순서대로 자원을 할당 받을 수 있게 한다.

 

회피

자원 요청에 대한 부가적인 정보를 이용해서 교착상태의 가능성이 없는 경우에만 자원을 할당한다.

프로세스가 시작될 때 필요로 하는 각 자원별 최대 사용량을 미리 선언해서, 현재의 가용자원만 가지고 최대 자원 요청을 처리할 수 있는 프로세스의 요청만 받아들인다.

• 자원을 할당받는 프로세스가 한개라면 자원 할당 그래프를 이용하여 회피
• 자원을 할당받는 프로세스가 여러 개라면 banker's 알고리즘을 사용하여 회피

 

탐지와 회복

교착상태를 발생하도록 내버려두다가, 만약 교착상태를 발견하면 그것을 회복시키는 방법이다.

• 자원을 할당받는 프로세스가 한개라면
  • 자원 할당 그래프의 변형인 wait-for 그래프를 이용해서 교착상태 사이클이 존재하는지 주기적으로 조사
• 자원을 할당받는 프로세스가 여러 개라면
  • banker's 알고리즘과 유사한 방법을 사용하여 사이클을 발견한다.

 

회복하는 방법은 2가지가 있다.

• 프로세스 종료
  • 교착상태에 걸린 모든 프로세스를 종료시킨다.
  • 또는 교착상태에 걸린 프로세스를 하나씩 죽이면서 교착상태가 해결되는지 확인한다.
• 자원 선점
  • 종료시켰을 때 비용이 최소화되는 프로세스를 선정한다. 그리고 그 프로세스를 safe한 상태로 롤백하여 restart시킨다.
  • 이 때 계속 동일한 프로세스가 선정되는 경우 기아 상태에 빠질 수 있으므로 롤백 횟수도 같이 고려해서 선정해야 한다.

 

무시

교착상태가 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는다.

교착상태는 매우 드물게 발생하므로 교착상태에 대한 조치가 교착상태에 걸린 것보다 훨씬 큰 오버헤드일 수 있다.

따라서 만약 시스템에 교착상태가 발생한 경우, 시스템이 비정상적으로 동작하는 것을 사람이 느낀 후 직접 프로세스를 종료하는 방법 등으로 대처한다.

현대의 대부분의 범용 OS가 채택하는 방식이다.