🚪 들어가며

"락"만으로는 병행 프로그램을 제대로 작성할 수 없음
➡️ 쓰레드가 계속 진행하기 전에 어떤 조건이 참인지를 검사해야 하는 경우가 많이 있음.

join(): 부모 쓰레드가 작업을 시작하기 전에 자식 쓰레드가 작업을 끝냈는지 검사

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); // 자식 생성하기
  while (done == 0); // 회전
  printf("parent: end\n");
  return 0;
}

위 처럼 공유 변수를 사용할 수도 있지만 부모 쓰레드가 회전을 하면서 CPU 시간을 낭비하므로 비효율적임.

1️⃣ 정의와 루틴들

🚦 컨디션 변수(conditional variable)

• 일종의 큐 자료 구조

• 어떤 실행의 상태(또는 어떤 조건)가 원하는 것과 다를 때 조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐

• 다른 쓰레드가 상태 변경 ➡️ 대기 중이던 쓰레드(하나 이상)를 깨움.(조건에 따라 시그널 전송)

✋ 컨디션 변수의 선언
pthread_cond_t c;

컨디션 변수에는 두 개의 연산이 존재

• wait(): 쓰레드가 스스로를 잠재우기 위해 호출

• signal(): 다른 쓰레드가 무언가를 변경하여 잠자던 쓰레드를 깨우기 위해 호출

POSIX의 사용례는 다음과 같음.

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

wait()에서 mutex를 매개변수로 사용한다는 것을 유의해야 함.

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

조건이 만족하여 깨어났더라도 락을 획득못하면 다시 sleep 상태로 들어감.
➡️ 복잡한 과정을 거치는 이유: 쓰레드가 스스로 재우려고 할 때, 경쟁 조건의 발생을 방지하기 위함.

아래의 예시와 함께 이를 살펴보자.

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

두 가지 경우를 살펴보자.

[1] 부모 쓰레드가 자식 쓰레드 생성 후 thr_join()을 호출하고 자식 쓰레드의 종료를 대기

1. 부모 쓰레드가 락 획득

2. 자식이 끝났는지 검사(done == 1)

   1. 자식이 끝나지 않았으므로, wait()를 호출하여 스스로를 잠재움.(락 해제)

3. 자식 쓰레드가 "child" 메시지 출력

4. 자식 쓰레드가 thr_exit()을 호출

   1. 락을 획득한 후 상태 변수 done을 설정

   2. 시그널을 보내어 부모 쓰레드를 깨움.

5. 부모 쓰레드가 호출했던 wait()에서 락을 획득한 채로 리턴

6. 부모 쓰레드가 실행하여 락을 해제하고 "parent: end" 메시지 출력

[2] 자식 쓰레드가 생성되면서 즉시 실행되고 done 변수를 1로 설정 후 시그널 전송

1. 자식 쓰레드가 생성되면서 즉시 실행

2. done 변수를 1로 설정 후 시그널 전송

   1. 자고있는 쓰레드가 없으므로 단순히 리턴

3. 부모 쓰레드가 실행하여 thr_join()을 호출

   1. done 변수가 1이므로 대기 없이 바로 리턴

⭐ 위의 코드에서 알 수 있듯, 부모 쓰레드가 조건을 검사할 때 if 문이 아니라 while 문을 사용

🤔 done 이라는 상태 변수가 꼭 필요할까? ➡️ 필요하다.

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

위의 경우에서 자식 프로세스가 생성 즉시 실행되어 thr_exit()을 호출하면 시그널을 보내지만 깨워야 할 쓰레드가 없음.
➡️ 부모 쓰레드가 실행되면 wait() 호출 시 어떤 쓰레드도 부모 쓰레드를 깨우지 않으므로 거기서 멈춤.

따라서 잠자고, 깨우고, 락을 설정하는 것이 done이라는 상태 변수를 중심으로 구현되어 있음.

🤔 시그널을 주거나 대기할 때 락을 획득할 필요가 없다면 어떤 문제가 생길까?

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

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

위의 경우 경쟁 조건이 발생한다.

