[운영체제] Condition Variables

전윤혁·2024년 12월 21일
OSconcurrency
0

OS

목록 보기
16/18

앞서 Lock에 대해 알아보며, Condition Variable을 "대기열"이라고 표현했었는데, 용어와 뜻이 일치되지 않아 와닿지 않을 수 있다. 이번 글에서는 Condition Variable에 대해 보다 자세히 살펴보자.

1. Condition Variables

용어의 뜻이 Condition Variable인 이유는, 특정 스레드가 실행을 할지 말지 현재의 상황, 즉 Condition을 확인하기 위한 대기열이기 때문이다!

하나의 예시로, 부모 스레드가 자식 스레드의 종료를 기다리는 과정을 살펴보자.

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); // create child
  // XXX how to wait for child?
  printf("parent: end\n");
  return 0;
}

우리가 바라는 실행 결과는 아래와 같다.

parent: begin
child
parent: end

먼저, 부모 스레드가 단순히 공회전을 하며 자식 스레드의 종료를 기다리는 예시는 아래와 같다.

volatile int done = 0;

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); // create child
  while (done == 0)
  	; // spin
  printf("parent: end\n");
  return 0;
}

앞선 글에서 지겹게 설명했듯이, 이는 CPU를 공회전으로 낭비하는 방식이기 때문에 다른 방법이 필요했고, 대신 스레드를 재우는 방법에 대해 Locks 파트에서 알아봤다.

따라서, 특정 조건이 만족될 때까지 스레드가 기다리도록 하고, 조건이 만족되었을 때 기다리고 있는 스레드들을 깨워주는 대기열을 Condition Variable이라고 정리할 수 있을 것 같다.

2. Definition and Routines

Condition Variable을 일종의 큐, 대기열로 이해하며 다음 내용으로 넘어가자.

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);

위는 POSIX 라이브러리에서 스레드를 재우고, 깨우는 함수이다.

pthread_cond_wait은 해당 함수를 호출한 스레드를 재워 큐에 삽입하고, pthread_cond_signal은 큐에 잠들어있는 스레드 중 하나를 깨운다.

주목할 점은, pthread_cond_wait은 인자로 pthread_mutex_t *m를 받지만, pthread_cond_signal은 해당 인자를 받지 않는다는 점이다. wait의 경우 Lock을 반환한 후 잠들어야하기 때문에 mutex를 인자로 받고 있고, signal을 통해 일어난 스레드는 Lock을 다시 얻어야한다.

POSIX 라이브러리를 사용하여 앞선 문제를 해결해보면 아래와 같다.

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);
  Pthread_mutex_unlock(&m);
}

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

void thr_join() {
  Pthread_mutex_lock(&m);
  while (done == 0)
  	Pthread_cond_wait(&c, &m);
  Pthread_mutex_unlock(&m);
}

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;
}

  • 부모 스레드가 자식 스레드를 생성한다.

  • 부모 스레드가 thr_join을 호출하여 자식 스레드가 끝나기(done == 0)를 기다린다.

  • 자식 스레드는 작업이 끝난 후 thr_exit()를 통해 done = 1;로 바꿔주고, Pthread_cond_signal을 호출한다.

  • Pthread_cond_signal을 통해 부모 스레드가 깨어나고, 다시 한번 while문을 통해 done 값을 확인하여, 0이 아닌 경우 실행한다.

만약 자식 스레드가 먼저 실행되는 경우에는 어떨까? 부모 스레드가 잠들기 전 자식 스레드가 Pthread_cond_signal을 호출하면 현재 잠들어있는 스레드가 하나도 없으므로 아무 일도 일어나지 않고, done이 1로 바뀐 후 부모 스레드가 실행되므로 부모 스레드 또한 잠들지 않고 정상적으로 실행되게 된다.

요약하면, 해당 코드는 문제없이 동작한다. 정상적으로 작동할 수 있는 이유를 하나씩 확인해보자.

  1. State Variable: done
    여기서 done은 특정 조건(예시의 경우 자식 스레드의 종료)을 의미하는 State Variable 역할을 수행한다. done이 없다면, 자식 스레드가 먼저 실행되는 경우 부모 스레드는 영원히 잠들게 될 것이다. (쉽게 이해할 수 있으니 과정을 생각해보자!)

  2. Lock
    Lock이 없는 경우에도 물론 정상적으로 작동하지 않을 것이다. 부모 스레드가 Pthread_cond_wait(&c, &m);을 호출하기 직전에 자식 스레드로 컨텍스트 스위칭되어 자식 스레드가 Pthread_cond_signal(&c);을 포함한 모든 작업을 완료한 후, 다시 부모 스레드로 컨텍스트 스위칭되는 경우를 생각해보자. 이 경우 또한 부모 스레드는 영원히 잠들게 될 것이다!

