14. Concurrency - Bugs

Concurrency: Bugs

Reading

• 이 단원은 Concurrency Bugs를 다룬다.
• 앞 단원들에서 thread, lock, semaphore, condition variable을 배웠다면, 14단원에서는 concurrency 상황에서 실제로 어떤 bug가 생기는지를 배운다.
• 주요 주제는 다음과 같다.
  • Atomicity bug
  • Ordering bug
  • Deadlock
  • Deadlock prevention
• 즉 이 단원은 “동기화 도구를 왜 조심해서 써야 하는가”를 bug 유형 중심으로 정리하는 단원이다.

Today’s Topics

• concurrency bug는 multi-threaded program에서 흔히 발생한다.
• 이 단원에서 다루는 대표적인 concurrency bug는 다음 세 가지다.
  • Atomicity bug
    • 원래 atomic하게 실행되어야 하는 코드 조각이 중간에 끼어들기를 허용해서 생기는 bug
  • Ordering bug
    • 어떤 작업이 다른 작업보다 먼저 일어나야 하는데, 순서가 보장되지 않아서 생기는 bug
  • Deadlock
    • 여러 thread가 서로 필요한 resource를 기다리며 영원히 멈추는 bug
• 그리고 deadlock을 막는 방법으로 deadlock prevention을 배운다.

Concurrency Study from 2008

• Lu et al.의 2008년 연구는 실제 큰 software project의 concurrency bug를 분석했다.
• 대상은 다음과 같은 major project들이었다.
  • MySQL
  • Apache
  • Mozilla
  • OpenOffice
• 500K개 이상의 bug report 중 concurrency bug sample을 분석했다.
• 주요 bug 유형은 다음과 같이 나뉜다.
  • atomicity bug
  • ordering bug
  • deadlock
  • other
• 이 연구가 보여주는 핵심은 concurrency bug가 이론적인 문제가 아니라 실제 대형 software에서도 자주 발생한다는 점이다.
• 특히 atomicity bug와 ordering bug는 lock이나 condition variable을 잘못 쓰거나 아예 쓰지 않을 때 쉽게 생긴다.

Atomicity Bug

• atomicity bug는 함께 실행되어야 하는 연산들이 쪼개져서 interleaving될 때 발생한다.
• 즉 programmer는 어떤 코드 조각이 한 번에 실행된다고 기대하지만, 실제로는 thread switch 때문에 중간에 다른 thread가 끼어든다.
• 그 결과 shared state가 예상과 다르게 변한다.
• atomicity bug의 핵심은 다음이다.
  • check와 use가 분리되어 있다.
  • read와 write가 분리되어 있다.
  • 여러 statement가 하나의 logical operation인데 보호되지 않는다.
• 예를 들어 if (ptr != NULL)로 확인한 뒤 그 pointer를 사용하는 사이에 다른 thread가 ptr = NULL로 바꾸면 문제가 생긴다.

Atomicity Bug in MySQL

• MySQL의 예시는 다음과 같다.
• Thread 1은 thd->proc_info가 NULL이 아닌지 확인한 뒤 사용한다.

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

• Thread 2는 같은 값을 NULL로 만든다.

thd->proc_info = NULL;

• 문제는 Thread 1의 check와 use가 atomic하지 않다는 것이다.
• 가능한 실행 순서는 다음과 같다.
  • Thread 1이 thd->proc_info != NULL임을 확인한다.
  • 그 직후 Thread 2가 thd->proc_info = NULL을 실행한다.
  • Thread 1이 다시 실행되어 fputs(thd->proc_info, ...)를 호출한다.
• 이때 Thread 1은 NULL pointer를 사용할 수 있다.
• 즉 test와 use 사이에 다른 thread가 shared variable을 바꾸면 bug가 생긴다.
• 따라서 thd->proc_info에 대한 check와 사용은 하나의 atomic region으로 묶여야 한다.

Fix Atomicity Bugs with Locks

• atomicity bug는 lock으로 고칠 수 있다.
• 핵심은 shared data를 확인하고 사용하는 전체 구간을 같은 lock으로 보호하는 것이다.
• Thread 1은 다음처럼 lock을 잡고 check와 use를 모두 수행해야 한다.

mutex_lock(&lock);

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

mutex_unlock(&lock);

• Thread 2도 같은 lock을 잡고 shared variable을 수정해야 한다.

mutex_lock(&lock);
thd->proc_info = NULL;
mutex_unlock(&lock);

