[OS] 30. Condition Variables

급식·2022년 5월 29일

OSTEP

목록 보기

22/24

이전 27장에서 Condition variable을 일종의 'Lock을 얻기 위한 대기열' 정도로 설명했었다.

근데 왜 이 대기열에 condition variable이라 이름을 붙인걸까?

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

부모 스레드가 자식 스레드를 '기다리는' 방법으로 크게 두 가지가 있는데, 첫째는 위와 같이 자식 스레드가 done을 1로 갱신해줄 때까지 그냥 아무 것도 하지 않고 위와 같이 무의미한 공회전을 하는 것이다.

그러나 이게 이전에 다루었듯 (일반적으론) 무지막지하게 비효율적인 접근이므로, 부모 스레드가 자식 스레드를 기다릴 때 ready↔run이 아니라 block(sleep) 상태에서 기다림으로써 무의미한 CPU 점유를 없애는 방법에 대해 28장에서 공부했었다.

그런데! 부모 스레드를 재우기 전에 해결해야할 문제가 있다. 부모 스레드는 어떻게 깨어날 수 있을까?
최초의 접근에서 그랬던 것처럼 heap 공간에서 공유되는 done과 같은 변수를 하나 놓고 부모 스레드가 이걸 검사해서 스스로 깨어나는 것은 말이 안된다. Block 상태에 들어가 있는 스레드는 다른 running thread가 깨워주기 전까지는 스스로 깨어날 수가 없으니까.

그렇기에 필요한 것이 잠들어 있는 스레드를 차레대로 깨워주기 위한 대기열, 달리 말하자면 어떤 조건을 만족할 때까지 스레드가 잠든 상태로 대기하기 위한 큐가 있어야 lock과 함께 쓰여 비로소 의도한대로 잘 작동하는 멀티 스레드 프로그램을 작성할 수 있을 것이다.

30.1 Definition and Routines

Condition variable(이하 condVar와 혼용)은 앞서 언급했듯 일종의 큐로써, 어떤 조건이 만족될 때까지 특정 스레드가 잠든 상태로 대기하거나 외부에서 특정 조건을 만족했을 때 보내주는 신호(signal)를 받아 잠들어 있는 스레드를 하나 깨워서 다시 실행될 수 있도록 해주는 무언가이다.

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

POSIX에서는 condVar와 위와 같이 상호작용할 수 있는데, pthread_cond_wait(이하 wait)은 해당 함수를 호출한 스레드가 특정 조건이 만족되어 신호를 받을 때까지 스스로 잠들고자 할 때, 그리고 pthread_cond_signal(이하 signal)은 condVar에 잠들어 있는 스레드 하나를 깨우고자 할 때(스케줄링 되기를 기다리기 위한 Ready queue로 옮기고자 할 때) 사용한다.

여기서 잠깐! signal과 달리 wait에는 왜 mutex를 넘겨주는 것일까?

먼저 내가 이해한대로 간단하게 설명하자면 잠들 스레드가 global lock을 풀어주지 않은 상태로 잠들어버릴 경우 다른 모든 스레드들이 이 lock에 가로막혀 이러지도 저러지도 못할테니, wait 호출과 동시에 쥐고 있던 lock을 풀어주는 작업까지 atomic하게 하기 위해 mutex를 인자로 넘겨주는 것이다.

그럼에도 번역본에서 너무 중요하니까 10번만 소리 내서 읽고 넘어가라고 강조하는 문장이 있어서 ㅋㅋㅋ 그대로 옮겨보겠다.

wait()가 호출될 때 mutex는 잠겨있었다고 가정한다. wait()의 역할은 락을 해제하고 호출한 쓰레드를 재우는 것이다. 어떤 다른 쓰레드가 시그널을 보내어 쓰레드가 깨어나면, wait()에서 리턴하기 전에 락을 재획득해야 한다.

흠,, 한 문장씩 끊어서 이해해보자.

wait()가 호출될 때 mutex는 잠겨있었다고 가정한다.

이를 달리 표현하자면, wait과 signal이 항상 critical section 안에서 호출됨을 전제로 한다고 할 수 있을 것 같다.

