[OSTEP] 32. Common Concurrency Problems

1.1 원자성 위반 (Atomicity Violation)#

원자성 위반은 원자적으로 실행되어야 할 코드 구간이 중간 끼어들기(interleaving)로 깨지는 현상입니다. 전형적인 형태는 체크 후 사용(check-then-use) 패턴입니다.

문제 코드(MySQL 예시):

1
// Thread 1
2
if (thd->proc_info) {
3
    // 이 사이에 다른 스레드가 끼어들 수 있음
4
    fputs(thd->proc_info, ...);
5
}
6

7
// Thread 2
8
thd->proc_info = NULL;

Thread 1이 proc_info != NULL을 확인한 직후 Thread 2가 proc_info = NULL로 바꾸면, Thread 1은 fputs()에서 NULL 포인터 역참조로 크래시가 날 수 있습니다.

해결책은 간단한 편입니다. 검사와 사용을 하나의 임계 영역으로 묶어 직렬화(serialize)하면 됩니다.

1
pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;
2

3
// Thread 1
4
pthread_mutex_lock(&proc_info_lock);
5
if (thd->proc_info) {
6
    fputs(thd->proc_info, ...);
7
}
8
pthread_mutex_unlock(&proc_info_lock);
9

10
// Thread 2
11
pthread_mutex_lock(&proc_info_lock);
12
thd->proc_info = NULL;
13
pthread_mutex_unlock(&proc_info_lock);

원자성 위반을 보는 실전 관점은 이렇습니다.

• 단일 변수라도 검사 → 사용이 분리되어 있으면, 그 사이가 취약 지점이 됩니다.
• 해결은 보통 락 추가이지만, 해당 변수를 접근하는 모든 경로가 같은 락 규약을 따라야 합니다.

1.2 순서 위반 (Order Violation)#

순서 위반은 두 스레드 사이에 기대한 실행 순서가 강제되지 않아 발생합니다. 예를 들어 Thread 2가 Thread 1의 초기화를 전제하는데, 스케줄링에 따라 그 전제가 깨질 수 있습니다.

문제 코드:

1
// Thread 1
2
void init() {
3
    mThread = PR_CreateThread(mMain, ...);
4
}
5

6
// Thread 2
7
void mMain(...) {
8
    mState = mThread->State; // mThread가 아직 NULL이면 크래시
9
}

해결책은 순서(초기화 완료)를 동기화로 강제하는 것입니다. 조건 변수(또는 세마포어)가 정석입니다.

1
pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
2
pthread_cond_t  mtCond = PTHREAD_COND_INITIALIZER;
3
int mtInit = 0;
4

5
// Thread 1
6
void init() {
7
    mThread = PR_CreateThread(mMain, ...);
8

9
    pthread_mutex_lock(&mtLock);
10
    mtInit = 1;
11
    pthread_cond_signal(&mtCond);
12
    pthread_mutex_unlock(&mtLock);
13
}
14

15
// Thread 2
16
void mMain(...) {
17
    pthread_mutex_lock(&mtLock);
18
    while (mtInit == 0)
19
        pthread_cond_wait(&mtCond, &mtLock);
20
    pthread_mutex_unlock(&mtLock);
21

22
    mState = mThread->State;
23
}

여기서도 핵심은 패턴입니다.

• 순서 위반은 결국 상태 변수(state) + wait/signal로 해결합니다.
• while로 조건을 재확인해야 합니다(Mesa semantics + spurious wakeup).

2.1 교착 상태의 필요조건 (Coffman Conditions)#

교착 상태는 아래 네 조건이 동시에 만족될 때 발생합니다.

1. 상호 배제(Mutual Exclusion): 자원을 배타적으로 점유합니다.
2. 점유 및 대기(Hold-and-Wait): 자원을 가진 채로 다른 자원을 기다립니다.
3. 비선점(No Preemption): 자원을 강제로 빼앗을 수 없습니다.
4. 순환 대기(Circular Wait): 대기 관계가 사이클을 이룹니다.

이를 논리식으로 쓰면 다음처럼 요약할 수 있습니다.

즉, 네 조건 중 하나라도 깨면 교착 상태를 예방할 수 있습니다.

3.1 순환 대기 예방: 락 순서 정하기 (Lock Ordering)#

가장 실용적이면서 자주 쓰는 방법이 락 획득 순서를 강제하는 것입니다.

• 항상 L1 → L2 순서로만 잡게 만들면, 사이클이 생길 수 없습니다.
• 복잡한 시스템에서는 전체 순서(total ordering) 대신 부분 순서(partial ordering)를 설계하기도 합니다.

