Common Concurrency Problems
- What Types Of Bugs Exist?
concurrent program에서 발생할 수 있는 버그는 Non-Deadlock Bug와 Deadlock Bug로 나눌 수 있다.
Non-Deadlock Bugs
Atomicity-Violation Bugs
다음은 MySQL에서 발견된 Atomicity Violation Bug다.
Thread 1::
if (thd->proc_info) {
...
fputs(thd->proc_info, ...);
...
}
Thread 2::
thd->proc_info = NULL;두 스레드 Thread1, Thread2가 같은 구조체 변수인 thd->proc_info에 접근한다.
Thread1의 if 문 이후에 Thread2가 들어오면 critical section을 침범한다.
위 버그를 lock을 이용해 해결해보자.
- Atomicity Violation - Solution(Lock)
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);성능 저하가 있지만 lock을 이용해 mutual exclusive하게 구현해야 한다.
Order-Violation Bugs
다음은 Order-Violation 버그다.
Thread 1::
void init() {
...
mThread = PR_CreateThread(mMain, ...);
...
}
Thread 2::
void mMain(...) {
...
mState = mThread->State;
...
}Thread1이 init을 하고 thread2가 사용하는 것이 정상적인 흐름이나 이를 위한 제어 장치가 전혀 없다.
condition variable을 이용해 버그를 수정해보자.
- Order-Violation - Solution(Condition variable)
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, ...);
// signal that the thread has been created...
pthread_mutex_lock(&mtLock);
mtInit = 1;
pthread_cond_signal(&mtCond);
pthread_mutex_unlock(&mtLock);
...
}
Thread 2::
void mMain(...) {
...
// wait for the thread to be initialized...
pthread_mutex_lock(&mtLock);
while (mtInit == 0)
pthread_cond_wait(&mtCond, &mtLock);
pthread_mutex_unlock(&mtLock);
mState = mThread->State;
...
}순서가 중요한 경우 condition variable을 이용해 해결할 수 있다.
Deadlock Bugs
Thread 1: Thread 2:
lock(L1); lock(L2);
lock(L2); lock(L1);lock을 얻으려 할 때 순서가 바뀌어 있는 경우 deadlock이 발생하기 쉽다.
deadlock이 발생하는 이유는 주로 complex dependencies과encapsulation 때문이다.
Conditions for Deadlock
deadlock은 아래 네 가지 조건을 모두 만족해야 발생한다.
- Mutual exclusion: Threads claim exclusive control of resources that they require (e.g., a thread grabs a lock).
- Hold-and-wait: Threads hold resources allocated to them(e.g.,locks that they have already acquired) while waiting for additional resources (e.g., locks that they wish to acquire). → 하나를 hold하고 다른걸 원하는(wait)하는 상황이어야 한다.
- No preemption: Resources (e.g., locks) cannot be forcibly removed from threads that are holding them. → 자신이 한번 자원을 얻으면 놓지 않아야 한다.
- Circular wait: There exists a circular chain of threads such that each thread holds one or more resources (e.g., locks) that are being requested by the next thread in the chain. → 자원의 hold-and-wait가 cycle을 이루어야 한다.
deadlock을 막는 방법은 Prevention과 Avoidence가 있다.
Prevention
prevent는 네 가지 조건 중 하나만 방지해도 deadlock이 걸리지 않는다.
Circular Wait
circular wait은 자원의 순서를 지정해서 막을 수 있다.
전체의 순서를 지정하는 total ordering은 현실적으로 쉽지 않다.
Linux에서는 partial ordering을 이용해 group 별로 나누어서 순서를 정해준다.
Code: Prevent - circular wait
do something(mutex t *m1, mutex t *m2) if (m1 > m2) { // grab locks in high-to-low address order pthread_mutex_lock(m1); pthread_mutex_lock(m2); } else { pthread_mutex_lock(m2); pthread_mutex_lock(m1); } // Code assumes that m1 != m2 (it is not the same lock)주소값을 이용해 ordering할 수 있다.
Hold-and-wait
hold-and-wait은 hold와 wait을 다른 lock을 이용해 atomic하게 만들 수 있다.
Code: Prevent - hold-and-wait
lock(prevention); lock(L1); lock(L2); ... unlock(prevention);위 처럼 L1과 L2을 얻는 과정을 atomic하게 구현할 수 있다.
No Preemption
trylock()을 이용해 preemtive하게 구현할 수 있다.
Code: Prevent - No Preemption
top: lock(L1); if (trylock(L2) == -1) { unlock(L1); goto top; }L1과 L2를 모두 얻은 경우 critical section으로 들어간다.
만약 L2를 얻지 못하면 L1을 포기하고 재시도 한다.
다른 스레드가 이 스레드의 lock을 preemptive하게 얻을 수 있도록 한다.
하지만 goto top을 무한반복 하게 될 수도 있다.
livelock: T2가 L2를 잡고 안 놔주면 T1은 goto top을 무한 반복한다.(deadlock은 아니다.)
trylock(): lock을 얻으려고 재시도(goto top)
Mutual Exclusion
lock을 쓰지 말고 (No lock) 대신 atomic한 기계어를 만들자
Code: Prevent - Mutual Exclusion
// 기계어 int CompareAndSwap(int *address, int expected, int new) { if (*address == expected) { *address = new; return 1; // success } return 0; // failure } // 기계어 : atomic하게 증가 void AtomicIncrement(int *value, int amount) { do { int old = *value; } while (CompareAndSwap(value, old, old + amount) == 0); } // insert는 어떻게 할까? // 기존 insert void insert(int value) { node_t *n = malloc(sizeof(node_t)); assert(n != NULL); n->value = value; n->next = head; // interrupt 가능 head = n; } // 조금만 lock 걸기 -> 여전히 deadlock 가능 void insert(int value) { node_t *n = malloc(sizeof(node_t)); assert(n != NULL); n->value = value; lock(listlock); // begin critical section n->next = head; head = n; unlock(listlock); // end of critical section } // 해결 void insert(int value) { node_t *n = malloc(sizeof(node_t)); assert(n != NULL); n->value = value; do { n->next = head; // lock없이 atomic하게 } while (CompareAndSwap(&head, n->next, n) == 0); }
wait(lock) free approach: lock을 얻으려 기다리지 않는다.
- Example - Dining philosopher
수정 전 철학자 → 4가지 deadlock condition 다 가짐
수정 후 철학자 → global ordering을 이용해 circular wait를 break.
Avoid
Deadlock Avoidance via Scheduling
스케줄링으로 관련 없는 스레드끼리 스케줄 하는 방법이다.
T1이 다 끝나고 T2를 scheduling한다.
대신 Lock 상황이 아래와 같다면 CPU2로 thread가 몰릴 수 있다.
Example: avoid 2
Detect and Recover
deadlock이 걸린 상태를 detect하고 이를 recover하는 방법이다.
그래프 알고리즘 등으로 detect하고, roll back이나 undo로 recover한다.
하지만 일반적인 프로그램에서는 사용하기 어렵다. (DB에서 사용 가능)
Uploaded by Notion2Tistory v1.1.0