• 중요한 점은 두 thread가 같은 lock을 써야 한다는 것이다.
• Thread 1만 lock을 잡거나 Thread 2만 lock을 잡으면 보호가 되지 않는다.
• lock은 shared state에 대한 모든 접근을 같은 규칙으로 감쌀 때 의미가 있다.
• 이 방식은 check-use sequence를 critical section으로 만들어 atomicity를 보장한다.

Ordering Bug

• ordering bug는 반드시 먼저 일어나야 하는 작업이 늦게 일어나거나, 나중에 일어나야 하는 작업이 먼저 일어날 때 발생한다.
• 즉 atomicity bug가 “중간에 끼어들면 안 되는 코드 조각”의 문제라면, ordering bug는 “실행 순서”의 문제다.
• 예를 들어 다음과 같은 상황이 있다.
  • Thread 1이 data structure를 초기화한다.
  • Thread 2가 그 data structure를 사용한다.
• 이때 Thread 2는 반드시 Thread 1의 initialization 이후에 실행되어야 한다.
• 하지만 synchronization이 없으면 Thread 2가 먼저 실행될 수 있다.
• 그러면 uninitialized value를 읽거나 invalid pointer를 사용할 수 있다.

Ordering Bug in Mozilla

• Mozilla의 예시는 다음과 같다.
• Thread 1은 thread를 만든다.

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

• Thread 2는 mThread를 사용한다.

void mMain(...)
{
    ...
    mState = mThread->State;
    ...
}

• 문제는 Thread 2가 mThread가 완전히 초기화되기 전에 실행될 수 있다는 점이다.
• Thread 1이 mThread 값을 설정하기 전에 Thread 2가 mThread->State를 읽으면 문제가 생긴다.
• 즉 여기서 필요한 것은 mutual exclusion만이 아니다.
• 중요한 것은 다음 순서다.
  • Thread 1이 mThread를 초기화한다.
  • 그 다음 Thread 2가 mThread를 읽는다.
• 이 순서를 보장하지 않으면 ordering bug가 생긴다.

Fix Ordering Bugs with Condition Variables

• ordering bug는 condition variable로 고칠 수 있다.
• 핵심은 “초기화가 끝났는지”를 나타내는 state variable을 두는 것이다.
• 예를 들어 mtInit이라는 flag를 둔다.
• Thread 2는 mtInit == 1이 될 때까지 기다린다.

void mMain(...)
{
    ...
    mutex_lock(&mtLock);

    while (mtInit == 0)
        cond_wait(&mtCond, &mtLock);

    mutex_unlock(&mtLock);

    mState = mThread->State;
    ...
}

• Thread 1은 mThread를 만든 뒤 mtInit = 1로 바꾸고 signal을 보낸다.

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

    mutex_lock(&mtLock);
    mtInit = 1;
    cond_signal(&mtCond);
    mutex_unlock(&mtLock);

    ...
}

• 여기서 mutex는 mtInit 상태를 보호한다.
• condition variable은 Thread 2가 “초기화 완료”라는 event를 기다리게 한다.
• while을 쓰는 이유는 깨어난 뒤에도 조건이 여전히 참인지 다시 확인해야 하기 때문이다.
• 즉 condition variable은 ordering constraint를 표현하는 데 적합하다.

Atomicity Bug vs Ordering Bug

• atomicity bug와 ordering bug는 비슷해 보이지만 초점이 다르다.
• atomicity bug는 여러 동작이 하나처럼 실행되어야 하는데, 중간에 다른 thread가 끼어드는 문제다.
  • 예: check 후 use 사이에 값이 바뀜
  • 해결: lock으로 critical section 보호
• ordering bug는 A가 B보다 먼저 일어나야 하는데 그 순서가 보장되지 않는 문제다.
  • 예: initialization 전에 use가 발생함
  • 해결: condition variable, semaphore 등으로 순서 보장
• 정리하면 다음과 같다.

Deadlock

• deadlock은 여러 thread나 process가 서로 필요한 resource를 기다리며 영원히 진행하지 못하는 상태다.
• 가장 직관적인 예시는 교통 deadlock이다.
  • 네 방향에서 차가 교차로에 진입한다.
  • 각 차가 앞을 막고 있다.
  • 모두가 다른 차가 먼저 빠지기를 기다린다.
  • 아무도 움직이지 못한다.
• thread에서도 같은 일이 생긴다.
• 예를 들어 두 lock a, b가 있다고 하자.
• Thread 1은 다음 순서로 lock을 잡는다.

lock(a);
lock(b);
/* do some work */
unlock(b);
unlock(a);

• Thread 2는 반대 순서로 lock을 잡는다.

lock(b);
lock(a);
/* do some work */
unlock(a);
unlock(b);

• 가능한 실행 순서는 다음과 같다.
  • Thread 1이 a를 잡는다.
  • Thread 2가 b를 잡는다.
  • Thread 1은 b를 기다린다.
  • Thread 2는 a를 기다린다.
• Thread 1은 Thread 2가 b를 풀어야 진행할 수 있다.
• Thread 2는 Thread 1이 a를 풀어야 진행할 수 있다.
• 둘 다 기다리기만 하므로 deadlock이다.

System Model

• deadlock을 일반화하기 위해 system을 resource들의 집합으로 본다.
• resource type은 다음처럼 표현할 수 있다.
  • R1, R2, ..., Rm
• resource의 예시는 다음과 같다.
  • CPU cycles
  • memory space
  • I/O devices
  • locks
  • files
• 각 resource type Ri는 여러 instance를 가질 수 있다.
  • 예를 들어 같은 종류의 printer가 여러 대 있을 수 있다.
  • 같은 종류의 memory block이 여러 개 있을 수 있다.
• process는 resource를 다음 순서로 사용한다.
  • Request
  • Use
  • Release
• deadlock은 request 단계에서 서로가 가진 resource를 기다리며 멈추는 문제다.

Conditions for Deadlock

• deadlock이 발생하려면 네 가지 조건이 모두 필요하다.
• 이를 deadlock의 necessary conditions라고 한다.
• 네 조건은 다음과 같다.
  • Mutual exclusion
  • Hold and wait
  • No preemption
  • Circular wait
• 이 네 조건 중 하나라도 깨면 deadlock은 발생하지 않는다.
• deadlock prevention은 바로 이 아이디어를 사용한다.
• 즉 deadlock을 막기 위해 네 조건 중 하나를 의도적으로 제거한다.

Mutual Exclusion

• mutual exclusion은 한 번에 하나의 process/thread만 resource를 사용할 수 있다는 조건이다.
• 예를 들어 lock은 동시에 여러 thread가 잡을 수 없다.
• printer도 한 순간에는 하나의 job만 출력할 수 있다.
• 이런 resource는 non-sharable resource다.
• 반대로 read-only file처럼 여러 process가 동시에 읽어도 되는 resource는 sharable resource다.
• deadlock은 주로 non-sharable resource에서 발생한다.
• mutual exclusion이 없다면 여러 process가 같은 resource를 동시에 사용할 수 있으므로 기다림이 줄어든다.
• 하지만 모든 resource에서 mutual exclusion을 없앨 수는 없다.
• 예를 들어 lock이나 write 가능한 shared data는 mutual exclusion이 필요하다.

Hold and Wait

• hold and wait은 process가 이미 어떤 resource를 들고 있으면서, 추가 resource를 기다리는 조건이다.
• 예를 들어 Thread 1이 lock a를 잡은 상태에서 lock b를 기다리는 상황이다.
• 이때 Thread 1은 a를 놓지 않고 b를 기다린다.
• Thread 2가 b를 잡은 상태에서 a를 기다리면 deadlock이 생길 수 있다.
• 즉 “잡은 것을 놓지 않고 다른 것을 기다리는 것”이 deadlock의 중요한 원인이다.

No Preemption

• no preemption은 resource를 강제로 빼앗을 수 없다는 조건이다.
• 어떤 thread가 lock을 잡고 있으면 OS나 runtime이 강제로 그 lock을 회수하지 않는다.
• resource는 그것을 들고 있는 process/thread가 자발적으로 release해야 한다.
• lock은 대표적으로 no preemption 성격을 가진 resource다.
• 만약 resource를 강제로 빼앗을 수 있다면 deadlock을 풀 수 있다.
• 하지만 lock이나 critical section을 강제로 중간에 빼앗으면 data structure invariant가 깨질 수 있다.
• 그래서 많은 synchronization resource는 preemption이 어렵다.

Circular Wait

• circular wait은 기다림의 고리가 생기는 조건이다.
• 예를 들어 다음과 같은 상황이다.
  • P0은 P1이 가진 resource를 기다린다.
  • P1은 P2가 가진 resource를 기다린다.
  • P2는 P0이 가진 resource를 기다린다.
