Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

지금까지 락의 개념과, 어떻게 하드웨어와 OS 지원의 조합을 통해 락을 만드는지에 대해서 공부했다. 하지만 락만이 병행적 프로그램들을 만드는 데에 필요한 것은 아니다.

구체적으로, 스레드는 실행을 계속하기 전에 특정한 조건이 참인지를 확인하고자 하는 경우들이 있다. 예를 들면 부모 스레드가 실행을 계속하기 전, 자식 스레드가 작업을 마쳤는지 확인하고자 하는 경우가 있다. 이런 대기는 어떻게 구현되어야 할까?

void *child(void *arg){
	printf("child\n");
	// 작업을 마쳤음을 어떻게 가리킬 수 있을까?
	return NULL;
}

int main(int arg, char *argv[]){
	printf("parent: begin\n");
	pthread_t c;
	Pthread_create(&c, NULL, child, NULL); // 자식 스레드 생성
	// 어떻게 자식 스레드를 기다릴 수 있을까?
	printf("parent: end\n");
	return 0;
}

위 코드를 실행해 얻고 싶은 출력은 다음과 같다

parent: begin
child
parent: end

이를 위해서는 아래와 같이 공유 변수를 사용할 수도 있을 것이다. 이 해결법은 보통 잘 동작하지만, 부모 스레드가 자식 스레드를 기다리며 스핀해야하고, 따라서 CPU 시간을 낭비하기 때문에 몹시 비효율적이다.

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

이 방법 대신, 우리가 기다리고 있는 조건이 참이 될 때까지 부모 스레드를 재우는 방법을 사용하게 될 것이다.

1. Definition and Routines

스레드가 조건이 참이 되기를 기다리게 하기 위해서는 조건 변수(condition variable)이라 부르는 것을 이용해야한다. 조건 변수는 어떤 실행 상태가 필요하지 않은 경우 스레드가 자기 자신을 집어 넣는 명시적인 큐다. 어떤 다른 스레드는 그런 상태를 바꿨을 때, 대기 중인 스레드 중 하나를 깨워 실행을 계속하게 할 수 있다. 이 아이디어는 Dijkstra의 "private semaphores" 사용으로까지 거슬러 올라가는데, 이와 비슷한 아이디어는 나중에 Hoare에 의해 "condition variable"이라는 이름 붙여졌다.

이러한 조건 변수를 선언하려면 단순히 pthread_cond_t c를 쓰면 된다. 조건 변수 c를 선언하는 것이다. 선언 후에는 알맞은 초기화 또한 필요하다. 조건 변수는 이와 관련한 두 연산, wait()와 signal()을 가진다. wait() 콜은 스레드가 자기 자신을 재우고 싶을 때 실행되고, signal() 콜은 스레드가 프로그램의 어떤 것을 변화시켜 해당 조건을 기다리고 있는 잠든 스레드를 깨우고 싶을 때 사용한다. 구체적으로, POSIX 콜들은 다음과 같다.

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

이들은 간단히 wait()와 signal()로 부르게 될 것이다. wait() 콜을 보면 조건 변수 c와 함께 뮤텍스 m도 파라미터로 가진다는 것을 볼 수 있는데, 이 뮤텍스는 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;
}

여기서 고려해야 할 두 가지 경우가 있다. 첫 번째로, 부모 스레드는 자식 스레드를 만들고 나서 계속 실행되어, 즉시 thr-join()을 호출해 자식 스레드가 종료되기를 기다리는 경우를 생각해보자. 이 경우 부모 스레드는 락을 얻고, 자식 스레드의 완료 여부를 확인하고, wait()를 호출해 자게 된다. 자식 스레드는 실행되어 "child" 메시지를 출력하고 thr_exit()을 호출해 부모 스레드를 깨운다. thr_exit()은 락을 얻고 상태 변수 done을 설정하고, 부모에 시그널을 보내 깨운다. 마지막으로 부모 스레드는 실행되고, 락을 풀고, "parent: end" 메시지를 출력한다.

