데드락(Dead Lock) 정리

목차

1. 데드락(Dead Lock) 개념
2. 데드락 발생 조건
3. 해결 방법
4. 식사하는 철학자

 

 

---

1. 데드락(Dead Lock) 개념

앞서 멀티 스레드를 사용할 경우 동시성 문제가 발생하기 때문에 이를 해결하기위해 Lock을 사용한다고 했다. 이러한 Lock을 사용하여 동시성 문제를 해결했지만 여전히 문제가 남아있다. 가장 대표적인 문제, 데드락에 대해 알아보자.

데드락(Dead Lock) = 서로 상대의 작업이 끝나기만을 기다리며 멈추게 되는 상태

 

예를 들어, 스레드 A, B가 각각 락 L1, L2를 들고 있으며 A는 L2를 얻으려하고, B는 L1 을 얻으려 한다고 가정하자. 이때, A는 B가 L2들 들고 있기에 더이상 진행할 수 없고, 반대로 B는 A가 L1을 들고있기 때문에 더 이상 진행할 수 없는 상태가 된다. 이러한 상황이 데드락이다.

 

이러한 데드락이 발생하는 이유는 코드의 의존성이 복잡해지고, 캡슐화 때문이다. 쉽게 말하면, 코드가 복잡해짐에 따라 모든 락을  추적하기가 어렵기 때문에 이러한 문제가 발생한다.

 

---

2. 데드락 발생 조건

스레드가 데드락 상태가 되면 더 이상 실행이 되지 않는 치명적인 문제가 발생하기 때문에 이를 해결할 필요가 있다. 데드락을 해결 방법을 공부하기에 앞서 우선 데드락이 어떤 경우에 발생하는지를 확인해보자.

 

아래 4가지 항목에 모두 해당할 때 데드락이 발생하며, 하나라도 해당 되지 않는다면 데드락이 발생하지 않는다.

1. 상호 배제(Mutual Exclusion)
- 스레드가 특정 자원에 대해 독자적인 제어권을 주장한다(eg. 스레드가 락을 획득).

2. 점유 및 대기(Hold-and-Wait)
- 스레드가 자신에게 할당된 자원을 점유한 채로 다른 자원을 대기한다(eg. 락을 획득 후 다른 락을 대기).

3. 비선점(No Preemption)
- 자원(락)을 점유하고 있는 스레드로 부터 자원을 강제적으로 뺏을 수 없다.

4. 순환 대기(Circular wait)
- 락을 가지고 있는 스레드 간에 사이클이 존재한다.

 

 

3. 데드락 해결 방법

데드락이 발생하는 조건을 알아보았으니 이제 해결 방법에 어떤 것들이 있는지 살펴보자. 크게 데드락을 예방하는 방법과 회피하는 방법, 그리고 발견하여 복구하는 방법으로 나뉜다. 

 

데드락 예방

앞서 데드락은 조건 4가지가 모두 성립해야 발생한다. 이 중 하나가 발생할 일을 없게 하여 데드락을 예방할 수 있다.

 

1. 상호 배제(Mutual Exclusion)

상호 배제 자체를 없애는 방법으로, 락이 필요없는 하드웨어 명령어를 사용하는 것이다. 기존에 락을 획득하고 락을 해제한는 대신, 특정 하드웨어 명령어(Compare-And-Swap)를 통해 값에 새로운 값을 갱신하도록 반복적으로 시도한다.

 

 

2. 점유 및 대기(Hold-And-Wait)

자원을 점유하고 있는 상태에서 다른 자원을 대기하는 것이 문제이므로, 특정 스레드에서 모든 자원을 얻게 하고 해제하도록 하여 문제를 해결한다. 즉, 락의 획득 및 해제에 락을 사용하여 원자성을 보장하는 것이다.

lock(prevention);
---
lock(L1);
lock(L2);
---
unlock(prevention);

 

한계

1. 원자적으로 실행할 락들을 정확히 파악해야한다.
2. 실제 필요할 때가 아닌 미리 락을 획득해 놓기 때문에 병행성이 저하된다.

 

 

3. 비 선점(No Preemption)

다른 스레드로 부터 락을 뺏어올 수는 없기에, 자신이 다른 락을 대기해야하는 경우, 기존에 가지고 있던 락을 해제하여 다른 스레드가 사용할 수 있도록 한다.

top:
    lock(L1);
    // L2를 획득하려고 시도, 대기해야하는 상황(-1) 인 경우 기존 L1을 해제한다.
    if (trylock(L2)== -1){
    	unlock(L1); // 기존에 들고 있던 L1 해제
        goto top;
    }

 

한계

1. 무한반복(livelock) 문제 발생 가능 - 서로 하나씩 가지고 양보하는 상황 발생
> 지연시간을 무작위로 조정하여 해결 가능

 

 

4. 순환 대기(Circular Wait)

가장 실용적인 방법은 순환대기가 발생하지 않도록 하는 것이라고 한다. 간단한 방법으로는 락을 획득하는 전체 순서(total ordering)을 조정하는 것이며, 시스템이 복잡한 경우에는 부분 순서(partial ordering)을 통해 부분적으로 순서를 정해준다. 부분 순서를 정해주는 예시를 코드로 살펴보자

