Condition Variables(조건 변수): for synchronization

Jin Hur·2021년 11월 23일

[Linux] Concurrency: 쓰레드, 락, 세마포어 그리고 데드락

목록 보기

6/7

reference: https://pages.cs.wisc.edu/~remzi/OSTEP/

조건변수(condition variables)

Locks: Mutual exclusion(상호 배제)의 대표적인 기법 중 하나.
- mainly focusing on mutual exclusion(오직 상호 배제에만 초점을 둠)
Condition variables
- synchronization(동기화)에 focusing
- 동기화는 mutex를 기본적으로 내포하면서, 순서 관계까지 보장하는 것이다.
- 특히 어떠한 조건의 만족 여부에 따라 동작이 달라진다.
- ex) 1) whether a child has completed. 2) whether a buffer is filled

자식 / 부모 쓰레드 동기화 문제

// 자식 쓰레드
void *child(void *arg){
    printf("child \n");
    // XXX how to indicate we are done?
    return NULL;
}

// 메인 쓰레드
int main(int argc, char *argv[]){
    printf("parent: begin \n");
    pthread_t c;
    // 자식 쓰레드 생성
    pthread_create(&c, NULL, child, NULL);
    // XXX how to wait for child?
    printf("parent: end \n");
    return 0;
}

자식 쓰레드 수행 -> 부모 쓰레드 수행 <- 순서 관계를 어떻게 보장할 수 있을까?

solution 1. busy waiting with a variable

valatile int done = 0;
// 변수를 선언할 때 앞에 volatile을 붙이면 
// 컴파일러는 해당 변수를 최적화에서 제외하여 
// 항상 메모리에 접근하도록 만듬
// https://dojang.io/mod/page/view.php?id=749

// 자식 쓰레드
void *child(void *arg){
    printf("child \n");
    // 자식 쓰레드 작업 수행..
    // ..
    done = 1;
    return NULL;
}

// 메인 쓰레드
int main(int argc, char *argv[]){
    printf("parent: begin \n");
    pthread_t c;
    // 자식 쓰레드 생성
    pthread_create(&c, NULL, child, NULL);
    
    while(done == 0);	// spin
    
    printf("parent: end \n");
    return 0;
}

일반적으로 잘 동작하나 spin waiting 방식이기에 CPU 자원의 낭비가 발생할 것이며, 때때로 다중 자식 쓰레드가 존재할 때 기대하는 결과를 도출하지 못할 수 있다.

solution 2. Condition variable

조건에 만족하지 못하여 수행할 수 없는 쓰레드는 큐(OS가 관리)에 메달려 대기상태가 된다. 즉 CPU 낭비를 줄일 수 있다.
어떤 다른 쓰레드로 인해 상태가 변화되고, 이에 따라 조건이 충족되어 실행될 수 있는 대기 쓰레드는 신호를 받아 다시 수행될 수 있다. (some other thread, when it changes state, can then wake one(or more) of those waiting threads and thus allow then to continue.)
pthread API
- pthread_cond_wait(pthread_cond_t c, pthread_mutex_t m);
- pthread_cond_signal(pthread_cond_t *c);

조건변수 예제

int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void thr_exit(){
    pthread_mutex_lock(&m);
    done = 1;
    pthread_cond_signal(&c);	// 자신의 작업이 끝나면 signal을 보냄 
    pthread_mutex_unlock(&m);
    
}
void thr_join(){
    pthread_mutex_lock(&m);
    while(done == 0)
        pthread_cond_wait(&c, &m);	// wait 호출 시 조건변수와 mutex변수 둘 다 전달
        							// 메인 쓰레드가 잡은 락은 암묵적으로 unlock 된다. 
    return NULL;
}

void *child(void *arg){
    printf("child \n");
    thr_exit();
    return NULL;
}

int main(int argc, char *argv[]){
    printf("parent: begin \n");
    pthread_t p;
    pthread_create(&p, NULL, child, NULL);
    thr_join();
    printf("parent: end \n");
    return 0;
}

1) 메인 쓰레드에서 자식 쓰레드를 생성하고 문맥교환이 발생하지 않음을 가정한다.

