[CS] 데드락(Deadlock)

아안뇨오엉하세요엉ㅇ

저번에 뮤텍스와 세마포어에 대해서 글을 적어봤는데요?

동기화기법은 신이고 무적같지만 사실 허점이 하나 있습니다.

바로 프로세스나 스레드간 교착 상태에 빠질 수 있다는 점인데요...

이 현상을 바로 데드락이라고 합니다!

데드락이 뭔지 같이 알아봅시당

---

데드락(Deadlock)이 뭘까?

데드락은 둘 이상의 프로세스나 스레드가 각각 서로 점유하고 있는 자원을 기다릴 때 무한 대기에 빠지는 상황을 일컫습니다.

아래 사진은 데드락이 생기는 과정을 사진으로 간단하게 나타낸 것입니다.

 

자원 A를 가진 스레드1이 있고,

자원 B를 가진 스레드2가 있을때,

스레드1: 야 B내놔ㅋ

스레드2: 싫어 A내놔ㅋ

이러고 있는거임ㅋㅋ

---

데드락이 생기는 조건?

데드락은 다음 네 가지 조건이 모두 만족될 때 발생합니다:

1. 상호 배제(Mutual Exclusion):
   • 자원은 동시에 하나의 프로세스만 사용할 수 있습니다.
2. 점유와 대기(Hold and Wait):
   • 프로세스는 자신이 이미 점유하고 있는 자원을 유지하면서, 추가로 다른 자원을 요청하며 대기합니다.
   • 예: 스레드1은 자원 A를 점유한 상태에서 자원 B를 요청
3. 비선점(No Preemption):
   • 점유한 자원은 해당 프로세스가 작업을 완료하기 전까지 강제로 빼았지 못합니다.
   • 예: 프로세스가 사용하는 자원은 작업 완료 전까지 다른 프로세스가 가져갈 수 없음.
4. 순환 대기(Circular Wait):
   • 프로세스들이 순환적으로 자원을 요청하며 서로 대기합니다.
   • 예: A → B → C → A 순환 구조로 자원을 기다리는 상황.

 

세상에 이런 상황이 있다고?

놀랍게도 이런 상황이 나올 수 있고, 생각보다 간단하게 나옵니다.

아래는 데드락이 발생할 수 있는 예제코드입니다.

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mutex1, mutex2;

void Worker1() 
{
    mutex1.lock();
    std::this_thread::sleep_for(std::chrono::milliseconds(100));  // 다른 스레드가 실행될 여유를 줌
    mutex2.lock();

    mutex1.unlock();
    mutex2.unlock();
}

void Worker2() 
{
    mutex2.lock();
    std::this_thread::sleep_for(std::chrono::milliseconds(100));  // 다른 스레드가 실행될 여유를 줌
    mutex1.lock();

    mutex2.unlock();
    mutex1.unlock();
}

int main() {
    std::thread t1(Worker1);
    std::thread t2(Worker2);

    t1.join();
    t2.join();

    return 0;
}

이렇게 되면 worker1은 mutex1을 통해 임계영역에 접근을 했지만, mutex2를 통해 또 다른 자원에 접근하고 싶지만, 이미 worker2가 mutex2를 통해 해당 자원을 점유한 상태입니다.
(따라서 초딩같이 싸우고 있다는거임ㅋㅋ)

---

데드락을 해결하려면?

데드락을 해결하려면 무슨 방법이 있을까요?

---

1) 예방(Prevention):

데드락 발생 조건 중 하나를 제거하여 문제를 사전에 방지.

• 상호 배제 제거: 자원을 공유 가능하게 설계 (단, 현실적으로 어려움).
• 점유와 대기 제거: 모든 자원을 한 번에 요청하도록 설계.
• 비선점 제거: 자원을 강제로 해제하거나 다른 프로세스로 넘김.
• 순환 대기 제거: 자원 요청 순서를 정해 순환 대기를 방지.

---

2) 회피(Avoidance):

자원 할당 시 데드락 발생 가능성을 분석해 안전한 상태(Safe State)만 유지.

• 은행원 알고리즘(Banker's Algorithm):
  • 은행원이 고객에게 대출을 승인하기 전에 시스템 상태를 분석하는 방식에서 이름이 유래했습니다. 이를 프로세스와 자원 할당 문제에 대입하면 다음과 같은 원리로 작동합니다.
    • 안전 상태(Safe State): 모든 프로세스가 작업을 완료하고 자원을 해제할 수 있는 상태입니다. 즉 모든 요청이 처리 가능한 상태.
    • 불안전 상태(Unsafe State): 특정 자원 요청이 승인을 받으면 다른 프로세스가 자원을 기다리면서 데드락이 발생할 가능성이 있는 상태입니다.

---

3) 탐지(Detection):