위의 과정이 잘 이해되지 않는다면 Locks 파트의 Wakeup/Waiting Race 부분을 읽어보는 것을 추천한다!

3. The Producer / Consumer (Bound Buffer) Problem

이번에는 흔히 Producer/Consumer, 또는 유한 버퍼 문제로 불리는 문제를 Condition Variable과 Lock을 통해 해결해보도록 하겠다.

먼저 문제 상황에 대해 알아보자. Producer/Consumer 문제란, 데이터를 생성하여 공유 버퍼에 저장하는 생산자(Producer)와, 공유 버퍼에서 데이터를 소비하는 소비자(Consumer) 간 동작이 멀티 스레드 환경에서 정상적으로 동작하게 하기 위한 문제이다.

멀티 스레드 웹 서버를 예시로 생각해보자. 생산자는 HTTP 요청을 작업 큐에 넣고, 소비자는 큐에서 요청을 꺼내 처리한다. 이 과정에서 Race Condition이 발생한다면 각 소비자 스레드가 중복된 요청을 처리하는 등, 여러가지 문제가 생길 수 있을 것이다. 지금부터 단계적으로 Producer/Consumer 문제를 해결해보자.

int buffer;
int count = 0; // initially, empty

void put(int value) {
  assert(count == 0);
  count = 1;
  buffer = value;
}

int get() {
  assert(count == 1);
  count = 0;
  return buffer;
}

버퍼는 위와 같이 가정하자. 버퍼에 값을 넣는 put과 값을 꺼내가는 get 함수는 위와 같고, assert문에서 볼 수 있듯이 count, 즉 현재 버퍼에 있는 데이터의 개수는 1 또는 0이다. (버퍼에 데이터가 있거나, 없거나 두 가지 상태만 존재한다.)

void *producer(void *arg) {
  int i;
  int loops = (int) arg;
  for (i = 0; i < loops; i++) {
  	put(i);
  }
}

void *consumer(void *arg) {
  while (1) {
    int tmp = get();
    printf("%d\n", tmp);
  }
}

생산자와 소비자의 역할은 위와 같다. 생산자의 경우 버퍼에 넣을 데이터의 개수만큼 삽입 작업을 수행하고, 소비자는 끝없이 버퍼로부터 값을 읽고 있다.

이제 위의 코드에 동기화를 구현해보자!

1) Single CV and If Statement

먼저 하나의 CV와 If문을 통해 구현한 결과이다.

int loops; // must initialize somewhere...
cond_t cond;
mutex_t mutex;

void *producer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    Pthread_mutex_lock(&mutex); // p1
    if (count == 1) // p2
      Pthread_cond_wait(&cond, &mutex); // p3
    put(i); // p4
    Pthread_cond_signal(&cond); // p5
    Pthread_mutex_unlock(&mutex); // p6
  }
}

void *consumer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    Pthread_mutex_lock(&mutex); // c1
    if (count == 0) // c2
    	Pthread_cond_wait(&cond, &mutex); // c3
    int tmp = get(); // c4
    Pthread_cond_signal(&cond); // c5
    Pthread_mutex_unlock(&mutex); // c6
    printf("%d\n", tmp);
  }
}

  • 생산자는 버퍼가 차있는 동안 데이터를 생산할 수 없으므로, 소비자가 데이터를 소비할 때까지 wait을 통해 잠든다.

  • 소비자는 버퍼가 비어있는 동안 데이터를 소비할 수 없으므로, 생산자가 데이터를 생산할 때까지 wait을 통해 잠든다.

  • 생산자와 소비자 모두 조건이 만족되는 경우 signal을 통해 잠에서 깨어난다.

단순하다! 하지만 이 해결책은 생산자와 소비자가 각각 1명인 경우에만 유효하다. 생산자와 소비자가 각각 2명인 아래의 경우를 생각해보자. 표가 길어보이지만 별거 없다!

  • Tc1가 먼저 실행되어 값을 가져가려고 했는데, 현재 버퍼가 비어있으므로 잠들었다.

  • 이후 Tp가 실행되어 버퍼에 값을 채우고, 잠들어있는 Tc1을 깨운 후 잠들었다.

  • 이 때 Tc1보다 Tc2가 스케줄링되며, Tc2는 버퍼에 있는 데이터를 소비하였다.

  • Tc1은 깨워진 후 버퍼에 데이터가 있을 것으로 기대하지만, Tc2에 의해 버퍼가 비워진 상태이므로 에러가 발생하게 된다!