다중 락을 인자로 받는 함수가 문제를 만들 수 있는데, 이때는 락 주소값으로 순서를 강제하는 테크닉이 실용적입니다.

1
void do_something(pthread_mutex_t *m1, pthread_mutex_t *m2) {
2
    if (m1 == m2) return; // 동일 락이면 특별 처리
3

4
    if (m1 > m2) { // 주소 큰 것부터(또는 반대로) 일관되게
5
        pthread_mutex_lock(m1);
6
        pthread_mutex_lock(m2);
7
    } else {
8
        pthread_mutex_lock(m2);
9
        pthread_mutex_lock(m1);
10
    }
11

12
    // ... critical section ...
13

14
    pthread_mutex_unlock(m1);
15
    pthread_mutex_unlock(m2);
16
}

락 순서는 결국 규약입니다. 규약이 깨지는 순간 교착은 다시 가능해지므로, 코드베이스 규모가 커질수록 문서화와 리뷰 규율이 중요해집니다.

3.2 점유 및 대기 예방: 한 번에 모두 획득하기#

점유 및 대기 조건을 깨려면 필요한 락을 한 번에 원자적으로 획득하면 됩니다. 전역 prevention 락으로 락 획득 구간을 감싸는 방식이 대표적입니다.

1
pthread_mutex_lock(&prevention);
2
pthread_mutex_lock(L1);
3
pthread_mutex_lock(L2);
4
// ...
5
pthread_mutex_unlock(&prevention);

단점이 명확합니다.

• 병행성이 크게 줄어듭니다.
• 필요한 락을 미리 알아야 하므로 캡슐화/모듈성이 발목을 잡습니다.

3.3 비선점 예방: trylock으로 후퇴(back off)하기#

pthread_mutex_trylock()을 이용하면, 두 번째 락 획득 실패 시 이미 잡은 락을 풀고 재시도할 수 있습니다.

1
top:
2
pthread_mutex_lock(L1);
3
if (pthread_mutex_trylock(L2) != 0) {
4
    pthread_mutex_unlock(L1);
5
    // livelock 완화를 위해 랜덤/지수 backoff를 두는 것이 일반적
6
    goto top;
7
}

이 방식은 교착은 피하지만, 서로가 계속 양보만 하는 라이브락(livelock) 이 발생할 수 있습니다. 실무에서는 랜덤 딜레이, exponential backoff 같은 완화책을 함께 둡니다.

3.4 상호 배제 예방: 락 없는(lock-free) 접근#

가장 강한 형태는 락 자체를 없애 상호 배제 조건을 성립하지 않게 만드는 것입니다. 대표가 CAS 기반의 lock-free 설계입니다.

CAS 정의:

1
int CompareAndSwap(int *addr, int expected, int newv) {
2
    if (*addr == expected) {
3
        *addr = newv;
4
        return 1; // success
5
    }
6
    return 0; // failure
7
}

CAS로 구현한 원자적 증가:

1
void AtomicIncrement(int *value, int amount) {
2
    int old, newv;
3
    do {
4
        old  = *value;
5
        newv = old + amount;
6
    } while (CompareAndSwap(value, old, newv) == 0);
7
}

락이 없으니 교착은 원천적으로 사라지지만, 구현이 어렵고, 다른 형태의 진행 실패(예: livelock/기아) 가능성도 남습니다. 또한 유용한 자료구조를 lock-free로 완성하려면 훨씬 더 많은 고려가 필요합니다.

4.1 회피 (Avoidance)#

스레드가 어떤 락을 필요로 하는지 사전에 알고 있다면, 스케줄러가 교착이 나지 않도록 실행을 배치할 수 있습니다. 은행원 알고리즘류가 여기에 속합니다.

하지만 범용 OS/일반 애플리케이션에서는 전역적인 요구(lock demand)를 정확히 아는 것이 어려워 실용성이 제한됩니다. 회피는 종종 병행성을 희생하며, 결과적으로 성능 손해로 이어지기도 합니다.

4.2 탐지와 복구 (Detect and Recover)#

교착을 완전히 막지 않고, 발생을 허용한 뒤 주기적으로 탐지하는 전략도 있습니다.

• 자원(락) 대기 그래프를 만들고 사이클을 검사합니다.
• 사이클 발견 시 스레드/트랜잭션을 중단하거나, 재시작으로 복구합니다.

데이터베이스 시스템이 대표적이며, 교착이 드물고 복구 비용이 감당 가능할 때 현실적인 접근이 됩니다.