[System Design]Producer Consumer Queue

Producer-Consumer problem is a well know problem, which describe two processes, producer and a buffer with fixed size, where:

• producer threads keep adding data onto the buffer
• consumer threads keep consuming data from the buffer

To be more accurate, we want the queue behaves as follow:

1. The queue will be a FIFO queue and has a maximum capacity
2. The producer threads will try to add new data onto the queue, if the queue is full, it will wait until there is room for new item
3. The consumer threads will try to consume data from the queue, if the queue is empty, it will wait until there is available item on the queue

To implement the class, we will need to use the following things:

• lock, to make sure each modification to the queue is correct and ordered correctly
• condition variable, thread will wait on this condition variable if the resource is not available, and will be notified if there is an update

Produce and consume logic:

• Producer thread will try to get the lock and add data onto the queue if it is not full, then notify the consumer to consume it; otherwise it will wait on the condition variable 
• Consumer thread will try to get the lock and remove data from the queue if it is not empty, then notify the producer if it is waiting; otherwise it will wait on the condition variable

The full code is like below:

Some explanations:

• cv.wait(lock, function) is the same as while(!function())wait(lock); The thread will wait on the condition variable and release lock, once it is notified, it will try to get lock again, if it has the lock it will exit wait method
• Why do we use while instead of if for the race condition check?
• One is the "spurious wakeup", which means the wait method can return without the thread having been notified
• The other is get notified doesn't necessarily mean the thread will try to get the lock next line, if some other threads are already waiting for the lock but are not in wait() method,  they might get the lock first and the condition might be changed, so we need to check it again
• Once the unique lock is constructed, the lock is acquired
• Why use notify_one() instead of notify_all() ?
• Notify_one() here is enough, since produce and consume threads are waiting on mutual exclusive conditions: one is when queue is full; the other is when queue is empty. So they won't wait at the same time, notify_one() can guarantee correct thread will be waked up every time.

Example testing: