[C언어] Deadlock(교착상태) 원인과 해결법

Issues in Multithread app (DeadLock)

멀티스레드 환경에서 나올수 있는 문제들 : 교착상태

 

Dining-Philosophers Problem

철학자-젓가락 문제는 멀티스레딩 환경에서 데드락(Deadlock)을 설명하기 위해 자주 사용되는 고전적인 문제이다.

문제 설명:

1. 철학자는 생각과 식사 중 하나만 할 수 있다.
2. 식사를 하기 위해서는 양쪽 젓가락 두 개를 들어야 한다.
   • 젓가락은 철학자와 이웃 사이에서 공유된다.
   • 한 철학자가 들고 있는 젓가락은 다른 철학자가 사용할 수 없다.
3. 식사를 마치면 철학자는 두 젓가락을 내려놓는다.

---

Deadlock

데드락이란 서로 다른 스레드(또는 프로세스)가 자원을 점유한 상태에서 서로의 자원을 기다리며 무한정 대기하는 상황을 말한다.

Deadlock이 발생하는 이유:

1. Hold and Wait: 하나의 젓가락을 점유한 상태에서 다른 젓가락을 기다린다.
2. No Preemption: 젓가락을 이미 점유한 철학자로부터 빼앗을 수 없다.
3. Circularity: 모든 철학자가 서로의 젓가락을 기다리는 순환 대기가 발생한다.
4. Mutual Exclusion: 각 젓가락은 동시에 하나의 철학자만 사용할 수 있다.

---

데드락 문제를 C 코드로 제시:

typedef struct
{
    pthread_mutex_t *lock[MAXTHREADS];
    int phil_count;
}Sticks;

void pickup(Phil_struct *ps){
    Sticks *pp;
    int phil_count;
    pp = (Sticks *)ps->v;
    phil_count = ps->phil_count;
    /* phil     0 1 2 3 4 */
    /* sticks  0 1 2 3 4  */
    pthread_mutex_lock(pp->lock[ps->id]);
    /* lock left stick */
    pthread_mutex_lock(pp->lock[(ps->id + 1) % ps->phil_count]);
    /* lock right stick */
}

void putdown(Phil_struct *ps){
    Sticks *pp;
    int phil_count;
    pp = (Sticks *)ps->v;
    phil_count = ps->phil_count;
    pthread_mutex_unlock(pp->lock[ps->id]);
    /* unlock left stick */
    pthread_mutex_unlock(pp->lock[(ps->id + 1) % ps->phil_count]);
    /* unlock right stick */
}

---

Deadlock 해결 방법

데드락을 예방하거나 회피하는 여러 가지 전략이 있다.

1. n-1명만 식사:
   식탁에 n명이 아니라 n-1명만 앉도록 하여 반드시 하나의 철학자가 젓가락을 사용할 수 있게 한다.
2. 동시에 들기:
   두 젓가락을 동시에 들도록 설정하여 Hold and Wait 조건을 제거한다.
3. 순서를 변경:
   특정 철학자만 먼저 들도록 순서를 정해 Circularity를 방지한다.
4. 비대칭 규칙:
   홀수 철학자는 왼쪽 젓가락부터, 짝수 철학자는 오른쪽 젓가락부터 드는 규칙을 적용한다.

4번 비대칭 규칙 코드 구현:

void pickup(Phil_struct *ps){
    Sticks *pp;
    int phil_count;
    pp = (Sticks *)ps->v;
    phil_count = ps->phil_count;
    /* phil     0 1 2 3 4 */
    /* sticks  0 1 2 3 4  */
    if (ps->id %2 == 1)
    {
        pthread_mutex_lock(pp->lock[ps->id]);
        /* lock left stick */
        pthread_mutex_lock(pp->lock[(ps->id + 1) % ps->phil_count]);
        /* lock right stick */
    }
    else
    {
        pthread_mutex_lock(pp->lock[(ps->id + 1) % ps->phil_count]);
        /* lock right stick */
        pthread_mutex_lock(pp->lock[ps->id]);
        /* lock left stick */
    }
}

---

Deadlock Free 상황에서 남아있는 문제

데드락을 해결해도 여전히 Starvation(기아 상태)와 Fairness(공정성) 문제가 남을 수 있다.

1. Starvation:
   특정 철학자가 지속적으로 젓가락을 사용하지 못하는 상태.
2. Fairness:
   모든 철학자가 자원을 균등하게 사용할 수 있도록 보장하는 문제.

---

해결 방법: Condition Variables 사용

Condition Variables를 활용하면 각 철학자를 대기열에 추가하여 공정성을 높일 수 있다. 이는 리눅스의 스케줄링 정책과 유사하다.

Queued Locking을 적용한 기본 아이디어:

• 젓가락을 사용할 수 없는 철학자는 대기열에 들어간다.
• 스케줄러가 대기열에서 가장 오래 기다린 철학자를 선택하여 자원을 배분한다.

이 방식으로 기아 상태와 공정성 문제를 해결할 수 있다.