• 이처럼 원형의 dependency가 생기면 아무도 진행하지 못한다.
• lock 예시에서는 다음과 같다.
  • T1은 lock A를 잡고 lock B를 기다린다.
  • T2는 lock B를 잡고 lock A를 기다린다.
• circular wait은 deadlock prevention에서 가장 실용적으로 많이 다루는 조건이다.
• lock acquisition order를 정하면 circular wait을 막을 수 있다.

Resource-Allocation Graph

• deadlock을 분석할 때 resource-allocation graph를 사용할 수 있다.
• graph는 vertex와 edge로 구성된다.
• vertex는 두 종류다.
  • process vertex
    • P = {P1, P2, ..., Pn}
  • resource vertex
    • R = {R1, R2, ..., Rm}
• edge도 두 종류가 있다.
  • request edge
    • Pi → Rj
    • process Pi가 resource Rj를 요청하고 기다리는 상태
  • assignment edge
    • Rj → Pi
    • resource Rj가 process Pi에 할당된 상태
• 이 graph를 보면 deadlock 가능성을 시각적으로 확인할 수 있다.

Basic Facts

• resource-allocation graph에 cycle이 없으면 deadlock은 없다.
• graph에 cycle이 있으면 deadlock 가능성이 있다.
• 단, resource instance 수에 따라 해석이 달라진다.
• 각 resource type에 instance가 하나뿐이면 cycle은 deadlock을 의미한다.
• 각 resource type에 instance가 여러 개 있으면 cycle이 있어도 반드시 deadlock은 아닐 수 있다.
• 즉 cycle은 deadlock의 중요한 신호지만, resource instance 수에 따라 정확한 판단이 달라진다.

Methods for Handling Deadlocks

• deadlock을 다루는 방법은 크게 네 가지다.
• 첫째, deadlock prevention이다.
  • deadlock의 necessary condition 중 하나를 제거한다.
  • 이 단원에서 주로 다루는 방법이다.
• 둘째, deadlock avoidance다.
  • resource request를 받을 때마다 승인할지 거절할지 판단한다.
  • system이 deadlock state로 들어가지 않도록 미리 피한다.
  • 추가적인 resource usage 정보가 필요하다.
• 셋째, deadlock detection and recovery다.
  • deadlock이 발생하는 것을 허용한다.
  • 이후 deadlock을 감지하고 복구한다.
• 넷째, ignore deadlock이다.
  • deadlock 문제를 무시하고, 발생하지 않는다고 가정한다.
  • UNIX를 포함한 많은 OS가 실용적으로 이 방식을 사용한다.
• 이 강의에서는 주로 deadlock prevention을 다룬다.

Deadlock Prevention

• deadlock prevention의 핵심은 deadlock의 네 필요조건 중 하나를 제거하는 것이다.
• 네 조건은 다음과 같다.
  • mutual exclusion
  • hold and wait
  • no preemption
  • circular wait
• deadlock은 네 조건이 모두 만족되어야 발생한다.
• 따라서 하나만 깨도 deadlock을 예방할 수 있다.
• 하지만 모든 조건을 깨는 것이 현실적으로 쉬운 것은 아니다.
• 예를 들어 mutual exclusion은 shared writable data를 보호하기 위해 필요한 경우가 많다.
• no preemption도 lock에서는 강제로 깨기 어렵다.
• 그래서 실제로 가장 실용적인 방법은 보통 circular wait을 막는 것이다.
• 즉 lock ordering을 정하고, 모든 code가 그 순서를 지키게 한다.

Preventing Mutual Exclusion

• mutual exclusion을 제거하면 deadlock 조건 하나가 사라진다.
• sharable resource에는 mutual exclusion이 필요하지 않다.
  • 예: read-only file
• 하지만 non-sharable resource에는 mutual exclusion이 필요하다.
  • 예: lock
  • 예: write 가능한 shared data
• mutual exclusion을 줄이는 한 가지 전략은 lock을 없애고 atomic primitive를 사용하는 것이다.
• 예를 들어 Compare-And-Swap을 사용하면 간단한 update를 lock 없이 처리할 수 있다.

int CompAndSwap(int *addr, int expected, int new);

