[Operating System] Condition Variables

지금까지 lock의 개념을 살펴보았고, hardware와 OS의 적절한 조합으로 어떻게 구현되는지 살펴보았다. 하지만, concurrent programs을 빌드하기 위한 기본 요소로 lock만이 있는 건 아니다.

 

특히, 스레드는 종종 실행을 계속하기 전에 condition이 true인지 확인하고 싶어한다. 예를 들어, 상위 스레드는 계속하기 전에 하위 스레드가 완료되었는지 확인하고 싶을 수 있다. 이를 join()이라고도 부른다. 이러한 기다림(wait)은 어떻게 구현할 수 있을 지 살펴보자. 

 

Spin-based Aproach - inefficient

---

Shared Variable(공유 변수)를 사용해 볼 수 있다. 이러한 Spin-based Approach라 칭한 이 솔루션은 일반적으로 작동하지만 상위 항목(parent)이 CPU 시간을 낭비(spin and waste)하고 있기 때문에 매우 비효율적이다.

 

대신에 우리가 원하는 것은 child의 실행이 끝날 때까지, 즉 우리가 기다리고 있는 condition이 실현될 때까지  parent를 sleep하는 것이다.(CPU를 낭비하지 않고).

 

멀티 스레드 프로그램에서, 스레드를 계속하기 전에 어떤 조건이 참일 때까지 기다리도록 하는 것이 종종 유용하다. condition이 true가 될 때까지 회전(spin)하는 간단한 방법은 매우 비효율적이며 CPU Cycles를 낭비하며, 경우에 따라서는 부정확할 수 있다. 그렇다면, 어떻게 thread를 wait하는 것이 좋을까?

 

 

 

 

Definition and Routines

---

조건이 참일 때까지(until the condition becomes true) 기다리기 위해서, 스레드는 조건 변수(conditional variable)라고 하는 것을 사용할 수 있다. 조건 변수는 condition에 따라 실행이 기다려지는 상황에서 적용할 수 있는 명시적 대기열(explicit queue)이다. 다른 스레드는 상태(state)가 변하면 대기 중인 하나 이상의 스레드를 깨울 수 있으며 따라서 스레드가 계속 진행될 수 있도록 허용한다.

 

이러한 Conditional Variable(조건 변수)는 크게 wait()와 signal() 두 가지 연산과 연관되어 있다. wait() 호출은 스레드가 절전 모드(sleep)로 전환할 때 실행되며, signal() 호출은 스레드가 프로그램에서 무언가를 변경했기 때문에 해당 조건에 대해서 대기 중인 절전 스레드를 깨우려고 할 때 실행된다.

 

여기서 done은 State Variable(상태 변수)다.

---

Conditional Variable (조건 변수)란,  Condition Variable은 특정 조건을 만족하기를 기다리는 변수이며, thread간의 신호 전달을 위해 사용한다.

 

출처 : ju-hy.tistory.com/39

 

---

아래는 Conditional Variable(조건 변수)와 State Variable(상태 변수)를 사용하여 thread_join과 thread_exit을 구현한 코드 예제이다.

 

 

위 코드의 두 가지 케이스를 살펴보자.

 

# Case 1.

부모는 자식 스레드를 만들지만 스스로 실행을 계속한다(우리는 하나의 프로세서만 가지고 있다). 따라서 자식 스레드가 완료될 때까지 기다리기 위해 즉시 thr__join()으로 호출한다. 이 경우 lock을 획득하고, child가 완료되었는지(아닌지) 확인한 후 wait()를 호출해 스스로 sleep한다.(따라서 unlock된다).

The child will eventually run, print the message “child”, and call thr exit() to wake the parent thread

 

하위 스레드가 마침내 실행되며, child메시지를 보내고, thr_exit()를 호출하여 부모에게 신호를 보낸다. 이 과정에서 lock을 걸고, 완료 상태(done=1)를 설정하며, 부모에게 신호를 보내어 깨운다. 마지막으로, 상위 스레드가 실행되며 잠금이 설정된 상태에서 wait()로부터 돌아오고, 잠금을 해제하고, "parent: end" 메시지를 출력한다.

 

# Case 2.

자식 스레드가 생성 즉시 실행되고 done을 1로 설정하며 signal을 호출하여 절전중(sleeping)인 스레드를 깨우고 완료된다. 그런 다음 상위 스레드가 실행되고  thr_join()을 call하며 done이 1인것을 확인하고 wait()하지 않고 return한다.  

 

 

* done이라는 상태 변수(state variable)가 꼭 필요한 지 의문이 들 수 있다. 만약 상태 변수가 없다면 어떻게 될까?

잘못된 접근 방식이다. Case 2의 상황에 대처할 수 없게 된다.

 