if (m1 >m2){
    pthreadd_mutex_lock(m1);
    pthreadd_mutex_lock(m2);   
}
else { 
    pthreadd_mutex_lock(m2);
    pthreadd_mutex_lock(m1);   
}

 

---

데드락 회피

특정 상황에서는 교착 상태를 예방하는 대신 회피하는 것이 유용할 때가 있다. 아래와 같은 상황이라면 회피가 가능하다.

1. 실행 중인 여러 스레드가 어떤 락을 획득하는지 파악

2. 1번 정보를 파탕으로 스레드를 스케줄링

 

스케줄링으로 어떻게 데드락을 회피할 수 있는 예시는 아래와 같다. 

	T1	T2	T3	T4
L1	예	예	아니오	아니오
L2	예	예	예	아니오

 

두 스레드 T1, T2 는 락 L1,L2 를 사용하며, T3와 T4는 하나 또는 락을 사용하지 않는다. 그렇기 때문에 L1과 L2만 동시에 실행하지 않는다면 데드락이 발생하지 않는다. 

 

CPU 1 : T1 > T2

CPU 2 : T3 > T4

 

위의 방식으로 데드락을 해결하는 것 처럼 보이지만 아래와 같은 상황도 발생한다.

	T1	T2	T3	T4
L1	예	예	예	아니오
L2	예	예	예	아니오

 

스레드 T1, T2, T3 가 모두 L1, L2를 사용하기 때문에 세 스레드가 순차적으로 실행된다.

 

CPU 1 : T1 > T2 > T3

CPU 2 : T4

 

이렇게 될 경우 CPU1 에  T1, T2, T3 가 몰리는 것을 볼 수 있다. 스케줄링을 통해 회피하는 것은 CPU 낭비가 발생하기 때문에 보편적으로 사용하는 방식은 아니다.

 

스케줄링을 활용하여 데드락을 회피할 수 있으나, 효율이 떨어진다.
보편적으로 사용하는 방식은 아니다.

 

---

데드락 발견 및 복구

마지막으로 교착 상태 발생을 허용하고, 교착 상태 발견 시 복구하도록 하는 방법이 있다. 많은 데이터 베이스에서 이러한 방식을 활용하여 데드락을 해결한다. 발견 및 복구 과정을 간단하게 정리하면 아래와 같다.

 

1. 교착 상태 발견을 주기적으로 실행하여 그래프를 그리고 사이클이 생겼는지 확인
2. 사이클이 발생하는 경우(교착 상태인 경우) 시스템을 재부팅

 

 

4. 식사하는 철학자(Dining Philosopher)

마지막으로 데드락과 관련된 유명한 문제인 '식사하는 철학자' 를 설명하고 끝내려한다. 

 

아래 사진과 같이 5명의 철학자가 식탁 주위를 원형으로 앉아 있다. 각자의 왼쪽과 오른쪽에는 포크가 하나씩, 총 5개의 포크가 위치해있다. 철학자는 식사하는 때가 있고 생각하는 때가 있다. 생각 중일 때는 포크가 필요 없으며, 식사하는 때에는 두 포크를 양손에 잡고 있어야 식사가 가능하다. 

 

예를 들어, 한 철학자 A가 식사를 하기 위해 양 옆 두 개의 포크를 들었다면, 이웃한 철학자는 A가 포크를 내려 놓을 때 까지 기다려야한다. 이 문제는 모든 철학자가 굶주리지 않고 효율적으로 식사를 할 수 있도록 하기 위해 어떻게 해야하는지 생각해야한다. 

 

기본 동작을 하는 코드는 아래와 같다.

int left(int p) { return p }; //왼쪽 포크를 든다.
int right(int p) { return (p+1)%s }; // 오른쪽 포크를 든다.

while(1){ 
	
    think();
    
    //포크를 모두 들고, 식사를 한다. 이후, 포크를 내려놓는다.
    getforks();
    eat();
    putforks();
}

 

 

가장 기본적으로는 각 철학자가 아래 코드처럼 왼쪽 포크를 모두 들고, 오른쪽 포크를 드는 방식이 있다. 

void getforks(){
    sem_wait(forks[left(p)]);
    sem_wait(forks[right(p)]);
}

void putforks(){
    sem_post(forks[left(p)]);
    sem_post(forks[right(p)]);
}

 

위와 같이 진행하는 경우, 문제가 발생하게 된다. 모든 철학자가 왼쪽의 포크를 드는 경우 서로 오른쪽 포크를 들기 위해 대기를 해야되기 때문에 데드락이 발생한다. 

 

 

 

 

요약

데드락(Dead Lock)
개념 - 스레드가 서로 끝나기만을 기다려서 멈춰있는 상태

발생 조건
1. 상호 배제
2. 점유 및 대기
3. 비선점
4. 순환 대기

해결 방법
1. 데드락 예방 - 주로 락의 순서를 정해서 해결
2. 데드락 회피 - 모든 스레드의 락을 파악하여 스케줄링
3. 데드락 발견 및 복구 - 주기적으로 데드락이 발생하는지 확인. 발생하면 시스템 재부팅

 

 

[참고 링크]

Remzi H. Arpaci-Dusseau,Andrea C. Arpaci-dusseau 공저, 「운영체제 아주 쉬운 세가지 이야기」, 홍릉, 2020

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/DeadLock.md