• 이 함수는 *addr 값이 expected일 때만 new로 바꾼다.
• 성공하면 1, 실패하면 0을 반환한다고 생각할 수 있다.
• lock을 쓰는 add는 다음과 같다.

void add(int *val, int amt)
{
    mutex_lock(&m);
    *val += amt;
    mutex_unlock(&m);
}

• CAS를 쓰면 lock 없이 retry loop로 만들 수 있다.

void add(int *val, int amt)
{
    int old;

    do {
        old = *val;
    } while (!CompAndSwap(val, old, old + amt));
}

• old는 while 조건에서도 보여야 하므로 loop 밖에서 선언해야 한다.
• 이 방식은 lock을 없애므로 deadlock 가능성을 줄인다.
• 하지만 lock-free code는 구현과 검증이 어렵다.

Wait-Free Algorithms

• mutual exclusion을 줄이는 또 다른 예는 wait-free algorithm이다.
• linked list insert를 생각해보자.
• lock을 사용하는 방식은 다음과 같다.

void insert(int val)
{
    node_t *n = malloc(sizeof(*n));
    n->val = val;

    lock(&m);
    n->next = head;
    head = n;
    unlock(&m);
}

• CAS를 사용하면 다음처럼 lock 없이 만들 수 있다.

void insert(int val)
{
    node_t *n = malloc(sizeof(*n));
    n->val = val;

    do {
        n->next = head;
    } while (!CompAndSwap(&head, n->next, n));
}

• 동작은 다음과 같다.
  • 현재 head를 읽어 n->next에 저장한다.
  • head가 여전히 그 값이면 head를 n으로 바꾼다.
  • 중간에 다른 thread가 head를 바꿨으면 실패하고 다시 시도한다.
• 이 방식은 lock을 사용하지 않으므로 deadlock 위험이 줄어든다.
• 하지만 ABA 문제, memory reclamation 문제 등 복잡한 문제가 생길 수 있다.
• 따라서 실무에서는 lock-free algorithm이 항상 쉬운 선택은 아니다.

Preventing Hold-and-Wait

• hold-and-wait을 막으려면 process가 resource를 요청할 때 이미 다른 resource를 들고 있지 않게 해야 한다.
• 방법은 크게 두 가지로 생각할 수 있다.
• 첫째, process가 실행을 시작하기 전에 필요한 모든 resource를 한 번에 요청하게 한다.
• 둘째, process가 어떤 resource도 들고 있지 않을 때만 새 resource를 요청하게 한다.
• lock 관점에서는 다음과 같은 전략이 가능하다.
  • 필요한 모든 lock을 한 번에 잡는다.
  • 이후에는 lock을 release할 수는 있지만, 다시 새 lock을 acquire하려면 모든 lock을 놓은 뒤 다시 시작해야 한다.
• 이를 구현하기 위해 meta lock을 사용할 수 있다.

lock(&meta);

lock(&L1);
lock(&L2);
...

unlock(&meta);

/* critical section */

unlock(...);

• meta lock은 여러 lock을 잡는 과정 자체를 serialize한다.
• 그러면 두 thread가 서로 다른 순서로 lock을 잡다가 꼬이는 상황을 줄일 수 있다.
• 하지만 단점도 있다.
  • concurrency가 크게 줄어든다.
  • 모든 resource를 미리 알아야 한다.
  • 필요한 resource가 동적으로 결정되는 경우 어렵다.

Preventing No Preemption

• no preemption을 막으려면 resource를 강제로 회수할 수 있어야 한다.
• lock에서는 일반적으로 강제 회수가 어렵다.
• 대신 비슷한 효과를 내는 방식으로 trylock을 사용할 수 있다.
• 예를 들어 A를 잡은 뒤 B를 잡으려 했는데 실패하면 A를 풀고 처음부터 다시 시도한다.

top:
    lock(A);

    if (trylock(B) == -1) {
        unlock(A);
        goto top;
    }

    ...

• 이 방식은 다음 상황을 막는다.
  • A를 잡은 상태로 B를 영원히 기다림
• B를 못 잡으면 A를 놓고 다시 시작하므로 hold-and-wait도 완화된다.
• 하지만 단점도 있다.
  • 계속 실패하면 livelock처럼 보일 수 있다.
  • retry 비용이 커질 수 있다.
  • 코드가 복잡해진다.
• 그래도 blocking lock 대신 trylock을 쓰면 deadlock 가능성을 줄일 수 있다.

Preventing Circular Wait