자식 스레드가 즉시 실행되서 thr_exit()를 호출하는 경우 자식 스레드는 signal을 보내지만 해당 condition에 대해서 asleep상태의 스레드가 없다. 부모 스레드가 실행되면, wait를 호출할 것이고 asleep 상태에 갇히게(stuck) 될 것이다. 어떠한 스레드도 해당 스레드를 깨우지 않을 것이다. 해당 예시로부터, 상태 변수 done의 중요성을 깨달을 수 있다. done이라는 상태 변수는 스레드가 알고자 하는 값을 기록한다. sleeping, waking, locking은 해당 변수를 둘러싸고 build된다.

 

 

* 만약 lock 기능이 없다면 어떻게 될까?

race condition이 발생한다. 만약 부모가 thr_join()을 호출한 다음 done의 값을 확인하면, 그것은 0일 것이고 wait()을 호출하여 sleep 상태빠지려 할 것이다. 이 때 lock 기능의 부재로 인해 parent가 interrupt되며 child가 실행된다면 child는 state variable인 done을 1로 변경하고 signal을 보낼 것이다. 하지만 waiting상태의 잠든 스레드가 없을 것이며, 다음으로 parent가 다시 실행될 때 영원히 sleep상태에 빠진다.

 

해당 join 예제를 통해서 조건 변수를 올바르게 사용하기 위한 몇 가지 기본 요소를 확인할 수 있었다.

 

 

 

signal()이나 wait() 호출 시 잠금을 유지하라 -Hold the lock when calling signal or wait.

---

wait()호출 시 lock을 유지하는 것은 선택사항이 아니라, wait() 의미론적으로 보았을 때 강제되어진다(필수사항이다).

 

왜냐하면,

(a) wait()를 호출할 때 lock이 유지된다고 가정하고,

(b) 호출자를 sleep 상태로 전환할 때 lock을 해제하며,

(c) sleep 상태로부터 돌아오기 직전에 다시 lock을 획득하기 때문이다.

 

따라서 signal() 또는 wait()를 호출할 때 lock을 유지하자. 

 

 

The Producer/Consumer (Bounded Buffer) Problem

---

이번에 다룰 동기화 문제는 Producer/Consumer Problem(생산자/소비자 문제)로 알려져있고, dijkstra에 의해 처음 제기되었다. 이 문제로부터 잠금 또는 조건 변수로 사용될 수 있는 일반화된 semaphore가 등장하였다.

 

하나 이상의 생산자 스레드와, 하나 이상의 소비자 스레드가 있다고 상상해보자. 생산자는 데이터 항복을 생성하여 버퍼에 배치하고, 소비자는 버퍼에서 지정된 항목을 가져와 어떠한 방식으로 소비한다.

 

이러한 방식은 실제 많은 시스템에서 사용되는 방식이다. 예를 들어, 멀티 스레드 웹 서버에서, 생산자는 HTTP 요청을 작업 대기열(the bounded buffer)에 넣고, 소비자 스레드는 이 대기열에서 요청을 꺼내서 처리한다.

 

Bounded buffer는 하나의 프로그램의 출력을 다른 곳으로 파이프(pipe)할 때도 쓰인다. 예를 들어, "grep foo file.txt | wc -l"이라는 커맨드를 입력하면, 두 프로세스를 동시에 실행한다. 프로세스 grep은 file.txt로부터 standard output에 한줄 한줄 출력하고, 이는 파이프를 통해 리디렉션되어  프로세스 wc의 표준 입력으로 들어온다. wc는 input stream의 라인 개수를 결과로 출력하는 프로세스이다. 그러므로, grep프로새스는 생산자이고, wc 프로세스는 소비자이다. 이들 사이에는 in-kernel bounded buffer가 있다.

 

bounded buffer는 공유 리소스이기 때문에 race condition을 막기 위해 동기화된 접근(synchronized access)를 필요로 한다.

 

 

Producer/Consumer with If statement

---

if문을 이용한 Producer/Consumer 코드

위 코드는  if를 사용한 producer/consumer 구현 코드이다. 이는 생산자와 소비자 스레드가 각각 하나일 때는 문제가 없지만, 여러개일 때 문제가 발생한다.

 

예를 들어, 생산자 스레드 1개, 소비자 스레드 2개가 있다고 생각해보자.

if문을 이용한 Producer/Consumer 구현에서 발생할 수 있는 문제 상황 (Broken Solution)

1. Tc1(첫번째 소비자 스레드)가 먼저 실행되고, c2 if문에서 count==0이므로(버퍼에 데이터가 존재하지 않으므로) sleep상태가 된다.

3. Tp1 스레드가 실행되며 count==0이므로 버퍼에 데이터를 넣고, Tc1에 신호를 보내어 sleep상태의 Tc1을 다시 스케줄링한다.

