본 글의 내용은 Operating Systems: Three Easy Pieces의 Condition Variable 챕터를 정리한 것입니다.

☑️ 개요

• 멀티 스레드 프로그램에서는 어떤 조건이 참이 될 때까지 스레드가 기다렸다가 진행해야 되는 경우가 많다.

• 이것을 spin으로 구현하는 것은 비효율적이기 때문에, 효율적으로 구현하기 위해 어떤 방법을 활용해야 할까?

☑️ 개념 정의 & 사용 사례

• 이런 경우 스레드는 condition variable(조건 변수)를 활용할 수 있다.

• 특정 스레드가 어떤 조건이 예상 값과 다를 때 대기(잠들기)하고, 다른 스레드가 해당 조건을 예상값으로 바꾸면서 신호를 보내면 그 스레드가 일어날 수 있다.

• 이 기능의 예시로 POSIX의 pthread_cond_wait 와 pthread_con_signal 이 있는데, 두 함수 모두 파라미터로 조건 변수를 전달 받는다.

• 이때 pthread_cond_wait 함수는 뮤텍스도 파라미터로 전달 받는데, 이때 전달받는 뮤텍스가 잠겨있다고 가정하고 전달받는다. 그리고 스레드가 뮤텍스 unlock과 스레드 잠들기를 원자적으로 수행하게 된다.

• 위 예제를 볼 때, 고려해야 할 경우가 두 가지 있다.

• 첫째로, 부모 스레드의 thr_join 함수가 먼저 호출되는 경우이다. 이때는 done 이 아직 0이기 때문에, 부모 스레드는 잠들게 되고 자식 스레드가 done 을 1로 만들고 signal 을 호출하면서 부모 스레드는 다시 깨어나게 된다.

• 둘째로, Pthread_create 가 호출되고 자식 스레드가 바로 thr_exit 을 빠르게 호출하는 경우이다. 이때 아직 부모 스레드는 잠들지 않았지만, done 이 자식 스레드에 의해 1이 되고, signal 을 통해 아무도 깨우지 않는다. 그러나 부모 스레드의 thr_join 이 호출될 때 done 이 1이 돼있기 때문에 부모 스레드는 잠들지 않는다.

• 만약 여기서 done 이 사라지면 어떻게 될까? 이러면 제대로 동작하지 못한다. 왜냐면 자식 스레드가 먼저 thr_exit 을 실행하면, 아무것도 깨우지 않고 끝이나고, 부모 스레드가 thr_join 을 뒤이어 실행하면서 영원히 잠들기 때문이다.

• 결론적으로 위 예제가 상태 변수 done 의 중요성을 알려준다.

• 이번엔 뮤텍스를 제거해볼 수도 있는데, 뮤텍스가 없으면 mutual exclusion이 제공되지 않기 때문에, 결과적으로 critical section에 race condition이 생겨 wait 와 signal 의 호출 시점이 interrupt에 의해 indeterminate하게 변한다.

☑️ 생산자/소비자(Bounded Buffer) 문제

• 하나 이상의 생산자 스레드, 그리고 소비자 스레드가 있다고 가정해보자.

• 생산자는 데이터를 생성하여 버퍼에 저장하고, 소비자는 버퍼의 데이터를 소비한다.

• 이런 구조는 웹 서버의 HTTP 요청 처리, UNIX 파이프(명령어를 | 로 연결하여 결과를 종합해 출력하는 것) 등 많은 실제 시스템에서 활용된다.

• 이러한 버퍼는 공유 리소스기 때문에, 당연히 race condition이 발생하지 않도록 해야 한다.

• 위 예제의 put 함수와 get 함수는 각각 buffer 상태 변수에 값을 저장하고, count 변수를 기준으로 예외를 발생시킨다. (예상값과 다르면 assert 호출)

• 그래서 생산자가 버퍼가 차있을 때 put 을 호출하거나, 소비자가 버퍼가 차있을 때 get 을 호출하면 뭔가 잘못된 것이다.

