Condition Variables

Condition Variables

concurrent program을 위한 유일한 요소는 lock뿐만이 아니다.

thread들이 실행을 계속할지의 여부를 결정하기 위해서는 condition을 확인해야한다.위의 코드처럼 부모 thread가 자식 thread의 종료를 기다리는 상황에서 단순하게 spin-base의 접근법을 생각해볼 수 있다. 하지만 spin-base 접근법의 문제인 CPU의 낭비가 발생한다는 문제를 피할 수 없다.
다른 방법으로는 자식 thread가 종료될 때 까지 부모 thread를 sleep 시켜두는 방식일 수 있다.

그렇다면 어떻게 thread가 그런 condition이 될 때까지 기다려야할까..?

Definition and Routines

condition을 기다리기 위해서는 condition variable이라는 것을 활용해야한다.

condition variable은 특정한 실행 상태(조건)가 원하는 상태가 아닐 때(예를들면 condition을 기다리는 상태) thread를 배치할 수 있는 thread queue이다. 즉 원하는 condition을 위해서 기다리는 thread를 저장해두기 위한 queue이다.

그래서 원하는 condition이 충족되면 signaling을 통해 하나 이상의 thread를 깨워서 실행할 수 있다.signal(), wait()과 관련된 Pthread_cond_t c ;를 선언한다. 그리고 lock을 걸어서 condition을 기다리고, unlock시에 condition에 signal을 발생시킨다.

이 상황에서 고려해야할 상황은 2가지이다.

첫번째는 부모 thread에서는 자식 thread를 생성한 이후에 계속 진행되어 thr_join()을 호출한 후 자식 thread가 종료될 때 까지 계속 확인하며 기다려야 한다. 자식 thread가 종료된 이후에는 thr_exit()이 호출되고 condition variable done을 1로 변경한 후 부모 thread를 깨운다.

또는 자식 thread가 시작하자마자 done을 1로 만들어서 부모 thread가 thr_join()을 하자마자 종료될 수 있는 경우이다.

하지만 condition varible이 없는경우를 생각해 볼 수도 있다.하지만 위의 코드는 잘못된 접근법이다. 왜냐하면 예를들어 자식 thread가 즉시 thr_exit()을 호출하는 경우를 생각해보자. 자식 thread가 signal을 보내지만 잠들어있는 thread가 하나도 없다. 그리고 부모 thread는 계속해서 자식 thread를 기다리고 있을 뿐이다.

따라서 위의 경우를 고려하면 condition variable이 필요하다는 것을 알 수 있다.

또한 lock이 없는 경우를 생각해 볼 수도 있다.하지만 위와같은 경우에도 race condition을 다뤄야 한다. condition variable을 바꾸려는 찰나에 interrupt가 발생하여 condition variable을 변경하게 될 수 있는 문제가 있다.

따라서 위의 경우도 역시 condition variable이 필요함을 알 수 있다.

The Producer/Consumer (Bounded Buffer) Problem

이제 좀 더 복잡한 경우를 살펴볼 것이다.

하나 이상의 producet thread와 하나 이상의 consumer thread가 있다고 생각해보자.
producer는 data item들을 만들고 buffer에 저장한다. consumer는 buffer에 있는 item들을 가져다가 사용한다.

예를들어 multi-threaded web server에서 producer thread는 http 요청을 작업 queue에 저장해두고, consumer thread가 이 queue에서 요청들을 가져다가 처리한다.

그리고 bounded buffer는 마치 pipe처럼 한 프로그램의 출력을 다른 프로그램으로 전달할 때 사용한다.

grep foo.txt | wc -l

bounded buffer는 shared resource라서 synchronized access가 필요하다.
오직 count가 0일 때만 buffer에 값을 넣을 수 있고, 오직 count가 1일 때만 buffer에서 값을 얻을 수 있다.
producer가 loop번 만큼 buffer에 값을 입력하고, consumer는 buffer에서 값을 읽어온다.

하지만 위의 코드에는 lock이 없기 때문에 추가 해줘야 한다. p1~p3는 producer가 buffer가 비어있을 때 까지 기다린다. c1~c3는 consumer가 buffer가 채워질 때 까지 기다린다. 만약 buffer가 비어있다면 p4~p6이 buffer에 값을 채우고, c4~c6에서 채워진 데이터를 사용한다.

이처럼 하나의 producer, 하나의 consumer 상황에서는 위의 코드가 잘 동작할 것이라고 유추할 수 있다. 하지만 producer 혹은 consumer가 하나가 아닌 경우에는 어떻게 될까?30.9 그림처럼 consumer가 2개인 경우를 생각해보자.