wait()의 역할은 락을 해제하고 호출한 쓰레드를 재우는 것이다.

위에서 wait이 critical section 안에 있음을 가정했으므로, 당연히 mutex lock이 걸려 있는 상태일 것이다. 따라서 '락을 해제한다'는 말도 납득할 수 있고, 해당 함수를 호출한 쓰레드를 재우는 것 역시 이 함수의 본 목적이므로 이 또한 옳다.

어떤 다른 쓰레드가 시그널을 보내어 쓰레드가 깨어나면, wait()에서 리턴하기 전에 락을 재획득해야 한다.

첫째로, wait을 호출한 함수는 마치 기나긴 루프 속에 갇힌 것처럼 반환되지 않은 상태로 머물러 있게 되는데, 외부에서 특정 조건을 만족해서 condVar에 signal을 보내주는 시점에 비로소 함수가 반환되어 다음 명령을 실행할 수 있게 된다.

그 다음 문장은 사실 나도 잘 이해가 안되는데(...) 번역본에서 '조건이 만족되어 잠에서 깨어났더라도 락을 획득하지 못하면 다시 sleep 상태로 들어간다'고 달리 표현해 놓은 쪽이 오히려 더 직관적인 것 같다.

여하튼 마지막 문장은 잠시 가슴 속에 품어두고, 위의 POSIX API대로 어떻게 스레드 간의 실행 순서를 보장할 수 있을지 코드로 직접 구현한 예시를 먼저 살펴보자.

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

위와 같은 코드에서는 어떠한 실행 흐름이 발생할 수 있을까?

Case 1

부모 스레드가 자식 스레드를 생성한다.
이어서 부모 스레드가 thr_join을 호출해 자식 스레드가 끝나기를 기다린다. (done이 0이므로)
자식 스레드가 스케줄링 되어 작업을 마친 후 thr_exit을 호출해 done을 1로 바꿔주고 condVar c에 signal을 보내준다.
이때 부모 스레드가 깨어났으므로 Pthread_cond_wait가 반환되고, 다시 while문의 조건식으로 돌아가 done의 값을 확인한다.
이때 done이 0이면 다시 잠들고, 1이면 thr_join이 반환되어 자식 스레드를 기다리는 것을 끝마친다.

Case 2

부모 스레드가 자식 스레드를 생성한다.
스케줄러에 의해 부모 스레드가 CPU에서 내려오고 자식 스레드가 실행된다.
자식 스레드는 done을 1로 갱신하고, condVar에 신호를 보낸다.
그런데! 부모 스레드가 잠들지 않은 상태에서 자식 스레드로 넘어왔기 때문에 잠들어 있는 스레드가 없어 condVar에 어떠한 상태 변화도 발생하지 않는다.
자식 스레드의 작업이 끝났으므로 부모 스레드가 실행되어 thr_join이 호출된다.
이때! done이 자식 스레드에 의해 1로 초기화 되었으므로 while문의 조건식이 거짓이 되어 그냥 바로 반환된다.

결론적으로는 두 케이스 모두 제대로 작동하는데, 눈여겨봐야 할 부분이 하나 있다.
왜 Pthread_cond_wait이 반환된 직후에 다음 코드로 넘어가는게 아니라, 다시 한 번 while문의 조건식으로 반복해서 평가받도록 하는걸까?

이 부분은 스레드가 2개뿐인 단순한 예제로 설명하는게 오히려 더 복잡할 것 같으니, 책의 흐름대로 뒤쪽에서 이어서 살펴보겠다.

뭐든 잃어봐야 소중함을 아는 법.
각각 자식 스레드의 작업이 끝났음을 알리는 thr_exit()과 부모 스레드가 자식 스레드를 기다리겠다는 신호를 보내는 thr_join의 구성 요소를 하나씩 빼보며 각 요소의 역할을 깊이 이해해보겠다.

1. No Status variable : No "done"

Condition variable이 일종의 대기열 역할을 한다면, done과 같은 status variable은 "특정 조건이 참이 될 때까지 대기한다"는 명제에서 "특정 조건"을 확인하는데 쓰인다.

