[OS/OSTEP] 30.threads-condition variable, 쓰레드 컨디션 변수, 컨디션 변수 두개, 쓰레드 동기화 문제, 생산자/ 소비자, covering condition/broadcast,

 

30.threads-condition variable

# 글을 시작하며

 저번 포스팅까지는 락이라는 것이 무엇인지 알았고, lock() unlock()으로 단지 락을 사용해보기만 했고 그 락은 unlock()이 오면 리턴한다고만 알았던 것을 직접 어떻게 구현되는지를 살펴보았다. 그 과정에서 spin방식을 사용해 while루프를 돌며 계속해서 Test-And-Set과 같은 Atomic한 기법으로 락을 소유할 수 있는지를 검사하는 과정을 거쳐서 구현할 수 있다는 사실을 알았다. 그러나 그 사실에서 CPU낭비가 생기기 때문에 lock이 올때까지 대기할 수 있도록 하는 방법에 대해서 고민해봤고, 첫째로는 yiled()를 사용해서 락을 가질 수 없다는 즉시 CPU를 반환하는 방법을 알 수 있었다. 둘째는 락이 없다면 sleep상태로 재우고 락을 얻을 수 있는 상황이 오면 락을 깨우는 방법을 알 수 있었는데, park()와 unpark()을 이용할 수 있었다. 셋째로는 futex-lock에서 사용하는 방법으로 2단계의 거쳐서 락을 계속해서 검사하는 과정을 거치고 futex_wait()와 futex_wake()를 사용해서 32비트를 가지는 락변수를 제어하는 방법에 대해서 알 수 있었다.

 

# 병행쓰레드의 요구사항

 락만으로는 병행프로그램을 제대로 작성할 수 없었다. 여러 쓰레드가 돌아감에따라서 각 쓰레드의 조건을 비교해본 후 멈추었다가 실행하는 루틴들이 필요하기 때문이다. 가장 직관적인 예로는 프로세스에서 맨 처음 공부했었던 부모가 자식의 종료를 기다리는 조건이다. 이러한 예는 쓰레드에서도 똑같이 적용 할 수 있다.

  위와같이 done이라는 공유변수를 활용하여 while문을 이용하여 상시 조건을 검사하는 방법이 존재하겠지만은 CPU시간을 낭비하게 된다. 어떠한 경우에는 부정확할 수도 있기 때문이다. 그렇다면 쓰레드는 어떻게 조건을 기다려야 하는 것일까?

 

# 컨디션 변수(conditional variable) 

 조건이 참이 될 때까지 기다리기 위해 컨디션 변수(conditional variable)를 활용할 수 있다. 이름과는 무색하게 일종의 큐로써 기능을 한다. 기다려야하는 쓰레드가 생기면 해당 컨디션 변수에 쓰레드를 추가하고 추후에 깨우라는 연락이 오게되면 큐에서 꺼내 깨우게 된다.

 간단히 pthread_cond_t c;로 선언하여 컨디션 변수를 초기화 시킨다. 이 컨디션 변수에는 wait()와 signal()이라는 연산이 존재한다.

 

 wait()는 두개의 인자를 가진다. 첫번째로는 등록할 큐 즉 컨디션 변수가 들어가고, 두번째로는 락이 들어간다. wait()의 역할을 알게되면 왜 두개의 인자가 필요한지 알 수 있을 것이다. 먼저 wiat()가 호출 되는 것은 어떠한 조건을 기다려야한다는 뜻이기 때문에 기다리기 위해 sleep에 들어간다. 그리고 그러한 sleep상태의 쓰레드들을 관리하기위하여 컨디션 변수 c에 넣어 관리한다. 앞서 강조했던거와 같이 잠들기전에는 항상 소유한 락을 반납해야한다. 락을 반납하지 않고 잠들게 된다면 해당 락에 아무도 접근할 수 없게되고 결국 깨울수도 없게 될 것이다. 그렇기 때문에 두번째 인자로 락을 넣어주어 깨울 락을 알리는 것이다. 그리고 깨워지는 순간은 쓰레드의 시점으로는 wait()에서 리턴한 것이기때문에 락을 소유하고 있어야 하기때문에 리턴하기전에 락을 다시 얻어야 한다.

 signal()은 해당 컨디션 변수에서 쓰레드를 깨워 Ready상태로 만들거나, 큐에 아무것도 없다면 즉시 리턴하여 다음 구문을 실행 할 수 있도록한다.

위 33.3의 코드와 같이, 부모먼저 -> 자식먼저 , 자식먼저 -> 부모먼저 의 경우를 생각해보면서 wait와 signal의 쓰임을 이해해보도록하자. 주의해야 할점은 항상 while문을 사용해야한다는 것이다.

