# 컨디션 변수 & 세마포어

# 컨디션 변수 (Condition Variable)

> Lock 과 Condition Variable 은 어떤 차이인가? 왜 둘 다 필요한거지? 둘 중 하나만 써도 되는 것 아닌가?

상호 배제의 문제는 Lock 을 통해 해결했지만, 스레드 간에 Lock 을 얻는 순서를 보장해줄 수 없다.

이를 해결하기 위해 Condition Variable 혹은 Semaphore 라는 개념이 등장했다.

먼저 Condition Variable(컨디션 변수)은 어떤 방식으로 스레드 간의 실행 순서를 보장했는 지 알아보자.

## Condition Variable 이란?

- Condition Variable 란 스레드***(조건이 만족되면 누군가 깨워주기를 바라고 잠든)***의 주소가 담긴 queue 자료 구조이다.
- 스레드 간 공유될 수 있는 공유 변수이다. → 상호 배제가 보장되어야 한다.

가령 부모 스레드가 자식 스레드가 작업을 끝냈는지 알기위해 join() 메소드를 사용한다.

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

위 코드를 살펴보면, 먼저 컨디션 변수를 초기화하고 선언한다. 컨디션 변수와 관련해서 `wait(c, m)` 와 `signal(c)`이라는 두 개의 메소드가 존재한다. `wait(c, m)` 는 스스로를 잠재우고 대기 큐(c)에 넣는 동작을 하고, `signal(c)` 는 대기 큐의 스레드를 하나 깨운다.

여기서 주의깊게 살펴봐야 할 메소드는 `wait(c, m)` 인데, `wait(c, m)` 가 호출될 때 mutex 는 잠긴 상태라고 가정한다. 그래서 `wait(c, m)`의 내부 동작은 먼저 파라미터로 넘겨받은 mutex 를 해제하고 현재 스레드를 대기 상태로 전환한다. 여기서 다른 스레드가 시그널을 보내어 대기중인 스레드가 깨어나면, `wait(c, m)` 를 리턴하기 전에 mutex 를 재획득한다. 시그널을 받아서 대기상태에서 깨어났더라도 락 획득에 실패하면 다시 대기상태로 돌아간다.

`대기 상태로 전환하기 전에 락을 반납하고, 대기에서 깨어난 후 락을 다시 획득하여 실행을 계속한다.`

wait 와 signal 을 사용하는 코드에 매번 락으로 감싸는 이유는 상태 검사와 메소드를 원자적으로 실행하여 race condition 을 예방하기 위함이다.

그리고 done 변수의 상태 검사 코드라 if 가 아니라 while 로 감싸져 있는 것에도 주목해보자. 스레드가 시그널을 받는 시점과 스레드가 실제로 실행되는 시점 사이에는 미세한 시차가 존재한다. 그래서 그 사이에 변수가 다시 변경될 수 있다. 그래서 조건 변수 검사를 if 가 아닌 while 로 만듦으로써 시그널을 보낸다는건 `해당 스레드를 깨워서 반드시 다음동작을 수행하게 하는게 아니라 깨어나서 조건 검사 한번 해봐라 정도의 의미가 되는 것`이다.

done 변수의 존재 의미가 궁금할 수 있는데, 이는 자식 스레드의 실행 시점이 언제일지 모르기 때문이다. 만약 자식 스레드가 생성과 동시에 실행되어서 즉시 thr_exit() 을 호출했는데 done 변수가 없다면 부모 스레드는 영영 깨어나지 못한다. wait() 을 실행했지만 본인을 깨워줄 자식 스레드는 이미 온데간데 없다.

> 의문 1) 락과 컨디션 변수의 차이가 뭐지?

정확히 말하면 Lock 은 온전히 코드의 상호 배제를 위한 테크닉이다. 한 코드 블럭을 한 순간에 한 스레드만 수행할 수 있고 다른 스레드는 그 동안 기다리게 하는 동작을 수행한다. 하지만 CV 는 내가 정의 한 특정 조건을 만족할 때만 스레드가 수행되게 할 수 있다. 애플리케이션의 정의한 조건에 따라 스레드를 대기하거나 다시 실행되게 만들 수 있는것이다.

→ Lock 과 CV 는 그 목적이 완전히 다르다!

wait() 은 현재 스레드를 blocked 상태에 두고 mutex lock 을 릴리즈하는 동작은 atomic 하게 수행한다.

