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

안녕하세요! Pingu입니다.

 

오늘도 열심히 OS에 대해 알아보겠습니다!

 

지난 글에서는 일반적인 자료구조에 Lock을 상호 배제 구현하여 thread safety 하게 만드는 방법에 대해 알아봤었습니다. 여러 가지 자료구조에 대해 lock으로 상호 배제를 구현하고 발생하는 문제점들을 해결했었죠! 이번 글에서는 Condition Variable(상태 변수)라는 것을 추가하여 lock을 사용할 때 상호 배제만 고려하는 것이 아닌 synchronization(동기화) 즉 스레드들의 실행 순서 관계를 관리하는 방법을 알아보려고 합니다. 제가 공부할 때 참고하고 있는 OSTEP 책에서는 Chapter 30 - Condition Variables 부분 입니다!

Conditional Variables

지난 글까지는 lock의 개념에 대해 알아보고 lock API를 활용해 lock을 사용했었습니다. 그리고 OS, 하드웨어의 지원을 받아 lock을 사용할 때 발생하는 문제점들을 해결했었습니다! 그런데 lock만 사용해서 concurrency를 구현할 수 있을까요? 동시성은 어떻게 구현할지 몰라도 synchronization(동기화)는 lock만으로 구현하기는 어려울 거예요. 여기서 동기화란 상호 배제와 순서 관계를 모두 고려하는 것입니다. 이를 이해하기 위해 부모 스레드, 자식 스레드가 존재하는 경우를 보면 lock만 사용하면 안 된다는 것을 알 수 있는데요, 여기서 부모 스레드는 자식 스레드를 만든 스레드라고 보시면 됩니다.

 

예를 들어 부모 스레드가 자식 스레드의 완료 여부를 알고 싶다면 어떻게 해야 할까요? join() 함수를 사용해서 이를 알 수 있었는데요, 그렇다면 join 함수를 사용하지 않고 자식 스레드의 완료를 알고 싶을 때 부모 스레드는 뭘 하면서 자식 스레드의 완료를 기다리고 있을까요?

void *child(void *arg){
    printf("child\n");
    return NULL;
}

int main(int argc, char *argv[]) {
    printf("parent: begin\n");
    pthread_t c;
    // 자식 스레드 생성
    pthread_create(&c, NULL, child, NULL);
    printf("parent: end\n");
    return 0;
}

위의 코드를 수행하면 위와 같은 결과가 나오게 됩니다. 아직은 자식 스레드의 완료를 기다리는 코드가 아닙니다. 지금까지 알아본 방법 중 spin lock 방법을 사용해서 부모 스레드가 자식 스레드의 완료를 기다리게 만들어보면..

volatile int done = 0;

void *child(void *arg){
    printf("child\n");
    done = 1;
    return NULL;
}

int main(int argc, char *argv[]) {
    printf("parent: begin\n");
    pthread_t c;
    // 자식 스레드 생성
    pthread_create(&c, NULL, child, NULL);
    // 자식 스레드가 전역변수 done을 1로 만들 때 까지 spin
    while (done == 0)
    
    printf("parent: end\n");
    return 0;
}

전역 변수를 하나 선언하고 자식 스레드가 완료될 때 이 값을 바꿔주는 것이죠. 부모 스레드는 해당 값이 바뀌었는지를 계속 확인하다 바뀐 순간 자신도 종료하게 됩니다. 근데 이렇게 만들어 버리면 자식 스레드가 완료될 때까지 부모 스레드는 하는 일도 없으면서 CPU를 차지하고 있게 됩니다. 따라서 자식 스레드가 완료될 때까지 부모 스레드는 잠시 sleep(절전) 상태로 변환해서 CPU의 낭비를 줄이고 싶고 이번 글에서 방법을 알아볼 예정입니다!

Definition and Routines

특정 작업을 기다릴 때 계속 조건을 확인하며 CPU를 차지하고 있는 게 아니라 sleep 상태로 전환하여 CPU 낭비를 줄이기 위해서는 condition variable(조건 변수)라는 것을 사용할 수 있습니다. 조건 변수는 스레드가 특정 조건이 만족되지 않았을 때 큐 안에서 대기하게 만들어 줍니다. 다른 스레드에서 큐 안에서 sleep 상태로 대기 중인 스레드를 깨우면 해당 스레드는 큐에서 나와서 다시 실행 가능한 상태가 됩니다. 예를 들어 A 스레드는 B 스레드가 완료된 후에 실행되고 싶다고 할 때 조건변수를 사용하면 A는 B가 완료될때까지 sleep 상태로 기다립니다. 그러다 B 스레드가 종료될 때 A 스레드를 깨우게 되고 그제서야 A 스레드는 실행가능한 상태가 되는 것입니다.

 