두 번째 경우, 자식 스레드는 생성되자마자 바로 실행되고, done을 1로 바꾸고, 잠들어 있는 스레드를 깨우는 시그널을 호출한 후, 작업을 마친다. 다만 이때에는 잠들어 있는 스레드가 없으므로 바로 리턴하게 된다. 그러면 부모 스레드가 실행되고 thr_join()을 호출하는데, 이때 done은 1이므로 대기하지 않고 바로 리턴한다.

부모 스레드가 if문이 아니라 while문을 통해 조건에 따라 대기하고 있음을 볼 수 있다. 프로그램의 로직에 따르면 엄격하게는 불필요해 보이지만, 사실은 좋은 이유가 있다. 그 이유는 아래에서 다룬다.

thr_exit()와 thr_join() 코드의 중요성을 잘 확인했는지 확인하기 위해, 몇 가지 다른 구현들을 시도해보자. 우선 상태 변수 done은 왜 필요한 걸까? 아래와 같이 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로 바꾸고 시그널을 보내지만, 대기 중인 스레드가 없으므로 어떤 스레드도 깨어나지 않는다. 부모 스레드는 재실행되면, 영원히 자게 된다.

이 간단한 조인 예제로부터 조건 변수를 적절하게 사용하기 위해 필요한 기본적인 요소들을 잘 알게 됐을 것이다. 이제는 좀 더 복잡한 예제들을 살펴보자. 생산자/소비자(producer/consumer), 또는 유한 버퍼(bounded-buffer)라 불리는 문제다.

2. The Producer / Consumer (Bounded Buffer) Problem

이 장에서 마주칠 다음 동기화 문제는 생산자/소비자 문제, 또는 유한 버퍼 문제라 불리는 것으로, Dijkstra가 처음으로 제기했다. 사실 Dijkstra와 그의 동료들이 일반화된 세마포어를 만들게 한 것이 바로 이 생산자/소비자 문제다. (세마포어에 대해서는 나중에 다루게 될 것이다)

하나 이상의 생산자 스레드와 하나 이상의 소비자 스레드가 있다고 생각해보자. 생산자 스레드는 데이터 아이템을 만들어 버퍼에 넣고, 소비자 스레드는 버퍼에서 그 아이템들을 가져와 각자의 방식으로 소비한다.

많은 실제 시스템에서 이와 같은 방식을 변용해 사용하는데, 예를 들어 멀티-스레드 웹 서버에서 생산자는 HTTP 요청은 작업 큐(즉 유한 버퍼)에 집어 넣고, 소비자는 큐에서 해당 요청을 꺼내 처리한다.

유한 버퍼는 한 프로그램의 아웃풋을 다른 프로그램으로 파이핑할 때도 사용된다 (예. grep foo file.txt | wc -l). 여기서는 두 프로세스가 병행적으로 실행되는데, grep은 file.txt 에서 foo 문자열을 찾아 표준 출력으로 출력한다. UNIX 쉘은 이 출력을 UNIX 파이프로 리다이렉트하는데, 이 파이프의 다른 한 끝은 프로세스 wc의 표준 입력에 연결되어있다. 이 wc는 단순히 입력 스트림의 줄 수를 세서 그 결과를 출력한다. 따라서 여기에서 grep은 생산자가 되고 wc는 소비자가 된다. 이 둘 사이에는 커널 내부의 유한 버퍼가 있다.

유한 버퍼는 공유 자원이기 경쟁 조건이 일어나지 않게 하기 위한 동기화된 접근을 필요로 한다. 이 문제에 대해 좀 더 잘 알기 위해, 다음의 실제 코드를 살펴보자.

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() 루틴은 버퍼가 비어있는지를 확인하고 공유 버퍼에 값을 넣은 뒤, 이 버퍼가 차 있음을 표시하기 위해 count를 1로 바꾼다. get() 루틴은 반대로 버퍼를 비우고 값을 반환한다. 이 공유 버퍼가 고작 하나의 엔트리를 가진다고 걱정하지는 말자. 나중에 이를 여러 엔트리를 담을 수 있는 큐로 일반화할 것이다.