void thr_exit() {
  Pthread_mutex_lock(&m);
  Pthread_cond_signal(&c);
  Pthread_mutex_unlock(&m);
}

void thr_join() {
  Pthread_mutex_lock(&m);
  Pthread_cond_wait(&c, &m);
  Pthread_mutex_unlock(&m);
}

이 status variable done을 exit/join에서 빼면 과연 제대로 작동할까? 생각해보자.

case 1-1. Success

부모 스레드가 자식 스레드를 생성한다.
이어서 부모 스레드가 thr_join의 Pthread_cond_wait까지 실행해 스스로 잠든다.
자식 스레드가 주어진 작업을 마치고 thr_exit을 호출하여 주어진 모든 명령어를 실행, 부모 스레드에 signal을 보낸다.
그럼 부모 스레드가 Pthread_cond_wait에서 반환되어 thr_exit을 모두 정상 처리한다.

case 1-2. Failed

부모 스레드가 자식 스레드를 생성한다.
자식 스레드로 바로 context switching 되어, thr_exit가 모두 실행된다.
이때 condVar에 잠들어 있는 스레드가 없으므로, 아무 스레드도 깨어나지 않는다.
다시 부모 스레드로 context switching되어 thr_join을 호출한다.
이때 Pthread_cond_wait에 의해 부모 스레드가 잠들게 되는데, 이를 깨워줄 방법이 없으므로 실패!

위의 두 케이스를 보고 exit/join에서 status variable의 역할을 생각해낼 수 있어야 한다.
실패한 1-2 케이스에서 만약 이미 자식 스레드가 작업을 마쳤음을 표시할 수 있었다면 조건문 등을 사용해 단계 5에 아예 진입하지 않았을 것인데, 이 흔적을 남기는 수단인 done이 status variable이므로 이것이 exit/join의 구현에 필수적임을 알 수 있다.

2. No Lock

void thr_exit() {
  done = 1;
  Pthread_cond_signal(&c);
}

void thr_join() {
  if (done == 0)
  	Pthread_cond_wait(&c);
}

그럼 Lock은? lock은 진짜 꼭 필요한 걸까?
Lock이 없는 경우 status variable인 done에 대한 race condition이 발생해 우리가 의도한대로 작동하지 않을 것이다.

Error case

부모 스레드가 자식 스레드를 생성한다.
부모 스레드가 thr_join을 호출해 실행하던 중, if (done == 0)을 evaluate해 해당 조건문이 참이므로 Pthread_cond_wait으로 넘어갈 준비를 마쳤다.
이때! 이 부분이 critical section이 아니므로 자식 스레드로 context switching 되어 버렸다.
자식 스레드가 주어진 작업을 모두 마치고, thr_exit를 완전히 실행했다. 즉, done을 1로 바꿔준 다음 condVar에 신호를 보냈다. (물론 잠들어있었던 스레드가 없으므로 아무 일 없이 넘어가지만)
자식 스레드가 끝났으므로 부모 스레드로 다시 context switching 되어 Pthread_cond_wait을 호출해버리면, 이젠 다시 done을 검사할 방법이 없기 때문에 잠드는 것을 피할 수도, 이를 깨워줄 스레드도 존재하지 않아 부모 스레드가 영원히 잠들게 된다.

이렇듯 exit/join을 제대로 활용하기 위해서는 해당 함수를 구성하는 signal/wait이 critical section 안에 있어야 하며, status variable을 적절히 활용하여 이미 자식 스레드의 작업이 끝났음을 부모 스레드에게 signal 외의 흔적을 제대로 남길 수 있어야 한다.

30.2 The Producer/Consumer (Bounded Buffer) Problem

Condition variable과 lock을 사용해서 부모-자식 스레드 사이의 실행 순서를 제어하는 문제를 해결했었다.

이번 절에서는 흔히 Producer/Consumer 문제, 또는 Bounded buffer(유한 버퍼) 문제로 불리우는 문제를 CondVar와 lock으로 해결해볼 것이다. 참고로 탈지구급 괴수 다익스트라가 그 유명한 세마포어를 발명하게 된 계기가 된 문제라고 한다. 덜덜,,

