- 다중 프로그래밍 시스템에서 아무리 기다려도 결코 일어나지 않을 사건을 기다리고 있는 하나 또는 그 이상의 프로세스들이 있는 상태
- 자원이 다수의 사용자 프로세스에 의해 공유되고 이들 각 프로세스가 자신에게 할당된 자원에 대해 독점적인 통제권을 가지고 있을 때 발생
- 둘 이상의 서로 다른 프로세스가 자신이 요구한 자원을 할당받아 점유하고 있으면서 상호간에 상대방 프로세스에 할당되어 있는 자원을 요구하는 경우에 발생
- 상호배제, 점유와 대기, 비선점, 환형대기의 조건을 모두 만족했을 경우 교착상태가 발생
4가지 필요조건
상호 배제(Mutual Exclusion) – 한 번에 하나의 프로세스만이 자원을 사용
점유와 대기(Hold and Wait) – 최소한 하나의 자원을 점유하는 프로세스가 존재하면서 이 프로세스가 다른 프로세스에 할당된 자원을 추가로 점유하기 위해 대기
비선점(Non-preemption) – 자원은 그 자원을 점유하고 있는 프로세스로부터 도중에 벗어나지 못한다.
환형 대기(Circular Wait) – 프로세스와 자원들이 원형을 이루며 각 프로세스가 자신에게 할당된 자원을 점유하면서 상대방 프로세스의 자원을 상호 요청
해결방법
예방(Prevention)
- 사전에 교착상태의 가능성을 없애는 것
-자원 낭비가 가장 심한 기법
상호 배제 부정 – 한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 함
점유 및 대기 부정 - 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 함
비선점 부정 - 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 함
환형 대기 부정 : 자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 함
회피(Avoidance)
-발생 가능성을 인정하고 발생하려고 할 때 이를 피해 가는 방법
은행원 알고리즘
- 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법
- 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 한다.
- 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장
안정(Safe 상태)
- 운영체제가 현재 모든 사용자에게 그들의 작업이 일정 기간 내에 끝나도록 할 수 있는 상태
불안정(Unsafe) 상태
- 운영체제가 현재 모든 사용자에게 그들의 모든 작업을 일정 기간 내에 끝낼 수 없는 상태
- 즉, 교착상태가 발생할 수 있는 상태
1. 15원이 더 필요한 첫번째 고객에게 15원을 빌려주고 첫번째 고객이 일을 해결하고 갚을 때까지 기다렸다가 다른 고객에게 돈을 빌려주는 방법
2. 두 번째 고객에게 남은 25원을 빌려주고 두번째 고객이 일을 해결하고 갚을 때까지 기다리는 방법이 있다.
3. 세 번째 고객이 먼저 빌리는 경우는 불가능! 은행은 25원이 남아있는데, 세번째 고객은 35원이 더 필요하기 때문이다.
돈을 빌려줄 수 있고, 다시 돈을 돌려 받을 수 있는 상태를 안전상태라고 한다.
고객1 - 고객2 - 고객3
고객2 - 고객1 - 고객3
고객2 - 고객3 - 고객1
이런 순서대로 모든 고객에게 돈을 빌려줄 수 있고 이를 안전 순서열이 존재한다고 한다.
안전한 수행 순서
p4 -> p2 -> p5 -> p3 -> p1
은행원 알고리즘의 단점
- 할당할 수 있는 자원의 수가 일정해야 한다.
- 사용자 수가 일정해야 한다.
- 항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮다.
- 최대 자원 요구량을 미리 알아야 한다.
- 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.
- 오버헤드가 너무 크고 실제 돌아가는 프로그램에 적용하기 어려워 채택하고 있는 방식은 아님.
발견(Detection)
- 일단 교착상태가 발생하도록 허용
- 발생하면 일어났는지를 판단하고 관련된 프로세스와 자원을 조사하여 결정
- 자원 할당 그래프 등을 사용하여 사이클을 탐지함으로써 교착상태를 검출
회복(Recovery)
- 교착상태를 제거하여 이후에는 교착상태에 빠지지 않게 하는 것
프로세스 종료
교착상태에 있는 프로세스를 종료하는 것으로, 교착상태에 있는 모든 프로세스를 종료하는 방법과 교착상태에 있는 프로세스들을 하나씩 종료해가며 교착상태를 해결하는 방법이 있습니다.
자원선점
교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지시키는 방법입니다. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점합니다.