다음으로는 데이터를 넣거나 빼기 위해 언제 버퍼에 접근하는 것이 괜찮을지를 알기 위한 루틴들을 작성해보자. 조건은 분명하다. count가 0일 때에만, 즉 버퍼가 비어있을 때에만 버퍼에 데이터를 집어 넣고, count가 1일 떄에만, 즉 버퍼가 꽉 차 있을 때에만 버퍼로부터 값을 꺼낸다. 만약 꽉 찬 버퍼에 값을 넣거나, 빈 버퍼로부터 값을 꺼내는 동기화 코드를 작성한다면 뭔가 잘못된 것이다.

이 작업은 두 종류의 스레드에 의해 진행될 것인데, 하나는 생산자 스레드이고, 나머지 하나는 소비자 스레드다. 아래는 공유 버퍼 loops에 정수를 몇 번 집어넣는 생산자와, 공유 버퍼로부터 계속해서 데이터를 꺼내어 해당 아이템을 출력하는 생산자의 코드다.

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

A Broken Solution

하나의 생산자와 소비자가 있다고 해보자. put()과 get() 루틴들은 임계 영역을 가지고 있다. put()은 버퍼를 업데이트하고 get()은 버퍼 내의 값을 읽어오기 때문이다. 하지만 코드 주변에 락을 집어 넣는 것은 동작하지 않는다. 뭔가가 더 필요하다. 바로 공유 변수다.

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

위 코드에서는 하나의 조건 변수 cond와, 이와 관련된 락 mutex를 사용한다. 생산자와 스레드 사이의 시그널링 로직을 살펴보자. 생산자는 버퍼를 채우고 싶을 때, 해당 버퍼가 비워질 때까지 기다린다. 소비자도 마찬가지의 로직을 가지고 있는데, 반대로 버퍼가 꽉 차있기를 기다린다.

하나의 생산자와 소비자를 사용하는 경우, 위 코드는 잘 동작한다. 하지만 더 많은 스레드들이 이러한 작업을 하게 되면, 이 해법은 두 가지의 심각한 문제들을 가진다.

첫 번째로, wait()를 호출하기 전의 if 문을 보자. 이때 소비자 스레드로는 $T_{c1}, T_{c2}$의 두 개가 있고 생산자 스레드로는 $T_p$ 하나가 있다고 가정한다. $T_{c1}$ 스레드가 먼저 돌아가서 락을 얻고(c1), 소비할 수 있는 버퍼가 있느니를 확인한 후(c2), 아무 것도 없으므로 대기하고 락을 푼다(c3).

다음으로 생산자 스레드 $T_p$가 돌아간다. 락을 얻고(p1), 버퍼가 차있는지 확인하고(p2), 그렇지 않으므로 계속 진행해 버퍼를 채운다(p4). 이후 생산자 스레드는 버퍼가 채워졌다는 시그널을 보낸다(p5). 이 시그널은 첫 번째 소비자 $T_{c1}$을 깨워 다시 실행시킬 수 있게 만든다. 이후로도 생산자 스레드는 버퍼가 꽉 차서 잠들기 전까지 계속 실행된다.

여기서 문제가 발생한다. 다른 소비자 스레드 $T_{c2}$가 들어와서 버퍼에 있는 한 값을 소비한다고 하자. 이때 $T_{c1}$이 돌아간다고 하자. 대기 상태에서 돌아가기 전에, 이 스레드는 락을 다시 얻고 나서 리턴한다. 그러고 나면 get()(c4)를 호출하는데, 버퍼에는 소비할 수 있는 게 없다. assertion 트리거와 코드는 바라던대로 동작하지 않는다. 여기서는 $T_{c2}$가 들어와 버퍼에 있는 값 하나를 소비 해갔으므로 $T_{c1}$이 또 버퍼로부터 값을 소비하는 일을 막아야 한다. 아래의 표는 시간에 따른 각 스레드가 동작과 해당 스레드의 스케줄러 상태를 보여준다.