```cpp
int cnd_wait(cnd_t *cv, mtx_t *mtx)
{
        mtx_unlock(mtx),
        futex_wait(&cv->value, 0, NULL);
        mtx_lock(mtx);
        return thrd_success;
}
```

코드로 표현하면 위 같은 그림일 것이다. 먼저 갖고있던 lock 을 해제하고 futex_wait 으로 현재 스레드를 blocked 상태로 전환한다.

futex 로 시그널을 주고 받는데 이 때 사용되는 변수가 condition variable 이다.

> 의문 2) 분명 Lock 도 스핀락이 아닌 이상 내부적으로 mutex 변수가 맞지 않으면 wait() 로 대기상태에 들어가고 다른 스레드가 unlock() 으로 wake() 를 수행하면 그 때 깨어나서 다시 Lock 을 획득한다.
CV 도 wait() 와 wake() 를 기반으로 동작하는데 그럼 둘의 차이는 뭐지?

물론 lock 의 구현에도 futex가 쓰이고 CV 메커니즘의 구현에도 futex가 쓰인다. 다만 그 용도가 다르다.

lock 은 mutex 변수와 futex 를 사용하여 상호 배제를 보장하고
CV 는 condition 변수와 futex 를 사용하여 스레드간의 시그널 전달으을 통한 순서 제어를 보장했다.

## 생산자/소비자 문제 (bounded buffer 문제)

Dijkstra 가 처음 제시한 생산자/소비자 문제는 그가 락이나 컨디션 변수를 대신하여 사용할 수 있는 일반화된 세마포어를 발명하게 된 이유이다.

다수의 생산자 스레드와 소비자 스레드가 있다고 하자. 생산자는 데이터를 만들어 버퍼에 넣고, 소비자는 버퍼에서 데이터를 꺼내어 사용한다.

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

여기서 데이터(bounded buffer)는 공유 자원이며, race condition 의 발생을 방지하기 위해 동기화가 필요하다.

버퍼의 count가 0이면 데이터를 넣고, count가 1이면 버퍼에서 데이터를 꺼낸다.

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

위 코드에서 put 동작과 get 동작을 하는 임계 영역을 락으로 보호했지만 이는 제대로 동작하기에 충분하지 않다.

생산자와 소비자가 각각 하나씩인 경우에는 위 코드가 정상적으로 작동하지만, 생산자와 소비자가 여러 스레드일 경우 위 방식에는 큰 문제가 있다.

- 하나의 컨디션 변수로는 생산자와 소비자 스레드 중 어느 스레드를 깨울 지 지정할 수 없다.

소비자가 버퍼를 비울 경우 생산자를 깨워야 하지만 소비자를 깨울 수도 있는 것이다. 이러면 모든 스레드가 대기 상태에 빠져버린다.

이는 우리가 원하던 상황이 아니다. 우리는 소비자는 생산자만을, 생산자는 소비자만을 깨우기를 원한다.

### 생산자/소비자 문제의 해법

이 문제는 컨디션 변수를 두 개 사용하면 해결된다. 깨워야 하는 스레드의 컨디션 변수로 시그널 메소드를 호출하면 된다.

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

생산자 스레드가 empty 컨디션 변수에 대해서 대기하고 fill 컨디션 변수에 대해서 signal 을 발행한다. 소비자 스레드는 반대로 fill 컨디션 변수에 대해서 대기하고 empty 컨디션 변수에 대해서 signal 을 발행한다. 이렇게 하면 소비자가 소비자를 깨우거나 생산자가 생산자를 깨울 일은 없다.

## Covering Condition

컨디션 변수의 signal 메소드는 signal 수신자를 명시하지 않는다. 해당 컨디션 변수에 대해서 대기하고 있는 스레드 중 어느 것을 깨울지 명시할 수 없다는 의미이다. 그래서 컨디션 변수를 사용하여 signal 을 보내면 해당 컨디션 변수에 대해서 대기중인 스레드는 모두 깨어나서 실행된다. 다수의 스레드를 불필요하게 깨울 수 있고 따라서 불필요한 문맥전환이 발생할 수 있다.

이런 경우를 Covering Condition 이라고 부른다. 스레드가 깨어나야 하는 모든 경우를 다 포함하기 때문이다.