• circular wait을 막는 가장 대표적인 방법은 total ordering을 부여하는 것이다.
• 모든 resource type에 순서를 정한다.
• 그리고 모든 process/thread가 resource를 항상 증가하는 순서로 요청하게 한다.
• 예를 들어 lock order를 다음처럼 정했다고 하자.
  • A before B
  • B before C
• 그러면 code는 A를 잡은 뒤 B를 잡을 수 있다.
• 하지만 B를 잡은 상태에서 A를 잡으면 안 된다.
• 전략은 다음과 같다.
  • 어떤 lock이 어떤 lock보다 먼저 잡혀야 하는지 결정한다.
  • 그 순서를 문서화한다.
  • 모든 code가 그 순서를 따르게 한다.
• 이 방식은 system에 distinct layer가 있을 때 잘 작동한다.
• 예를 들어 file system layer, memory layer, page table layer처럼 계층이 있으면 lock order를 정하기 쉽다.
• 실제 kernel code에서도 lock ordering은 매우 중요하다.

Lock Ordering

• lock ordering은 deadlock prevention에서 가장 실용적인 방법이다.
• 핵심은 모든 code path가 lock을 같은 순서로 잡는 것이다.
• 예를 들어 어떤 code는 A → B 순서로 lock을 잡고, 다른 code는 B → A 순서로 잡으면 deadlock 위험이 생긴다.
• 따라서 global lock order를 정해야 한다.
• 예시는 다음과 같다.
  • 먼저 mmap_sem
  • 그다음 i_mmap_rwsem
  • 그다음 page_table_lock
  • 그다음 i_pages lock
• 실제 Linux kernel도 lock ordering을 주석으로 문서화한다.
• lock ordering은 단순하지만 강력하다.
• 다만 system이 커질수록 모든 lock 관계를 관리하기 어려워진다.
• 그래도 현실적으로 deadlock prevention에서 가장 많이 쓰이는 방법 중 하나다.

Deadlock Avoidance

• deadlock avoidance는 prevention과 다르다.
• prevention은 deadlock 조건 자체를 깨는 방식이다.
• avoidance는 각 resource request를 받을 때 이 요청을 승인해도 안전한지 판단한다.
• 즉 system이 unsafe state로 들어가지 않게 한다.
• 대표적인 예는 banker’s algorithm이다.
• 하지만 avoidance는 추가 정보가 필요하다.
  • 각 process가 앞으로 어떤 resource를 얼마나 요청할지
  • system의 available resource
  • 현재 allocation 상태
• 일반-purpose OS에서는 이런 정보를 미리 알기 어렵다.
• 그래서 이 강의에서는 deadlock avoidance를 자세히 다루지 않는다.

Deadlock Detection and Recovery

• deadlock detection and recovery는 deadlock이 생기는 것을 허용한다.
• 대신 주기적으로 deadlock이 있는지 검사한다.
• deadlock이 발견되면 recovery를 수행한다.
• recovery 방법은 다음과 같을 수 있다.
  • process를 kill한다.
  • resource를 강제로 회수한다.
  • rollback한다.
• 이 방식은 database system 등에서는 사용될 수 있다.
• 하지만 OS kernel lock deadlock에서는 recovery가 쉽지 않다.
• kernel 내부 deadlock은 system 전체가 멈추는 심각한 문제가 될 수 있다.

Ignore Deadlock

• 많은 OS는 deadlock을 완전히 해결하지 않고 사실상 무시하는 전략을 사용한다.
• “deadlock이 드물게 발생한다고 보고, 발생하면 reboot하거나 debugging한다”는 식이다.
• UNIX 계열 OS도 실용적으로 이 접근을 사용하는 경우가 많다.
• 이유는 deadlock을 완벽히 예방하거나 회피하려면 비용이 크고 구조가 복잡해지기 때문이다.
• 물론 kernel 개발에서는 lock ordering이나 coding convention으로 deadlock을 최대한 줄인다.
• 즉 deadlock을 이론적으로 완전히 없애기보다는, 실용적인 규칙으로 위험을 낮춘다.

Atomicity Bug 해결 전략

• atomicity bug를 막으려면 “논리적으로 하나의 작업”을 하나의 critical section으로 묶어야 한다.
• 예시는 다음과 같다.
  • check와 use를 같은 lock 안에 둔다.
  • read-modify-write를 같은 lock 안에 둔다.
  • data structure invariant가 깨지는 구간을 lock으로 보호한다.