2) 메인 쓰레드는 thr_join() 내에서 락을 걸고 수행 흐름을 이어나가려 하지만 조건(done==0)에 만족하지 않고 wait 함수가 호출하게 된다. 이때 전역에 선언된 mutex변수와 컨디션 변수를 전달한다. 이 때 메인 쓰레드가 잡은 락은 암묵적으로 풀리게 된다.

3) 메인 쓰레드는 대기 상태로 빠지고, 자식 쓰레드가 문맥교환되어 수행된다. 자식 쓰레드는 자신의 수행 작업을 마친 후 the_exit() 내부로 들어간다. done변수를 1로 변경하고(메인 쓰레드 수행 조건) 조건 변수를 통해 시그널을 보낸다. 이전에 동일한 조건 변수를 가지고 sleep 상태로 빠진 쓰레드에 신호를 보내는 것이다.

4) 신호를 받은 메인 쓰레드가 깨어나 다시 수행할 수 있다. 이때는 조건도 충족되있는 상태이다. (신호에 깨어난 다는 것은 sleep상태에서 ready 상태로 변한다는 것이다. sleep -> run 이 아니다.)

=> 결국 자식 쓰레드와 메인 쓰레드간의 동기화(순서 관계)가 보장된 것이다.
-> 자식의 작업 수행 후 부모의 작업 수행

생산자 소비자 문제(producer/consumer problem)

a.k.a Bounded buffer problem
시나리오
- 생산자는 데이터를 생성하여 버퍼에 담는다. 버퍼는 일종의 메모리 공간이다. 배열, 링크드 리스트 등
- 소비자는 버퍼에 있는 데이터를 꺼내서 소비한다.
- ex) DB 서버, 스트리밍 서버, pipe, cache 등은 생산자/소비자 시나리오로 동작한다.
Issue
- Mutual exclusion이 보장되어야 한다. 예를 들어 하나의 아이템을 두고 두 소비자가 동시에 가져가려 할 수 있다.
- Empty case(버퍼가 빈 상태)를 해결해야 한다.
- Full case(버퍼가 꽉 찬 상태)를 해결해야 한다.
  
  => 이러한 이슈를 조건변수 또는 세마포어를 통해 해결한다.

생산자 소비자 문제 솔루션

생산자/소비자 문제의 기본적 구조

shared buffer: put(), get() interfaces
producer/consumer: producer(), consumer()

싱글 버퍼의 예

int buffer;
int count = 0; 	// 처음엔 empty란 의미

void put(int value){
    assert(count == 0);	// assert 함수: 조건이 만족되지 않으면 에러를 출력하고 종료시킨다.
    // 'count == 0'이 거짓이란 것은 싱글 버퍼가 이미 차있다는 뜻이다.
    // 버퍼가 이미 차 있을 때에는 새로운 값을 put 할 수 없다. 
    
    count = 1;
    buffer = value;	// 버퍼에 데이터 PUT
}
int get(){
    assert(count == 1);
    // 'count == 1'이 거짓이란 것은 싱글 버퍼가 비어있다는 뜻이다.
    // 비어있는 버퍼에서 무언가를 가져온다는 것은 어불성설이다. 
    
    count = 0; 
    return buffer;
}

// 생산자 함수
void *producer(void *arg){
    int i;
    int loops = (int) arg;
    for(i=0; i<loops; i++){
        put(i);
    }
}
// 소비자 함수
void *consumer(void *arg){
    int i;
    while(1){
        int temp = get(i);
        // 데이터 소비
        printf("%d \n", temp);
    }
}

생산자 쓰레드와 소비자 쓰레드가 한번이라도 순서 관계가 맞추어지지 않는다면 assert 함수에 걸려 프로그램이 에러를 출력하고 종료될 것이다. 따라서 순서 관계를 보장해주어야 한다.

cond_t cond;	// for ordering
mutex_t mutex;	// for mutex

...
...

// 생산자 함수
void *producer(void *arg){
    int i;
    int loops = (int) arg;
    for(i=0; i<loops; i++){
        pthread_mutex_lock(&mutex);
        // put 하기 전에 조건을 판단 
        if(count == 1)
            pthread_cond_wait(&cond, &mutex);
        put(i);
        pthread_cond_signal(&cond);
        pthread_mutex_unlock(&mutex);
    }
}
// 소비자 함수
void *consumer(void *arg){
    int i;
    int loops = (int)arg;
    for(i=0; i<loops; i++){
        pthread_mutex_locK(&mutex);
        if(count == 0)
            pthread_cond_wait(&cond, &mutex);
        int temp = get();
        pthread_cond_signal(&cond);
        pthread_mutex_unlock(&mutex);
        printf("%d \n", temp);
    }
}