개요만 보면 간단하다. 데이터를 만들어서 공통의 버퍼에 넣어 놓는 생산자(producer) 스레드가 여러개, 이 버퍼에 들어 있는 데이터를 가져다 쓰는 소비자(consumer) 스레드가 여러개 있는 상황에서 문제 없이 잘 실행되도록 만들어주면 된다!

크기가 정해져 있는 생산자/소비자 스레드의 공동 자원인 유한 버퍼는 각 스레드들이 동시에 접근하기를 원할 수 있으므로 당연히 race condition이 발생할 수 있는데, 책에는 멀티 스레드 웹 서버에서 클라이언트로 들어온 HTTP 요청을 handler 스레드가 받을 수 있도록 작업 큐에 넣어 놓고, 각각의 handler 스레드가 이걸 가져다가 처리하는 방식을 예로 들었다. 근데 여기서 이 버퍼에 대한 race condition을 해결하지 못한다면 막 요청을 동시에 두 handler 스레드가 받아서 응답을 두번씩 보내려고 하는 이상한 일이 발생할 수 있겠지?

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문을 보면 알겠지만 버퍼의 크기가 1로 고정되어 있으므로, 버퍼에는 값이 [있거나/없는] 두 가지의 상태만 있을 수 있음을 알 수 있다.

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

그럼 일단 간단하게 이 put/get을 사용하는 생산자 스레드와 소비자 스레드가 실행할 루틴을 위와 같이 정의해보자.

producer는 값을 버퍼에 넣어 놓을 횟수를 전달받아 일정 횟수만큼 값을 버퍼에 저장하고, consumer는 끝없이 버퍼로부터 값을 읽어서 출력하도록 구현되어 있다.

물론~~ 공부를 성실히 했다면 딱 느낌이 오겠지만 producer와 consumer 사이의 buffer에 대한 동기화가 제대로 되어 있지 않기 때문에 원하는대로 잘 작동하지 않을 것이다. 개선이 필요하다!

A Broken Solution

그럼 배웠던대로 condVar과 lock을 사용해서 이 문제를 해결해보자.

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

선요약을 해보자면 producer는 버퍼가 차있으면 할 수 있는 일이 없으므로 잠들었다가 consumer가 값을 빼서 버퍼가 비었을 때 깨어나며, consumer는 버퍼가 비어 있으면 할 수 있는 일이 없으므로 잠들었다가 producer가 값을 넣어서 버퍼가 차면 깨어나도록 구현한 것이다. 이걸 좀 더 자세히 써보자면,,

producer

producer의 경우 buffer가 차있으면(count == 1) 할 수 있는 일이 없으므로 condVar cond에 스스로를 등록한 뒤 잠들고(Pthread_cond_wait), 외부에서 이 스레드를 깨워주면(consumer가 값을 필요로 하면) 일어나서 값을 넣어 놓은 다음 cond에 신호를 보내 다시 consumer를 깨워주는 일을 loops번 수행한다.

consumer

consumer의 경우 buffer가 비어 있으면(count == 0) 할 수 있는 일이 없으므로 condVar cond에 스스로를 등록한 뒤 잠들고(Pthread_cond_wait), 외부에서 이 스레드를 깨워주면(producer가 값을 빼주기를 기다리면) 일어나서 값을 뺀 다음 cond에 신호를 보내 다시 producer를 깨워주는 일을 loops번 수행한다.

참고로 이전 절에서 살펴보았듯 이 모든 작업들이 mutual exclusive 하게 실행되어야 하므로 공통의 lock을 작업 전후에 acquire/free해주고 있다.

Thread trace를 해보면 알겠지만, producer가 먼저 스케줄링 되든, consumer가 먼저 스케줄링 되든 각각 1개의 producer/consumer만 있는 상황에서는 이 솔루션이 유효하다. 복잡하게 생각할 것 없이 생산자는 값을 넣을 수 없으면 빌 때까지 기다리고, 소비자는 값을 뺄 수 없으면 찰 때까지 기다리기만 하면 되니까!

