This week we continued learning about concurrency, focusing on synchronization. We covered OSTEP 30, 31, and 32, as well as a technique for writing concurrent code called the Anderson/Dahlin method.
OSTEP 30: Condition Variables
This lecture started with an example of why locks alone are sometimes not enough. Locks either let a thread proceed or block it from executing, but have no way to communicate anything beyond “this resource is in use.” If a thread needs to be notified when some condition becomes true, another mechanism is needed.
Condition variables allow signaling between threads. A thread can go to sleep, and another thread can send a signal for it to wake up, or broadcast to wake up multiple threads. The lecture used a temperature monitor as an example: with a lock, another thread monitoring a temperature variable would have to repeatedly poll for changes, wasting CPU time. With a condition variable, it can go to sleep and wake up when the temperature variable changes.
Bounded Buffer Problem
This was a hands-on lecture walking through a thread-safe queue as an example of a bounded buffer. The bounded buffer problem involves a shared, limited storage area (a buffer), where multiple producer threads add data, while consumer threads remove data from it. There are a few problems that can arise with bounded buffers:
- Buffer overflow: a producer thread can overflow the buffer by adding data when it is full
- Buffer underflow: a consumer may try to remove data while the buffer is empty
- Race conditions: threads may attempt to access the buffer at the same time, leading to indeterminate behavior
The demo showed how race conditions can lead to indeterminate behavior. When threads adding to the queue raced against threads trying to read from it, the output could include -1 (returned when the queue is full or empty) in different orders across runs. To prevent race conditions, threads can continually poll the queue to make sure that it isn’t full or empty, but this is inefficient, since the spinning thread will waste CPU time.
To make the queue more efficient, the condition variables is_not_empty and is_not_full were added, signaling to waiting threads when the queue is ready, so that they don’t need to spin and waste CPU.
Anderson/Dahlin Method
This lecture presented a repeatable process for turning a regular class into a concurrent, thread-safe class. The Anderson/Dahlin method is a five-step procedure that uses only locks and condition variables.
First, design the class as normal (without any concurrency), then add concurrency by following these steps:
- Add a single lock
- Use the lock around critical sections of the code
- Add condition variables for situations where a thread will need to wait
- Add signal and broadcast calls to coordinate threads
- Add wait conditions within loops, so threads will sleep when the condition variable is false, then check it again when it wakes up
One thing to keep in mind is that state variable names should make the condition obvious. For example, can_push and can_pop make it clear when the push and pop methods can be used.
OSTEP 31: Semaphores
Semaphores are a synchronization primitive that combines the behavior of a lock and a condition variable. It’s based on an integer value, which supports two operations after initialization: increment (signal) and decrement (wait). The integer value of the semaphore represents how many “slots” are available for threads to run.
The initialization value of the semaphore matters. Setting a semaphore to 1 makes it behave like a mutex. Setting it to 0 makes the first wait block immediately, which is useful for ordering.
Threads can also use semaphores to “rendezvous”, so that both threads will wait until the other thread has reached a certain point before proceeding. This can be accomplished by initializing the semaphore to 0, then having the thread signal with one semaphore, while it waits on the semaphore that the other thread will use to signal.
Synchronization Barriers
This lecture introduced the concept of a synchronization barrier, which is like the rendezvous pattern mentioned above, but extended to many threads.
The example in the lecture used two semaphores and a shared counter to create a synchronization barrier:
- A mutex semaphore (initialized to
1) ensures that updates to the counter are atomic - A barrier semaphore (initialized to
0) blocks all threads until the last one arrives - A shared count varaible tracks how many threads have checked in
Each thread locks the mutex, increments count, then unlocks it so the next thread can update the counter. After that, the thread waits at the barrier. When the count is equal to the number of threads, that means it’s the last thread, so it uses the barrier semaphore to signal to the other threads that they can all proceed.
The synchronization barrier example made it clear how semaphores can act as both a lock and a condition variable. In the same piece of code, one semaphore acts as a mutex and the other acts as a gate that signals when it is safe to move forward.
Reflection
After reviewing the lectures and readings from this week, I feel like I have a better understanding of concurrency and the kinds of bugs that can appear in concurrent programs. The code examples were especially helpful, since they made the problems more concrete and showed how synchronization tools like condition variables and semaphores can solve common issues. The Anderson/Dahlin method was also helpful, since it provides a structured process for designing thread-safe code.
Looking ahead, next week focuses on persistence, which should pair well with our group project on the Google File System. For the project, I’ve been learning about the challenges involved in designing a distributed file system, so it will be helpful to compare it to the challenges that are involved with a traditional file system.