The setup
Let us consider a variant of the classical multithreaded programming problem: the producer/consumer problem. We have some finite number of resources (for simplicity, let there be just a single resource). The producer thread continuously creates new resource units, until the resource buffer is full (in our case, it can only produce one resource unit before blocking). The consumer thread fetches resources from the buffer and performs some work with them.
The problem
The trick is to use some sort of a synchronisation primitive (or several primitives) to prevent the buffer from entering an inconsistent state as a result of race conditions, etc.
The question
As far as I know, the problem could be solved using any of the following:
- monitors
- a mutex and a condition variable
- two semaphores
- three mutexes
I could use the algorithm from the semaphore solution to solve the problem using just two mutexes, but since the thread is only allowed to unlock its own mutexes, this algorithm cannot be applied here. I have not been able to come up with another one so far.
Thus, my question is:
Is it possible to solve the described variant of producer/consumer problem using just a pair of mutexes, without any other synchronisation primitive?
If it is not, why? Could you provide a formal proof?
Best Answer
Basically the producer/consumer architectures use a queue that is fed by the producer(s) and read by the consumer(s):
The concurrency and racing conditions are all related to the management of the queue.
The simplest way to proceed would be to protect every queue access with a single mutex, held and released either by producer or the consumer. The problem in your scenario, is that the producer writes continuously new items until buffer is full, so there is a risk of letting the consumers starve until buffer is full, thus arriving de facto at a sequentialization of the processing.
The variants that you propose avoid starvation by ensuring a more balanced access to the shared queue (as for example the condition variable with the mutex).
But it is also possible to share a queue using two mutexes ! One such example consist of using a mutex for the head and a mutex for the tail (a so-called fine grained lock as implemented here)