🔎 잘못된 접근 예제

• 위 예제에 생산자와 소비자가 각각 하나씩 존재한다고 가정해보면 큰 문제는 없다.

• 그러나 여기서 소비자가 두 스레드 존재한다면 문제가 발생한다.

  1. 소비자1이 데이터가 없는 것을 확인하고 wait 로 잠에 든 후, 생산자가 데이터를 만들어낸 뒤 signal 을 호출하여 소비자1를 깨운다.

  2. 이때 소비자2가 먼저 데이터를 소비하고, signal 로 생산자를 깨운 뒤 잠에 든다.

  3. 대기열에 있었던 소비자1이 이제 비로소 데이터 소비를 시도하고, 데이터가 없으므로 예외가 발생한다.

• 이 문제는 signal 이 단순히 스레드를 깨울 뿐, 버퍼의 상태 변경을 막지 않았기 때문에 벌어진 상황이다. 잠든 후 깨어났을 때 상태가 원하는 대로 유지된다는 보장은 없다. 이러한 해석을 Mesa semantics이라 한다.

🔎 If 대신 While을 써도 남아있는 문제

• 위 예제는 결론적으로 if 조건문 때문에 생긴 문제기 때문에, if 를 while 로 변경하면 스레드가 일어났을 때 다시 상태 변수를 확인하기 때문에 문제를 해결할 수 있다.

• 그러나 조건 변수 때문에 생기는 문제도 존재한다.

• 소비자1, 소비자2가 순차적으로 가져갈 데이터가 없어서 잠에 든 상태에서, 생산자가 데이터를 생성한 뒤 signal 을 호출했다고 해보자.

• 이때 소비자1이 다시 깨어나서 데이터를 소비하고, signal 을 호출하는데 조건 변수 cond 를 세 스레드가 공유하고 있기 때문에, 소비자2가 깨어날 수도 있다.

• 그래서 소비자2가 깨어나서 데이터가 없는 것을 확인 후, wait 를 통해 잠에 든다.

• 결과적으로 생산자, 소비자 스레드 모두 잠든 상태가 되었다.

🔎 솔루션

• 위 문제를 해결하기 위해 조건 변수를 여러개 사용할 수 있다. 생산자는 empty 에 대기하고, fill 에 signal 을 호출하며, 소비자는 fill 에 대기하며, empty 에 signal 을 호출한다.

• 이 구조를 통해 실수로 깨우지 말아야 할 스레드를 깨우는 것을 방지할 수 있다.

☑️ Covering conditions

• 이런 생산자/소비자 구조는 메모리 할당 시스템에도 사용될 수 있다.

• 만약 스레드 A가 allocate(100) 을 호출하고 스레드 B가 allocate(10) 을 호출한 뒤 대기하고 있을 때, 스레드 C가 free(50) 을 호출하여 메모리에 여유를 만들 수 있지만, 이 메모리를 제대로 필요로 하는 스레드를 깨우지 못할 수도 있다.

• 이런 상황에는 cond_broadcast 를 호출하여 잠든 모든 스레드를 깨울 수 있는데, 성능에 부정적인 영향을 미칠 수 있다는 단점이 있다. 그래서 몇몇 스레드는 조건을 확인 후 즉시 잠들면 된다.

• 이런 조건을 Lampson과 Redell(mesa semantics를 정의한 사람들)이 Covering condition이라 명칭하였다.

✅ 요약

• 스레드가 잠에 들 때, 다시 깨어나기 위해 condition variable(조건 변수)를 활용한다.

• 조건 변수를 활용하는 예시 중 생산자/소비자 문제가 있으며, 조건 변수 뿐만 아니라 뮤텍스, 상태 변수도 조합해서 문제를 해결한다.

• 모든 이슈는 모두 interrupt에 의한 동시성 문제에서 오는 것이다.

• 가끔은 잠든 모든 스레드를 깨우는 방식이 필요할 때가 있는데, 이런 상황을 covering condition이라 한다.