4

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;
  }
}
Jack Chen
  • 79
  • 1
  • 7
  • 1
    why are you trying to [reinvent the wheel](https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/BlockingQueue.html)? Btw : Semaphore is not a mutex nor a "critical section". Both of these terms have completely different meanings – specializt Feb 03 '16 at 05:57
  • 1
    @specializt Actually I was asked this question in a interview before, so I am trying to figure out how to do it by myself. I know Semaphore is not a mutex, or a critical section. I just mean that I am using a Semaphore named mutex to protect the critical section. Sorry for the unclear description. – Jack Chen Feb 03 '16 at 06:12
  • 1
    there is no critical section in your code ... also : employers which ask you to reimplement things which already exist should be avoided at all costs ... just saying. In fact it is desirable to search for employees who re-use proven, stable libraries instead of re-writing everything because this speeds up development massively - it also boosts software quality. – specializt Feb 03 '16 at 06:16
  • Oh I thought LinkedList's add() and remove() are not thread-safe, so I had to protect the critical section. Isn't it the case? In that interview, I was using C++ instead of Java. That might be the reason that the interviewer asked me to implement blocking queue. Maybe C++ doesn't have similar class in its STL. – Jack Chen Feb 03 '16 at 06:36
  • again : there is no critical section in your question and nothing is being "protected" – specializt Feb 03 '16 at 07:05
  • 1
    Unfortunately I only had time to browse it shortly, but IMHO it's a basically reasonable approach. I just wanted to refer you to the java implementation http://grepcode.com/file_/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/concurrent/ArrayBlockingQueue.java/?v=source which relies on Condition vars instead, and might be more robust in terms of interruptions etc (note the conditions are tied to a single lock). But that doesn't make your approach wrong. – Pelit Mamani Feb 03 '16 at 10:18
  • 1
    @JackChen You may want to add some try-finally clauses and a basic check for existance in the dequeue code. Your current implementation only produces deadlocks. – billc.cn Feb 03 '16 at 13:57
  • @specializt, Why do you keep saying there is no critical section? A critical section is defined as a sequence of instructions that only one thread can execute at a time. (https://en.wikipedia.org/wiki/Critical_section) And why would you think a semaphore can not be used for mutual exclusion? (See section 3.3 of "The Little Book of Semaphores" by Allan B. Downey.) – Solomon Slow Feb 03 '16 at 14:48
  • I recommend doing a bit of research about mutexes and critical sections, the above example can be executed by arbitrary amounts of threads and can be interrupted at any time whereas csections are quite the opposite, Semaphores can be controlled by any instance whereas mutexes can only be controlled by its original creator. IT books often contain noticeable amounts of utter bullshit, even wiki is better sometimes.l – specializt Feb 03 '16 at 14:51
  • @specializt can you please tell us what's your definition for *critical section*? Because, from what I've been taught, the one in the OP *is* a *critical section*. – StepTNT Feb 03 '16 at 15:41
  • you havent even read what i wrote until now, huh? For instance : interrupt handler routines _(hardware interrupts, that is)_ are critical sections, thats why they **need** to be fast and well-tested. – specializt Feb 03 '16 at 16:12
  • Until now you just wrote that there's no cs in that code and that *books often contain noticeable amounts of utter bullshit*, which adds really nothing to the discussion. By the way, your definition is way too narrow. In multi-threading environments the common definition is the one posted by @jameslarge. Also, *mutex* means *mutual exclusion*, so you can use *java* `Semaphore` as a *mutex*. Please remember that we're talking about high-level languages, there's no need to overcomplicate things. – StepTNT Feb 03 '16 at 16:29
  • the solely possible definition is "way too narrow" and non-exclusion suddenly is exclusion. Yeah. Right. Im kinda glad that i never was slave to the made-up words of confused old men or children ... – specializt Feb 03 '16 at 19:23

3 Answers3

2

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.

Pelit Mamani
  • 2,321
  • 2
  • 13
  • 11
  • 1
    `ArrayBlockingQueue` is a good reference for the style of protection OP has implementated but is not a good example of how to turn a linked list into a concurrent queue. Atomic compare-and-swap, which the Semaphore will use internally (if provided by the platform), is the most clean and efficient way. See `ConcurrentLinkedQueue` source code. – billc.cn Feb 03 '16 at 14:02
  • Locks and binary semaphores dont "protect" critical sections, that doesnt even make any sense -- csections cannot be "protected" to any extent, they run outside of the scope of normal applications most of the time (with exceptions of course) – specializt Feb 03 '16 at 16:18
  • Great! I will read these references. By the way, what does the name "Reentrant" mean? – Jack Chen Feb 03 '16 at 19:22
  • Just found [this](http://stackoverflow.com/questions/1312259/what-is-the-re-entrant-lock-and-concept-in-general) post that explain what does "reentrant" mean. – Jack Chen Feb 03 '16 at 19:38
1

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.

user2023577
  • 1,752
  • 1
  • 12
  • 23
0

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.

Sanushi Salgado
  • 1,195
  • 1
  • 11
  • 18