데드락이 발생했는지 확인하고, 이를 해결하기 위한 전략을 사용하는 방법입니다. 탐지는 데드락을 허용한 상태에서 주기적으로 시스템의 자원 상태를 검사하여 데드락을 확인합니다. 탐지 후에는 데드락을 해결하기 위한 적절한 조치를 취합니다.

• 시스템 상태 검사
  
  • 자원 할당 상태와 프로세스의 요청 상태를 바탕으로 Deadlock Detection Algorithm을 실행합니다. 데드락의 주요 조건인 사이클(Cycle) 또는 교착 상태(Wait-for Graph)를 탐지합니다. 
  • 입력 데이터를 통해 현재 상태를 보내줍니다. 
    
    • Available (가용 자원): 현재 시스템의 남아 있는 자원 수.
    • Allocation (현재 할당): 각 프로세스에 이미 할당된 자원의 양.
    • Request (현재 요청): 각 프로세스가 추가로 요청한 자원의 양.

---

4) 회복(Recovery):

데드락 탐지 이후 이미 발생한 데드락을 해결하는 과정입니다. 시스템이 데드락 상태임을 확인한 후, 프로세스를 종료하거나 자원을 회수하여 데드락을 해소하는 방법입니다.

• 데드락 회복 전략
  
  • 프로세스 강제 종료(Termination) : 데드락 상태를 해소하기 위해 프로세스를 강제로 종료하여 자원을 해제하는 방법입니다.
  • 자원 강제 회수 (Resource Preemption) : 데드락 상태를 해소하기 위해 프로세스를 강제로 종료하여 자원을 해제하는 방법입니다.
  • 데드락에 얽히지 않은 프로세스 우선 실행 : 데드락 상태의 프로세스는 중단하거나 대기시키고, 데드락에 얽히지 않은 다른 프로세스부터 실행합니다.

---

데드락을 해결하는 방법을 알아봤지만, 결국엔 알고리즘과 상태검사로 인해 성능 오버헤드가 발생할 수 있습니다.

가장 좋은 방법은 데드락이 발생하지 않도록 예방하는 것이 중요하다고 생각합니다!

무엇이든 예방이 중요하다...

---

현대 OS는 데드락을 어떻게 처리할까?

현대의 운영체제, 즉 UNIX를 포함한 대부분의 OS는 일반적으로 데드락 탐지나 회복을 직접적으로 처리하지 않는 경우가 많습니다. 대신, OS는 데드락이 발생할 가능성을 낮추거나 개발자나 시스템 관리자가 이 문제를 처리하도록 설계하는 데 중점을 둡니다.

---

현대 OS가 데드락을 처리하지 않는 이유는?

(1) 성능 오버헤드

• 데드락을 탐지하거나 예방하는 알고리즘은 복잡한 연산을 포함하며, 이를 실시간으로 처리하려면 시스템 리소스에 큰 부하가 걸릴 수 있습니다.
• 특히 멀티스레드 환경이나 분산 시스템에서는 데드락 상태를 정확히 탐지하는 것이 어렵고, 탐지 비용이 높습니다.

(2) 일반화된 해결책 부족

• 데드락은 특정 상황에서 발생하므로, 모든 프로그램에 대해 범용적으로 작동하는 데드락 처리 방법을 제공하기 어렵습니다.
• 데드락을 해결하기 위한 프로세스 종료나 자원 회수는 애플리케이션의 상태를 망가뜨릴 수 있어, OS가 임의로 조치하는 것은 적절하지 않을 수 있습니다.

---

현대 OS는 데드락 처리를 시스템 수준에서 자동화하지 않고, 다음과 같은 방식을 통해 간접적으로 문제를 다룹니다:

1. 개발자가 예방적 설계를 할 수 있도록 동기화 메커니즘과 도구 제공.
2. 시스템 로그와 디버깅 툴로 데드락 원인 파악 지원.
3. 사용자에게 프로세스 종료와 같은 수동적 해결책 제공.

운영체제는 성능과 안정성을 위해 데드락 관련 문제를 개발자의 책임으로 위임하는 방향으로 설계되었습니다.

따라서 우리 개발자는 데드락이 발생하지 않도록 신중히 코드를 짤 필요가 있습니다...ㅇㅅㅇ