Condition Synchronization

Why Do We Need Condition Synchronization?

지금까지 살펴본 Mutual Exclusion(상호 배제)는 여러 프로세스 또는 스레드가 동시에 공유 자원에 접근하지 못하도록 하는 기법이었다.

즉,

한 번에 하나의 스레드만 접근 가능

을 보장하는 것이 목표이다.

하지만 동시성 프로그램에서는 이것만으로 충분하지 않다.

실제로는

지금 실행해도 되는가?

라는 문제가 자주 발생한다.

예를 들어 Producer-Consumer 문제를 생각해보자.

Producer
↓
Buffer
↓
Consumer

Consumer는 버퍼에 데이터가 존재할 때만 작업을 수행할 수 있다.

Buffer Empty

인 상태에서는 임계 구역에 진입할 수 있더라도 수행할 작업이 존재하지 않는다.

따라서 단순한 상호 배제가 아니라

특정 조건이 만족될 때까지 기다리는 기능

이 필요하다.

이를 Condition Synchronization(조건 동기화)라고 한다.

Busy Waiting의 문제

가장 단순한 방법은 공유 변수를 계속 확인하는 것이다.

while(done == 0)
{
}

또는

while(buffer.empty())
{
}

하지만 이러한 방식은 CPU를 계속 사용하게 된다.

조건 확인
↓
실패
↓
조건 확인
↓
실패
↓
...

이러한 방식을 Busy Waiting 또는 Spinning이라고 한다.

조건이 만족될 때까지 CPU를 낭비하게 되므로 비효율적이다.

Condition Variable

Condition Variable(CV)은 특정 조건이 만족될 때까지 스레드를 잠재우기 위한 동기화 자료형이다.

강의자료에서는

"A waiting queue on a condition"

으로 설명한다.

즉,

조건이 만족되지 않음
↓
Sleep
↓
조건 만족
↓
Wake Up

을 수행하는 대기 큐라고 생각하면 된다.

Condition Variable Operations

Condition Variable은 두 개의 기본 연산을 제공한다.

wait()

wait();

조건이 만족되지 않으면 스레드를 Sleep 상태로 전환한다.

signal()

signal();

조건을 기다리는 스레드 중 하나를 깨운다.

broadcast()

broadcast();

조건을 기다리는 모든 스레드를 깨운다.

State Variable

Condition Variable을 사용할 때는 일반적으로 조건을 나타내는 상태 변수(State Variable)가 필요하다.

예를 들어

int done = 0;

와 같이 정의할 수 있다.

done = 0
→ 작업 미완료

done = 1
→ 작업 완료

Condition Variable은 조건 자체를 저장하는 것이 아니라

상태 변수
+
대기 큐

를 이용하여 동작한다.

wait()의 원자성

Condition Variable에서 가장 중요한 특징 중 하나는

pthread_cond_wait()

가 원자적으로 동작한다는 것이다.

wait()는 다음 세 작업을 하나의 원자적 연산처럼 수행한다.

1. Mutex 해제
2. Sleep
3. Mutex 재획득

만약 이 과정이 원자적이지 않다면 신호를 놓쳐(Lost Wakeup) 영원히 잠들 수 있다.

Why Use while Instead of if?

많은 학생들이 다음과 같이 작성한다.

if (count == 0)
    pthread_cond_wait(&cv, &m);

하지만 이는 올바르지 않다.

Condition Variable에서 깨어난 이후에도 조건이 여전히 만족되지 않을 수 있기 때문이다.

따라서 반드시 조건을 다시 검사해야 한다.

while (count == 0)
{
    pthread_cond_wait(&cv, &m);
}

이를 Re-checking the Condition이라고 한다.

Producer-Consumer Problem

대표적인 조건 동기화 문제이다.

조건

Consumer
→ Buffer Empty 이면 대기

Producer
→ Buffer Full 이면 대기

One Condition Variable Is Not Enough

처음에는 하나의 Condition Variable만 사용하려고 생각할 수 있다.

pthread_cond_t cv;

하지만 Producer와 Consumer가 모두 같은 CV를 사용하면 잘못된 스레드가 깨어날 수 있다.

Producer 깨워야 하는데
Consumer가 깨어남

Consumer 깨워야 하는데
Producer가 깨어남

이러한 문제로 인해 모든 스레드가 잠드는 상황이 발생할 수 있다.

Two Condition Variables

강의자료의 최종 해결책은 Condition Variable을 두 개 사용하는 것이다.

pthread_cond_t empty;
pthread_cond_t fill;

empty

버퍼에 빈 공간이 생김

Producer를 깨운다.

fill

버퍼에 데이터가 들어옴

Consumer를 깨운다.

while (count == MAX)
    pthread_cond_wait(&empty, &m);

while (count == 0)
    pthread_cond_wait(&fill, &m);

이 방식은 Producer와 Consumer를 정확하게 깨울 수 있어 효율적이다.

정리

Condition Synchronization은 "누가 들어갈 수 있는가?"를 해결하는 Mutual Exclusion과 달리,

지금 실행 가능한가?

를 해결하는 동기화 기법이다.