Condition variable은 락으로 보호되는 공유 조건을 안전하게 기다리는 패턴을 구현한 동기화 primitive이다.
여기서 조건은 condition variable 내부에 저장되는 값이 아니다. 조건은 공유 상태에 대한 predicate, 즉 참/거짓으로 평가되는 조건식이다.
예시는 다음과 같다.
count > 0
queue_empty(&q) == false
state == READYCondition variable은 이 조건을 직접 검사하지 않는다. 조건 검사는 사용자 코드가 수행한다.
사용자 입장에서 condition variable은 다음 패턴으로 사용한다.
lock_acquire(&lock);
while (!condition) {
cond_wait(&cv, &lock);
}
/* condition == true 이고 lock을 잡은 상태 */
do_work();
lock_release(&lock);깨우는 쪽은 다음과 같은 형태이다.
lock_acquire(&lock);
change_shared_state(); // condition이 true가 될 가능성이 생김
cond_signal(&cv); // 대기 중인 스레드 하나를 깨움
lock_release(&lock);외부 사용자 시점에서 중요한 규칙은 다음과 같다.
1. condition을 검사할 때 lock을 잡는다.
2. condition이 false이면 cond_wait()를 호출한다.
3. cond_wait()에서 리턴하면 다시 lock을 잡은 상태이다.
4. 깨어났다고 condition이 반드시 true라는 보장은 없으므로 while로 재검사한다.
5. 공유 상태를 변경해서 condition이 true가 될 가능성이 생기면 signal/broadcast를 호출한다.
즉, 사용자 코드의 책임은 다음과 같다.
사용자 코드:
- lock을 잡고 predicate를 검사한다.
- predicate가 false이면 cond_wait()로 대기한다.
- 공유 상태를 변경한다.
- 조건이 참일 가능성이 생기면 cond_signal() 또는 cond_broadcast()를 호출한다.
Condition variable의 책임은 다음과 같다.
condition variable:
- 기다리는 스레드를 대기 상태로 만든다.
- signal/broadcast 호출 시 대기 중인 스레드를 깨운다.
- 조건 자체를 판단하지 않는다.
따라서 condition variable은 스스로 조건을 감시하지 않는다.
사용자 코드가 공유 상태를 변경한 뒤 조건이 참일 가능성이 생겼다고 판단하면 signal 또는 broadcast를 호출한다. 깨어난 스레드는 다시 조건을 검사하고, 조건이 만족되면 작업을 진행한다.
예시는 다음과 같다.
lock_acquire(&lock);
while (count == 0) {
cond_wait(¬_zero, &lock);
}
count--;
lock_release(&lock);다른 스레드:
lock_acquire(&lock);
count++;
cond_signal(¬_zero);
lock_release(&lock);이 관점에서는 condition variable을 다음처럼 이해할 수 있다.
lock:
공유 상태를 보호한다.
condition:
공유 상태에 대한 predicate이다.
condition variable:
predicate가 true가 될 가능성을 기다리는 스레드들의 대기 큐이다.
내부적으로 cond_wait()는 단순히 “잠든다”만 수행하지 않는다.
다음 동작이 하나의 안전한 순서로 처리되어야 한다.
1. 현재 스레드를 condition variable의 wait queue에 등록한다.
2. 사용자가 넘긴 lock을 release한다.
3. 현재 스레드를 sleep 상태로 만든다.
4. signal/broadcast에 의해 깨어난다.
5. 사용자가 넘긴 lock을 다시 acquire한다.
6. 호출자에게 리턴한다.
이를 추상 코드로 쓰면 다음과 같다.
void cond_wait(struct condition *cv, struct lock *lock) {
register_current_thread_to_wait_queue(cv);
lock_release(lock);
sleep_current_thread();
lock_acquire(lock);
}여기서 중요한 점은 “wait queue 등록”과 “lock release 후 sleep” 사이에 race가 없어야 한다는 것이다.
즉, 다음 흐름이 보장되어야 한다.
대기자는 lock을 놓기 전에 wait queue에 등록되어 있어야 한다.
그래야 다른 스레드가 signal을 호출했을 때 깨울 대상을 찾을 수 있다.
잠들기 전에 lock을 놓는 이유는 다른 스레드가 공유 상태를 변경해서 조건을 만족시킬 수 있도록 하기 위해서이다.
깨어난 뒤 다시 lock을 잡는 이유는 공유 상태를 안전하게 다시 검사하고 작업을 수행하기 위해서이다.
다만 이것은 내부 동작의 추상 설명이다. 실제로 이 atomic성을 어떻게 보장할지는 구현마다 다르다.
구현 예:
- 인터럽트 비활성화
- 내부 spinlock
- 커널 wait queue
- futex
- 세마포어
따라서 이론적으로 중요한 것은 특정 구현 방식이 아니라 다음 보장이다.
condition variable은
대기자 등록, lock release, sleep 전환 과정에서 lost wakeup이 발생하지 않도록 구현되어야 한다.
Pintos에서는 condition variable을 세마포어를 이용해서 구현한다. 여기서 condition variable 자체가 세마포어라는 뜻은 아니다. 이미 구현된 세마포어를 이용해서 스레드를 재우고 깨우는 구조이다.
Pintos의 condition variable은 대기자 리스트를 가진다.
condition variable
└── waiters list
├── waiter A: semaphore value = 0
├── waiter B: semaphore value = 0
└── waiter C: semaphore value = 0
각 waiter는 내부에 세마포어 하나를 가진다.
struct semaphore_elem {
struct list_elem elem;
struct semaphore semaphore;
};cond_wait()를 호출할 때마다 새로운 semaphore_elem이 생성된다.
void cond_wait(struct condition *cond, struct lock *lock) {
struct semaphore_elem waiter;
sema_init(&waiter.semaphore, 0);
list_insert_ordered(&cond->waiters, &waiter.elem,
cmp_priority, NULL);
lock_release(lock);
sema_down(&waiter.semaphore);
lock_acquire(lock);
}동작은 다음과 같다.
1. 현재 스레드 전용 세마포어를 만든다.
2. 세마포어 초기값을 0으로 설정한다.
3. 현재 스레드를 condition variable의 waiters 리스트에 등록한다.
4. lock을 release한다.
5. 자신의 세마포어에서 sema_down()으로 잠든다.
6. signal을 받아 깨어난다.
7. 다시 lock을 acquire한다.
8. cond_wait()에서 리턴한다.
이 구현에서는 cond_wait() 호출 하나마다 세마포어가 하나 만들어진다. 따라서 일반적인 사용에서는 대기 스레드 하나와 세마포어 하나가 1:1로 대응한다고 볼 수 있다.
cond_signal()은 waiters 리스트에서 하나를 꺼내고, 그 waiter의 세마포어를 up한다.
void cond_signal(struct condition *cond, struct lock *lock) {
if (!list_empty(&cond->waiters)) {
sema_up(&list_entry(list_pop_front(&cond->waiters),
struct semaphore_elem, elem)->semaphore);
}
}즉, cond_signal()의 의미는 다음과 같다.
1. condition variable의 waiters 리스트에서 대기자 하나를 선택한다.
2. 그 대기자의 개인 세마포어에 sema_up()을 호출한다.
3. 해당 세마포어에서 자고 있던 스레드가 깨어난다.
cond_broadcast()는 이 과정을 waiters 리스트가 빌 때까지 반복한다.
void cond_broadcast(struct condition *cond, struct lock *lock) {
while (!list_empty(&cond->waiters)) {
cond_signal(cond, lock);
}
}Pintos 구현에서 핵심은 condition variable이 직접 스레드를 block/unblock하는 로직을 새로 만들지 않고, 이미 구현된 세마포어의 sema_down() / sema_up()을 이용한다는 점이다.
다만 이것은 구현 선택이다. Condition variable을 반드시 세마포어로 구현해야 하는 것은 아니다. 세마포어와 비슷한 wait queue, thread block/unblock 로직, 인터럽트 비활성화 등을 직접 사용해서도 구현할 수 있다.
Pintos에서는 편의상 다음과 같이 구현한 것이다.
condition variable:
waiters 리스트 관리
각 waiter:
개인 세마포어 보유
cond_wait:
waiter 등록
lock release
개인 세마포어에서 sleep
wakeup 후 lock reacquire
cond_signal:
waiter 하나 선택
그 waiter의 개인 세마포어 up
정리하면 다음과 같다.
이론적 condition variable:
공유 상태의 predicate가 만족될 때까지 기다리는 동기화 패턴
Pintos의 condition variable 구현:
각 대기자마다 값 0인 세마포어를 만들고,
signal 시 해당 세마포어를 up해서 스레드를 깨우는 구현
즉, condition variable은 개념적으로 “조건을 기다리는 큐”이고, Pintos에서는 그 큐의 각 대기자를 세마포어로 재우고 깨우는 방식으로 구현한다.