Editing Monitor (synchronization) (section)

===Case study: classic bounded producer/consumer problem===
A classic concurrency problem is that of the '''bounded producer/consumer''', in which there is a [[queue (data structure)|queue]] or [[circular buffer|ring buffer]] of tasks with a maximum size, with one or more threads being "producer" threads that add tasks to the queue, and one or more other threads being "consumer" threads that take tasks out of the queue.  The queue is assumed to be non–thread-safe itself, and it can be empty, full, or between empty and full.  Whenever the queue is full of tasks, then we need the producer threads to block until there is room from consumer threads dequeueing tasks.  On the other hand, whenever the queue is empty, then we need the consumer threads to block until more tasks are available due to producer threads adding them.

As the queue is a concurrent object shared between threads, accesses to it must be made [[atomicity (database systems)|atomic]], because the queue can be put into an '''inconsistent state''' during the course of the queue access that should never be exposed between threads.  Thus, any code that accesses the queue constitutes a '''[[critical section]]''' that must be synchronized by mutual exclusion.  If code and processor instructions in critical sections of code that access the queue could be '''interleaved''' by arbitrary '''context switches''' between threads on the same processor or by simultaneously-running threads on multiple processors, then there is a risk of exposing inconsistent state and causing [[race condition]]s.

====Incorrect without synchronization====
A naive approach is to design the code with '''busy-waiting''' and no synchronization, making the code subject to race conditions:

<syntaxhighlight lang="cpp">
global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.
        while (queue.isFull()) {} // Busy-wait until the queue is non-full.
        queue.enqueue(myTask); // Add the task to the queue.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        while (queue.isEmpty()) {} // Busy-wait until the queue is non-empty.
        myTask = queue.dequeue(); // Take a task off of the queue.
        doStuff(myTask); // Go off and do something with the task.
    }
}
</syntaxhighlight>

This code has a serious problem in that accesses to the queue can be interrupted and interleaved with other threads' accesses to the queue.  The ''queue.enqueue'' and ''queue.dequeue'' methods likely have instructions to update the queue's member variables such as its size, beginning and ending positions, assignment and allocation of queue elements, etc.  In addition, the ''queue.isEmpty()'' and ''queue.isFull()'' methods read this shared state as well.  If producer/consumer threads are allowed to be interleaved during the calls to enqueue/dequeue, then inconsistent state of the queue can be exposed leading to race conditions.  In addition, if one consumer makes the queue empty in-between another consumer's exiting the busy-wait and calling "dequeue", then the second consumer will attempt to dequeue from an empty queue leading to an error.  Likewise, if a producer makes the queue full in-between another producer's exiting the busy-wait and calling "enqueue", then the second producer will attempt to add to a full queue leading to an error.

====Spin-waiting====
One naive approach to achieve synchronization, as alluded to above, is to use "'''spin-waiting'''", in which a mutex is used to protect the critical sections of code and busy-waiting is still used, with the lock being acquired and released in between each busy-wait check.

<syntaxhighlight lang="cpp">
global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock; // A mutex for the ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isFull()) { // Busy-wait until the queue is non-full.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a consumer might take a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isFull()".
        }

        queue.enqueue(myTask); // Add the task to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isEmpty()) { // Busy-wait until the queue is non-empty.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a producer might add a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isEmpty()".
        }
        myTask = queue.dequeue(); // Take a task off of the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.
        doStuff(myTask); // Go off and do something with the task.
    }
}
</syntaxhighlight>

This method assures that an inconsistent state does not occur, but wastes CPU resources due to the unnecessary busy-waiting.  Even if the queue is empty and producer threads have nothing to add for a long time, consumer threads are always busy-waiting unnecessarily.  Likewise, even if consumers are blocked for a long time on processing their current tasks and the queue is full, producers are always busy-waiting.  This is a wasteful mechanism.  What is needed is a way to make producer threads block until the queue is non-full, and a way to make consumer threads block until the queue is non-empty.

(N.B.: Mutexes themselves can also be '''spin-locks''' which involve busy-waiting in order to get the lock, but in order to solve this problem of wasted CPU resources, we assume that ''queueLock'' is not a spin-lock and properly uses a blocking lock queue itself.)