둘 이상의 프로세스 혹은 스레드(작업)들이 서로 상대방이 사용중인 자원을 쓰기 위해 대기하고 있는 상황
*병목현상과 혼동하지만 원인이 다르다.
병목 현상은 여러 구성 요소가 동시에 실행될 때, 가장 느린 쪽의 속도에 맞추기 위해 전체 시스템이 느려지는 상황.
*기아상태와도 혼동할 수있다.
교착상태 = 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태,
기아 상태 = 프로세스가 원하는 자원을 계속 할당 받지 못하는 상태이다.
즉, 교착 상태는 여러 프로세스가 동일한 자원 점유를 원할 때 발생하고
기아 상태는 여러 프로세스가 자원을 점유하기 위해 경쟁 할 때 특정 프로세스가 영원히 자원 할당을 받지 못하는 것.
다음 4가지의 조건을 모두 만족해야 교착상태가 발생한다.
→ 즉, 한 가지 조건이라도 만족하지 못하게 한다면 교착상태를 해결할 수 있다.
1. 상호 배제(mutual exclusion)
매 순간 하나의 자원은 하나의 작업이 점유한다. 즉, 하나의 자원을 얻었다면 독점적으로 사용하며,
다른 작업이 해당 자원을 요청하면 자원이 방출될 때까지 지연(대기)한다.
2. 점유 대기(Hold-and-wait)
자원을 가진 작업이 하나의 자원을 가진 채 다른 자원을 기다릴 때, 현재 보유한 자원을 놓지 않고 계속 기다린다.
3. 비선점 (no preemption)
자원을 선점할 수 없다. 즉, 자원이 강제적으로 빼앗기지 않고, 작업이 끝난 이후 자발적으로만 반납(방출)된다.
4. 순환 대기(circular wait)
자원을 기다리는 작업들 간에 사이클이 형성되어야 한다. (1→2→3→1 )
- 문제 무시
- 예방
- 회피
- 교착 상태 허용 후 복구
대부분의 운영체제는 1번 방법, 교착상태를 처리하는 프로그램을 작성하는 것은 응용 개발자의 몫이며,
통상 2,3번 접근법을 사용한다. DB와 같은 일부 시스템은허용 후 복구작업을 수행한다.
*현대 OS가 Deadlock을 처리하지 않고 무시하는 이유는?
- 빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해 훨씬 더 많은 오버헤드를 들이는것이 비효율적이라고 판단
- 현대 시스템의 복잡성으로 인해 교착 상태를 완전히 방지하는 것은 불가능
- 만약 시스템에서 교착상채가 발생한 경우 시스템이 비정상적으로 작동한것을 사람이 느낀후 직접 process를 죽이는 방법으로 대처
데드락을 발생시키는 4가지 조건 중 적어도 하나가 성립하지 않도록 보장하는 방법
- 상호 배제
자원을 작업들이 동시에 사용할 수 있게 하는 방법. 이를 사용하면 동시에 접근이 가능하여 교착상태가 일어나지 않는다.
불가능하다. 어떤 자원은 근본적으로 공유가 불가능(mutex 락, 프린터 등)하고, 동기화에 문제가 생길 수 있다.
- 점유 대기
작업이 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장. 즉, 하나의 프로토콜이 필요한 모든 자원을 요청하고 할당해야 한다.
자원 이용률이 낮아진다. 요청만 해놓고 안쓰는 자원이 많아진다. (기아상태 발생 가능성)
- 비선점
이미 다른 작업이 가지고 있는 자원을 선점한다. 모든 자원을 얻을 수 있을 때, 그 작업이 다시 시작된다.
CPU레지스터나 DB트랜젝션처럼, 그 상태가 쉽게 저장되고 복원될 수 있는 자원에 종종 적용된다.
가장 흔하게 교착상태가 발생하는 mutex 락이나 세마포 같은 자원에는 일반적으로 적용할 수 없다.
- 순환대기
모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.
데드락을 예방하는 방법은 자원의 낭비가 극심하기 때문에 좋은 방법은 아니다.