데드락(Deadlock)

1. 데드락이란

두 개 이상의 스레드가 서로가 보유한 자원을 기다리며 무한히 대기하는 상태

데드락이 발생하기 위해서는 다음 네 가지 조건이 동시에 충족되어야 한다.

 

1) 상호 배제(Mutual Exclusion): 최소한 하나의 자원이 독점적으로 사용되어야 함

2) 점유와 대기(Hold and Wait): 스레드가 최소 하나의 자원을 보유한 채 다른 스레드에 할당된 자원을 추가로 요청해야 함

3) 비선점(No Preemption): 자원을 강제로 빼앗을 수 없어야 함

4) 순환 대기(Circular Wait): 스레드 간에 순환적인 형태로 자원을 기다리는 관계가 형성되어야 함

 

예를 들어, 스레드 t1이 자원 X를 보유하고 자원 Y를 기다리는 동시에, 스레드 t2가 자원 Y를 보유하고 자원 X를 기다리는 상황이 데드락의 전형적인 예시다.

 

ex)

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
using namespace std;
mutex resource_X;
mutex resource_Y;
#define GET_NAME(n) #n

void GetResource(mutex& mtx, const char* name) {
    cout << this_thread::get_id() << " -> " << name << "\n";
    mtx.lock();
    cout << this_thread::get_id() << " -> " << name << " Get!\n";
}

void Thread_1() {
    GetResource(resource_X, GET_NAME(resource_X));
    this_thread::sleep_for(chrono::seconds(1));
    GetResource(resource_Y, GET_NAME(resource_Y));

    // 두 리소스로 작업 수행

    resource_Y.unlock();
    resource_X.unlock();
}

void Thread_2() {
    GetResource(resource_Y, GET_NAME(resource_Y));
    this_thread::sleep_for(chrono::seconds(1));
    GetResource(resource_X, GET_NAME(resource_X));

    // 두 리소스로 작업 수행

    resource_X.unlock();
    resource_Y.unlock();
}

int main() {
    thread t1(Thread_1);
    thread t2(Thread_2);

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

    cout << "작업 종료\n";
}

 

위 예시에서 각 스레드가 하나의 자원을 획득한 후 다음 자원을 얻기 위해 무한정 대기하게 된다.

 

 

2. 데드락 예방 기법

1) 자원 할당 그래프: 시스템의 자원 할당 상태를 그래프로 표현하여 데드락 가능성을 시각화한다.

 

2) 은행원 알고리즘(Banker's Algorithm): 시스템이 안전 상태를 유지하도록 자원을 할당한다. 프로세스가 요청한 자원을 할당한 후에도 안전 상태를 유지할 수 있는 경우에만 자원을 할당한다.

 

3) 예방 기법:

  - 상호 배제 조건 제거: 가능한 경우 자원을 공유 가능하게 만든다.

  - 점유와 대기 조건 제거: 프로세스가 실행되기 전에 모든 필요한 자원을 할당받도록 한다.

  - 비선점 조건 제거: 자원을 빼앗을 수 있도록 한다.

  - 순환 대기 조건 제거: 자원에 전체적인 순서를 부여하고, 순서대로만 자원을 요청하도록 한다.

 

 

3. 데드락 탐지 및 복구

데드락을 완전히 예방하는 것이 어려운 경우, 탐지 및 복구 방법을 사용할 수 있다.

 

1) 주기적 검사:

  - 시스템의 상태를 주기적으로 검사하여 데드락 발생 여부를 확인

  - 자원 할당 그래프나 데드락 탐지 알고리즘을 사용

 

2) 복구 방법:

  - 프로세스 종료: 데드락에 관련된 프로세스 중 하나 이상을 강제 종료

  - 자원 선점: 데드락에 관련된 프로세스로부터 자원을 강제로 회수하여 다른 프로세스에게 할당

 

3) 복구 시 고려사항:

  - 종료할 프로세스 선택: 우선순위, 실행 시간, 남은 작업량 등을 고려

  - 기아(Starvation) 방지: 특정 프로세스가 지속적으로 희생되는 것을 방지

  - 롤백(Rollback): 선점된 프로세스의 상태를 안전한 이전 상태로 되돌린다.