## 잘못된 사용 1

아래와 같이 thr_exit()와 thr_join()을 구성한다면 왜 잘 동작하지 않을까? 아래 코드는 done이라는 변수의 사용과 while문을 사용하지 않았다.

먼저 자식먼저( thr_exit ) -> 부모먼저(thr_join)가 실행되는 경우를 생각해보자. 자식이 먼저 실행되면서 컨디션변수에 있는 쓰레드를 깨운다. 이 경우에는 깨울것이 없기때문에 아무런 동작을 하지 않고 끝나게 되고, 부모가 thr_join을 그 후에 호출하게 되면서 wait하여 sleep하게 되지만 아무도 부모를 깨워 줄 수 없다. 즉 잠들면 안되는 상황이지만 잠에 들게 된 것이다. done이라는 변수를 사용함으로써 잠들지 않아야하는 상황을 구분할 수 있다.

 

## 잘못된 사용 2

 이번에는 lock을 사용하지 않았다. 각각의 쓰레드들은 done이라는 상태를 바꾸지 않기때문에 얼핏보기에는 별 문제가 없다고 생각이 들 수 있을 것이다. 그렇지만 lock을 사용하지 않는다면 그 구문끼리는 인터럽트가 아무 문제없이 걸리고 인터럽 된 코드가 문제없이 실행됨을 뜻 할 수 있다. 

 부모먼저(thr_join) -> 7번라인 검사후 인터럽트 -> 자식(thr_exit) -> 부모로 인터럽트 가 실행되는 경우를 생각해보자. 7번 라인에서 done이 0인것을 확인한 부모는 wait를 호출하려는 찰나의 순간에 7~8번 라인 사이에 인터럽트가 들어와 thr_exit가 된다. done=1로 바뀌고 signal을 보내어 깨울게 있음 깨우지만 깨울게 없기때문에 코드가 끝난다. 즉 이 시점까지 실행된다면 자식의 실행이 끝난 상태이다. 다시 인터럽트가 걸리면서 부모가 마저 실행하려는 것을 실행하기 위해 8번라인을 실행한다. 설계의 의도대로라면 실행되면 안되지만 이미 7번을 통해 TEST가 끝난 상황이지만 그것을 알아내지 못했기 때문에 sleep이 되고 아무도 부모를 깨울 수 없게 된다.

 

얻은 결론은 wait뿐만 아니라 signal을 보낼때는 무조건 lock을 사용하는 것이 좋다는 것이다.

 

 # Producer (생산자 ) / Consumer (소비자) 문제

 생산자 - 소비자 그리고 유한버퍼문제는 동기화를 사용할때 생각해봐야할 대표적인 문제점이다. 간단한 설명을 하자면 생산자(p)는 유한버퍼(공유자원)에 항상 값을 넣고, 소비자(c)는 유한버퍼에서 값을 항상 꺼내오도록 한다. 생산자와 소비자가 쓰레드를 사용해 각각 실행되고 있다면 이 유한버퍼의 상태를 확인해가면서 동작해야한다. 즉 생산자는 유한버퍼에 값이 꽉찼는데 넣으면 문제(assert)가 발생하는 것이고, 소비자는 값이 없는데 가져가게 되면 문제(assert)가 발생하게 되는 것이다. 

## 버퍼, put()과 get()

 위의 설명이 put()과 get()의 정의이다. 아직은 버퍼가 1개의 값만을 저장할  수 있다는 가정하에 세워진 코드이다.

 

## 단일 컨디션 변수와 if문을 사용

 먼저 단일 컨디션 변수와 if문을 사용했을때 생기는 문제점을 알아보자. 위 코드는 생산자와 소비자가 각각 한개씩 존재할때는 문제 없이 실행된다. 그러나 두개 이상의 같은 종류의 쓰레드가 존재한다면 문제가 발생하게 된다.

 첫번째 문제점은 if문과 관련이 있다. C1과 C2가 소비자쓰레드가 두개 존재하고 P라는 생산자 쓰레드가 존재한다는 가정하에 C1이 먼저 실행하고 버퍼가 없기 때문에 wait한다. 이후에 P가 두번째로 실행되고 put하여 쓰레드를 넣어 주고나서 signal을 보내어 C1을 깨우고 아직 실행은 되지 않았지만 Ready상태에 들어간다. 이때 C2가 실행되어 P가 넣어뒀던 값을 빼내어 사용하게 되고 C1이 21번째 라인인 wait에서 리턴하여 get을 실행하게 된다. 그러나 C2가 이미 get을 했기 때문에 더이상 얻어 갈 값이 없게된다. if문을 사용했기 때문에 문제가 발생했다. 깨어난 후에 다른 소비자쓰레드가 가로채어 먼저 실행했는지 한번 더 확인하는 과정을 거쳐야 하기 때문에 20라인의 if를 while로 바꿔야 하는 것이다.  아래 흐름을 참고해보자.

 