부모 쓰레드가 thr_join()을 호출한 후 done 변수 값이 0인 것을 확인한 후 잠자려고 할 때, wait() 호출 직전 부모 쓰레드가 인터럽트에 걸려 자식 쓰레드가 실행되는 경우
➡️ 자식 쓰레드가 상태 변수 done의 값을 1로 변경하고 시그널을 보내지만 대기 중인 쓰레드가 없으므로 부모 쓰레드가 다시 실행되면, wait()를 호출하고 잠자게 되지만 깨워줄 쓰레드가 없음.

⭐ 컨디션 변수를 사용할 때는 락을 획득한 후에 시그널을 보내는 것이 가장 간단하고 최선의 방법

2️⃣ 생산자/소비자(유한 버퍼) 문제

Dijkstra가 처음 제시한 동기화 문제(producer/consumer)로, 유한 버퍼(bounded 버퍼) 문제로도 알려져 있음.
➡️ 락이나 컨디션 변수를 대신하여 사용할 수 있는 일반화된 세마포어를 발명하게 됨.

여러 개의 생산자 쓰레드(데이터를 만들어 버퍼에 넣음)와 소비자 쓰레드(버퍼에서 데이터를 꺼내어 사용)가 있다고 하자.
➡️ 예시로 멀티 쓰레드 웹 서버(생산자는 HTTP 요청을 작업 큐(유한 버퍼)에 넣고, 소비자는 이 큐에서 요청을 꺼내어 처리)가 있음.
➡️ grep foo file.txt | wc -l과 같은 파이프(pipe) 명령으로 한 프로그램의 결과를 다른 프로그램에게 전달할 때도 유한 버퍼를 사용

grep foo file.txt | wc -l에서 두 개의 프로세스가 병행 실행되는 예시를 살펴보자.
➡️ grep 프로세스가 생산자, wc 프로세스가 소비자
➡️ 둘 사이에는 커널 내부에 있는 유한 버퍼가 존재

🗃️ 유한 버퍼는 공유 자원이다.
➡️ 경쟁 조건의 발생 방지를 위한 동기화가 필요

int buffer;
int count = 0; // 처음에는 비어있음

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

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

비록 위의 코드에서는 1과 0으로 값 하나에 대한 저장을 표시하지만, 버퍼가 차 있는 지 확인하고 접근, 확인 후 비움 표시 등을 제대로 하고 있다.
➡️ 버퍼의 count가 0(버퍼 비어있음)이면 데이터 삽입
➡️ 버퍼의 count가 1(버퍼 가득 참)일 때만 버퍼에서 데이터 추출

put()과 get() 루틴에는 임계 영역이 있다.
➡️ 하지만 락 추가만으로 제대로 동작하는 것은 아님.
➡️ 🚦컨디션 변수가 필요

아래의 코드는 cond 컨디션 변수 하나와 그에 연결된 mutex 락을 사용한다.

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

생산자는 버퍼가 빌 때까지 기다리고(p1-p3), 소비자도 버퍼가 차기를 기다린다.(c1-c3)
➡️ 🚫 하지만 두 개 이상의 같은 종류의 쓰레드가 있다면, 이 방법에서는 두 가지 문제가 발생한다.

두 개의 소비자(Tc1, Tc2)와 한 개의 생산자(Tp)가 있다고 가정하자.

[⚠️ 문제점1]

1. Tc1이 실행하여 락을 획득(c1)하고 버퍼를 소비할 수 있는지 검사(c2)

2. 비어 있음을 확인 후 대기하며(c3) 락을 해제

3. Tp가 실행하여 락을 획득(p1)하고 버퍼가 비었는지 확인(p2)

4. 비어 있음을 확인하고 버퍼를 채운(p4) 후 버퍼가 가득 찼다는 시그널 전송(p5)

5. 대기 중인 Tc1은 깨어나 ready queue로 이동하지만 아직 실행하지 않음.

6. 생산자가 계속 실행하지만 버퍼가 차 있으므로 대기 상태로 전이(p6, p1-p3)