• 중요한 원칙은 다음이다.
  • shared variable을 읽고 쓰는 모든 thread가 같은 lock을 사용해야 한다.
  • lock을 일부 code path에만 적용하면 보호가 깨진다.
  • lock 범위가 너무 작으면 중간 상태가 노출될 수 있다.
• 따라서 correctness가 의심될 때는 concurrency를 조금 더 제한하는 편이 안전하다.

Ordering Bug 해결 전략

• ordering bug를 막으려면 필요한 event 순서를 명시적으로 표현해야 한다.
• 대표적인 도구는 다음과 같다.
  • condition variable
  • semaphore
  • join
  • barrier
• 예를 들어 “초기화가 끝난 뒤 사용해야 한다”는 조건은 다음처럼 표현한다.
  • initialized flag를 둔다.
  • 사용자는 initialized == 1이 될 때까지 기다린다.
  • 초기화 thread는 initialized = 1로 바꾸고 signal한다.
• condition variable을 쓸 때는 반드시 state variable과 mutex를 함께 사용해야 한다.
• CV signal은 history가 없기 때문에 flag 없이 signal만 쓰면 lost wakeup이 생길 수 있다.
• 따라서 ordering bug를 고칠 때는 event 자체보다 event를 나타내는 state를 보호하는 것이 중요하다.

Deadlock 해결 전략

• deadlock을 줄이는 실용적인 전략은 다음과 같다.
• 첫째, lock을 가능한 한 적게 잡는다.
  • 불필요한 nested lock을 피한다.
• 둘째, lock hold time을 줄인다.
  • lock을 잡은 채 오래 걸리는 작업을 하지 않는다.
• 셋째, lock order를 정한다.
  • 모든 code path가 같은 순서로 lock을 잡게 한다.
• 넷째, 필요하면 trylock을 사용한다.
  • 실패하면 들고 있던 lock을 풀고 retry한다.
• 다섯째, lock-free나 wait-free 구조를 고려한다.
  • 단, 복잡도가 높으므로 신중해야 한다.
• 여섯째, lock order와 lock의 보호 대상 data를 문서화한다.
  • 어떤 lock이 어떤 invariant를 보호하는지 명확해야 한다.
• 가장 현실적인 방법은 lock ordering을 정하고 지키는 것이다.

Deadlock Prevention Summary

• Mutual exclusion 제거
  • 가능하면 lock-free 또는 atomic primitive를 사용한다.
• Hold-and-wait 제거
  • 필요한 lock을 한 번에 모두 잡는다.
  • meta lock을 사용할 수 있다.
• No preemption 제거
  • trylock 실패 시 잡고 있던 lock을 풀고 다시 시도한다.
• Circular wait 제거
  • 모든 lock에 global ordering을 부여하고 항상 같은 순서로 잡는다.

Summary

• 이 단원은 concurrency bug의 대표 유형을 다룬다.
• 주요 bug는 다음 세 가지다.
  • atomicity bug
  • ordering bug
  • deadlock
• atomicity bug는 함께 실행되어야 하는 코드가 중간에 끊겨서 발생한다.
• atomicity bug는 lock으로 critical section을 보호해 해결할 수 있다.
• ordering bug는 특정 작업 순서가 보장되지 않아서 발생한다.
• ordering bug는 condition variable이나 semaphore로 event ordering을 보장해 해결할 수 있다.
• deadlock은 process/thread들이 서로의 resource를 기다리며 영원히 멈추는 상태다.
• deadlock의 네 가지 필요조건은 다음과 같다.
  • mutual exclusion
  • hold and wait
  • no preemption
  • circular wait
• deadlock prevention은 이 네 조건 중 하나를 제거하는 방식이다.
• mutual exclusion을 없애려면 lock-free atomic primitive를 사용할 수 있다.
• hold-and-wait을 없애려면 필요한 resource를 한 번에 요청하게 할 수 있다.
• no preemption을 완화하려면 trylock 실패 시 들고 있던 resource를 풀고 retry할 수 있다.
• circular wait을 막으려면 total lock ordering을 정하면 된다.
• 실제로 가장 실용적인 deadlock prevention 방법은 lock ordering이다.
• 이 단원의 핵심은 concurrency bug는 timing에 따라 드러나기 때문에 찾기 어렵고, 따라서 처음부터 atomicity, ordering, lock order를 명확히 설계해야 한다는 것이다.