Concurrency refers to when there are one or more tasks that have overlapping lifetimes (between starting, running, and terminating).
Sequential concurrency is the idea that within a single Thread, we assume that the order of operations are the same as the program order, e.g. line by line.
Data race versus race condition
Data race: concurrent access to a shared resource with at least one write that can cause the resource to enter an invalid or unexpected state.
Race condition: when the program exhibits different behavior depending on the ordering of concurrent threads. This can occur even if we correctly gate shared resources.
Producer-consumer problem
Sometimes threads need to communicate with one another to know when they can perform operations. A common design pattern is the idea of producers/consumers.
- One or more thread(s) creates the tasks/data
- One or more thread(s) consumes the produced tasks/data to perform some operation.
Example
An application of this is a message queue. Another are Pipes: one end of the pipe waits on data to be sent from the other end.
Dependencies across threads
Usually both the producer and consumer are reading/writing to the same shared data structure or resource. How do we make sure that the threads play nice together?
- A consumer thread can acquire a Lock then block until it receives data from the shared resource. However, now the producer will not be able to acquire the lock, so the system becomes indefinitely stuck.
- A race condition can occur if the consumer runs before the producer.
“Failed” attempt: unlocking then locking
If blocked, release the lock then immediately attempt to acquire it back. This way we give an opportunity for the producer to access the resource.
void consume() {
while (true) {
pthread_mutex_lock(&lock);
// Potentially unlock so that the producer has a chance
while (shared_resource.is_empty()) {
pthread_mutex_unlock(&lock);
pthread_mutex_lock(&lock);
}
/* Consume shared resource... */
pthread_mutex_unlock(&lock);
}
}
This works, however we’re wasting CPU cycles by endlessly getting stuck in the while loops. We probably want a better solution that stops the thread entirely when there’s no data to consume.
Condition variables
Thread synchronization primitive. They’re variables that allow a thread to wait until they’re notified to resume.
- Avoids spinning—wasting clock cycles on waiting
- Performed in the context of mutual exclusion. A thread must already have a lock, which it temporarily releases while waiting.
- Once notified, the thread reacquires the lock and resumes execution.
POSIX threads condition variables API
<pthread.h>
also gives us condition variable data structures. It defines a pthread_cond_t
datatype which is then consumed by the pthread_cond_*
family of functions which initialize, wait, signal, and destroy these condition variables.
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);
Given a condition variable and mutex, this function calls the thread that calls it to release the mutex, sleep until it’s woken up, then attempt to reacquire the lock.
int pthread_cond_signal(pthread_cond_t *cond);
int pthread_cond_broadcast(pthread_cond_t *cond);
The first function signals one thread that is listening to cond
to wake up.
The second function broadcasts to all threads waiting on cond
to wake up. Note that only one of the threads will successfully acquire the lock, meaning the other threads will (most likely) go back to sleep again.
Also see
- Mutex, another synchronization primitive
- Communication across threads