OSTEP 30 - Condition Variables

JiYun·2025년 3월 22일
CSOSOSTEP

OSTEP

목록 보기
19/21

지금까지 락의 개념을 학습하면서 하드웨어와 운영체제의 적절한 지원을 통해 제대로 된 락을 만드는 법을 살펴보았다. 불행히도“락”만으로는 병행 프로그램을 제대로 작성 수 없다.

쓰레드가 계속 진행하기 전에 어떤 조건이 참인지를 검사해야 하는 경우가 많이 있다. 예를 들면 자식 쓰레드가 작업을 끝냈는지 여부를 알 필요가 있다. 이런 걸 어떻게 구현할 수 있을까?

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)
	; // spin
	printf(“parent: end\n ”);
	return 0;
}

위처럼 공유 변수로 구현할 수 있다 하지만 부모 쓰레드가 spin 하면서 자원을 낭비하고 있다. 이 방법 대신 부모 쓰레드가 특정 조건이 만족될때까지 잠자면서 기다리는 것이 더 좋다.

1. 정의와 루틴들

조건이 참이 될 때까지 기다리기 위해 컨디션 변수를 활용할 수 있다. 일종의 큐 자료로서, 어떤 실행의 상태가 원하는 것과 다를 때 조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐이다. 쓰레드가 상태를 변경시켰을 때, 대기 중이던 쓰레드를 깨워 이어서 진행될 수 있도록 한다.

pthread_cond_t c; 라고 써서 c가 컨디션 변수가 되도록 선언하고 초기화한다. 컨디션 변수에는 wait() 과 signal() 이라는 두 가지 연산이 존재한다.

wait() 은 쓰레드가 스스로를 잠재우기 위해 호출하는 것이고, signal()은 쓰레드가 무엇인가를 변경했기 때문에 조건이 참이 되기를 기다리며 잠자고 있던 쓰레드를 깨울 때 호출한다.

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()을 호출하고 자식 쓰레드를 기다리는 경우

    부모 스레드는 thr_join()에서 done이 아직 1이 아니기 때문에 잠들게 된다. 자식 스레드의 실행 종료 후, 부모 스레드가 깨어나게 된다.

  2. 자식 쓰레드가 생성되자마자 즉시 실행되는 경우

    자식 쓰레드가 즉시 실행되기 때문에, 부모 스레드가 thr_join()에 진입할 때 이미 done은 1이다. thr_join() 함수에서 대기가 일어나지 않고 바로 리턴한다.

매우 중요한 사실이 있다. 부모 쓰레드가 조건을 검사할 때(이 예제에서는 done의 값) if 문이 아니라 while 문을 사용한다는 사실이다

thr_exit(), thr_join()의 중요성을 이해할 수 있도록 몇 가지 구현의 방식을 살펴보자.

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()를 호출하는 경우를 생각해 보자. 이 경우 자식 스레드가 시그널을 보내는 시점에는 깨워야할 스레드가 없다. 부모 스레드가 실행되면 깨워줄 스레드가 없게된다. 이를 통해 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()가 호출되기 직전에 인터럽트가 발생하게 된다면 자식 스레드가 먼저 실행될 것이다. 이후에는 위 예시와 비슷하게 부모가 wait() 호출하여 잠자게 되고, 깨워줄 스레드가 없게된다.

시그널을 보내기 전에 항상 락을 획득하자

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

다음으로 살펴볼 동기화 문제는 Dijkstra가 처음 제시한 생산자/소비자(producer/consumer) 문제이다. 유한 버퍼(bounded 버퍼) 문제로도 알려져 있다. lock 대신 일반화된 세마포어를 발명하게 된 이유가 이 문제 때문이다.

여러 개의 생산자 쓰레드와 소비자 쓰레드가 있다고 하자. 생산자는 데이터를 만들어 버퍼에 넣고, 소비자는 버퍼에서 데이터를 꺼내어 사용한다. 이러한 관계는 실제로 시스템에서 자주 일어난다. 예를 들어 멀티 쓰레드 웹 서버의 경우 생산자는 HTTP 요청을 작업 큐 (유한 버퍼) 에 넣고, 소비자 쓰레드는 이 큐에서 요청을 꺼내어 처리한다.

grep foo file.txt | wc -l와 같은 문장처럼 파이프 명령으로 한 프로그램의 결과를 다른 프로그램에게 전달할 때도 유한 버퍼를 사용한다. UNIX 쉘은 출력 결과를 UNIX 파이프 라는 곳으로 전송한다. 파이프의 한쪽 끝에는 wc 프로세스의 표준 입력과 연결되어 있다. 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;
}
  • put() 버퍼가 비어있다고 (count == 0 인지 확인하고), 값을 버퍼에 넣고 count를 1로 설정해 가득 찼음을 표시한다.
  • get() 버퍼가 찼는지 확인하고 (count == 1 인지), 값을 꺼낸 후 버퍼가 비었다고 설정한다.

두개의 스레드에서 하나는 put()하고 다른 하나는 get()을 수행한다고 생각했을 때, 당연히 제대로 동작하지 않을 것이다.

불완전한 해법

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

컨디션 변수 하나와 그것과 연결된 mutex 락을 사용하는 방식을 먼저 시도해보자.