> 컨디션 변수는 스레드를 특정 조건이 만족될 때 까지 대기하도록 하여 동기화 문제를 쉽게 해결했다.

# 세마포어 (Semaphore)

다양한 병행성 문제를 해결하기 위해서는 락과 컨디션 변수가 모두 필요하다. Dijkstra 는 이를 위해 조금 일반화된 개념인 세마포어를 개발했다. 곧 보겠지만 세마포어 하나로 락과 컨디션 변수가 하는 동작을 모두 구현할 수 있다.

## Semaphore 란?

- 정수 값을 갖는 객체이다.
- wait() 와 post() 두 개의 메소드로 조작한다.
- 정수 값을 어떻게 초기화 하냐가 굉장히 중요하다.

```cpp
#include <semaphore.h>
sem_t s;
sem_init (&s, 0, 1);
```

위 코드의 경우 세마포어의 값을 1로 초기화 했다. 중간 인자인 0은 스레드간에 세마포어를 공유한다는 것을 의미한다.

```cpp
int sem_wait(sem_t *s) {
	decrement the value of semaphore s by one
	wait if value of semaphore s is negative
}

int sem_post(sem_t *s) {
	increment the value of semaphore s by one
	if there are one or more threads waiting, wake one
}
```

- sem_wait() 메소드는 세마포어의 값이 1 이상이 될 때 까지 대기하거나 즉시 리턴한다.
- sem_post() 메소드는 세마포어의 값을 증가시키고 대기 중인 스레드 중 하나를 깨운다.
- 여기서 말하는 대기가 만드시 sleep 을 의미하는 건 아니다. spin 이 될 수도 있다.

## Binary Semaphore (이진 세마포어) = Lock

방금 배운 세마포어를 락으로 먼저 활용해보자.

```cpp
sem_t m;
sem_init(&m, 0, X); // initialize to X; what should X be?

sem_wait(&m);
// critical section here
sem_post(&m);
```

위처럼 sem_wait() 과 sem_post() 로 임계영역을 감싸서 상호 배제를 보장하려면 세마포어의 초기값(X)는 무엇이 되어야 할까?

정답은 1 이다.

첫 스레드가 sem_wait() 을 호출해서 세마포어 값을 1로 감소시켜서 0으로 만든 후 임계영역으로 진입한다. 그리고 두 번째 스레드가 임계 영역에 진입하기 위해 sem_wait() 을 호출할 경우 세마포어 값을 1 감소시켜서 -1 이 되고 대기 상태에 들어간다. 첫 스레드가 작업을 끝내서 sem_post() 을 호출하여 세마포어 값을 1 증가시켜서 0으로 만들고 두 번째 스레드를 깨우면 두 번째 슬헤드는 sem_wait() 을 탈출해서 임계영역으로 진입한다.

이렇게 세마포어를 락으로 쓸 수 있다는 것을 알았다. 락은 두 개의 상태만 존재하므로 이진 세마포어라고도 불린다.

## 순서 보장을 위한 세마포어 = Condition Variable

세마포어를 순서 보장을 위해 컨디션 변수처럼 활용할 수도 있다.

컨디션 변수를 배울 때 나왔던 부모, 자식 스레드 예제를 다시 떠올려보자.

```cpp
sem_t s;

void *child(void *arg) {
	printf("child\n");
	sem_post(&s); // signal here: child is done
	return NULL;
}

int main(int argc, char *argv[]) {
	sem_init(&s, 0, X); // what should X be?
	printf("parent: begin\n");
	pthread_t c;
	Pthread_create(&c, NULL, child, NULL);
	sem_wait(&s); // wait here for child
	printf("parent: end\n");
	return 0;
}
```

세마포어로 앞의 부모, 자식 예제의 동작을 똑같이 보장하려면 세마포어의 초기값(X)가 무엇이 되어야 할까?

정답은 0 이다.

초기값이 0일 경우 wait() 을 호출한 부모는 대기상태로 들어가서 자식의 시그널을 기다릴 수 있고, 자식이 생성되자마자 실행돼서 부모가 늦게 실행되더라도 동작에는 문제가 없다.

## 생산자/소비자 문제 (bounded buffer 문제)

앞에서 컨디션 변수를 공부할 때 배웠던 생산자/소비자 문제를 세마포어로 해결해보자.