7. ⚠️ Tc2가 실행하여 버퍼 값을 소비(c1-c2, c4-c6)

8. Tc1이 실행되어 대기에서 리턴하기 전 락 획득

9. get()을 호출(c4)하지만 버퍼는 비어있음. ➡️ 의도한 대로 기능X

Tc1이 깨어나서 실행되기까지 사이에 유한 버퍼의 상태가 변경됨.
➡️ 시그널은 쓰레드를 깨우지만 쓰레드가 실제 실행되는 시점에도 그 상태가 유지된다는 보장X

💡 이런 식으로 시그널을 정의하는 것을 Mesa semantic이라고 함.
➡️ 대부분의 시스템이 채용

💡 이와 대비되는 개념은 Hoare semantic이 있음.
➡️ 구현하기는 더 어렵지만 깨어난 즉시 쓰레드가 실행되는 것을 보장

✅ 위의 문제는 대기 명령 전의 if 문을 while 문으로 바꾸어 해결할 수 있다.
➡️ Tc1이 깨어나서(락을 획득한 상태) 즉시 공유 변수의 상태를 재확인하여 버퍼가 비어 있다면 대기 상태로 돌아감.
➡️ 소비자 코드와 함께 생산자 코드에서도 if 문을 while 문으로 변경

아래는 수정된 코드이다.

cond_t cond;
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(&cond, &mutex); 
    put(i);                             
    Pthread_cond_signal(&cond);         
    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(&cond, &mutex); 
    int tmp = get();                    
    Pthread_cond_signal(&cond);         
    Pthread_mutex_unlock(&mutex);       
    printf("%d\n", tmp);
  }
}

Mesa semantic의 컨디션 변수에서 가장 기본적인 법칙: 언제나 while 문을 사용
➡️ 항상 검사하는 것이 안전

[⚠️ 문제점2]

이 문제는 Tc1과 Tc2가 먼저 실행한 후 둘 다 대기 상태에 있을 때 발생한다.

1. 두 소비자 쓰레드는 대기하고 Tp가 실행되어 버퍼에 값을 넣고 Tc1을 깨우고 자신은 대기

2. Tc1이 wait()에서 리턴을 받아 깨어나고 조건을 재확인

3. 버퍼가 차있다는 것을 발견하고 값을 소비

4. 이후 시그널을 전송하여 대기 중인 쓰레드 중 하나를 깨움.

   1. 이때 어떤 쓰레드를 깨워야 할까?

⚠️ 소비자가 버퍼를 비웠으므로 당연히 Tp를 깨워야 하지만, Tc2를 깨운다면 문제가 발생함.
➡️ Tc2가 깨어나면 버퍼가 비어 있다는 것을 확인한 후 대기 상태로 들어감.
➡️ 버퍼에 값을 넣어야 하는 Tp와 다른 소비자인 Tc1 역시 대기 상태에 들어감.
➡️ 세 개의 쓰레드가 모두 대기 상태에 놓임.

⭐ 시그널을 보내는 것은 꼭 필요하지만 대상이 명확해야 함.
➡️ 소비자는 다른 소비자를 깨울 수 없고 생산자만 깨워야 하며, 반대로 생산자의 경우도 마찬가지임.

✅ 위의 문제는 두 개의 컨디션 변수를 사용하여 시스템의 상태가 변경되었을 때 깨워야 하는 쓰레드에게만 시그널을 제대로 전달하여 해결할 수 있다.

아래는 수정된 코드이다.

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

생산자 쓰레드가 empty 조건 변수에서 대기하고 fill에 대해서 시그널을 발생

소비자 쓰레드는 fill에 대해서 대기하고 empty에 대해서 시그널을 발생

즉, 서로가 같은 종류의 쓰레드를 절대로 깨울 일이 없도록 만듦.

최종적인 생산자/소비자 해법

이제 제대로 동작하는 생산자/소비자 해법을 얻었지만 아직까지는 보편적인 방법은 아님.

다음을 통해 병행성을 증가시키고 더 효율적으로 만듦.

