10 Deadlock (교착 상태)

교착 상태는 다중 프로세스나 스레드 환경에서 발생할 수 있는 심각한 문제 중 하나입니다. 이를 설명하기 위해 식사하는 철학자 문제를 살펴보면 교착 상태의 본질을 더 잘 이해할 수 있습니다.

 

 식사하는 철학자 문제(The Dining Philosophers Problem)와 교착 상태 

인간의 철학자 5명이 탁자에 앉아 철학적인 문제를 고민하고 있습니다. 그들은 테이블을 둘러싸고 있으며, 각 철학자의 앞에는 젓가락이 있습니다. 철학자들은 식사를 위해 젓가락을 사용해야 하지만, 젓가락은 두 개를 동시에 집을 수 없기 때문에 옆에 있는 철학자와 공유해야 합니다.

 

철학자들은 다음과 같은 행동을 합니다:
배고플 때: 양쪽 젓가락을 동시에 집으려고 시도합니다.
젓가락을 얻었을 때: 식사를 합니다.
식사를 마쳤을 때: 젓가락을 내려놓고 철학적인 문제에 집중합니다.

이상적으로는 모든 철학자가 식사를 원활히 할 수 있어야 하지만, 이러한 행동 방식으로는 교착 상태가 발생할 수 있습니다. 모든 철학자가 동시에 양쪽 젓가락을 집으려고 할 때, 자원(젓가락)을 공유하는데 있어 불일치가 발생하여 모든 철학자가 기다리며 아무것도 하지 못하는 상황이 발생할 수 있습니다.

 

이 문제는 컴퓨터 시스템에서 발생하는 교착 상태와 유사한 상황을 설명하는데 사용됩니다. 프로세스나 스레드가 서로가 필요한 자원을 소유한 채로 서로를 기다리는 상황이 발생하여 더 이상 진행되지 못하는 것을 '교착 상태'라고 합니다.

 

 

---

교착 상태가 발생하는 4가지 조건 

교착 상태가 발생하기 위해서는 다음 네 가지 조건, 즉 "교착 상태의 필요조건"이 동시에 충족되어야 합니다. 이러한 조건들은 다음과 같습니다:

1. 상호 배제 (Mutual Exclusion): 최소한 하나의 자원이 배타적으로 사용되어야 합니다. 즉, 한 번에 여러 프로세스나 스레드가 해당 자원에 접근하지 못하도록 막아야 합니다.
2. 보유 및 대기 (Hold and Wait): 프로세스나 스레드가 적어도 하나의 자원을 보유하고 있으면서 다른 자원을 기다리고 있어야 합니다. 즉, 어떤 프로세스가 자원을 얻기 위해 대기하면서 다른 자원을 이미 보유하고 있어야 합니다.
3. 비선점 (No Preemption): 다른 프로세스나 스레드가 이미 보유한 자원을 강제로 빼앗을 수 없어야 합니다. 즉, 자원은 해당 프로세스나 스레드가 스스로 반납하기 전까지 그 사용이 보장되어야 합니다.
4. 순환 대기 (Circular Wait): 프로세스나 스레드 간에 자원을 대기하는 순환 구조가 형성되어야 합니다. 예를 들어, 프로세스 A가 프로세스 B가 보유한 자원을, B가 C가 보유한 자원을, C가 A가 보유한 자원을 대기하고 있어야 합니다.

이러한 네 가지 조건이 동시에 충족될 때 교착 상태가 발생할 수 있습니다. 교착 상태를 방지하기 위해서는 이러한 조건 중 하나 이상을 제거해야 합니다. 예를 들어, 교착 상태를 방지하려면 보유 및 대기, 비선점, 순환 대기 중 하나의 조건을 깨뜨려야 합니다. 이를 위해 다양한 데드락 방지 알고리즘이나 교착 상태 해결 전략들이 존재합니다.

 

---

 

교착 상태 해결 방법 

교착 상태를 해결하기 위해서는 다양한 방법과 전략들이 있습니다. 이러한 방법들은 교착 상태의 발생 조건 중 하나 이상을 제거하거나 교착 상태가 발생했을 때 효과적으로 해결할 수 있는 방법들입니다. 몇 가지 일반적인 해결 전략은 다음과 같습니다:

1) 예방(Prevention): 교착 상태의 발생 조건 중 하나를 미리 방지하는 방법입니다.

• 상호 배제 예방: 자원 공유 시 상호 배제를 유연하게 처리하도록 설계합니다.
• 보유 및 대기 예방: 프로세스가 모든 필요한 자원을 한 번에 요청하도록 강제합니다.
• 비선점 예방: 자원 할당 중에 다른 프로세스에게 자원을 뺏을 수 있도록 합니다.
• 순환 대기 예방: 자원에 고유한 번호를 부여하고, 순환 대기를 방지하도록 순서를 정합니다.

2) 감지 및 회복(Detection and Recovery): 교착 상태가 발생했을 때 이를 감지하고, 회복하는 방법입니다.

• 교착 상태 감지: 주기적으로 시스템 상태를 모니터링하여 교착 상태를 감지합니다.
• 교착 상태 회복: 감지된 교착 상태에 대한 회복 전략을 동작시켜 교착 상태를 해결합니다. 이는 프로세스를 중지하거나, 자원을 회수하거나, 프로세스를 종료하는 등의 방법을 포함할 수 있습니다.

3) 데드락 예방 알고리즘 사용: 데드락 예방 알고리즘을 사용하여 교착 상태를 방지합니다. 예를 들어, 은행원 알고리즘(Banker's Algorithm)이나 Wait-Die, Wound-Wait 등의 트랜잭션 관리 기법을 사용할 수 있습니다.

 

4) 자원 할당 그래프 이용: 자원 할당 그래프를 통해 교착 상태를 검출하고, 검출된 경우에 대한 회피나 회복 전략을 수행합니다.

 

5) 프로세스 종료 및 자원 회수: 교착 상태가 감지되면 해당 상태에서 원인이 되는 프로세스를 종료하고 해당 프로세스가 보유한 자원을 회수하여 교착 상태를 해결합니다.

 

6) 교착 상태 회피(Deadlock Avoidance)는 교착 상태가 발생하지 않도록 시스템이 자원을 할당하는 전략입니다. 이 방법은 자원을 안전하게 할당하여 시스템이 항상 안전 상태로 유지되도록 하는 것이 목표입니다.

 

ex) 은행원 알고리즘(Banker's Algorithm

• 가용 자원(Available Resources): 시스템이 현재 사용 가능한 자원의 양을 나타냅니다.
• 최대 요청(Maximum Request): 각 프로세스는 필요로 하는 자원의 최대량을 미리 선언합니다.
• 할당된 자원(Allocated Resources): 각 프로세스는 현재까지 할당받은 자원의 양을 나타냅니다.
• Need Matrix: 각 프로세스가 더 필요로 하는 자원의 양을 나타내는 행렬입니다.

은행원 알고리즘은 다음 규칙을 따릅니다:

1. 프로세스가 자원을 요청할 때, 시스템은 해당 자원을 할당했을 때 안전 상태를 유지하는지 미리 확인합니다.
2. 안전 상태를 유지할 수 있다면 자원을 할당하고, 그렇지 않으면 프로세스는 대기 상태로 전환됩니다.
3. 자원 반납이 있을 때마다 시스템은 현재의 자원 할당 상태에 대해 다시 안전 상태인지를 검사합니다.

 

교착 상태의 해결은 특정 상황과 시스템 요구에 따라 다양한 방법을 조합하여 사용해야 합니다. 특히 예방이나 회복과 같은 방법들은 시스템의 특성에 따라 적절한 방법을 선택하는 것이 중요합니다.

 

 

---

Dining Philosophers Problem
A classic synchronization problem in computer science where philosophers sitting around a dining table must use shared chopsticks to eat, illustrating challenges in resource sharing and deadlock avoidance.

Deadlock Definition
Deadlock is a state in a computer system where processes or threads are unable to proceed due to circular waiting for resources, stemming from conditions like mutual exclusion, hold and wait, no preemption, and circular wait. It can impact system performance and requires careful design to prevent or resolve.