신경써야할 점은 다음과 같을 것이다.

1. 생산자와 소비자를 따로 깨울 수 있어야한다.
2. get() 과 put() 동작은 atomic 해야한다. → 상호배제를 보장해야한다.

1 번을 위해 세마포어를 두 개로 분리하고, 2 번을 위해 mutex 세마포어를 따로 생성하자.

```cpp
sem_t full;
sem_t empty;
sem_t mutex;

void *producer(void *arg) {
		int i;
		for (i = 0; i < loops; i++) {
		sem_wait(&mutex); // Line P0 (NEW LINE)
		sem_wait(&empty); // Line P1
		put(i); // Line P2
		sem_post(&full); // Line P3
		sem_post(&mutex); // Line P4 (NEW LINE)
	}
}

void *consumer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&mutex); // Line C0 (NEW LINE)
		sem_wait(&full); // Line C1
		int tmp = get(); // Line C2
		sem_post(&empty); // Line C3
		sem_post(&mutex); // Line C4 (NEW LINE)
		printf("%d\n", tmp);
	}
}

int main(int argc, char *argv[]) {
	// ...
	sem_init(&empty, 0, MAX); // MAX are empty
	sem_init(&full, 0, 0); // 0 are full
	sem_init(&mutex, 0, 1); // init lock
	// ...
}
```

언뜻보면 완벽히 동작할 것 처럼 보인다. 앞 장에서 문제시 되었던 부분은 모두 해결했기 때문이다.

하지만 위 코드에는 아주 큰 문제가 하나 있다.

바로 Dead-Lock (교착상태) 이다.

생산자와 소비자 스레드가 각각 하나씩 있고, 소비자 스레드가 먼저 실행되었다고 하자. mutex를 획득(C1)한 후, full 세마포어에 대해 sem_wait() 을 호출(C2)한다. 버퍼가 비어있으므로 해당 스레드는 대기 상태로 전환된다. 중요한 점은 소비자는 아직도 락을 갖고 놓지 않았다는 것이다.

이후 생산자 스레드가 실행되면 mutex 획득을 시도(P0)할 것이고, mutex 는 아직 소비자 스레드가 가지고 있으므로 생산자 스레드는 대기 상태로 전환된다.

서로가 상대방을 기다리는 Dead-Lock 상태가 발생했다.

### 이에 대한 해법

위 문제를 해결하기 위해서는 락의 범위(scope)를 줄여야 한다.

```cpp
void *producer(void *arg) {
		int i;
		for (i = 0; i < loops; i++) {
		sem_wait(&empty); // Line P0
		sem_wait(&mutex); // Line P1 
		put(i); // Line P2
		sem_post(&mutex); // Line P3 
		sem_post(&full); // Line P4
	}
}

void *consumer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&full); // Line C0
		sem_wait(&mutex); // Line C1
		int tmp = get(); // Line C2
		sem_post(&mutex); // Line C3 
		sem_post(&empty); // Line C4
		printf("%d\n", tmp);
	}
}
```

mutex 를 획득, 해제하는 코드를 임계 영역 직전과 직후로 옮겨서 범위를 축소했다. full 과 empty 세마포어 관련 코드는 바깥으로 이동했다. 이러면 Dead-Lock 문제는 발생하지 않는다.

## 스레드 제어

세마포어가 유용하게 쓰이는 또 하나의 사례가 있다.

동시에 너무 많은 스레드가 실행되면 시스템의 물리 메모리 양을 초과하여 thrashing 이 시작될 것이고 이는 퍼포먼스의 큰 하락을 가져온다. 이 때 프로그래머는 동시 실행 가능한 스레드의 갯수를 제어할 수 있을까? 세마포어로 가능하다.

세마포어의 값을 동시 최대 실행 가능한 스레드의 개수로 초기화 하고 코드의 앞, 뒤에 sem_wait() 과 sem_post() 를 추가하면 해당 코드 내에서 동시 실행 가능한 스레드의 개수를 통제할 수 있다.

> 세마포어를 락과 컨디션 변수의 일반화로 볼 수 있을까? 그런 일반화가 필요하기는 한가?
세마포어를 이용하여 컨디션 변수의 동작을 구현하는 것이 어렵다는 것을 바탕으로 생각하면 이 일반화가 우리가 생각하는 것만큼 일반적이지 않을 수도 있다.