생산자는 버퍼가 빌 때까지 기다린다(p1-p3). 소비자도 버퍼가 차기를 기다린다(c1-c3). 생산자와 소비자가 하나씩인 경우에는 잘 동작하지만, 소비자가 더 많아지면 문제가 있다.

첫 번째 문제.

wait()함수 전의 if문과 관계가 있다.

생산자와 소비자 1, 2가 존재한다고 가정하자.

  1. 소비자 1이 먼저 실행된다. 버퍼가 비어있기 때문에 wait()를 호출하고 잠들게 된다.
  2. 생산자가 실행된다. 버퍼가 비어있으므로 버퍼를 채운다. 이후 다시 생산자가 실행되면서 버퍼가 차있기 때문에 잠들게 된다.
  3. 소비자 2가 갑자기 끼어든다. 버퍼가 차있기 때문에 이를 소비하게된다.
  4. 이제 소비자 1이 실행된다. wait()가 실행된 코드를 지나 get()을 호출하게 되는데, 버퍼가 비어있게 된다!

코드가 의도한대로 동작하지 못했다.

문제의 원인은 Tc1이 깨어나서 실행되기까지의 사이에 유한 버퍼의 상태가 변경되었기 때문이다. 시그널은 쓰레드를 깨우기만 하고, 깨어난 쓰레드가 실제 싱행되는 시점에 그 상태가 유지된다는 보장은 없다. 이런 식으로 시그널을 정의하는 것을 Mesa Semantic이라 한다. 대비되는 개념은 Hoare Semantic인데 구현하기는 더 어렵지만 깨어난 즉시 쓰레드가 실행되는 것을 보장한다.

개선된, 하지만 아직도 불완전한: if문 대신 while문

while문을 사용하게 된다면, 위 경우에서 소비자 1이 깨어나게 되더라도, 버퍼가 비었는지를 다시 확인하고 잠들게 될 것이다. Mesa semantic의 컨디션 변수에서 가장 기본적인 법칙은 언제나 while 문을 사용하라는 것이다.

하지만 아직도 코드에는 버그가 있다. 컨디션 변수가 하나라는 것과 관계가 있다.

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

두 번째 문제.

이 문제는 소비자 1, 2가 모두 먼저 실행되어 대기 상태에 있을 때 발생한다.

  1. 생산자가 실행되어 버퍼를 채우고, 소비자 1을 깨웠다고 가정하자. 생산자는 다시 잠들 것이다.
  2. 소비자 1은 버퍼를 소비하고, 대기 중인 스레드를 하나 깨운다. 어떤 스레드를 깨워야할까?
  3. 당연히 생산자를 깨워야하겠지만, 소비자 2를 깨웠다고 가정해보자.
  4. 소비자 2는 while문에서 버퍼가 비어있는걸 확인하고 다시 잠들게 된다.

이럴수가! 모든 스레드가 잠들어버렸다.

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

단일 버퍼 생산자/소비자 해법

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

생산자 쓰레드가 empty 조건 변수에서 대기하고 fill에 대해서 시그널을 발생한다. 정반대로 소비자 쓰레드는 fill 에 대해서 대기하고 empty에 대해서 시그널을 발생시킨다. 이를 통해 반드시 소비자는 생산자를 깨우고, 생산자는 소비자를 깨우게 된다.

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 == 1) // 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() 함수를 수정했다.

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

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

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

멀티 쓰레드 기반 메모리 할당 라이브러리 예제를 살펴보자.

메모리 할당 코드를 호출하면, 공간이 생길 때까지 기다려야할 수도 있다. 반대로 쓰레드가 메모리를 반납 시, 메모리 공간의 발생을 알리는 시그널을 생성할 수 있다. 이 시그널을 날릴 때, 어떤 스레드가 깨어나야 될까?

이러한 시나리오를 살펴보자

  1. 쓰레드 1이 allocate(100), 쓰레드 2가 allocate(10) 를 호출한다. 아직 여유 공간이 없어 둘다 대기 상태가 된다.
  2. 쓰레드 3은 free(50)을 호출한다. 상식적으로 생각하면, 스레드 2를 깨워야할 것이지만, 코드는 원하는대로 동작하지 않는다.

해법은 단순하다.

pthread_cond_signal()을 대기 중인 모든 쓰레드를 깨우는 pthread_cond_broadcast()로 바꿔서 사용하면 된다. 다만 깨어날 필요가 없는 불필요한 쓰레드가 모두 깨어나 성능에 안좋은 영향을 미칠 수 있다.

이런 경우를 포함 조건(covering condition)이라고 한다. 쓰레드가 깨어나야하는 모든 경우를 다 포함하기 때문이고, 모든 스레드가 깨어나기 때문에 문맥전환 오버헤드가 크다.

일반적으로 시그널을 브로드캐스트(broadcast)로 바꿨을 때만 프로그램이 동작한다면 아마도 버그가 존재하는 것일 거다. 앞서 다룬 메모리 할당 문제의 경우 브로드캐스트를 적용하는 것이 가장 자명한 해법이다.

profile
JiYun
고수가 되고싶다
이전 포스트

OSTEP 29 - Locked Data Structures

다음 포스트

OSTEP 31 - Semaphore

0개의 댓글