solution 1의 문제점

생산자, 소비자가 각각 하나씩이라면 비교적 잘 동작.
하지만 2개 이상부터 문제가 발생할 수 있다.

신호를 보낸다는 것은 조건변수 전달하고 sleep에 빠진 쓰레드를 다시 ready 상태로 바꿀 뿐이다. 따라서 ready 상태에 여러 쓰레드가 존재할 때 어떤 쓰레드가 먼저 수행될지는 알 수 없다.
즉, 깨어난 쓰레드가 시그널을 받고 바로 수행된다는 보장이 없다.

solution 2. while instead of if

cond_t cond;	// for ordering
mutex_t mutex;	// for mutex

...
...

// 생산자 함수
void *producer(void *arg){
    int i;
    int loops = (int) arg;
    for(i=0; i<loops; i++){
        pthread_mutex_lock(&mutex);
        // while instead of if
        // 조건을 한번 더 확인하는 장치라 볼 수 있다. 
        //if(count == 1)
        //    pthread_cond_wait(&cond, &mutex);
        while(count == 1)
        	pthread_cond_wait(&cond, &mutex);
        put(i);
        pthread_cond_signal(&cond);
        pthread_mutex_unlock(&mutex);
    }
}
// 소비자 함수
void *consumer(void *arg){
    int i;
    int loops = (int)arg;
    for(i=0; i<loops; i++){
        pthread_mutex_locK(&mutex);
        //if(count == 0)
        //    pthread_cond_wait(&cond, &mutex);
        while(count == 0)
            pthread_cond_wait(&cond, &mutex); 
        int temp = get();
        pthread_cond_signal(&cond);
        pthread_mutex_unlock(&mutex);
        printf("%d \n", temp);
    }
}

solution 2의 문제점 => "Dead Lock(교착 상태)" 발생 가능

'생산자 -> 소비자 -> 생산자 -> 소비자'와 같이 동기화를 맞추며 수행되면 문제가 없지만, '소비자1->소비자2->생산자->소비자1->소비자2->,,와 같이 수행되면 교착 상태가 발생할 수 있다.

먼저 큐에 메달린 Tc2 쓰레드가 먼저 깨어나서 문제가 발생한 것이다.

=> 해결책은 서로 다른 조건 변수를 쓰는 것이다! (생산자 쓰레드용 조건 변수, 소비자 쓰레드용 조건 변수)

