운영체제 아주 쉬운 세가지 이야기 12주차(병행성 관련 버그)

실제 MySQL, Apache, Mozilla, OpenOffice 같은 실전 코드에서 나온 사례를 다룹니다.

---

1. 동시성 버그, 진짜 뭐가 그렇게 문제인가?

1.1 어떤 종류의 버그들이 실제로 많이 나올까?

Lu et al.이 MySQL, Apache, Mozilla, OpenOffice의 실제 버그 리포트를 분석해서 동시성 버그를 유형별로 분류했습니다. 그 결과:

• 비-데드락(non-deadlock) 버그가 더 많다 (총 105개 중 74개)
• 데드락(deadlock) 버그는 상대적으로 적지만, 발생하면 시스템이 멈추므로 치명적

그리고 비-데드락 버그의 대부분(97%)은 두 종류가 거의 다 먹고 들어갑니다:

1. Atomicity Violation (원자성 위반)
2. Order Violation (순서 위반)

즉, “동시에 돌릴 때 어디서 틀어지냐?”를 보면, 원자성과 실행 순서 문제를 가장 조심해야 한다는 이야기입니다. 

---

2. Atomicity Violation – ‘한 덩어리’라고 믿었는데 아닌 경우

2.1 원자성 위반이란?

코드가 어떤 구간을 사실상 한 덩어리(atomic)로 작동한다고 믿고 작성되었는데, 실제로는 그 사이에 다른 스레드가 끼어들어 중간 상태가 노출되는 경우를 말합니다.

정의 (Lu et al.):
“여러 메모리 접근들 사이에 원하는 serializability(직렬화)가 깨짐. 즉, 어떤 코드 영역이 atomic하게 실행되길 의도했지만, 실행 중에 그 atomicity가 보장되지 않는 상황.”

2.2 MySQL 예제 – NULL 체크 후 사용

// Thread 1
if (thd->proc_info) {
    fputs(thd->proc_info, ...);
}

// Thread 2
thd->proc_info = NULL;

의도는 단순합니다:

• Thread 1: proc_info가 NULL이 아니면 출력
• Thread 2: 어떤 시점에 proc_info를 NULL로 바꾼다

하지만 스케줄링이 이렇게 되면 문제가 터집니다:

1. Thread 1: if (thd->proc_info)에서 NULL 아님을 확인
2. → 바로 fputs() 호출 직전에 컨텍스트 스위치
3. Thread 2: thd->proc_info = NULL; 수행
4. Thread 1 다시 실행: 이제 fputs(thd->proc_info, ...)는 NULL 포인터 역참조

프로그래머 머릿속에선 “if (non-null) { print } 는 하나의 덩어리”인데, 실제 실행은 “check”와 “use” 사이에 틈이 생겨 다른 스레드가 값을 바꿔버립니다. 이게 전형적인 원자성 위반입니다.

2.3 어떻게 고칠까? – 임계구역(락)으로 감싸기

공유 데이터 thd->proc_info에 접근하는 모든 곳을 하나의 뮤텍스로 보호합니다.

pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;

// Thread 1
pthread_mutex_lock(&proc_info_lock);
if (thd->proc_info) {
    fputs(thd->proc_info, ...);
}
pthread_mutex_unlock(&proc_info_lock);

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

이제 “NULL 체크 + 사용”이 락 안에서 한 덩어리로 실행됩니다. 두 스레드 중 하나만 그 구간을 실행할 수 있으므로, 중간에 끼어들어 값이 바뀌는 일이 없습니다.

실무 인사이트:

• “읽고-검사하고-사용하는” 패턴(get-check-use)은 항상 원자성 후보입니다.
• 공유 포인터/상태를 락 없이 읽고 판단하고 있다면, 거의 100% 버그 후보라고 의심해도 됩니다.

---

3. Order Violation – 순서를 가정했는데, 스케줄러는 그런 거 모를 때

3.1 순서 위반이란?

두 스레드가 어떤 자원을 사용하는 순서에 대한 암묵적 가정이 있는데, 실제 실행 순서가 그 가정과 다를 때 나는 버그입니다.

정의:
“A가 항상 B보다 먼저 실행되어야 하지만, 그 순서가 실행 중에 강제되지 않아 깨지는 경우.”

3.2 Mozilla 예제 – 스레드 생성 vs 스레드 내부 코드

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

// Thread 2 (스레드 함수)
void mMain(...) {
    mState = mThread->State;
}

작성자는 “mThread는 init()에서 이미 세팅되었을 거야”라고 믿습니다.
하지만 현실은:

1. Thread 1: mThread = PR_CreateThread(...) 호출
2. OS: 새 스레드(Thread 2)를 바로 스케줄링할 수 있음
3. Thread 2: mState = mThread->State; 실행 → mThread는 아직 NULL일 수도

“먼저 init이 끝나고, 나중에 mMain이 돈다”는 보장은 없습니다. 스케줄러는 그런 논리적 순서를 모릅니다. 우리가 명시적으로 순서를 만들어 줘야 합니다.

3.3 어떻게 고칠까? – 조건변수로 “준비 완료” 신호 주기

전형적인 해결책: “init이 끝났다는 사실”을 나타내는 상태 변수 + 조건변수 + 뮤텍스.

pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  mtCond = PTHREAD_COND_INITIALIZER;
int mtInit = 0;

// Thread 1
void init() {
    ...
    mThread = PR_CreateThread(mMain, ...);

    // 스레드 생성 완료 신호
    pthread_mutex_lock(&mtLock);
    mtInit = 1;
    pthread_cond_signal(&mtCond);
    pthread_mutex_unlock(&mtLock);
}

// Thread 2
void mMain(...) {
    // init()이 끝날 때까지 대기
    pthread_mutex_lock(&mtLock);
    while (mtInit == 0)
        pthread_cond_wait(&mtCond, &mtLock);
    pthread_mutex_unlock(&mtLock);

    // 여기 오면 mThread는 준비 완료
    mState = mThread->State;
}

핵심은:

• 상태 변수 mtInit로 “초기화가 되었는가?”를 기록하고
• Thread 2는 while (mtInit == 0)로 조건을 직접 확인한 뒤, not-yet이면 wait
• Thread 1은 초기화가 끝난 시점에 signal()로 깨운다

이렇게 하면 “init 이후에 mMain이 실행되어야 한다”는 순서를 코드로 명시할 수 있습니다.

---

4. Deadlock – 서로 잡고 서로 기다리기

4.1 가장 단순한 데드락 예제

// Thread 1
pthread_mutex_lock(L1);
pthread_mutex_lock(L2);

// Thread 2
pthread_mutex_lock(L2);
pthread_mutex_lock(L1);

가능한 실행 시나리오:

1. Thread 1: L1 획득
2. Context switch
3. Thread 2: L2 획득
4. Thread 1: pthread_mutex_lock(L2) → L2를 기다리며 블록
5. Thread 2: pthread_mutex_lock(L1) → L1을 기다리며 블록

이제 두 스레드는 둘 다 “상대가 가진 락”을 기다리고 있으므로, 누구도 앞으로 나아가지 못합니다.
이게 데드락입니다.

4.2 Coffman의 데드락 4조건

데드락이 발생하려면, 아래 네 가지 조건이 모두 만족되어야 합니다:

1. Mutual Exclusion (상호 배제) - 자원은 동시에 한 스레드만 사용 가능 (락 자체가 이런 자원)
2. Hold-and-Wait - 이미 어떤 자원은 들고 있으면서, 다른 자원을 기다리는 상태
3. No Preemption - 누군가 잡고 있는 자원을 강제로 뺏지 못함 (UNIX 락은 그렇죠)
4. Circular Wait - 자원/스레드들이 원형으로 “서로가 가진 것을 서로 기다리는” 관계

이 중 어느 하나라도 깨면 데드락은 발생할 수 없습니다. 그래서 데드락 해결 전략은 보통 “4가지 중 하나를 막자”로 정리됩니다.

---

5. Deadlock 다루는 4가지 전략

5.1 예방(Prevention) – 아예 조건을 깨버리자

(1) Circular Wait 막기 – 락 순서를 강제

가장 실용적인 전략입니다: 모든 락에 순서를 매기고, 항상 그 순서대로 획득하게 합니다.

• 예: 시스템에 락 L1, L2, L3가 있으면, 항상 “번호 작은 것 → 큰 것” 순서로 lock
• A 스레드가 (L1 → L2), B 스레드가 (L2 → L1)을 잡으면 데드락이지만, “항상 L1 먼저, 그 다음 L2”만 허용하면 원형 대기가 불가능

실무에서는:

• “DB → 캐시 → 파일” 이런 식으로 자원 계층을 정하고 그 순서대로 lock
• 특히 “두 객체를 동시에 락 잡는 함수”는 주소 순으로 정렬하여 lock 하는 패턴이 자주 쓰임

(2) Hold-and-Wait 깨기 – “한 번에 다 잡거나, 아예 안 잡거나”

모든 락을 한 번에 atomically 획득하게 해서, “일부를 들고 나머지를 기다리는” 상태를 없애는 접근도 있습니다.

