Deadlock에 대해 설명해보세요.
Deadlock(교착상태)
-
교착상태란 상호 배제에 의해 나타나는 문제로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 상태를 말한다.
- 위의 그림과 같이 프로세스 1은 자원 A가 필요하고 프로세스 2는 자원 B가 필요하지만, 자원 A는 프로세스 2에 의해 잠겨 있고 자원 B는 프로세스 1에 의해 잠겨있는 상태이다. 결국 어느 한 프로세스를 강제적으로 종료하지 않으면 어떠한 작업도 수행할 수 없다.
교착상태 예시(식사하는 철학자 문제)
- 교착상태를 쉽게 이해시켜주는 대표적인 예시이다.
- 철학자는 식사를 하기 위해 2개의 포크를 사용해야 한다. 이 때, 모든 철학자가 자신의 왼쪽 포크를 하나씩 집게 되면, 자신의 오른쪽 포크를 사용 가능할 때까지 대기해야 한다. 하지만 모든 철학자가 같은 상황이므로 누구도 식사를 할 수 없게 된다. 이러한 상황을 교착상태라고 하며, 철학자들에게 기아현상이 발생한다.
교착상태 발생 조건
-
교착상태는 다음 네 가지 조건이 모두 만족할 때 발생한다.
-
Mutual Exclusion(상호 배제)
: 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있다. -
Hold and Wait(점유와 대기)
: 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재한다. -
Non-preemption(비선점)
: 다른 프로세스에 할당된 자원은 강제로 빼앗을 수 없다. -
Circular Wait(순환 대기)
: 공유 자원을 사용하기 위해 대기하는 프로세스의 집합이 원형의 순환 형태로 구성되어 있다.
-
교착상태 해결 방법
-
교착상태의 해결 방법은 크게 세 가지로 분류할 수 있다.
-
Deadlock Prevention(교착상태 예방)
: 애초에 교착상태가 발생하지 않도록 발생 조건 중 하나를 부정하여 예방한다. 하지만 시스템의 처리량이나 효율성이 떨어지는 단점이 있다.-
상호 배제 부정
: 여러 프로세스가 동시에 공유 자원을 사용할 수 있도록 한다. 하지만 추후 동기화 관련 문제가 발생할 수 있다. -
점유 대기 부정
: 프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나, 자원이 점유되지 않은 상태에서만 자원 요청을 받도록 한다. 하지만 이는 자원이 오랫동안 할당되고 사용되지 않으면서 낭비가 된다. -
비선점 부정
: 모든 자원에 대하여 선점을 허용한다. -
순환 대기 부정
: 자원을 순환 형태로 대기하지 않도록 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.
-
-
Deadlock Avoidance(교착상태 회피)
: 교착상태가 발생할 가능성을 배제하지 않고 안전한 상태(Safe State)에서만 자원 요청을 허용한다. 안전 상태란 시스템이 교착상태를 일으키지 않으면서 모든 프로세스들이 완료될 수 있는 상태를 말하며, 반대 개념인 불안전 상태는 교착 상태가 발생할 수 있는 상태를 의미한다. 이러한 특징을 살린 대표적인 알고리즘으로 은행원 알고리즘과 자원할당 그래프 알고리즘이 존재한다. -
Deadlock Detection and Recovery(교착상태 탐지 및 회복)
: 교착상태를 예방하거나 회피하지 않으면 교착상태가 발생할 수 있으므로 탐지하고, 회복하는 방법이다.- 탐지 기법
: Allocation, Request, Available 등으로 시스템에 교착상태가 발생했는지 여부를 탐지한다. - 회복 기법
: 모든 프로세스를 중단시키거나, 프로세스를 하나씩 중단할 때마다 교착상태를 탐지하면서 회복하는 프로세스 중단 방법과, 프로세스에 할당된 자원을 선점해서 교착상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해주는 자원 선점 방법이 있다.
- 탐지 기법
-
자원 할당 그래프 알고리즘
- 교착상태를 눈으로 확인할 수 있는 좋은 방법이다.
-
P, R, 화살표는 각각 프로세스, 자원, 요청을 의미한다. 그래프를 그려서 사이클의 유무에 따라 교착상태를 확인할 수 있다
-
그래프에 사이클이 없으면 교착상태가 아니지만, 자원의 수에 따라
-
자원의 개수가 1개인 경우 교착상태가 있지만,
-
그 이상으로 존재할 경우 상황에 따라 교착상태가 있을수도 있고, 없을수도 있다.
-