그런데 producer든 consumer든 갯수가 2개 이상이 되면 문제가 발생한다. 여기서는 1개의 producer(Tp), 2개의 consumer(Tc1, Tc2)를 가정해보자.

Tc1이 먼저 실행되어 버퍼에서 값을 가져가려고 시도했는데, 버퍼가 비어 있으므로 스스로 sleep하며 lock을 풀어준다.
그 다음으로 Tp가 실행되어 값을 채워주고, 잠들어 있는 Tc1을 깨워줌으로써 Tc1이 condVar에서 Ready Queue로 이동된다.
Tp는 할 일을 다 마쳤으므로 다시 for문의 시작 부분으로 되돌아가는데, 이때 버퍼가 차있으므로 Tp가 sleep 상태에 들어간다.
근데 이때! 또다른 소비자 Tc2가 실행되어 Tc1 앞에 끼어들었다!
이 Tc2는 버퍼가 차있으니 그냥 값을 빼다가 쓰고, 기다리고 있던 Tc1이 값을 읽으려 하는 시점(c4)에는 값이 버퍼에서 빠져 있으니 assert 문에 의해 오류가 발생한다.

처음에는 Tc1이 먼저 기다렸는데 Tc2가 끼어 들어서 스레드간의 실행 순서가 보장되지 않은게 문제의 핵심인줄 알았는데, 그게 아니라 값이 빠졌는데도 sleep 상태에서 깨어나자마자 값이 여전히 들어 있는지 확인하지도 않고 값을 빼서 쓰려고 한 것이 문제였다.

이렇듯 signal은 그냥 condVar에 잠들어 있는 스레드를 그냥 깨워주는 역할만을 할 뿐 signal이 condVar를 깨워주기 위해 만족시킨 특정 조건이 잠들었다가 일어난 스레드가 다시 기다리던 작업을 바로 실행할 수 있도록 보장해주지는 않는다. 즉, 위와 같이 중간에 다른 스레드가 개입해 잠들어 있는 기다리던 조건을 바꿔놓는 상황이 발생할 수 있다.

이러한 signal을 Mesa semantic이라 하며, 반대로 signal이 깨워 놓은 스레드가 기다리던 작업을 바로 실행할 수 있도록 보장해주는 signal을 Hoare semantic이라 한다. 다만 구현하기가 어려워서 그런지 대부분의 시스템이 Mesa semantic을 사용하며, 이번 포스트에서도 Mesa semantic signal에서 이 문제를 어떻게 해결할지 공부해볼 것이다.

Better, But Still Broken: While, Not If

위의 문제가 발생한 이유를 한 마디로 정리하자면, "잠들어 있던 스레드가 깨어나서 다시 실행되는 시점에, 잠들면서 만족되기를 기다렸던 조건이 여전히 참인지 다시 검사하지 않았기 때문"이라고 할 수 있겠다.
Hoarse semantic이라면 이 조건을 검사할 필요도 없이 바아로 깨어난 스레드가 실행될 보장이 있지만 Mesa semantic에서는 그렇지 않다는게 포인트이다!

그럼 잠들어 있던 스레드가 깨어나더라도 기대했던 조건을 아직 만족하고 있는지 다시 확인해 주면 되지 않을까?

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

다른건 이전 예제와 모두 같은데, 특정 조건이 만족(producer에서는 count != 1, consumer에서는 count != 0)되었는지 sleep 상태에서 깨어난 이후에도 다시 한 번 확인하고, 그새 기대했던 조건이 만족되지 않았을 경우 다시 한 번 sleep 상태에 들어가는 것을 원하는 결과를 얻을 때까지 반복하도록 개선되었다.

이제야 왜 위에 나온 thr_join의 Pthread_cond_wait이 if문이 아닌 while문으로 감싸져 있었는지 설명할 수 있게 되었다! 이는 만약 done을 바꿀 수 있는 또 다른 상황에서 thr_join이 while문이 아닌 if문을 사용한다면, 부모 스레드가 깨어난 직후에 다른 스레드가 done 값을 바꿔 우리가 원하는 결과를 얻지 못할 수도 있기 때문이다.