하지만 현실적으로:

• 어떤 함수가 내부에서 잡는 락들을 모두 밖에서 미리 알아야 함 → 캡슐화와 충돌
• 락을 너무 일찍, 너무 많이 잡아서 병렬성이 크게 떨어짐

(3) No Preemption 완화 – trylock과 “포기 후 재시도”

pthread_mutex_trylock()은 락을 잡으려다 실패하면 바로 리턴합니다. 이를 이용하면:

top:
    pthread_mutex_lock(L1);
    if (pthread_mutex_trylock(L2) != 0) {
        pthread_mutex_unlock(L1);
        goto top;   // 다시 시도
    }

이렇게 하면 “L2를 못 잡았을 때, L1을 포기하고 처음부터 다시”라는 전략으로 “서로가 서로를 기다리는” 상태를 피할 수 있습니다.

단점:

• 운 나쁘면 둘이 계속 재시도만 하는 livelock 가능
• 그 안에서 메모리/자원 할당이 있다면, 재시도 전에 깔끔히 정리해야 해서 코드 복잡

(4) Mutual Exclusion 피하기 – Lock-free / Wait-free 구조

Herlihy 같은 연구에서 나온 아이디어: Compare-And-Swap(CAS) 같은 강력한 하드웨어 원자 연산을 이용해, 락 없이(shared lock 없음) 자료구조를 안전하게 업데이트하는 방법입니다.

예를 들어, 리스트 머리에 노드 삽입을 CAS로 구현하는 코드:

void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    n->value = value;
    do {
        n->next = head;
    } while (CompareAndSwap(&head, n->next, n) == 0);
}

락이 없으니 데드락 자체가 발생하지 않습니다. 대신 구현 난이도가 매우 높고, 일반 개발자가 직접 만들기엔 부담이 큽니다. 그래서 보통은 “라이브러리 수준의 고성능 자료구조”로 제공되는 경우가 많습니다. [oai_citation:5‡threads-bugs.pdf](sediment://file_0000000000ec7209b15fcf8875bb9005)

---

5.2 회피(Avoidance) – 스케줄러가 영리하게 데드락을 피하게

이론적으로는 “각 스레드가 어떤 락들을 사용할지”를 미리 안다면, 스케줄러가 데드락이 일어나지 않는 순서로만 스레드를 돌릴 수 있습니다.

대표적인 알고리즘: Banker’s Algorithm (Dijkstra). 하지만 현실의 일반-purpose OS/서비스에서는:

• 모든 스레드의 “향후 락 사용 계획”을 알 수 없음
• 필요 이상으로 보수적으로 스케줄해서 성능을 많이 포기할 수 있음

그래서 일반 애플리케이션 개발에서 직접 쓰는 경우는 거의 없습니다.

---

5.3 검출 & 복구(Detect & Recover)

“데드락이 아주 가끔 일어난다” 정도라면, 현실적인 선택은 이렇습니다:

• 그냥 가끔 죽는 것을 감수하고, 재시작 스크립트/오케스트레이션(Kubernetes 등)으로 복구
• DBMS처럼 중요한 시스템은 주기적으로 wait-for graph(자원 그래프)를 만들고 사이클을 찾아서, 사이클의 한 트랜잭션을 강제 롤백

즉, “완벽하게 막기보단, 일어나면 감지하고 죽이고 치우자”라는 pragmatic한 접근입니다.

---

6. 실무/면접에서 자주 나오는 포인트 정리

6.1 코드 리뷰할 때 체크리스트

• 원자성 후보:
  • “값 읽기 → 검사 → 그 값 기반으로 행동” 패턴 (check-then-act)
  • 락 없이 공유 포인터/공유 상태를 검사하고 있다면? → 의심
• 순서 가정:
  • “A 함수가 반드시 먼저 호출되고, B는 그 다음이다” 같은 주석/문서가 있는지
  • 그 순서를 진짜 조건변수/플래그 등으로 코드에 반영했는지
• 락 획득 순서:
  • 두 개 이상 락을 잡는 부분이 있다면, 모두 같은 순서로 잡는지
  • “객체 주소 순으로 락 잡기” 같은 패턴이 일관되게 쓰이는지

---

7. 미니 퀴즈 (정리용)

1. 다음 코드에서 어떤 종류의 버그가 발생할 수 있는가? (atomicity vs ordering vs deadlock)

// 공유 변수
int *ptr = NULL;

// Thread 1
ptr = malloc(...);
if (ptr != NULL) {
    do_something(ptr);
}

// Thread 2
if (ptr != NULL) {
    free(ptr);
    ptr = NULL;
}