이 문제는 다음의 간단한 이유로 일어난다. 생산자 스레드가 $T_{c1}$을 깨운 후, 그리고 $T_{c1}$이 실행되기 시점에 유한 버퍼의 상태가 변했기 때문이다. 스레드에 시그널을 보내는 것은 그저 스레드를 깨울 뿐으로, 관심이 있는 상태가 변했다는 힌트를 줄 뿐이다. 이것이 깨어난 스레드가 실행될 때에도 해당 상태가 여전히 바라던대로라는 것을 보장해주지는 않는다. 시그널의 의미를 이렇게 해석하는 것을 Mesa semantics라 부른다. 이와 반대되는 것으로는 Hoare semantics가 있다. 이는 만들기는 어렵지만 깨어난 스레드가 깨어난 직후 바로 실행될 것임을 보장해준다. 실제로는 거의 모든 시스템들이 Mesa semantics를 사용하고 있따.

Better, But Still Broken: While, Not If

다행스럽게도 고치는 것은 쉽다. if를 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);
	}
}

왜 이것이 동작하는지를 생각해보자. 이제는 $T_{c1}$이 일어나면 락을 잡고 공유 변수의 상태를 즉시 재확인한다(c2). 만약 이 지점에서 버퍼가 비어있으면 소비자 스레드는 그냥 다시 잠든다(c3). 셍산자 스레드의 루틴에서도 마찬가지로 if를 while로 바뀐다(p2).

Mesa semantics에서 조건 변수를 사용하기 위해 기억해야 할 간단한 법칙은 항상 while 루프를 사용하는 것이다. 어떤 경우에는 조건을 재확인할 필요가 없을지도 모르겠지만, 항상 이렇게 하는 게 안전하다.

하지만 이 수정된 코드에도 버그가 있다. 위에서 언급한 두 문제 중 두 번째로, 오직 하나의 조건 변수만을 사용한다는 사실과 관련이 있다.

문제는 두 소비자 스레드가 먼저 실행되고, 그 모두가 잠들게 되는 경우에 발생한다. 이후에는 생산자 스레드가 실행되어 버퍼에 값을 집어 넣고 소비자 스레드 중 하나($T_{c1}$이라 하자)를 깨운다. 생산자는 다시 루프하고 버퍼에 더 많은 데이터를 넣으려 하겠지만, 버퍼가 이미 꽉 차있으므로 대기하며 잠든다. 이제 $T_{c1}$ 스레드는 실행 대기 상태에 있고, 나머지 두 스레드는 잠들어 있다.

이제 $T_{c1}$은 $wait()$로부터 돌아와 깨어나고(c3), 조건을 재확인하고(c2), 버퍼가 꽉 차있음을 보고 값을 소비한다(c4). 이 소비자는 시그널을 발생해, 잠들어 있는 스레드들 중 하나만을 깨운다. 그런데 잠들어 있는 스레드는 두 개였다. 이 중 어떤 스레드를 깨워야할까?

소비자자 스레드가 버퍼를 비웠으므로, 분명히 생산자 스레드를 꺠워야 할 것 같다. 하지만 이 스레드가 만약 $T_{c2}$ 스레드를 깨운다면 문제가 발생한다. $T_{c2}$는 깨어나고, 버퍼가 비어있음을 확인하고(c2), 다시 잠든다(c3). 생산자 $T_p$는 그냥 잠들어 있는 상태로 있는다. 버퍼가 비어있으므로 $T_{c1}$도 다시 잠든다. 모든 스레드들이 잠들게 되는 것이다. 전체적인 흐름은 아래의 표를 보라.

시그널링은 필요하지만, 좀 더 직접적이어야 한다. 소비자는 다른 소비자가 아닌 생산자만을 깨워야하고, 반대도 마찬가지다.

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

