[OSTEP 운영체제 정리] - Condition Variable

핀터레스트에 맛들인 인간.

조건을 기다리는 방법

어떤 조건이 참이 되기 전까지 스레드가 대기하는 것이 필요하다.

물론 조건이 참이 될 때까지 단순히 반복할 수 있지만 ⇒ CPU 사이클을 낭비

volatile int done = 0;

void *child(void *arg) {
    printf("child\\n");
    done = 1;
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t c;
    printf("parent: begin\\n");
    pthread_create(&c, NULL, child, NULL); // create child
    while (done == 0); // 회전
    printf("parent: end\\n");
    return 0;
}

Condition Variable

조건이 참이 될 때까지 기다리기 위해 컨디션 변수를 활용할 수 있다.

컨디션 변수는 일종의 큐 자료 구조 어떤 실행의 상태가 원하는 것과 다를 때 조건이 참이 되기를 기다리며 쓰레드가 대기할 수 있는 큐이다.

다른 쓰레드가 상태를 변경시켰을 때, 대기 중이던 쓰레드를 깨우고, 계속 진행할 수 있도록 한다.

// c가 컨디션 변수가 되도록 선언
pthread_cond_t c; 

// 컨디션 변수에는 wait()와 signal() 두개의 연산이 있다.

//wait
pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
쓰레드가 스스로를 잠재우기 위해서 호출하는 것
mutex를 매개변수로 사용한다
wait의 역할은 락을 해제하고 호출한 쓰레드를 재우는 것
다른 쓰레드가 시그널을 보내어 쓰레드가 깨어나면 ***wait()에서 리턴하기 전에 락을 재획득해야 한다.***

//signal()
pthread_cond_signal(pthread_cond_t *c);
쓰레드가 무엇인가를 변경했기 때문에 조건이 참이 되기를 기다리며 잠자고 있던 쓰레드를 깨울 때 호출한다. 

int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void *child(void *arg) {
	printf("child\\n");
	thr_exit();
	return NULL;
}

int main(int argc, char *argv[]) {
	pthread_t p;
	printf("parent: begin\\n");
	pthread_create(&p, NULL, child, NULL);
	thr_join();
	printf("parent: end\\n");
	return 0;
}

void thr_exit() {
	pthread_mutex_lock(&m);
	done = 1;
	pthread_cond_signal(&c);
	pthread_mutex_unlock(&m);
}

void thr_join() {
	pthread_mutex_lock(&m);
	while (done == 0)
		pthread_cond_wait(&c, &m);
	pthread_mutex_unlock(&m);
	}

What if ? – No State Variable, 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()을 호출하고 거기서 멈춰있을 것이다. 어떤 쓰레드도 부모를 깨우지 않을 것이다.

➡️ 상태 변수는 중요하다 !

 

What if ? – No Lock

시그널을 주거나 대기할 때 락을 획득할 필요가 없다고 가정

void thr_exit() {
	done = 1;
	pthread_cond_signal(&c);
}
void thr_join() {
	while (done == 0)
	pthread_cond_wait(&c);
}

여기서는 경쟁 조건이 발생한다.

만약 부모 쓰레드가ㅏ thr_join()을 호출하고나서 done 변수 값이 0인 것을 확인한 후 잠자려고 했다. 하지만 wait()을 호출하기 직전에 부모 쓰레드가 인터럽트에 걸려서 자식 쓰레드가 실행이 되었다.

자식 쓰레드는 done을 1로 변경하고 시그널 보낸다.

하지만 댁기중인 쓰레드가 없다.

부모 쓰레드가 다시 실행되면 wait()을 호출하고 잠자게 된다.

➡️ 잠든 부모 쓰레드를 깨워줄 쓰레드가 없다.

Producer/Consumer Problem

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

생산자 : 데이터를 만들어 버퍼에 넣는다.

소비자 : 버퍼에서 데이터를 꺼내어 사용한다.

ex) web server grep foo file.txt | wc –l, ⇒ 한 프로그램의 결과를 다른 프로그램에게 전달

✅ 유한버퍼(bounded buffer)는 공유 자원이다. 경쟁 조건의 발생을 방지하기 위해 동기화가 필요하다.

생산자는 넣고 소비자는 꺼내어 쓸 수 있는 공유 버퍼가 하나 필요, 한개의 정수를 사용하고 공유 버퍼에 값을 넣는 루틴과 버퍼에서 값을 꺼내는 루틴 두개가 있다.

IF

int buffer; // single buffer
int count = 0; // 처음에는 비어있음
void put(int value) {
	assert(count == 0);
	count = 1;
	buffer = value;
}
int get() {
	assert(count == 1);
	count = 0;
	return buffer;
}

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

 

