lock은 여러 스레드가 한 번에 공유 데이터(critical section)에 접근 하는것을 제한하는 것이라면, condition variables은 스레드간 동기화를 위해 사용된다.

Condition Variables

실행을 계속하기전에 스레드가 condition이 true인지 체크하길 원하는 경우가 많다. 예를 들어
만약 parent스레드는 child스레드의 결과를 이용하여 수행된다면, parent스레드는 child스레드의 작업이 끝날때까지 기다려야 할 것이다. (join)
여기서 parent는 어떻게 child가 끝났는지 알 수 있을까? 또, child는 parent에게 어떻게 끝났다고 알릴 수 있을까?

Spin-based Approach

child의 상태를 알 수 있는 전역변수 done을 사용하고, 부모 스레드에서 계속하여 done변수의 값을 체크한다. 이 방식은 parent가 spin하면서 CPU times를 낭비하므로 매우 비효율적이다.

그럼 어떻게 condition을 기다릴까?

Condition Variable(queue와 유사)

• Waiting on the condition: 실행의 상태가 충족되지 않을 때 스레드가 스스로를 명시적인 큐에 넣을 수있다.
• Signaling on the condition: 다른 스레드는 상태가 변경되면 대기중인 스레드를 깨워 계속 진행하도록 할 수 있다.

1. Definition and Routines

• Definition
• Operation (the POSIX calls)
  • wait() call은 mutext를 parameter로 가진다
    • wait()이 호출될 때 mutex가 held 되었다고 가정한다. 즉 lock 상태임을 가정
    • wait() call이 lock을 해제하고 호출한 스레드를 sleep시킨다.
    • 스레드가 깨어났을 때, lock을 다시 얻는다.
  • signal()은 만약 condition variable을 기다리고 있는 스레드가 있다면 하나의 스레드를 깨운다.

2. Parent waiting for Child: Use a condition variables

condition variable을 이용하여 Join 구현

Parent가 먼저 수행되는 케이스
child가 먼저 수행되는 케이스
두 경우 모두 잘 동작하는 것을 확인 할 수 있다.

2-1. Join 구현에서 state variable인 done의 중요성

만약 thr_exit과 thr_join에 done변수 없어도 되지 않나 생각할 수 있다. 다음을 보자
child가 즉시 실행되는 케이스를 생각해보자. child는 exit내에서 signal을 보내지만, condition에 sleep 상태인 스레드가 존재하지 않는다. 이후 parent가 실행될때, parent는 wait을 call하면 sleep 상태에 빠지고 sleep을 깨워줄 스레드가 존재하지 않게 된다.

이 케이스는 공용 데이터(done과 같은)에 접근이 없으므로 race condition이라고 보기는 어렵다.

Race Condition이란 두 개 이상의 프로세스가 공통 자원을 concurently하게 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서로 이루어졌는지에 따라 그 실행 결과가 달라지는 상황

2-2. Join 구현에서 lock의 중요성

만약 thr_exit과 thr_join에 lock을 사용하지 않아도 문제가 발생할지도 궁금할 수 있다.
결론부터 말하면 race condition이 발생한다. parent가 thr_join을 호출하여 done 변수가 0인 것을 확인하고 wait함수를 호출하기전 context switch가 발생할 수 있다.
이후 child는 done을 1로 바꾸고, signal을 보낸다. 그러나 깨울 스레드가 존재하지 않는다.
parent가 재시작되면, 영원히 sleep상태에 빠지게 된다.

3. Producer/Consumer(Bound Buffer) 문제

• Producer는 data items를 생성한다. data를 버퍼에 저장
• Consumer는 buffer로 부터 data items를 잡고 소비한다.
• 예로는 Multi-thread를 이용한 웹 서버가 있다.
  • Producer는 HTTP요청을 작업 큐에 넣는다.
  • Consumer 스레드는 큐로부터 요청을 꺼내서 처리한다.

Bounded Buffer

Bounded Buffer는 한 프로그램의 출력 결과를 다른 프로그램으로 연결할때 사용한다 위 예시에서 grep이 producer 프로세스이고 wc가 consumer 프로세스이다.
grep의 출력 결과를 consumer가 사용
Bounded Buffer는 공유된 자원이므로 동기화된 접근이 요구된다.

동기화 되지 않은 version

buffer가 차있을 때만 get하고 buffer가 비었을 때만 put한다.

3-1. Version 1: Single CV and If statement

하나의 condition variable과 If문을 사용한 버전이다. 만약 producer와 consumer가 각각 하나씩 있으면 잘 동작한다. 하지만 두개 이상의 producer와 consumer가 있다면 문제가 발생한다.
위에서 Producer가 Tc1을 깨운 후, Tc1이 실행되기전에 Tc2가 실행되어 Bounded buffer의 상태가 변할 때 문제가 발생한다.

• 깨어난 스레드가 실행될때, 그 상태가 여전히 원하는 상태인지 알 수 없다. -> Mesa semeantics. 즉 ready 상태 -> 실제 수행될 때(Running) 사이에 다른 thread가 실행되어 Bounded Buffer의 상태를 변경할 수 있다.
• Hoare semantics는 깨어난 스레드가 깨어났을 대 즉시 실행되도록 강력하게 보장한다.

3-2. Version 2: Single CV and While

스레드가 깨어난 후 원하는 상태인지 한 번더 확인한다. 즉 count = 1인지 다시 확인.
하지만 이 코드에도 여전히 문제가 있다.
Tc1와 Tc2가 먼저 실행된 후 sleep상태가 되고, Tp가 실행된 후 buffer에 data item을 채우고 먼저 큐에 들어간 Tc1을 깨운다. 이후 Tc1은 data를 가져가고 signal을 보내면 먼저 큐에 들어간 Tc2가 깨어나게 된다. 이렇게 되면 Tc2는 데이터가 가져갈 데이터가 없기 때문에 문제가 발생한다.

이 문제를 해결하기 위해서는 consumer는 producer만 깨우고, producer는 consumer만 깨우도록 해야한다. 따라서 consumer condition variable과 producer condition variable을 별개로 두어야 한다.

3-3. Version 3: Two CV and While

두 개의 condition variables과 while을 사용한다.

• Producer 스레드는 empty condition에서 wait하고, fill을 signal 한다.
• Consumer 스레드는 fill condition에서 wait하고, empty를 signal 한다.
  

3-4. Version 4: More Buffer slots

concurrency와 efficiency를 더 높이기 위해 더 많은 buffer slots을 추가한다.

• context switch 비용이 감소한다.
• 동시 생성과 소비가 가능해진다. 이제 Prouducer는 모든 buffer가 차있는 상태에서만 sleep하고 Consumer는 buffer가 텅 빈 상태에서만 sleep하게 된다.

4. Covering Conditions

별개의 문제로 Covering Conditions에 대해 간단히 알아보자.
현재 0 bytes의 free가 있고, 스레드 a가 allocate(100)을 호출하고 스레드 b가 allocate(10)을 호출한다. 따라서 a와 b모두 condition을 기다리고 sleep한다. 이 때 스레드 c가 free(50)을 호출한다면 어느 waiting 스레드를 깨워야 할까? 누구에게 wake signal을 보내야할지 어떻게 알 수 있을까?

solution

pthread_cond_signal을 pthread_cond_broadcast()로 교체한다.

• pthread_cond_broadcast는 모든 waiting 스레드를 깨운다.
• 많은 스레드가 깨어나므로 cost가 발생
• 깨어나면 안되는 스레드들은 condition을 확인하고 다시 sleep한다.

이 해결책은 대부분의 스레드가 쓸데없이 깨어난다는 점에서 문제가 있다.

여기까지 Condition Variables에 대해 공부하였습니다. 다음 글에서는 synchronization과 관련된 모든 것을 위한 semaphore(locks와 condition variables 모두로 사용이 가능)를 소개하겠습니다.