Tc2가 새치기를 한게 문제라고 생각할 수 있지만, 문제의 핵심은 if문에 있다. Tc1이 깨어난 후 조건을 재확인하지 않고 실행한 것이 문제!

여기서 Mesa semantics와 Hoare semantics 두 가지 개념을 엿볼 수 있는데, Mesa semantics는 깨워진 스레드가 즉시 실행되지 않을 수도 있다는 약한 보장을 제공하고, Hoare semantics는 깨워진 스레드가 즉시 실행된다는 강한 보장을 제공한다.

대부분의 운영체제는 Mesa semantics 방식을 사용하는데, Hoare semantics는 구현이 복잡하고 성능 비용이 크기 때문이다. 이번 글에서도 Mesa semantics 방식을 기준으로 위의 문제를 해결해보도록 하자.

2) Single CV and While

int loops;
cond_t cond;
mutex_t mutex;

void *producer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    Pthread_mutex_lock(&mutex); // p1
    
    while (count == 1) // p2
    	Pthread_cond_wait(&cond, &mutex); // p3
        
    put(i); // p4
    Pthread_cond_signal(&cond); // p5
    Pthread_mutex_unlock(&mutex); // p6
  }
}

void *consumer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    Pthread_mutex_lock(&mutex); // c1
    
    while (count == 0) // c2
    	Pthread_cond_wait(&cond, &mutex); // c3
    
    int tmp = get(); // c4
    Pthread_cond_signal(&cond); // c5
    Pthread_mutex_unlock(&mutex); // c6
    printf("%d\n", tmp);
  }
}

if문이 문제였으니, if문 대신 while문을 사용하여, 스레드가 잠에서 깨어나더라도 조건을 한 번 더 확인하게 하면 어떨까? 위의 코드는 p2, c2 부분을 while문으로 바꾼 버전이다. 이를 통해 앞선 문제를 해결할 수 있다.

하지만 아직 문제가 남아있다. 아래의 표를 살펴보자.

  • 이번에도 Tc1이 먼저 실행된 후, 현재 버퍼가 비어있으므로 잠들었다.

  • 하지만 이번에는 Tp보다 Tc2가 먼저 실행되면서, Tc2 역시 현재 버퍼가 비어있으므로 잠들었다.

  • 마지막으로 Tp가 실행되어 버퍼에 데이터를 삽입한 후, 잠들어있던 Tc1을 깨웠다.

  • Tc1은 실행 후, 현재 버퍼의 값이 차있는 것을 확인하고, 버퍼에 있는 데이터를 소비하였다. 이후 잠들기 전 큐에서 스레드를 하나 깨웠는데, 이 때 Tp 대신 먼저 잠들었던 Tc2를 깨워버렸다!

  • Tc2는 깨어난 후 현재 버퍼의 값을 확인하는데, 버퍼가 비어있기 때문에 다시 잠들게 된다. 결과적으로, 모든 스레드가 잠들어버리는 상황이 발생해버렸다!

문제가 발생한 이유는 무엇일까? 맞다! 생산자와 소비자는 잠들고, 깨어나는 조건이 상이한데, 이를 무시한 채 하나의 큐에 무작정 집어넣었기 때문에 위와 같은 문제가 발생한 것이다.

3) Single Buffer Producer/Consumer Solution

위의 문제를 해결하기 위해, 하나가 아니라 두 개의 Condition Variable이 필요하다. 수정된 코드는 아래와 같다.

cond_t empty, fill;
mutex_t mutex;

void *producer(void *arg) {
  int i;
  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 tmp = get();
    Pthread_cond_signal(&empty);
    Pthread_mutex_unlock(&mutex);
    printf("%d\n", tmp);
  }
}

수정된 코드에서는 두 개의 CV인 empty와 fill이 존재한다. 생산자의 경우 현재 버퍼가 가득 차있다면 버퍼가 비기를 바라는 empty 대기열에서, 소비자의 경우 현재 버퍼가 비어있다면 차기를 바라는 fill 대기열에서 잠들게 된다.

