Condition Variable

Condition variable for thread synchronization. More...

Detailed Description

Condition variable for thread synchronization.

This file contains a condition variable with Mesa-style semantics.

Condition variable solve the following problem. Suppose that a thread should sleep until a certain condition comes true. Condition variables provide a primitive whereby a thread can go to sleep by calling cond_wait(). Then, when the condition comes true in a thread or interrupt context, cond_signal() can be called, to wake up the thread.

"Mesa-style semantics" means that, when cond_signal() is called, the sleeping thread becomes runnable, but may not be scheduled immediately. In contrast, "Hoare-style semantics" means that when cond_signal() is called, the sleeping thread is awakened and immediately scheduled. The condition variable in this file implements Mesa-style semantics, as is used by other standard implementations, such as pthreads.

To avoid races, condition variables are used with mutexes. When a thread is put to sleep with cond_wait, it atomically unlocks the provided mutex and then goes to sleep. When it is awakened with cond_signal, it reacquires the mutex.

As a rule of thumb, every condition variable should have a corresponding mutex, and that mutex should be held whenever performing any operation with the condition variable. There are exceptions to this rule, where it is appropriate to call cond_signal or cond_broadcast without the mutex held (for example, if you know that no thread will call cond_wait concurrently). It is safe to call cond_signal or cond_broadcast in interrupt context.

However, the programmer should be aware of the following situation that could arise with Mesa-style condition variables: the condition may become true, making the sleeping thread runnable, but the condition may become false again before the thread is scheduled. To handle this case, the condition variable should be used in a while loop as follows:

mutex_lock(&lock);
while (condition_is_not_true) {
cond_wait(&cond, &lock);
}
// do work while condition is true.
mutex_unlock(&lock);

When used in this way, the thread checks, once it has has awakened, whether the condition is actually true, and goes to sleep again if it is not. This is the standard way to use Mesa-style condition variables.

Example: Suppose we want to implement a bounded queue, such as a Unix-style pipe between two threads. When data is written to the pipe, it is appended to a queue, and the writing thread blocks if the queue is full. When data is read from the pipe, it is removed from the queue; if the queue is empty, the reading thread blocks until it is not empty. If the pipe is closed by the sender, waiting reading threads wake up.

Here is a sketch of how to implement such a structure with condition variables. For simplicity, messages are single bytes. We assume a FIFO data structure queue_t. We assume it is unsafe to add to the queue if it is full, or remove from the queue if it is empty.

typedef struct pipe {
queue_t queue;
cond_t read_cond;
cond_t write_cond;
mutex_t lock;
bool closed;
void pipe_init(pipe_t* pipe) {
queue_init(&pipe->queue);
cond_init(&pipe->read_cond);
cond_init(&pipe->write_cond);
mutex_init(&pipe->lock);
pipe->closed = false;
}
void pipe_write(pipe_t* pipe, char c) {
mutex_lock(&pipe->lock);
while (queue_length(&pipe->queue) == MAX_QUEUE_LENGTH && !pipe->closed) {
cond_wait(&pipe->write_cond, &pipe->lock);
}
if (pipe->closed) {
mutex_unlock(&pipe->lock);
return 0;
}
add_to_queue(&pipe->queue, c);
cond_signal(&pipe->read_cond);
mutex_unlock(&pipe->lock);
return 1;
}
void pipe_close(pipe_t* pipe) {
mutex_lock(&pipe->lock);
pipe->closed = true;
cond_broadcast(&pipe->read_cond);
cond_broadcast(&pipe->write_cond);
mutex_unlock(&pipe->lock);
}
int pipe_read(pipe_t* pipe, char* buf) {
mutex_lock(&pipe->lock);
while (queue_length(&pipe->queue) == 0 && !pipe->closed) {
cond_wait(&pipe->read_cond, &pipe->lock);
}
if (pipe->closed) {
mutex_unlock(&pipe->lock);
return 0;
}
*buf = remove_from_queue(&pipe->queue);
cond_signal(&pipe->write_cond);
mutex_unlock(&pipe->lock);
return 1;
}

Note that this could actually be written with a single condition variable. However, the example includes two for didactic reasons.

Files

file  cond.h
 Condition variable for thread synchronization.
 

Data Structures

struct  cond_t
 Condition variable structure. More...
 

Macros

#define COND_INIT   { { NULL } }
 Static initializer for cond_t. More...
 

Functions

void cond_init (cond_t *cond)
 Initializes a condition variable. More...
 
void cond_wait (cond_t *cond, mutex_t *mutex)
 Waits on a condition. More...
 
void cond_signal (cond_t *cond)
 Wakes up one thread waiting on the condition variable. More...
 
void cond_broadcast (cond_t *cond)
 Wakes up all threads waiting on the condition variable. More...
 

Macro Definition Documentation

◆ COND_INIT

#define COND_INIT   { { NULL } }

Static initializer for cond_t.

Note
This initializer is preferable to cond_init().

Definition at line 167 of file cond.h.

Function Documentation

◆ cond_broadcast()

void cond_broadcast ( cond_t cond)

Wakes up all threads waiting on the condition variable.

The threads are marked as runnable and will only be scheduled later at the scheduler's whim, so they should re-check the condition and wait again if it is not fulfilled.

Parameters
[in]condCondition variable to broadcast.

◆ cond_init()

void cond_init ( cond_t cond)

Initializes a condition variable.

For initialization of variables use COND_INIT instead. Only use the function call for dynamically allocated condition variables.

Parameters
[in]condPre-allocated condition structure. Must not be NULL.

◆ cond_signal()

void cond_signal ( cond_t cond)

Wakes up one thread waiting on the condition variable.

The thread is marked as runnable and will only be scheduled later at the scheduler's whim, so the thread should re-check the condition and wait again if it is not fulfilled.

Parameters
[in]condCondition variable to signal.

◆ cond_wait()

void cond_wait ( cond_t cond,
mutex_t mutex 
)

Waits on a condition.

Parameters
[in]condCondition variable to wait on.
[in]mutexMutex object held by the current thread.
mutex_lock
void mutex_lock(mutex_t *mutex)
Locks a mutex, blocking.
pipe_write
ssize_t pipe_write(pipe_t *pipe, const void *buf, size_t n)
Write to a pipe.
cond_wait
void cond_wait(cond_t *cond, mutex_t *mutex)
Waits on a condition.
cond_signal
void cond_signal(cond_t *cond)
Wakes up one thread waiting on the condition variable.
cond_broadcast
void cond_broadcast(cond_t *cond)
Wakes up all threads waiting on the condition variable.
mutex_init
static void mutex_init(mutex_t *mutex)
Initializes a mutex object.
Definition: mutex.h:156
cond_t
Condition variable structure.
Definition: cond.h:153
pipe_t
struct riot_pipe pipe_t
A generic pipe.
pipe_init
void pipe_init(pipe_t *pipe, ringbuffer_t *rb, void(*free)(void *))
Initialize a pipe.
pipe_read
ssize_t pipe_read(pipe_t *pipe, void *buf, size_t n)
Read from a pipe.
riot_pipe
A generic pipe.
Definition: pipe.h:55
cond_init
void cond_init(cond_t *cond)
Initializes a condition variable.
mutex_unlock
void mutex_unlock(mutex_t *mutex)
Unlocks the mutex.
mutex_t
Mutex structure.
Definition: mutex.h:120