One of the classic problems in synchronization is the producer-consumer problem (also known as the bounded buffer problem). We can think about the problem like this: let us return to our guitar store where we are constantly both selling the guitars we have in stock as well as making new ones. But we only have enough space in our store to hold n
guitars at a time.
Programmatically, we can represent the spots for guitars in our store as places in a buffer. Since we can have a maximum of n
guitars in the store at a time, our buffer is of length n
. The problem we face is synchronizing the buffer such that multiple threads can write to it and read from it in a thread-safe manner.
There are two rules: if the buffer is empty, no thread can read from it, and if the buffer is full, no thread can write to it.
One solution could be for each thread to lock the entire buffer, see whether it can do its operation, and then unlock it. But consider how inefficient this is, especially as n
becomes large and the number of threads increases. If we can hold five thousand items and have a hundred threads writing to and reading from our buffer, then each time a thread performs a task, the other ninety-nine are forced to wait.
The best solution is to use semaphores. Semaphores are essentially just integers that will keep track of two values, num_free
for how many empty places and num_occupied
for how many occupied places there are in the buffer.
write()
wait until num_free > 1
decrement num_free
add to the buffer
increment num_occupied
read()
wait until num_occupied > 1
decrement num_occupied
read from the buffer
increment num_free
As a result, the adding and removing of items from the buffer and corresponding semaphore values will look like the graphic to the right. As elements are added to the buffer, the number of taken spaces increases, and the number of empty spaces decreases. The same occurs in reverse when elements are removed from the buffer. When there are no empty spaces, the producer thread must wait. Conversely, when there are no taken spaces, the consumer thread must wait.
Instructions
Click Next when you’re ready to move on to the next exercise.