Bounded Blocking queue in Java(programming exercise)

Question

This problem is LeetCode 1188 and stated here. I am able to implement it using Java's synchronized keyword. Pasting the problem here before asking my question.

Implement a thread safe bounded blocking queue that has the following methods:

• BoundedBlockingQueue(int capacity) The constructor initializes the queue with a maximum capacity.
• void enqueue(int element) Adds an element to the front of the queue. If the queue is full, the calling thread is blocked until the queue is no longer full.
• int dequeue() Returns the element at the rear of the queue and removes it. If the queue is empty, the calling thread is blocked until the queue is no longer empty.
• int size() Returns the number of elements currently in the queue.

I saw a solution here. Pasting the solution has well(from the link).

class BoundedBlockingQueue {
  public BoundedBlockingQueue(int capacity) {
    this.enqueueSemaphore = new Semaphore(capacity);
  }

  public void enqueue(int element) throws InterruptedException {
    enqueueSemaphore.acquire();
    q.offer(element);
    dequeueSemaphore.release();
  }

  public int dequeue() throws InterruptedException {
    dequeueSemaphore.acquire();
    final int element = q.poll();
    enqueueSemaphore.release();
    return element;
  }

  public int size() {
    return q.size();
  }

  private Queue<Integer> q = new ArrayDeque<>();
  private Semaphore enqueueSemaphore;
  private Semaphore dequeueSemaphore = new Semaphore(0);
}

Why is this implementation correct is what is bothering me? I understand why and how the semaphores are being used. What I don't understand is that the access to the private Queue<Integer> q = new ArrayDeque<>(); is not restricted when one thread is modifying it. I mean to say if one thread is mutating the queue, another can too. How is this correct? Should not the queue be guarded by a mutex as well apart from the use of semaphores? As per Java, the queue implementation being used is not thread safe.

Answer 1

You are correct to be skeptical. Synchronizing access to data shared among different threads is easy to get wrong, and testing may be inconsistent. Happily, java.util.concurrent recapitulates the Memory Consistency Properties, which may be used to reason about the proposed solution. In general:

Each action in a thread happens-before every action in that thread that comes later in the program's order.

Moreover, each Semaphore has a particular memory consistency effect:

Actions in a thread prior to calling a "release" method such as release() happen-before actions following a successful "acquire" method such as acquire() in another thread.

Finally, the intended usage must be considered:

[It] will be tested using multiple threads at the same time. Each thread will either be a producer thread that only makes calls to the enqueue method or a consumer thread that only makes calls to the dequeue method.

Example 1. One consumer thread; one producer thread. Because each mutation of q happens-before a semaphore is released and subsequently acquired on the opposite thread, each thread sees a consistent view of the ArrayDeque. The two semaphores act in concert to preclude deadlock, as when a producer blocks waiting for a permit and a consumer has yet to release one.

Example 2. Four consumer threads; three producer threads. In this case the actions remain correctly ordered, but the competing threads deadlock fairly promptly in what appears to be pool-induced deadlock, mentioned here. One remediation is suggested in a subsequent comment in the example, which notifies waiting producers that a permit has become available or idle consumers that an element has become available.

Use key word synchronized to control queue access from different threads.