문제점

$ T_{c1} $과 $T_{c2}$ 라는 두개의 소비자

$T_{p}$ 의 한개의 생산자.

1. 소비자 $T_{c1}$이 먼저 실행
2. 락을 획득하고 버퍼를 소비할수 있는지 확인, 비어았음 확인 후 대기, 락 해제
3. $T_{p}$ 실행 락을 획득, 버퍼 비엇는지 확인, 비었다⇒ 채우고 버퍼 다 찻다는 시그널 보내기
4. 대기중이던 $T_{c1}$ 깨어나 준비 큐로 이동, 실행할 수 있지만, 아직 실행 상태가 아님

만약 여기서 다른 소비자 $T_{c2}$가 끼어들어 버퍼를 소비한다면?

 

 

 

 

$T_{c1}$이 실행되다고 하면 대기에서 리턴하기 전에 락을 획득한다. 그리고 get()을 호출하여 하지만 버퍼는 비었다 ➡️ 끼어들어 소비하여서 $T_{c1}$이 비어있는 행위를 막았어야됐다 !

✅ 문제의 원인 : $T_{c1}$이 깨어나서 실행되기까지 사이에 유한 버퍼의 상태가 변경되었다.

 

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

 

문제점

문제는 소비자 쓰레드 $T_{c1}$과 $T_{c2}$가 먼저 실행한 후에 둘다 대기상태에 있을 때 발생한다.

 

생산자가 실행되어 버퍼에 값을 넣고 대기 중인 쓰레드 하나를 깨우고 자신은 대기한다. $T_{c1}$이 실행할 준비가 되었고 $T_{c2}$와 $T_{p}$는 대기중이다.

 

$T_{c1}$은 wait()에서 리턴을 받아 깨어나고 버퍼가 차있는 것을 확인하고 값을 소비한다. 후에 시그널을 전송하여 대기중인 쓰레드 중 하나를 깨운다

 

버퍼를 비웠기 때문에 생산자를 깨워야한다. 하지만 만약 소비자가 $T_{c2}$를 깨운다면 ?????

 

$T_{c2}$도 버퍼가 비어있다는 것을 알고 다시 대기상태로,

‼️ 세개의 쓰레드 모두 대기 상태

✅ 소비자는 다른 소비자를 깨울 수 없고 생산자만 깨우자 !!!, 그 반대 생산자의 경우도 그러자!!

 

 

while & Two CVs

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

생산자 쓰레드가 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);
	}
}

More Concurrency & Efficiency

‼️ 더 병행성을 증가시키고 효율적으로 만들어보자

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, tmp;
	for (i = 0; i < loops; i++) {
		pthread_mutex_lock(&mutex); // c1
		while (count == 0) // c2
			pthread_cond_wait(&fill, &mutex); // c3
		tmp = get(); // c4
		pthread_cond_signal(&empty); // c5
		pthread_mutex_unlock(&mutex); // c6
		printf("%d\\n", tmp);
	}
}

Covering Conditions: 컨디션 변수 사용시 주의 점

메모리 할당 코드를 호출하면 공간이 생길 때까지 기다려야할 수 있다. 반대로, 쓰레드가 메모리 반납시, 사용 가능한 메모리 공간을 발생을 알리는 시그널을 생성할 수 있다.

문제점 : 어떤 쓰레드가 깨어나야 하는가?

  빈공간이 없다고 가정하고 쓰레드 $T_{a}$가 allocate(100)을 실행하고 다음으로 쓰레드 $T_{b}$가 allocate(10)을 호출한다.
  쓰레드 $T_{a}$ 와 $T_{b}$는 대기 상태로 들어간다. 이 시점에서 쓰레드 $T_{c}$가 세번째로 free(50)을 호출한다.
  ⇒ 이 호출의 결과로 잘못된 쓰레드가 깨어날 수 있다.

  ⇒ $T_{b}$가 깨어나야 한다. , 어떤 쓰레드를 깨워야할지 모르기 때문에 문제 발생

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

✅ 해결방법

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

단점

: 아직 깨어나면 안되는 여러 쓰레드가 불필요하게 깨어날 수도 있다는 점이 성능에 안좋다. 그렇게 깨어난 쓰레드들은 깨어나서 조건을 재검사하고, 즉시 대기 상태로 들어간다.

---

[출처]
https://github.com/remzi-arpacidusseau/ostep-translations/blob/master/korean/README.md

ostep-translations/korean/README.md at master · remzi-arpacidusseau/ostep-translations

 

해당 책을 기반으로 정리하였습니다.