그럼 이런 조건 변수를 사용하는 방법을 살펴보겠습니다.

위와 같이 pthread_cond_t 타입으로 조건 변수를 만들어 줄 수 있습니다. 코드를 잘 살펴보시면 조건 변수를 사용하는 함수에 wait, signal이라는 함수가 있는 것을 볼 수 있는데요, 말 그대로 wait은 기다리는 함수이고 signal은 기다리는 함수를 깨우는 함수입니다.

// 스레드를 sleep 상태로 만드는 함수
pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m); 

// 스레드를 ready 상태로 만드는 함수
pthread_cond_signal(pthread_cond_t *c);

wait 함수를 잘 살펴보시면 mutex, 즉 lock을 매개변수로 갖는 것을 볼 수 있습니다. wait는 매개변수로 받는 lock을 해제하여 다른 스레드가 lock을 획득하게 해 주고 원래 lock을 갖고 있던 스레드는 sleep 상태로 전환합니다. 이 모든 과정은 원자적으로 수행됩니다.

 

위의 코드가 실행된다면 어떻게 될까요? 만약 싱글 프로세서 시스템이라고 가정하면 2가지 경우로 실행될 수 있습니다.

 

첫 번째 경우는 부모 스레드가 자식 스레드를 만들고 바로 thrjoin() 함수를 호출하여 자식 스레드가 완료되는 것을 기다립니다. 이게 정상적인 방법이었죠?

 

두 번째 경우는 부모 스레드가 자식 스레드를 만들면 자식 스레드가 바로 수행되어 done을 1로 바꾸고 부모 스레드가 thr_join을 호출합니다. done은 이미 1이므로 wait를 하지 않고 바로 끝나게 됩니다.

 

위의 코드에서는 부모가 done을 확인하는 부분을 while로 처리했는데, 만약 if로 처리한다면 어떻게 될까요? 이에 대한 부분은 잠시 후에 생산자/소비자 문제에 대해 알아볼 때 알아보기로 하겠습니다. 그전에 thr_exit(), thr_join()에 대해 좀 더 알아보고 넘어가기 위해 아래와 같이 코드를 바꿔보겠습니다.

아까 코드와 바뀐 점은 done이라는 전역 변수가 사라진 것입니다. 이렇게 코드가 바뀌게 되면 자식 스레드가 바로 실행되어 thr_exit()를 호출한다면 깨울 스레드가 없는데도 그냥 signal을 보내고 끝나게 됩니다. 그런 뒤 부모 스레드에서 wait()를 호출하여 sleep 상태로 넘어가면 아무도 부모 스레드를 깨울 수 없게 되어 버리는 것이죠. 따라서 done이라는 변수가 중요한 것을 알 수 있습니다.

그럼 이젠 lock을 사용하지 않고 wait, signal을 사용하면 어떻게 될까요? done이라는 변수는 부모, 자식 스레드 모두 접근할 수 있는 임계 영역입니다. 임계 영역에 대한 상호 배제가 구현되지 않은 상태로 실행하게 되면 발생하는 문제점은 이전 글들에서 자세히 알아봤었죠? 따라서 위의 코드도 문제가 많은 코드입니다.

 

그럼 이제 wait, signal을 사용하는 간단한 예를 알아봤으니 좀 더 복잡한 예를 알아볼까요?

The Producer/Consumer (Bounded Buffer) Problem

이번에 알아볼 문제는 Producer/Consumer (생산자/소비자) 문제입니다. 생산자는 말 그대로 어떤 데이터를 만드는 녀석이고 소비자는 생산자가 만든 데이터를 소비하는 녀석이라고 생각하시면 됩니다. 그리고 여기서 buffer라는 용어가 나오게 되는데 buffer(버퍼)는 생산자가 뭔가를 생산하면 넣어두는 창고라고 생각하시면 됩니다. 그리고 소비자는 버퍼에서 뭔가를 꺼내 소비하게 됩니다.

 

Bounded buffer(경계 버퍼)는 다양한 프로그램에서 사용되는 아이디어로 HTTP 요청을 처리하는 작업이나 한 프로그램의 출력을 다른 프로그램으로 파이프 할 때도 사용됩니다. 여기서 버퍼는 공유 자원이므로 여러 스레드에서 접근이 가능한데 여기서 race condition이 발생할 수 있고 이를 해결하기 위한 방법이 필요합니다. 그럼 간단한 코드를 보며 생산자/소비자 문제를 살펴보겠습니다.

