[Synchronization] Condition Variables

💡Condition variables

스레드가 실행을 하면 안되는 상황(특정 조건 미충족 등)일 때 자기 스스로를 넣어놓는 queue이다.

 

✅스레드는 condition variable에 대해 아래와 같은 동작을 수행할 수 있다.

 

- wait(condition_variable, lock): 실행하면 안되는 상황일 때, 스레드 자신의 lock을 release하고 스스로를 어떤 queue에 넣음

- signal(condition_variable): 스레드 자신의 state를 바꾸면서, waiting하던 다른 스레드 하나를 깨움

 

✅condition variable을 이용하기 위해서는 아래 요소도 필요하다.

- state variable: child 스레드가 일을 끝냈는지 여부

- locks: state variable 보호

 

 

💡Parent waiting for child

 

✅올바른 구현 방식: condition variable, state variable, locks 모두 활용

 

위에서, condition variable 외에도 state variable과 lock이 필요하다 하였다.

각 요소가 왜 필요한건지, 요소를 사용하지 않은 예시를 통해 직접 확인해보자.

 

✅condition variable을 사용하지 않은 경우 (= Spin-based Approach)의 문제점

 

parent thread가 계속 spin하므로 CPU time의 낭비이다.

: child thread가 done되었는지를 쓸데없이 반복해서 확인하고 있다.

 

 

✅state variable (= done)이 없는 경우의 문제점

 

parent	child
child 스레드 생성
	바로 child로 context switch됨
	thr_exit() 실행됨
	Pthread_cond_signal(&c)으로 parent를 wake up하려 함
waiting list에 못 갔으므로, wake up 될 수가 없음
다시 parent로 context switch되어 thr_join() 실행됨
Pthread_cond_wait() 호출하여 sleep하러 감
깨워줄 사람이 없어서 영원히 sleep

 

만약 child 스레드가 작업을 마쳤는지 여부를 나타내는 state variable이 있었다면,

parent 스레드는 thr_join()에서 state variable을 기준으로 하여 sleep을 할지 말지를 올바르게 결정할 수 있었을 것인데

(child가 아직 완수가 안됐으면 sleep하고, 다 완수했으면 sleep 안함),

 

이것이 없으니, parent는 thr_join()을 호출하여 lock을 얻자 마자,

child가 이미 완수해서 parent는 더이상 sleep할 필요가 없는데도 냅다 sleep해버려 문제가 생기는 것이다. 

 

 

✅Lock이 없는 경우의 문제점

parent	child
child 스레드 생성
call thr_join()
if (done == 0)
Pthread_cond_wait()을 실행하여 sleep하러 갔어야 했는데, 아직 못함!!
	child 스레드로 context switch됨 (이렇게 되어버린 이유: lock을 통해 critical section으로 보호받았어야 했는데, lock이 없음!!)
	call thr_exit()
	done = 1
	Pthread_cond_signal(&c)으로 parent를 wake up하려 함
waiting list에 못 갔으므로, wake up 될 수가 없음
sleep하게 되면 영원히 잠드는 것

 

만약 lock이 있었다면,

child로의 context switch가 일어나지 않고 parent의 실행이 보호돼서, parent는 안전히 sleep하러 갈 수 있었을 것이다!!

 

 

 

💡Producer / Consumer (Bound Buffer) Problem과 해결책

 

✅primitive version 

 

 

✅Single CV & If 

🚩

문제점: C1이 wake up한 직후 C2가 생산물을 채가면? -> C1이 get()할 때 오류 발생

(시간 순임)

 

- C1이 실행되었으나, buffer에 아무 것도 없어 (즉, count == 0) sleep queue에 들어간다.

- 그 이후 P1이 실행되어 buffer에 put()하고 (즉, count == 1 됨) signal을 보낸다.

- 위 signal을 C1이 받기 전에, C2가 먼저 실행이 준비되어 ready queue에 들어간다.

- 이후에 C1이 ready queue에 들어오더라도 C2가 순서상 우선하게 된다.

- 그래서, buffer에 있는 P1의 생성물을 C1이 아닌 C2가 consume해 버려 count == 0이 된다.

 

- 이 이후 C1이 뒤늦게 signal을 받게 되고, C1은 Pthread_cond_wait()으로부터 return된다.

- C1은 count == 0이 된지도 모르고 get()을 실행하고, assert(count == 1)에 위반되어 오류가 발생하게 된다!

 

원인: C1이 signal을 받은 뒤, 아무런 확인 과정 없이 get()을 실행한다.

이것의 문제는, C1이 signal을 받고 get()을 실행하는 그 사이에 C2이 P1의 생산물을 채간 경우,

C1은 그 사실을 인지하지 못한 채 get()을 실행한단 것이다.

🚩

해결책 (아래 ✅): if를 while로 바꿈

위 코드에서 if를 while로 바꿔 주면,

C1이 signal을 받고 Pthread_cond_wait()으로부터 return한 뒤,

바로 get()을 하는 게 아니라, while문 안에서 다시 한 번 count == 0인지를 확인하게 된다. (re-check)

그럼, C2이 이미 채간 뒤 count == 0이 되었으므로, 

다시 Pthread_cond_wait()을 실행함으로써 sleep queue에 들어간다.

 

 

✅Single CV & While

 

 

🚩

그러나 아직도 문제점이 있다: C1, C2가 먼저 실행되고 sleep하러 가면? -> 모두가 sleep하게 된다. 

(시간 순임)

 

- C1이 먼저 실행하였으나 아직 count == 0이므로 sleep queue에 들어간다.

- C2가 실행되고 C2 역시 count  == 0을 보고 sleep queue에 들어간다.

- P1이 실행되어 put()하고 (이로써 count == 1 됨) signal을 보낸 뒤, 다음 loop를 돌기 시작한다.

- 이미 count == 1이므로 P1은 while문 내의 Pthread_cond_wait()을 실행하여 sleep한다.

 

- 이 signal로 인해 C1은 wake up한 뒤 실행되어 get()한 뒤 signal을 보내고 sleep한다.

- 이 signal은 단 하나의 스레드만 깨우므로, 현재 sleep queue의 맨 앞에 있는 C2를 깨우게 된다. 즉, consumer의 signal이 producer가 아니라 또다른 consumer를 wake up해버린 것이다.

- C2는 실행되었지만 count == 0인 것을 보고 다시 sleep한다.

 

- 결과적으로, C1, C2, P1 모두 sleep하고 있으며, 누구도 wake up해줄 수 없는 상황이 되어버렸다.

 

원인: C/P가 보낸 signal을 P/C가 아니라 다른 C/P가 받을 수 있다.

"찼다"는 신호든 "비었다"는 신호든 다 cond라는 CV 하나로 퉁쳐지니까, consumer인지 producer인지 구분도 안 하고 냅다 깨우는 것이다.

🚩

해결책 (아래 ✅): CV를 두 개 쓴다 - "empty", "fill"

이렇게 하면, consumer가 보낸 "empty" signal은 producer를 깨우고, producer가 보낸 "fill" signal은 consumer를 깨우게 되어 분리 성공.

 

 

✅Final version: Two CVs & While

count는 state variable이다.

(이전까지는 count가 0 또는 1만 가졌는데, final version에선 이를 일반화하여 0에서부터 MAX까지 가질 수 있다.)