교착 상태(dead lock)
운영체제 혹은, 또는, 그리고 소프트웨어의 잘못된 자원 관리로 인하여 둘 이상의 프로세스(또는 쓰레드)가 퍼지는 현상
(source: https://namu.wiki/w/%EB%8D%B0%EB%93%9C%EB%9D%BD)

solution 3(final). two condition variables

시그널을 보낼 쓰레드를 구분한다.
"indicate explicitly which thread I want to send my signal."

cond_t empty, fill;	// 두 개의 조건 변수 사용
                        // 생산자용, 소비자용
mutex_t mutex;	// for mutex

...
...

// 생산자 함수
void *producer(void *arg){
    int i;
    int loops = (int) arg;
    for(i=0; i<loops; i++){
        pthread_mutex_lock(&mutex);
        // while instead of if
        // 조건을 한번 더 확인하는 장치라 볼 수 있다. 
        while(count == 1)
        	pthread_cond_wait(&empty, &mutex);
        put(i);
        pthread_cond_signal(&fill);
        pthread_mutex_unlock(&mutex);
    }
}
// 소비자 함수
void *consumer(void *arg){
    int i;
    int loops = (int)arg;
    for(i=0; i<loops; i++){
        pthread_mutex_locK(&mutex);
        while(count == 0)
            pthread_cond_wait(&fill, &mutex); 
        int temp = get();
        pthread_cond_signal(&empty);
        pthread_mutex_unlock(&mutex);
        printf("%d \n", temp);
    }
}

버퍼가 가득 차 있다면 생산자 쓰레드는 while 루프에 들어가 신호를 받을 때까지 대기한다(if 구현과의 차이점). 만약 생산자 쓰레드가 버퍼에 생산하면 모든 대기하는 쓰레드(동일한 조건변수를 가진 상황)에 신호를 보내는 것이 아니라 대기중인 '소비자' 쓰레드에게만 신호를 보낸다(fill 조건 변수를 가지고 대기하던 쓰레드).

Multiple buffers cases with final solution

int buffer[MAX];
int fill_ptr = 0;
int use_ptr = 0;
int count = 0;

void put(int value){
	buffer[fill_ptr] = value;
    fill_ptr = (fill_ptr + 1)%MAX;	// 원형 버퍼 방식
    count++;
}
int get(){
    int temp = buffer[use_ptr];
    use_ptr = (use_ptr + 1)%MAX;
    count--;
    return temp;
}

cond_t empty, fill;	// 두 개의 조건 변수 사용
mutex_t mutex;

void *producer(void *arg){
    int i;
    int loops = (int)arg;
    for(i=0; i<loops; i++){
        pthread_mutex_lock(&mutex);
        while(count == 1)
            pthread_cond_wait(&empty, &mutex);
        put(i);
        pthread_cond_signal(&fill);
        pthread_mutex_unlock(&mutex);
    }
}

void *consumer(void *arg){
    int i;
    for(i=0; i<loops; i++){
        pthread_mutex_lock(&mutex);
        while(count == 0)
            pthread_cond_wait(&fill, &mutex);
        int temp = get();
        pthread_cond_signal(&empty);
        pthread_mutex_unlock(&mutex);
        printf("%d \n", temp);
    }
}

(+) pthread_cond_broadcast: Covering Conditions

Memory allocation library for multi-thread env.
no free space, T1 asks 100B, T2 asks 10B, Both sleep -> T3 free 50B -> T2 wake up: Okay, but T1 wake up: sleep again, T2 alse sleeps => Dead Lock!

pthread_cond_signal()로 하나의 쓰레드만 깨우는 것이 아니라 pthread_cond_broadcast()로 sleep 중인 모든 쓰레드를 깨운다.

// how many bytes of the head are free?
int bytesLeft = MAX_HEAP_SIZE;

// need lock and cond 
cond_t c;
mutex_t m;

void *allocate(int size){
	pthread_mutex_lock(&m);
    while(bytesLeft < size)
        pthread_cond_wait(&c, &m);
    void *ptr = // get mem from heap (ex, malloc)
    bytesLeft -= size;
    pthread_mutex_unlock(&m);
    return ptr;
}

void free(void *ptr, int size){
	pthread_mutex_lock(&m);
    bytesLeft += size;
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
}

Jin Hur

이전 포스트

(+) Summary

다음 포스트

Condition Variables(조건 변수): for synchronization

[Linux] Concurrency: 쓰레드, 락, 세마포어 그리고 데드락

조건변수(condition variables)

자식 / 부모 쓰레드 동기화 문제

solution 1. busy waiting with a variable

solution 2. Condition variable

조건변수 예제

생산자 소비자 문제(producer/consumer problem)

생산자 소비자 문제 솔루션

solution 1의 문제점

solution 2. while instead of if

solution 2의 문제점 => "Dead Lock(교착 상태)" 발생 가능

solution 3(final). two condition variables

Multiple buffers cases with final solution

(+) pthread_cond_broadcast: Covering Conditions

(+) Summary

Semaphore(세마포어): structure for concurrency control

0개의 댓글

Condition Variables(조건 변수): for synchronization

[Linux] Concurrency: 쓰레드, 락, 세마포어 그리고 데드락

조건변수(condition variables)

자식 / 부모 쓰레드 동기화 문제

solution 1. busy waiting with a variable

solution 2. Condition variable

조건변수 예제

생산자 소비자 문제(producer/consumer problem)

생산자 소비자 문제 솔루션

solution 1. considering sharing

solution 1의 문제점

solution 2. while instead of if

solution 2의 문제점 => "Dead Lock(교착 상태)" 발생 가능

solution 3(final). two condition variables

Multiple buffers cases with final solution

(+) pthread_cond_broadcast: Covering Conditions

(+) Summary

Semaphore(세마포어): structure for concurrency control

0개의 댓글