## 컨디션 변수가 하나여서 생기는 문제

 Mesa semantic의 컨디션 변수에서 가장 기본적인 법칙은 언제나 while문을 사용하라는 것이다. 당연히 생산자도 if문을 while문으로 바꿔야 한다. 

 컨디션 변수가 하나뿐이여서 생기는 문제는 간단하다. 

위와 같은 흐름으로 실행된다면 C1과 C2과 컨디션 변수 c에 들어갈 것이다 즉, [C] -> Tc1 ->Tc2가 달려있는 상태가 될 것이고, p1이 실행되어 값을 하나 생성하여 넣고 signal을 보내 깨운다 [C] -> Tc2 -> P . 그러면 Tc1이 실행되게 될 것이다. 그리곤 get()을 실행한후 23번째 라인의 signal을 호출하여 현재 컨디션 변수에서 다음값인 Tc2를 깨운다 [C] -> P -> TC1. 여기서 문제가 생긴다. 소비자가 실행됐으면 생성자가 실행되고 다시 소비자가 실행되도록 해서 버퍼에 값을 넣고 빼는 것이 계속해서 일어나야하지만, 위 경우는 그렇지 않게 된다. 깨어난 Tc2는 21번라인에서 리턴됐기 때문에 20번라인에서 다시 검사를 하고 사용할 값이 없기때문에 다시 잠들게 된다.[C] -> P -> TC1 -> TC2 , Tc2는 아무것도 깨우지 않고 잠들었기 때문에 모든 쓰레드가 잠들어 대기상태에 빠져있기 때문에 어떤 쓰레드도 실행 될 수 없는 상태에 빠지게 된다. 

 

### 단일 버퍼의 생산자/ 소비자 해법

 생산자는 소비자를 깨우고, 소비자는 생산자를 깨울 수 있는 장치가 필요하다. 소비자가 소비자를 깨워버리는 경우 아무도 signal을 보내 깨우지 않고 잠들어 벌이는 상황이 올 수 있기 때문이다. 물론 그 반대도 그렇다.

 즉 두개의 컨디션 변수를 만들어, 생산자는 empty 큐에 들어가게 되고, 소비자는 fill큐에 들어가게 하면 된다. 생산자가 생산을 완료하면 소비자의 큐인 fill에 signal을 보내고, 소비자가 소비를 완료하면 생산자의 empty큐에 signal을 보내어 깨우면 된다.

 

# 최종적인 생산자 / 소비자 해법

단일 버퍼가 아닌 버퍼가 유한개를 저장하며 여러개의 값을 계속해서 소비하고 생산하는 로직을 만들어야 한다.

 

 

# covering condition - 한개의 컨디션 변수를 활용해 broadcast()

메모리 할당의 예시를 들어 생각해본다. 여러 쓰레드가 메모리 할당을 위해 공간을 요구하거나, free를 통해 반납하는 경우가 존재할 수 있다. 

A와 B가 각각 100과 10의 공간을 allocate를 호출하였으나 공간이 없어 아래와 같이 컨디션 변수에 저장되게 된다.

C는 50의 Free하여 힙에 공간을 만들었다. 원래는 b를 깨워 공간을 줘야하지만 그렇지 못했다. a가 깨어나고 공간이 부족하여 다시 잠에 빠지고 모든 쓰레드가 큐에서 대기상태가 되버린다. 

이에 대한 해결책으로는 cond_signal을 사용하여 컨디션 변수에 있는 쓰레드를 하나만 깨우는 것이 아닌, pthread_cond_broadcast()를 이용하여 컨디션 변수에 있는 모든 쓰레드를 깨워버리는 것이다. 그렇게 깨어난 쓰레드들은 다시 검사과정을 통해 wait하거나 실행하려던 것을 실행 할 수 있을 것이다. 

 이런 경우를 Covering Condition( 포함 조건 ) 이라고 한다. 비록 문맥 전환 오버헤드가 크다는 단점이 있다. 

 

# 마치며 

잘 정리된 쓰레드 트레이스를 첨부하도록하겠다.

## Broken Solution

 

## Better, But Still Broken : use While not If

 

## use two condition variable

 

## Covering Conditions