음,, 설명이 좀 억지스러운 면도 없잖아 있는 것 같은데, 그냥 속편하게 Mesa semantic에서 signal을 받아 wait으로부터 반환되는 코드는 if문이 아니라 while문을 무조건 사용해주는게 좋다고 생각하고 있어도 될 것 같다. 조건식을 한 번 평가할 것인지, 여러 번 평가할 것인지의 차이니까.

다 된줄 알았는데, 아직 문제가 하나 남아있다.

어우, 줄글로 풀어서 이해해보자. (condVar가 FIFO로 작동한다고 가정한다.)

이번에도 이전과 마찬가지로 Tc1이 가장 먼저 스케줄링되어 버퍼가 비어 있으므로 sleep 상태에 들어가는 것까지는 동일하다.
그러나 이전에는 Tp가 아닌 Tc2가 스케줄링되어, Tc1과 마찬가지로 버퍼가 비어 있으므로 sleep 상태에 들어가게 된다.
마지막으로 Tp가 스케줄링 되어 버퍼에 값을 써주고, 잠들어 있던 Tc1을 깨워준 뒤 다시 for문의 첫 부분으로 돌아가 버퍼가 아직 차있음을 확인하고 스스로 sleep 상태에 들어간다.
깨어난 Tc1은 wait 상태에서 깨어나 while문으로 이동해 여전히 기대했던 조건(버퍼가 차 있는 상황)이 참임을 확인하고, 값을 빼서 쓴 뒤 condVar에 신호를 보낸다.
여기서 Tc1이 기대했던 것은 Tc1이 값을 빼다가 썼으니 Tp가 다시 값을 채워줄 수 있도록 깨워주는 일이었는데, 본의아니게 Tp가 아니라 그 앞에서 condVar에 대기하고 있던 Tc2를 깨워버렸다.
Tc1가 Tc2를 깨워준 다음 다시 for문의 시작점으로 돌아가 버퍼가 비어 있음을 확인하고 스스로 잠에 들면,
영문도 모르고 깨어난 Tc2는 다시 while문으로 돌아가 버퍼가 비어 있음을 확인하고 마찬가지로 잠에 든다.
악! 어쩌다보니까 Tc1, Tc2, Tp가 모두 잠들어 아무 것도 할 수 없는 deadlock이 걸려 버렸다!

이 문제는 왜 발생한 걸까?

핵심은 깨우는 대상이 잘못 되었기 때문이다. 위의 단계 5에서 Tc2가 아니라 Tp를 깨워주기만 했더라면 이와 같은 상황이 발생하지는 않았을 것이다.

이걸 달리 설명하자면 Consumer와 Producer가 서로 기대하는 조건이 각각 버퍼가 다시 차는 것과 버퍼가 다시 비는 것으로 서로 다른데, 이걸 구분하지 않고 그냥 한 줄(cond)로 세워 두었기 때문에 발생한 문제라고 할 수도 있을 것 같다.

The Single Buffer Producer/Consumer Solution

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

그럼 각각의 관심사가 분리된대로 condVar도 나누어 주면 되지 않을까?
이 아이디어를 코드로 표현하면 위와 같다.

producer는 버퍼가 이미 차있는 경우 버퍼가 비어 있기를 바라며 기다리는 condVar인 empty에 가서 기다리고, 값을 채워준 다음에는 버퍼가 차있기를 바라며 기다리는 conVar인 fill에 잠들어 있는 consumer 스레드를 깨워주면 된다.

반면 consumer는 이와 반대로 버퍼가 비어 있는 경우 버퍼가 차있기를 바라며 기다리는 condVar인 fill에 가서 기다리고, 값을 뺀 다음에는 버퍼가 다시 비게 되기를 바라며 기다리는 condVar인 empty에 잠들어 있는 producer 스레드를 깨워주면 된다. 와!

이렇게 함으로써 producer는 항상 consumer만을 깨우며, consumer는 항상 producer만을 깨워 아까와 같은 문제가 발생하지 않게 되었다. (뒤에 나오지만, 잠들어 있는 consumer와 producer를 몽땅 깨워버려도 해결할 수는 있다.)

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