이 코드에서 생산자 스레드는 조건 empty에 따라 기다리고, fill에 시그널을 보낸다. 반대로 소비자 스레드는 fill에 따라 대기하고 empty에 시그널을 보낸다. 이렇게 함으로써 위의 두 번째 문제점은 해결된다. 소비자가 의도치 않게 다른 소비자를 깨우는 일은 없고, 생산자가 의도치 않게 다른 생산자를 깨우게 되는 일도 없다.

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

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()이 바뀌어야 하고, 생산자와 소비자가 잠들지의 여부를 결정하기 위해 확인하는 조건도 바뀌어야 한다. 변경된 올바른 대기 및 시그널링 로직은 위와 같다. 생산자는 모든 버퍼가 차있는 경우(p2)에만 잠들고, 비슷하게 소비자는 모든 버퍼가 비어있는 경우(c2)에만 잠든다.

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

코드에서 볼 수 있듯, 스레드는 메모리 할당 코드를 호출했을 때 더 많은 메모리가 사용 가능해지기를 기다려야할 수도 있다. 반대로 스레드는 메모리 할당을 해제 했을 때, 더 많은 메모리가 사용 가능하다는 시그널을 보내야 한다. 하지만 위의 코드는 문제를 가지고 있다. 대기 중인 스레드 중 어떤 것이 깨어나야 할까?

다음과 같은 시나리오를 생각해보자. 지금 가용 메모리는 없다. 스레드 $T_a$가 allocate(100)을 호출하고, 뒤이어 스레드 $T_b$는 allocate(10)을 호출한다. 현재 이 두 요청을 만족시킬 수 있는 충분한 가용 메모리가 없으므로 두 스레드는 모두 조건-대기하고 잠든다.

이때, 세 번째 스레드 $T_c$가 free(50)을 호출했다고 해보자. 이 스레드는 대기 중인 스레드를 깨우는 시그널을 보낸다. 이때 잠들어 있는 스레드 중 $T_b$가 깨어나야 하고, $T_a$는 잠들어 있어야 한다. 하지만 $T_c$의 시그널이 올바른 스레드를 깨우리라는 보장은 없다. 그렇기 때문에 위 코드는 작동하지 않을 수 있다. 다른 스레드들을 깨우는 스레드는 어떤 스레드가 깨어나야 할지는 모르기 때문이다.

Lampson과 Redell이 제시한 해법은 직관적이다. 코드의 pthread_cond_signal() 콜을 대기 중인 모든 스레드를 깨우는 pthread_cond_broadcast()로 바꾸는 것이다. 이렇게 하면 깨어나야 하는 어떤 스레드든지 깨어난다는 것을 보장할 수 있다. 물론 성능적으로는 좋지 않다. 깨어나지 않아도 되는 것들을 포함해, 필요 이상으로 많은 스레드들을 깨우게 될 것이기 때문이다. 그 스레드들은 깨어나서, 조건을 재확인하고, 즉시 다시 잠들게 된다.

Lampson과 Redell은 이런 조건을 포함 조건(covering condition)이라 불렀는데, 이것이 스레드가 깨어나야 하는 모든 경우들을 포함하는 것이기 때문이다. 앞서 말했듯, 비용은 너무 많은 스레드들이 깨어나게 될 것이라는 점이다.

이와 같은 접근법을 앞서의 생산자/소비자 문제에서도 사용할 수 있었을 것이다. 하지만 그 경우에는 위에서 나온 해법이 더 낫다. 일반적으로 프로그램이 시그널을 브로드캐스트로 바꿔야만 작동한다면, 아마도 버그가 있을 것이다. 하지만 위의 메모리 할당기와 같은 경우, 브로드캐스트가 가능한 가장 직관적인 해법일 것이다.

4. Summary

지금까지 락보다도 중요한, 다른 동기화 기법에 대해 알아봤다. 원하지 않는 프로그램 상태에서는 스레드를 잠들게 함으로써, 조건 변수는 많은 중요한 동기화 문제들을 해결할 수 있게 해준다.