put(), get()이라는 단순한 두 함수로 생산자/소비자가 하는 일을 표현할 수 있습니다. put()은 공유 버퍼의 값을 변화시키고 get()은 공유 버퍼의 값을 반환하는 것이죠. 그리고 count는 공유 버퍼의 사이즈라고 보시면 됩니다. 즉 위의 코드에서는 사이즈가 1인 것입니다. 카운트가 0일 때만 put()은 동작하며 카운트가 1일 때만 get()은 동작하게 됩니다.

이렇게 만든 put(), get() 함수를 생산자, 소비자 스레드가 사용하는 코드는 위와 같습니다. 생산자는 반복 횟수만큼 데이터를 공유 버퍼에 저장하고 소비자는 get()이 될 때마다 공유 버퍼의 값을 가져옵니다. 그럼 현재 위의 코드와 같이 구현된 생산자/소비자에서 문제는 없을까요?

 

현재 문제점은 buffer, count라는 임계 영역이 존재하는데 여기에 대한 상호 배제가 구현되어있지 않습니다. 그리고 이번 글에서 동기화를 위해 알아보고 있는 조건 변수도 존재하지 않으니 이를 추가한 코드를 작성해야 합니다.

위와 같이 만들었다면 이제 생산자, 소비자를 각각 하나씩 존재할 때는 잘 작동할 거예요. 근데 만약 생산자나 소비자가 둘 이상 존재한다면..? 잘 작동할까요? 또한 아까 임계 영역의 데이터를 확인할 때 while 대신 if를 사용하면 어떨지에 대해 나중에 알아본다고 했는데 위의 코드는 if를 사용하고 있으니 여기에 대한 문제도 없을지 살펴보도록 하겠습니다. 문제점을 살펴보기 위해 소비자가 2개, 생산자가 1개 있는 상황을 가정해보겠습니다.

위와 같이 소비자가 2개(Tc1, Tc2)이고 생산자가 1개(Tp1)인 상황에서 스레드들을 실행한다고 했을 때 가장 먼저 소비자 Tc1이 수행된다고 생각해보겠습니다. 쭈욱 수행하다 코드에서 c2 부분에서 count == 0 이므로 c3으로 넘어가 wait()을 호출하게 되고 Tc1이 sleep 상태로 변환됩니다. 그런 뒤 Tp가 스케줄링되어 count == 0이라서 put()을 호출하여 생산을 하게 되고 p5 부분에서 signal()이 호출되어 아까 sleep 상태로 전환했던 Tc1을 깨웁니다. 그러다 다시 반복문에 의해 반복할 땐 count == 1이므로 wait()가 호출되어 sleep으로 전환됩니다. 그런 뒤 이번에는 Tc2가 수행되고 count == 1이라 get()을 하게 되고 count를 0으로 초기화합니다. 그런 뒤 스케줄링에 의해 Tc1이 수행될 때 드디어 문제가 발생합니다. Contect switch가 되며 이전에 수행하던 지점부터 수행하게 되는데 아까 c3까지 수행했으므로 이젠 c4를 수행할 차례인데 버퍼에는 아무것도 존재하지 않습니다. 여기서 발생한 문제를 단순화하면 Tc1이 실행되기 전에 버퍼의 상태가 변경되었다는 것이죠.

이게 바로 while 대신 if를 사용할 때 발생할 수 있는 문제입니다. 다시 확인을 하지 않기 때문에 버퍼가 비었는데도 불구하고 get()을 하려고 하는 것이죠.

따라서 while을 사용해야 방금 발생한 문제를 해결할 수 있습니다.

 

하지만 아직 문제는 하나 더 존재합니다. 조건 변수가 하나라는 사실이죠. 조건 변수가 하나라서 발생하는 문제를 살펴볼까요?

