I. Bounded Partial Queue

1. Overview

Assumming that the head of the queue is a sentinel node.

Composition

Use permits.getAndIncrement/Decrement to modify the size of queue.

Each lock has an associated condition:

• $\tt notFullCondition$ for enqLock is used to notify waiting enqueuers when the queue is no longer full;
• $\tt notEmptyCondition$ for deqLock is used to notify waiting dequeuers when the queue is no longer empty.

<aside> 🔍 Lost Wakeup

Consider the following scenario:

Consumers A and B both try to dequeue an item from an empty queue, both detect the queue is empty, and both block on the notEmpty condition.

Producer C enqueues an item in the buffer, and signals notEmpty, waking A. Before A can acquire the lock, however, another producer D puts a second item in the queue, and because the queue is not empty, it does not signal notEmpty.

Then A acquires the lock and removes the first item, but B, victim of a lost wakeup, waits forever, even though there is an item in the queue to be consumed.

Solution: always use signalAll and notifyAll

</aside>

2. Split Counter

In this approach, the enq() and deq() share no locks, but do share an atomic counter.

Therefore, we can split counter:

• Enqueuer decrements enqSidePermits
• Dequeuer increments deqSidePermits
• When enqueuer runs out
  • Locks deqLock and transfers permits
• Intermittent synchronization
  • Not with each method call but need to get both deqLock and enqLock

3. Unbounded Total Queue

Eliminate permits, the enq() method always enqueues its item, and deq() throws EmptyException if there is no item to dequeue.