4) Final Producer/Consumer 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 tmp = buffer[use_ptr];
  use_ptr = (use_ptr + 1) % MAX;
  count--;
  return tmp;
}

  • 이전에는 버퍼의 크기가 1이었기 때문에 병목을 유발하였는데, 수정된 코드에서는 이를 MAX로 바꾸면서, 여러 스레드가 동시에 버퍼에 값을 읽고 쓸 수 있도록 하였다.

  • 버퍼는 기본적으로 Circular Queue를 사용하기 때문에 버퍼의 양 끝이 연결된 것처럼 사용될 수 있다.

  • 버퍼의 크기가 1이 아님에 따라, assert문도 사라졌다.

cond_t empty, fill;
mutex_t mutex;

void *producer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    Pthread_mutex_lock(&mutex); // p1
    while (count == MAX) // p2
    	Pthread_cond_wait(&empty, &mutex); // p3
    put(i); // p4
    Pthread_cond_signal(&fill); // p5
    Pthread_mutex_unlock(&mutex); // p6
  }
}

void *consumer(void *arg) {
  int i;
  for (i = 0; i < loops; i++) {
    Pthread_mutex_lock(&mutex); // c1
    while (count == 0) // c2
    	Pthread_cond_wait(&fill, &mutex); // c3
    int tmp = get(); // c4
    Pthread_cond_signal(&empty); // c5
    Pthread_mutex_unlock(&mutex); // c6
    printf("%d\n", tmp);
  }
}
  • producer, consumer 코드에서는 버퍼의 크기가 늘어남에 따라 while문의 조건만 바뀌었다.

4. Covering Conditions

마지막 주제로, 메모리 동적 할당 과정에서 스레드를 깨우는 우선순위에 대해 생각해보자.

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

// need lock and condition too
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
  bytesLeft -= size;
  Pthread_mutex_unlock(&m);
  return ptr;
}

void free(void *ptr, int size) {
  Pthread_mutex_lock(&m);
  bytesLeft += size;
  Pthread_cond_signal(&c); // whom to signal??
  Pthread_mutex_unlock(&m);
}

allocate 함수는 메모리 동적 할당을 수행하는데, 현재 남아있는 메모리 공간이 요청된 메모리보다 더 작을 경우, 해당 요청을 한 스레드는 wait을 호출하여 충분한 메모리가 free될 때까지 기다려야 한다.

현재 사용 가능한 메모리가 0 바이트라고 가정할 때, 아래의 3가지 케이스를 고려해보자.

  • 스레드 A: allocate(100) 호출
    메모리 100바이트를 할당하려고 하지만, 현재 메모리가 부족하므로 조건을 기다리며 대기

  • 스레드 B(Thread B): allocate(10) 호출
    메모리 10바이트를 할당하려고 하지만, 동일하게 조건을 기다리며 대기

  • 스레드 C(Thread C): free(50)
    메모리 50바이트를 반환(해제)

스레드 C가 50바이트를 해제한 후, 스레드 A와 B 중 누구를 깨워야 할까?

먼저, 단순히 FIFO 방식을 통해 스레드 A를 깨운다고 해보자. 50바이트가 해제되었지만 여전히 스레드 A는 메모리가 부족하기 때문에 다시 잠들게 되고, 스레드 A와 B가 기약 없이 잠드는 상태가 된다.

이에 대한 해결책으로 Broadcasting을 사용할 수 있다. 이는 pthread_cond_signal()을 pthread_cond_broadcast()로 변경하여 구현할 수 있는데, pthread_cond_broadcast()는 현재 자고 있는 모든 스레드를 깨운다. 각 스레드들은 깨어난 후 다시 조건을 검사하기 때문에, 깨어날 스레드를 제외한 다른 스레드들은 다시 잠들게 된다.

물론, Broadcasting 방식은 모든 스레드를 깨우고, 다시 재우고, 그 과정에서 컨텍스트 스위칭을 유발하기 때문에 오버헤드가 크다는 단점이 있다.

마치며

이번 글에서는 단어부터 애매했던 Conditional Variable에 대해서 알아봤다. 지금까지는 Lock과 Condition Variable을 사용한 동기화 기법을 공부했는데, 다음 글에서는 또다른 방법을 통해 동기화를 구현하는, 세마포어(Semaphore)에 대해 알아보도록 하겠다.

profile
전윤혁
전공/개발 지식 정리
이전 포스트

[운영체제] Lock-based Concurrent Data Structures

다음 포스트

[운영체제] Semaphores

0개의 댓글