A bounded
buffer is a
queue data structure with a maximum capacity. In systems programming, the most
common bounded buffers hold up to CAP characters, where CAP is the buffer
capacity. A writer can write characters into the buffer until it is full, and
a reader can read characters out of the buffer until it is empty. This kind of
bounded buffer is used to implement pipe buffers, network socket buffers, and
other communication buffers. (We implemented a bounded buffer in the
kernel8
classwork.)
Bounded buffers have interesting blocking behavior.
- A writer that attempts to write a character into a full buffer should block until some space is available (or the buffer is closed).
- A reader that attempts to read a character out of an empty buffer should block until some characters are available (or the buffer is closed).
Bounded buffers also have interesting synchronization behavior, because they involve multiple communicating threads or processes.
Conceptual work
How would you use mutexes and condition variables to build a correctly-synchronized bounded buffer?
1. How many condition variables, and corresponding to which conditions?
2. How many mutexes?
3. Sketch out some pseudocode.
Concrete work
If you have time, implement your plan in our bounded buffer code, cs61-lectures/net5/bbuffer.cc.
Condition variable operations
std::condition_variable_any cv;
std::mutex m;
cv.wait(m);
// In one atomic step, effectively:
// (1) Unlocks `m` via `m.unlock()`
// (2) Blocks until another thread calls `cv.notify*()`.
// Then, when this thread is woken up, it re-locks `m` via `m.lock()`
// before returning.
cv.notify_all();
// Wakes up all threads blocked in `cv.wait()`.
We recommend always using std::condition_variable_any, because
std::condition_variable has some surprising
gotchas.