4. 먼저 스케줄링되어있던 Tc2가 버퍼에 있는 데이터를 소비한다.

5. 다음으로 sleep상태에서 깨어난 Tc1가 실행되지만, buffer가 비어있는 문제가 발생한다.

 

즉, 여기서 볼 수 있는 문제는 Tp1(생산자가) Tc1(소비자)를 깨운 후에, Tc1이 다시 실행되기 전에 bounded buffer의 상태가 변경되었다(Tc2에 의해)는 점이다. 즉, 깨어난 스레드가 실행될 때 원하는 대로 상태(state)가 존재할 것이라는 보장이 없다.

 

이러한 문제를 해결하기 위해서는 아래처럼 while문을 이용하면 된다.

 

Producer/Consumer with While statement (with one condition variable)

---

하지만, while 문을 사용하더라도 해결하지 못하는 문제 하나가 더 있다. 바로 조건 변수가 하나라는 점이다.

 

While문을 이용한 Producer/Consumer 코드

 

이전과 같이 예를 들어, 생산자 스레드 1개, 소비자 스레드 2개가 있다고 생각해보자.

 

While문을 이용한 Producer/Consumer 구현에서 발생할 수 있는 문제 상황 (Broken Solution)

 

1.Tc1, Tc2가 순서대로 실행되며, 소비할 데이터가 존재하지 않으므로 sleep상태가 된다.

2. Tp1이 데이터를 생산하여 bounded buffer에 데이터를 넣고, Tc1을 깨운다.

3. Tc1이 데이터를 소비하고, Tc2를 깨운 후 sleep 상태에 빠진다. (조건 변수가 하나이므로 다음 대기열에 있는 Tc2를 깨우는 것이다.)

4. Tc2가 실행되지만 buffer에 데이터가 없으므로 sleep상태에 빠진다.

5. Tp1, Tc1, Tc2 모두가 sleep 상태에 빠지는 문제가 발생한다.

 

이 문제를 해결할 수 있는 단순한 방법은 조건 변수를 2개 사용해서 생산자는 소비자만 깨우도록, 그리고 소비자는 생산자만 깨우도록 만드는 것이다.

 

 

Producer/Consumer with While statement (with two condition variable)

---

While문을 이용한 Producer/Consumer 코드 (조건 변수 2개)

 

위처럼 조건 변수 2개를 사용하여 생산자는 소비자만 깨우고, 소비자는 생산자만 깨우도록 바꾸어 문제를 해결할 수 있다.

 

 

Producer/Consumer with While statement (with two condition variable and multiple buffer size)

---

이번엔, buffer size가 1 이상 일때의 구현을 살펴보자.

 

이전과 달라진 점은 buffer의 크기가 1이 아닌 다수라는 점이다. 이에 따라 put()과 get()코드가 수정되고, 생산자는 버퍼가 가득찬 경우에만 wait()을 수행하며, 소비자는 버퍼가 비어있을 경우에만 wait()를 사용한다.

 

 

 

Covering Conditions

---

이번엔 다른 문제 상황을 살펴보자.

 

위 코드는 멀티 스레드에서 메모리를 할당하고 해제하는 일부 라이브러리의 코드이다. 메모리를 할당받는 allocate() 코드는 소비자(메모리 할당받는) 스레드가 원하는 size만큼의 메모리를 할당받을 수 있을 때까지 wait하고, 메모리를 해제하는 스레드는 사용중인 메모리를 할당 해제한 후 신호를 보내 메모리를 할당받으려하는 스레드를 깨운다.

 

여기서 문제는 어떠한 스레드에 신호를 보내야 하는 가이다. 예를 들어, free()를 통해서 여유 메모리가 100이 되었는데, 메모리를 할당받으려하는 두 스레드(첫번째 스레드는 150만큼의 메모리를, 두번째 스레드는 50만큼의 메모리를 필요로한다.) 중 첫번째 스레드를 깨운다면 여유 메모리가 부족하여 할당받을 수 없으므로 다시 sleep상태가 되고 할당받을 수 있던 두번째 스레드에게는 기회가 가지 않는 문제가 발생한다. 즉, 수행할 수 있는 스레드가 있음에도 아무것도 수행하지 않는 상태가 된다.

 

이러한 문제를 해결하기 위해서 signal() 대신 broadcast()를 사용하여 sleep상태의 모든 스레드를 깨우는 방법이 있다. 물론 성능 면에서 부정적인 영향을 줄 수는 있지만, 위와 같은 이슈를 해결할 수 있다. 이러한 trade-off를 잘 고려해야 한다.

 

 

---

pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

+) 참고한 블로그 : icksw.tistory.com/164?category=878876

[OS] Synchronization(동기화)를 위한 condition variables(조건 변수) - OS 공부 21