CODEWITHSUNDEEP
javamutexsemaphoreblockingqueue
Jack Chen
Jack Chen

Reputation: 79

Can I implement blocking queue using Semaphore in Java?

I wonder if it is possible to use Semaphore to implement blocking queue?

In the below codes, I use one Semaphore to protect the critical section, and two more Semaphore objects to track the number of empty slots and filled objects.

public class BlockingQueue {
  private List<Object> queue = new LinkedList<Object>();
  private int limit;
  private Semaphore slots; // semaphore for empty slots
  private Semaphore objs;  // semaphore for filled slots
  private Semaphore mutex; // for the critical section
  public BlockingQueue(int limit) {
    this.limit = limit;
    this.slots = new Semaphore(limit); // initial empty slot = capacity
    this.objs = new Semaphore(0);
    this.mutex = new Semaphore(1);
  }
  private void enqueue(Object o) throws InterruptedException {
    slots.acquire();
    mutex.acquire(); // critical section starts
    queue.add(o);
    mutex.release(); // critical section ends
    objs.release();
  }
  private Object dequeue() throws InterruptedException {
    objs.acquire();
    mutex.acquire(); // critical section starts
    Object o = queue.remove(0);
    mutex.release(); // critical section ends
    slots.release();
    return o;
  }
}

Upvotes: 4

Views: 3807

Answers (3)

Sanushi Salgado
Sanushi Salgado

Reputation: 1456

Semaphore is another way to achieve mutual exclusion & synchronization. A binary semaphore or mutex can be used for locking & unlocking the critical section. A general semaphore or counting semaphore can be used to keep track of free slots & occupied slots.

Upvotes: 0

user2023577
user2023577

Reputation: 2121

Without testing, I would say this works. However, every release() will notify the thread blocked in acquire(). So you really have at least the same cost as a reentrantlock+condition, likely worse because there is 2 acquire and 2 release() calls.

Upvotes: 1

Pelit Mamani
Pelit Mamani

Reputation: 2381

Adding to a previous comment - we can agree your code works (it's a well known algorithm), in particular you're correct in protecting the LinkedList since it's not internally thread safe.

However, if you compare your code to the java util implementation http://grepcode.com/file_/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/concurrent/ArrayBlockingQueue.java/?v=source it might bring up some points to consider:

  1. please Google for discussions on "ReentrantLock versus Binary Semaphore": They both create a mutex & protect a critical section, but the former better describes your intentions, plus it might be easier for future maintenance. Eg a fellow programmer can't accidentally release a ReentrantLock by a thread that didn't acquire it

  2. Google for discussions on "semaphore versus condition variable" : Both allow you to "wait for something to become available", but condition variable might be more general, plus you can tie all your conditions to a single lock (as the java util code does). I assume this has some minor effect on performance, plus the way you'll need to approach future requirements such as interrupts, timeouts, crashes. This doesn't make your code "wrong", it's just something for you to consider.

Upvotes: 2

Related Questions