교착 상태
교착 상태
교착 상태(Deadlock)란, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 아무것도 완료되지 못하는 상태이다. 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제이고 이를 해결하는 일반적인 방법은 아직 없는 상태이다.
교착 상태의 조건
1971년, E. G. 코프만 교수는 교착상태가 일어나기 위해 4가지 필요 조건을 충족시켜야 한다고 보였다.
- 상호배제(Mutual exclusion) : 한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
- 점유 대기(Hold and wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
- 비선점(Non-preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
- 순환(환형)대기(Circular wait) : 공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 한다.
위의 4가지 조건 중에서 하나라도 만족하지 않으면 교착 상태는 발생하지 않는다. 순환대기 조건은 점유대기 조건과 비선점 조건이 만족되어야 성립하므로, 서로 완전히 독립적이지는 않다.
교착 상태 처리 기법
교착 상태를 처리하는 방법에는 3가지가 존재한다.
- 교착상태를 예방하거나 회피하는 프로토콜을 사용하는 것
- 교착상태가 되도록 허용한 다음 이를 회복시키는 방법
- 시스템의 교착상태를 무시하고 발생하지 않는 것처럼 꾸미는 방법
세번째 방법의 경우 현대의 운영체제들이 대부분 사용하는 방식이고 교착상태를 처리하는 것은 응용 개발자의 몫이다. 간혹 교착상태가 없으면서 실행이 동결된 상태가 있을 수 있는데, 이를 수작업으로 한번 복구하는 것이 효율적이므로 "수작업 복구 방법"을 반드시 가지고 있어야 한다.
교착 상태 예방 기법(Prevention)
교착 상태 예방 기법은 위의 4가지 조건 중에서 하나를 제거함으로서 수행된다. 자원낭비가 가장 심한 기법이다.
- 상호 배제 부정 : 한번에 여러개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
- 점유 및 대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.
- 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
- 순환 대기 부정 : 자원을 선형 순서로 분류하여 고유 번호를 할당하고 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 한다.
교착 상태 회피 기법(Avoidance)
교착 상태 회피 기법은 교착상태가 발생할 가능성을 배제하지 않고, 교착상태가 발생하면 적절히 피해나가는 방법이다. 주로 은행원 알고리즘이 사용된다.
은행원 알고리즘
- 은행원 알고리즘은 다익스트라가 제안한 기법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래한 기법이다.
- 각 프로세스에게 자원을 할당하여 교착상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전상태, 교착상태가 발생할 수 있는 상태를 불안전 상태라고 한다.
- 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다.
- 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.
은행원 알고리즘을 예시를 들어 설명드리겠습니다.
프로세스 P0, P1, P2가 있고 운영체제는 12개의 자기 테이프 드라이브를 공유자원으로 가지고 있다. 프로세스 P0을 수행하는데 10개의 테이프 드라이브 사용이 필요하고, P1은 최대 4개, P2는 9개가 요구된다.
특정시간 t0 시각에 P0가 5개의 테이프 드라이브를 사용하고 있고, P1은 2개, P2는 2개를 사용하고 있다고 가정하자. 현재 운형체제에는 총 3개의 테이프가 사용가능한 자원으로 남아있다.
이 상태가 안전상태이다.
하지만 t1이라는 시각에 p2 프로세스가 자원을 하나 더 요청한다고 해보자. P0는 5개, P1은 2개, P2는 3개를 가지고 있겠고 사용가능한 테이프는 2개가 된다. P0는 5개가 필요하기 때문에 불가능하다. P1이 다 사용되고 반환되어도 4개의 테이프가 사용가능하기 때문에 P0나 P2를 해결해줄 수 없다. P2도 마찬가지이다. 결국 다 해결해줄 수가 없으니 불완전상태가 된다.
이처럼 P2가 자원을 요청하였을 때 P2를 주지않고 P1이 먼저 끝나도록 했으면 해결이 가능했을 것이다. 이렇게 문제를 회피하는 것이 회피 기법이다.
은행원 알고리즘은 엄청나게 복잡하고 오버헤드가 크다. 또한 프로그램에 적용하기 어렵기 때문에 현재 채택하고 있는 방식은 아니다.
교착 상태 발견 기법(Detection)
교착 상태 발견 기법은 시스템에 교착 상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견함을 의미한다.
- 교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다.
교착 상태 회복 기법(Recovery)
교착 상태 회복 기법은 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미한다.
프로세스 종료
교착상태에 있는 프로세스를 종료하는 것으로, 교착 상태에 있는 모든 프로세스를 종료하는 방법과 교착상태에 있는 프로세스들을 하나씩 종료해가며 교착상태를 해결하는 방법이 있다.
모든 프로세스를 종료하게 되면 상당히 큰 비용이 발생한다. 그 이유는 진행된 많은 작업들을 다시 해야하기 때문이다.
두번째 방법은 각 프로세스가 중지될 때마다 교착 상태 여부를 확인해야 하기 때문에 상당한 오버헤드를 유발한다.
자원 선점
교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시정지시키는 방법이다. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점한다.
::: tip
자원 선점시 고려사항
- 희생자 선택(Selection of a victim) : 최소의 피해를 줄 수 있는 프로세스를 선택한다.
- 롤백(Rollback) : 자원이 부족한 상태이므로 대부분 일시 중지시키고 다시 시작하는 방법을 사용한다.
- 기아 현상 문제(Starvation) : 한 프로세스가 계속하여 자원 선점 대상이 되지 못하도록 고려해야 한다.
:::
나올 수 있는 면접 질문
교착 상태란 무엇인가?
교착 상태에는 어떤 기법들이 있으며 각각 어떤 역할을 하는가?
교착 상태를 어떻게 해결할 것인가?
참고 url
기여자
HelloNaks
📦