기본적으로 buffer의 크기가 이전에는 1이었으므로 단일 정수값 변수를 사용했었는데, producer와 consumer가 각각 1개씩 있든, 여러개가 있든 필연적으로 병목을 유발할 수밖에 없는 구조이다.

즉 버퍼가 차있는 동안에는 producer가 몽땅 아무 것도 할 수 없고, 버퍼가 비어 있는 동안에는 consumer가 몽땅 아무 것도 할 수 없으니, 아예 버퍼의 크기를 늘려 멀티 스레드 방식의 이점을 살릴 수 있도록 개선했으며 동시에 같은 종류의 여러 스레드가 실행될 수 있는 여지가 버퍼의 크기 만큼 늘어났으므로 context switching 비용 역시 전체적으로 낮아지는 부수 효과까지 얻을 수 있다.

여기서 buffer는 기본적으로 Circular Queue를 사용하며, fill_ptr은 producer가 다음으로 값을 넣을 위치, use_ptr은 consumer가 다음으로 값을 읽을 위치를 의미한다. circular하게 구현되어 있으므로 값의 범위가 버퍼의 크기 안쪽인 것 역시 잘 봐두자! (이게 이해가 잘 안되면 자료 구조의 circular queue 관련 자료를 읽어 봤으면 좋겠다.)

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

사실 위의 put/get에서 빠진 요소가 하나 있는데, 이번엔 producer가 값을 채우려는데 버퍼가 가득 차있는 상황, consumer가 값을 빼려는데 버퍼가 비어 있는 상황에서 각각 put/get이 assertion error를 발생시키는 부분이다.

또한 이젠 버퍼의 크기가 1이 아니라 MAX가 되었으므로 버퍼가 가득 찬 상황을 판별하는 조건식도 약간 수정되었음을 확인할 수 있다. 끝!

30.3 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 함수는 전달받은 size만큼 메모리를 동적으로 할당해서 할당받은 공간의 시작 주소를 넘겨주는데, 만약 남은 가용한 메모리 사이즈(byteLeft)보다 현재 요청된 메모리 크기가 더 크면 할당해줄 수 없으므로 자리가 날 때까지 wait하게 된다.

반면 free 함수는 이전에 할당받은 동적 메모리 공간의 주소(ptr)를 전달받아 size만큼 메모리를 해제해주었다고 표시한 뒤 기다리고 있던 스레드를 깨워줄 뿐 스스로 sleep 상태에 들어가는 일은 없다. 위의 Producer/Consumer 문제와 달리 어떤 조건을 거짓으로 만드는 코드가 없으므로! (사족이긴 한데, 뭐 메모리를 해제해주는 system call을 따로 호출하는게 아니라 그냥 가용한 메모리 크기를 올려주기만 했으므로 여전히 그 자리에는 데이터가 잔류해있을 것이다.)

allocate를 요청하는 2개의 스레드(c1, c2), free를 요청하는 1개의 스레드(p)가 있을 때 다음과 같은 실행 흐름이 발생할 수 있다.

현재 시스템에 동적으로 할당해줄 수 있는 메모리가 남아 있지 않았다고 가정한다.
c1이 100바이트의 메모리를 요청했으나, 줄 수 있는 메모리가 없으므로 sleep 상태에 들어간다.
이어서 c1가 10바이트의 메모리를 요청했으나, 줄 수 있는 메모리가 없으므로 sleep 상태에 들어간다.
p가 스케줄링 되어 50바이트의 메모리를 해제해준 다음, cond에 signal을 보내 c1을 깨웠다. (FIFO)
이어서 p가 남은 unlock 작업까지 마치고 완전히 종료되어 버렸다. 그럼? c1은 ready, c2는 sleep 상태일 것이다.
깨어난 c1이 스케줄링 되어 다시 while문의 조건식을 검사하는데, 가용한 메모리가 50바이트 뿐이므로 다시 sleep 상태에 들어가 결국 c1, c2가 모두 기약 없이 잠들게 된다.

