[CS][Study] Monitor & Conditional Variable

조건변수란? 동기화 메커니즘 중 세마포어와 뮤텍스, 락은 익숙한데 여기서 약간 더 심화한다면 나올 수 있는 게 조건변수다. 생성자-소비자 문제와 관련해 사용될 수 있다.

1. Monitor

동시성 프로그래밍에서, 모니터는 스레드가 공유 객제의 상태에 동시적으로 접근하는 것을 막고 해당 상태가 변경되어 조건이 충족될 때까지 대기할 수 있도록 하는 동기화 구조이다. 즉, 접근 가능한 스레드의 수를 제한하는 세마포어나 일반 뮤텍스와 다르게, 모니터는 특정 조건의 충족을 기준으로 공유 자원에 대한 독점적인 액세스를 제공한다. (한 번에 하나의 스레드만 접근할 수 있다.) 일반적으로 락과 하나 이상의 조건 변수로 구성된다.

2. Conditional Variable

조건 변수는 해당 조건의 충족을 대기하고 있는 대기열로 구성된다. 조건 변수는 해당 상태가 변경될 때 명시적으로 시그널을 보내 대기열에 있는 스레드 중 일부 또는 전부를 wake한다.

wait(condvar, lock)

만약 조건변수가 참이 아니라면, 모니터를 획득할 수 없으므로 wait 연산을 실행하게 된다. 스레드의 상태가 Running에서 Block로 변경되고, condvar의 대기열로 이동되어 블락된다.

signal(condvar)

조건변수가 참이 되면 모니터를 획득한 스레드에 의해 호출된다. 대기열에서 하나의 스레드를 선택해 깨우는 연산으로, 구체적으로는 상태를 Block에서 Ready로 변경한 후 스케줄링을 위한 대기 큐로 이동시킨다. 어느 스레드를 깨울지는 구현 정책에 따라 달라지는데, FIFO를 쓸수도 있고 우선순위 스케줄링에서는 우선순위 순일수도 있다.

broadcast(condvar)

signal과 유사하지만, 해당 조건변수의 모든 스레드를 깨운다는 점이 다르다. 깨어난 스레드는 대기열에서 나온 순으로 락의 획득을 시도하고, 나머지 스레드는 해당 락의 대기열로 들어간다.

3. Producer-Consumer Problem

작업 큐와 생산자, 소비자 스레드가 있다고 하자. 생산자 스레드는 큐에 작업을 추가하고 소비자 스레드는 큐에서 작업을 꺼낸다. 이 큐를 thread safe하도록 하려면 어떻게 해야 할까?

일단 만약 큐에 대한 상호 배제가 없다면 어떻게 될까? 큐에 접근할 때의 큐의 상태가 일관되지 않을 수 있다. 생산 혹은 소비 접근이 원자적으로 이루어지지 않기 때문이다. 이러한 상태를 race condition이라고 한다.

그래서 큐에 락을 걸어 상호 배제를 구현했다. 하지만 큐에 대한 접근을 상호 배제하는 것으로는 부족하다. 여러 생산자 스레드가 큐가 가득 찼음에도 불구하고 돌아가면서 큐에 삽입을 시도할 수 있기 때문이다.

즉, 단지 접근 제어가 아니라 큐의 상태 (is_full, is_empty)를 보아야 한다. 큐의 상태를 체크하면서 busy-waiting 방식으로 스레드를 대기시키는 스핀락을 사용할 수도 있지만, 명시적인 대기열을 두고 blocking 방식을 사용하는 게 CPU낭비가 없다는 점에서 더 좋다. 따라서 이를 위해 조건변수가 사용될 수 있다.

// pseudo

bool is_full, is_empt;
cv cv_full;     // full 인 경우 생산자 스레드가 대기함
cv cv_empt;     // empty인 경우 소비자 스레드가 대기함
queue taskq;

void produce(Task t) {
    acquire(taskq.lock);

    while(taskq.is_full) {
        wait(taskq.lock, cv_full);
    }

    taskq.enqueue(t);
    signal(cv_empt);    // 대기하던 소비자 스레드 깨움
    release(taskq.lock);
}

Task consume() {
    acquire(taskq.lock);

    while(taskq.is_empty) {
        wait(taskq.lock, cv_empt);
    }

    Task t = taskq.dequeue();
    signal(cv_full);    // 대기하던 생산자 스레드 깨움
    release(taskq.lock);

    return t;
}

What's more?

Spurious wakeup

스레드가 신호를 받지 않았는데 대기에서 깨어나는 경우가 있다. (왜 그런가?) 이런 현상이 있어서 signal함수 종료 후에 실제 조건 변수가 변경된 게 맞는지 한 번 더 검증하는 코드를 심을 수 있다. cv_full 조건변수에 대한 signal함수 실행 후에 !taskq.is_full 이 true인지 한번 더 체크하고, 아닐 경우 다시 wait하는 식이다.