현재 코드로 소비자 2개, 생산자 1개 일 때 작업을 수행하면 위와 같은 문제점이 발생합니다. 먼저 Tc1이 실행되고 count == 0이므로 wait()합니다. 그런 뒤 Tc2가 수행되고 역시나 count == 0이므로 wait()합니다. 드디어 Tp가 수행되고 count == 0 이므로 put()을 호출해 버퍼에 값을 넣고 signal()을 호출하여 Tc1을 깨운 뒤 반복을 다시 하는데 이젠 count == 1이라서 wait()합니다. Tc1만 깨어있으므로 Tc1을 수행하는데 context switch에 의해 c2부터 시작되고 이번에는 while로 바꿨기 때문에 다시 한번 count를 확인합니다. 한 번 get()을 한 뒤 sleep 중인 Tc2를 깨우고 다음 반복에서는 count == 0이므로 다시 wait()이 호출됩니다. 이제 수행되는 Tc2 역시 context switch 되어 c2부터 수행되며 count == 0이므로 wait()을 호출합니다. ??? 이렇게 되니 결국 모두가 sleep인 상태가 되어버렸네요. 이는 큰 버그입니다. 단순하게 이를 해결할 수 있는 방법은 생산자는 소비자만 깨우고 소비자는 생산자만 깨우는 뭔가 그러한 규칙이 존재해야겠네요. 이를 위해 조건 변수를 2개 사용합니다.

따라서 위와 같이 조건 변수를 2개로 만들어 생산자는 소비자만 깨우고 소비자는 생산자만 깨우도록 하도록 해줘야 아까 발생한 모두가 sleep인 문제가 발생하지 않습니다.

 

이제 그럼 버퍼의 크기가 1인 경우는 잘 동작하니 버퍼의 크기를 키워보도록 하겠습니다. 이를 위해 버퍼 구조 자체를 수정하고 put(), get()을 수정해야 합니다. 또한 생산자와 소비자의 wait() 호출 시점도 다르게 해야 하는데, 생산자는 버퍼가 가득 찬 경우에만 wait()하며 소비자는 버퍼가 모두 비었을 때에만 wait() 해야 합니다.

즉 위와 같이 수정하게 되면 버퍼의 크기가 큰 상황에서 생산자, 소비자가 여러 개라도 잘 작동하는 코드가 완성됩니다!

Covering Conditions

하나의 상황은 문제없이 해결했으니 그럼 조건 변수를 사용하는 다른 예를 하나 더 살펴볼까요? 

위의 코드는 멀티 스레드 메모리 할당 라이브러리에서 문제를 발생하는 코드입니다. 코드를 보면 스레드가 메모리 할당 코드(allocate())를 호출할 때 더 많은 메모리가 사용 가능해질 때까지 기다려야 할 수 있습니다. 반대로 스레드가 메모리를 해제하면 더 많은 메모리를 사용할 수 있다고 신호를 보내죠. 근데 만약 메모리를 할당받으려는 스레드가 여러 개일 때는 어떤 스레드를 깨워야 할까요? 선택 장애가 오는 시점입니다. 만역 여기서 아무 스레드나 깨워버리면 발생하는 문제는 뭘까요?

예를 들어 위와 같이 처음에 사용 가능한 메모리가 0인 상태에서 Ta, Tb가 각각 100, 10의 메모리를 요청했다고 가정해보겠습니다. 처음엔 사용가능한 메모리가 0이니 두 스레드 모두 sleep상태가 됩니다. 후에 Tc가 수행되어 50의 메모리가 해제되었는데 이때 Ta 스레드를 깨우면 문제가 발생합니다. Ta는 자신에게 필요한 100만큼이 없으므로 다시 sleep에 빠지게 되는데 이 때 그냥 혼자 sleep에 빠지게 되는 것이죠. Tb는 수행될 수 있는데도 말이에요. 따라서 위와 같은 상황이 발생하면 수행할 수 있는데도 불구하고 아무것도 수행하지 않는 상태가 됩니다. 이를 해결하기 위한 방법으로 지금까지 스레드를 sleep에서 깨울 때 사용한 signal() 말고 broadcast()라는 녀석을 사용하는 방법입니다. broadcast()는 sleep 상태의 모든 스레드를 깨우는 함수입니다. 물론 이 때 성능에 부정적인 영향을 줄 수도 있지만 이렇게 하면 방금 발생한 문제는 해결할 수 있죠. 하지만 분명 문제가 있는 방법일 수 있으니 잘 고려해서 사용해야 합니다.

Summary

이번 글에서는 동시성을 구현할 때 상호 배제를 위한 lock 말고도 동기화를 위한 condition variable(조건 변수)에 대해 알아봤습니다. 계속 CPU를 사용하면서 대기하기보다는 sleep 상태로 전환해서 기다리는 방법을 위한 wait(), signal(), broadcast()에 대해서도 알아봤었죠 또한 생산자/소비자 문제에서 발생하는 문제점들을 해결도 했었습니다. 다음 글에서는 드디어 그 유명한 Semaphores에 대해 알아보도록 하겠습니다.

 

감사합니다.