Deadlock

Deadlock

Deadlock(교착 상태)은 멀티프로세스 시스템에서 발생할 수 있는 상황으로, 각 프로세스가 서로가 점유하고 있는 자원을 요구하며 무한히 대기하는 상태를 말합니다. 이러한 상태에서는 어떤 프로세스도 진행할 수 없으며, 시스템의 작동이 멈추게 됩니다.

Deadlock은 can occur across machines or processes

"Necessary" Conditions for a Deadlock

Deadlock은 일반적으로 다음 네 가지 필요조건이 동시에 성립할 때 발생합니다 -> Deadlock can arise if the following four conditions hold simulaneously

1. Mutual exclusion(상호배제): 자원은 동시에 여러 프로세스에 의해 사용될 수 없으며, 한 번에 하나의 프로세스만이 자원을 사용할 수 있습니다. (only one process at a time can use a resource)
2. Hold and Wait(점유 대기): 프로세스가 적어도 하나의 자원을 점유한 상태에서 다른 자원을 얻기 위해 대기하는 상태입니다. 이때, 다른 프로세스가 이미 필요로 하는 자원을 점유하고 있습니다.
3. No preemption(비선점):다른 프로세스에 의해 점유된 자원을 선점할 수 없습니다. 자원을 사용하고 있는 프로세스가 자발적으로 반납할 때까지 기다려야 합니다.
4. Circular wait(순환 대기): 서로 다른 프로세스들이 자원을 점유하기 위해 순환적으로 대기하는 상태입니다. 즉, 프로세스의 집합이 순환적으로 자원을 대기하고 있어야 합니다.

위 네 가지 조건들은 데드락이 발생할 수 있는 조건들을 제시하는 것이며, 모든 조건이 충족되었을 때 데드락이 발생한다고 볼 수는 있습니다. 하지만 이러한 조건들만 충족되었다고 해서 데드락이 발생한다는 것은 아닙니다. 데드락이 발생하기 위해서는 이러한 조건들이 모두 충족되면서 동시에 특정 상황이 형성되어야 합니다. 그렇기 때문에 이러한 조건들은 단순히 데드락 발생의 충분 조건은 아닙니다.

Methods for Handling Deadlocks

Deadlock Prevention or Avoidance - Ensure that the system will never enter a deadlock state

• Prevention: 필요조건 중 하나를 제거하여 교착 상태 발생을 예방합니다. 예를 들어, 자원의 점유와 대기를 분리하여 상호 배제나 점유 대기 조건을 만들지 않도록 합니다.
• Avoidance: 교착 상태가 발생할 가능성이 있는 자원 요청을 피하기 위한 알고리즘을 사용합니다. 은행원 알고리즘(Banker's Algorithm)이 대표적인 예

Deadlock Detection and Recovery - Allow the system to enter a deadlock state and then recovery

• Detection and Recovery: 교착 상태를 주기적으로 검사하여 발견하고, 발견된 경우 해당 상태를 복구합니다. 이를 위해 리소스 할당 그래프 등의 알고리즘이 사용될 수 있습니다.