• 💡 버퍼 공간을 추가

  • 대기 상태 진입 전 여러 값들이 생산될 수 있도록 함.

  • 여러 개의 값이 대기 상태 전에 소비될 수 있도록 함.

하나의 생산자와 소비자의 경우, 버퍼가 커지면 쓰레드 간의 문맥 교환이 줄어들어 더 효율적

멀티 생산자 또는 멀티 소비자의 경우 생산과 소비가 병행될 수 있으므로 병행성이 좋아짐.

아래과 같이 버퍼 구조와 put()과 get()을 변경하여 적용시킬 수 있다.
이와 함께 생산자와 소비자가 대기 상태가 되는 지에 대한 여부를 결정하는 조건도 약간 변경한다.

int buffer[MAX];
int fill = 0;
int use = 0;
int count = 0;

void put(int value) {
  buffer[fill] = value;
  fill = (fill + 1) % MAX;
  count++;
}

int get() {
  int tmp = buffer[use];
  use = (use + 1) % MAX;
  count−−;
  return tmp;
}

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

✅ 생산자는 모든 버퍼가 현재 가득 차있다면 대기 상태에 들어간다.

✅ 소비자도 모든 버퍼가 비어 있다면 대기에 들어간다.

3️⃣ 컨디션 변수 사용 시 주의점

먼저 아래의 코드를 살펴보자.

// 몇 byte나 힙이 비어 있는가?
int bytesLeft = MAX_HEAP_SIZE;

// 락과 컨디션 변수가 필요함
cond_t c;
mutex_t m;

void *allocate(int size) {
  Pthread_mutex_lock(&m);
  while (bytesLeft < size)
    Pthread_cond_wait(&c, &m);
  void *ptr = ...; // 힙에서 메모리를 할당 받음
  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);
}

메모리 할당 코드를 호출하면 공간이 생길 때까지 기다려야할 수 있다.

반대로 쓰레드가 메모리 반납 시, 사용 가능한 메모리 공간의 발생을 알리는 시그널을 생성할 수 있다.
➡️ ⚠️ 이때 어떤 쓰레드가 깨어나야 하는가?

아래와 같은 상황을 가정해보자.

• 현재 빈 공간이 없음.

• 쓰레드 Ta가 allocate(100)을 실행

• 그 후 쓰레드 Tb가 allocate(10)을 실행

• 쓰레드 Ta와 Tb는 대기 상태 진입(현재 요청 만족 불가능)

이 시점에서 쓰레드 Tc가 free(50)을 호출하고 다른 쓰레드를 깨운다고 할 때,
➡️ 10 bytes 공간을 필요로 하는 쓰레드 Tb가 깨어나야 함.
➡️ 하지만 현재 어떤 쓰레드를 깨워야할 지 모르므로 Ta가 깨어날 수 있음.

[✅ 해법1 - Lampson과 Redell이 제시]

pthread_cond_signal()을 대기 중인 모든 쓰레드를 깨우는 pthread_cond_broadcast()로 바꿔서 사용한다.

⚠️ 단, 아직은 깨어나면 안 되는 여러 쓰레드가 불필요하게 깨어날 수 있음.
➡️ 성능에 안 좋은 영향을 미침.
➡️ 그러한 쓰레드들은 깨어나서 조건을 재검사하고, 즉시 대기 상태로 다시 들어감.

Lampson과 Redell은 이런 경우를 포함 조건(covering condition)이라고 함.
➡️ 쓰레드가 깨어나야 하는 모든 경우를 다 포함하기 때문

불필요하게 많은 쓰레드가 깨어나는 단점이 있고, 문맥 전환 오버헤드가 크지만 앞서 다룬 메모리 할당 문제의 경우 브로드캐스트를 적용하는 것이 가장 자명한 해법임.
➡️ 위의 생산자/소비자 문제의 경우 더 좋은 해법이 있었으므로 그 방법을 채택

📚 참고 문헌

Operating Systems: Three Easy Pieces ― 30: Condition Variables

운영체제 아주 쉬운 세 가지 이야기 ― 33: 컨디션 변수