1. consumer1이 먼저 실행되고 buffer에 값이 없으므로 data를 채울 때 까지 sleep에 빠진다.
2. 그 이후 producer가 버퍼에 값을 채우고
3. 이후에 consumer2가 실행된다면 이미 buffer에 값은 채워진 상태이므로 buffer에 있는 data를 처리하고
4. buffer에 값이 채워졌다는 signal을 받은 consumer1이 깨어나서 buffer를 사용하려고 보니 data가 이미 다 사용돼버렸다!

이처럼 깨어난 thread가 바람직한 상태에 있더라도 반드시 동작한다는 것을 보장할 수 없는 문제를 mesa semantic이라고 한다. 반대로 깨어난 thread가 반드시 즉각적으로 동작하는 것을 보장하는 용어로 hoare semantic이라고 부른다.

Producer/Consumer: Single CV And While

위의 문제를 while문을 결합하여 해결할 수 있다. buffer가 비어있는 경우에만 consumer가 잠에 들 수 있다.

하지만 이 방법에도 문제는 존재한다.예를들어 c1(consumer1), c2(consumer2)가 먼저 실행되고 나중에 p(producer)가 실행된다고 하자.

buffer가 비어있기 때문에 2개의 consumer모두 잠에 들 수 있고, p가 실행되어 buffer를 채우기 시작한다. 그리고 buffer를 모두 채우면 p는 잠든다.
그 후 c1, c2중 하나가 깨어나는데 c1이 깨어났다고 하자.
그래서 c1이 data를 사용한다. 이 data를 모두 다 사용했을 때 또다시 잠들어있는 thread중 하나를 깨워야만 하는데 지금 상황으로는 c2, p가 잠들어있다.
데이터를 모두 사용했을 때 당연히 p를 깨워야하지만 queue가 어떻게 구성되어있는지에 따라 c2가 깨어나는 것도 가능하기 때문에 만약 c2를 깨우는 경우에는 buffer가 이미 모두 사용된 상태기 때문에 다시 잠에 빠진다.
그래서 모든 thread가 잠에 빠지는 문제가 발생할 수 있다.

The Single Buffer Producer/Consumer Solution

그래서 이 문제를 해결하기 위한 방법으로는 2개의 condition variable을 활용하는 것이다.consumer와 producer thread 모두 empty, fill이라는 condition variable을 기다린다.

위의 코드에서 producer는 empty를 기다리고, fill signal을 보낸다. 반대로 consumer는 fill을 기다리고 empty signal을 보낸다.

The Correct Producer/Consumer Solution

더 뛰어난 동시성과 효율성을 위해서는 buffer를 추가하는 것이 도움이된다.
여러개의 buffer를 활용하여 동시에 producing, consuming을 할 수 있다.위의 코드에서 볼 수 있듯이 producer는 모든 buffer가 채워져있어야만 잠을 잘 수 있고, consumer는 모든 buffer가 비어있어야만 잠에 빠질 수 있다.

Covering Condition

위의 코드를 보면 allocate를 위해서는 할당할 수 있는 공간의 크기(byteLeft)가 할당하려는 크기(size)보다 더 큰 경우에 할당이 이루어질 수 있다.

그런데 만약 현재 메모리에 여유가 0 byte인 상태에서 thread a에서 100byte의 할당 요청이 있고, thread b에서 10byte의 할당 요청이 있을 때 두개의 thread는 모두 메모리가 확보될 때 까지 잠에 빠진다.

그런데 thread c가 50byte를 해제한 경우에 thread b는 10byte만 할당하면 되므로 깨어나도 되지만 thread a의 100byte에는 모자라므로 thread a가 깨어나서는 안된다.

하지만 컴퓨터는 둘중 어떤 thread를 깨워야하는지 알 수 없다.

그래서 이 문제를 해결하기위해서 pthread_cond_signal()을 pthread_cond_broadcast()로 대채하였다.
잠들어있는 모든 thread를 깨워서 50byte 크기에 만족하는 할당을 수행할 수 있도록 한 것이다.

하지만 이 방법은 모든 thread를 깨워서 상태를 체크하고 조건에 맞지않으면 다시 재우는 과정 때문에 성능에 악영향을 줄 수 있다.

그래서 이처럼 모든 thread를 다 깨우는 상황을 covering condition이라고 부른다.

출처: OSTEP