여기서 문제의 핵심은 무엇일까? 이전의 bounded buffer 문제와 같이 condVar의 유형을 구분하지 못해서 발생한 것도 아니고, 동일한 유형의 요구 사항을 가지는 스레드들이 잠들어 있는 condVar에 signal을 보냈음에도 문제가 발생했다.

이는 동일한 관심사를 가지는 sleeping thread들 사이에서도 깨워줘야 할 스레드를 상황에 따라 선별하여 깨워주어야 하는데, 여기서는 FIFO 정책에 의해 잘못된 스레드가 깨어났기 때문에 문제가 발생했다고 할 수 있다. 만약 단계 4에서 c1이 아닌 c2를 깨워줬다면? c2는 10바이트만 필요로 하므로 정상적으로 수행되었을 것이다.

물론 잠들어 있는 스레드의 상태를 하나하나 확인해서 뭐,, 깨워주는 구현이 있을 수도 있겠지만 가장 간단한 해법으로써 pthread_cond_signal 대신 pthread_cond_broadcast를 사용하는 방법이 있다.

이 pthread_cond_broadcast는 인자로 전달 받은 condVar에 잠들어 있는 모든 스레드들을 몽땅 깨워주는 역할을 수행하는데, 이걸 위의 상황에 적용해서 다시 thread tracing을 해보겠다.

현재 시스템에 동적으로 할당해줄 수 있는 메모리가 남아 있지 않았다고 가정한다.
c1이 100바이트의 메모리를 요청했으나, 줄 수 있는 메모리가 없으므로 sleep 상태에 들어간다.
이어서 c1가 10바이트의 메모리를 요청했으나, 줄 수 있는 메모리가 없으므로 sleep 상태에 들어간다.
p가 스케줄링 되어 50바이트의 메모리를 해제해준 다음, cond에 잠들어 있는 c1과 c2를 모두 깨워준다. (어느쪽이 먼저 스케줄링 되어도 상관 없지만, c1이 먼저 스케줄링 되었다고 가정해보자.)
이어서 p가 남은 unlock 작업까지 마치고 완전히 종료되었다.
이제 Ready queue에 들어 있는 두 스레드 중 c1이 먼저 스케줄링 되었으나, 아직 조건을 만족하지 않아(메모리 공간이 충분하지 않아) 다시 sleep 상태에 들어간다.
혼자 Ready queue에 남아 있는 c2가 이제 스케줄링 되어, 요구하는 메모리 공간이 가용한 메모리 공간보다 작으므로 메모리를 할당 받고 남은 작업을 마저 수행하여 allocate가 반환된다.

이렇듯 pthread_cond_broadcast이 잠들어 있는 스레드들이 잠들며 기대했던 모든 가능성들을 다시 깨어나 확인하도록 하기 때문에 이를 Covering condition이라 하며, 당장의 문제는 해결했지만 조건을 만족하지 않는 스레드들까지 전부 깨우기 때문에 context switching에 소요되는 overhead가 커진다는 단점이 있다.

물론 위의 멀티 스레드 환경에서의 메모리 동적 할당 문제와 같이 broadcast로 문제를 해결해야 하는 케이스도 있지만, 워낙에 불필요한 overhead가 크므로 잘 생각해서 사용하는 것이 좋겠다.

마무리

휴! 이전에 배운 Lock와 conditional variable을 사용해서 어떻게 멀티 스레드 프로그램을 제대로 작동할 수 있을지 공부했다.

문제가 참 복잡한 것 같으면서도 여기까지는 직관적으로 알아들을만한 부분이 많아서 그나마 괜찮았는데, 다음 주제인 세마포어는 각오 좀 하고 와야될걸,,,,,?

급식

뭐 먹고 살지.

이전 포스트

[OS] 29. Lock-based Concurrent Data Structures

다음 포스트

[OS] 31. Semaphores

2개의 댓글

이지민

2024년 5월 31일

감사합니다….덕분에 운영체제 이해를 할수있네요 책에는 두루뭉술해서 이해가 잘안됬는데

1개의 답글