교착 상태(Deadlock)에 대해 설명하세요
Keyword
점유, 무한히 대기, 상호 배제, 점유와 대기, 비선점, 원형 대기
Script
Deadlock은 쉽게 말해서, 둘 이상의 프로세스가 서로가 점유하고 있는 자원을 기다리면서 무한히 대기하는 상황을 말합니다. Deadlock은 상호 배제(mutual exclusion), 점유와 대기(hold and wait), 비선점(nonpreemptive), 원형 대기(circular wait)로 이 4가지 조건이 모두 만족할 경우에 발생할 수 있습니다.
Additional
식사하는 철학자 문제(dining philosophers problem)
만약 식사를 반드시 2개의 포크로만 먹을 수 있다고 가정했을 때, 각 철학자들이 집어들 수 있는 포크가 있을 때 집어들게 되면(왼쪽 or 오른쪽 포크를 모든 철학자가 각각 집어든다), 그 누구도 식사를 할 수가 없게 된다.
deadlock의 가장 쉬운 예시로, 모두가 자원을 점유하고 있어서 서로 자원을 기다리며 무한히 작업이 중단되며 진행이 멈춰버리는 것을 쉽게 예시로 설명하는 문제이다.
자원 할당 그래프(resource-allocation graph)
자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지 표현하는 그래프이다.
위 그림처럼, 프로세스는 원으로, 자원은 사각형으로 표현된다. 그리고 자원 사각형 안의 점들은 사용할 수 있는 자원의 개수를 의미한다.
그리고 프로세스가 어떤 자원을 할당 받아 사용 중일때, 자원에서 프로세스로 화살표를 표시한다. 그리고 어떤 프로세스가 자원을 기다리고 있다면, 프로세스에서 자원쪽으로 화살표를 표시한다.
식사하는 철학자 문제를 자원 할당 그래프로 나타내면 다음과 같다.
이렇게 원의 형태를 띄고 있으면, Deadlock이 발생한다.
Deadlock condition
상호 배제(mutual exclusion)
만약 하나의 자원을 동시에 여러개의 프로세스가 사용할 수 있다면, Deadlock은 발생할 수 없다. 동기화 문제를 해결하기 위한 상호 배제가 Deadlock의 요인이 될 수 있다.
점유와 대기(hold and wait)
프로세스가 특정 자원을 할당 받은 상태에서 다른 자원을 할당받기를 기다리는 경우에, 점유와 대기 상태가 발생할 수 있다.
비선점(nonpreemptive)
만약 프로세스가 강제로 자원을 뺏을 수 있다면, Deadlock은 발생할 수 없다. 하지만, 비선점 자원으로 이루어져 있어, 해당 작업이 끝나야만 이용할 수 있는 방식이라면 Deadlock이 발생할 수 있다.
원형 대기(circular wait)
자원 할당 그래프가 원형으로 그려지게 되면, 즉, 서로가 자원을 hold하고서 서로의 자원을 wait 하는 경우가 발생하게 되면, Deadlock이 발생할 수 있다.
Reference
