Creating a class that mimics a semaphore but the number of permits should never exceed 0

user_5677675 0
Viewed 170

I came across a problem to design a queue using a semaphore such that all threads that acquire it must wait until some thread releases them. But the catch here is that if release is called when no thread is waiting then it should not have any effect unlike a real semaphore where an extra permit will be added. I started trying something like this:

public class QueueOfThreads {
    
    private Semaphore valve = new Semaphore(0);
    volatile int count = 0;
    
    
    public void acquire() throws InterruptedException {
        synchronized(this) {
            count++;
        }
        valve.acquire();
    }
    
    public void release() {
        synchronized(this) {
            if(count > 0) {
                valve.release();
                count--;
            }
            else {
                System.out.println("will not release since no thread is waiting");
            }
        }
    }

}

But I can see that this is wrong since if a thread is preempted after count++ then the release can be called before acquire.

I spent a lot of time trying to find a way to make sure that at least one acquire is called before any release. But I always end up with the same problem, I can not signal to other threads about acquiring the semaphore after the semaphore is acquired since the current thread will be in waiting state. But if I signal before acquiring the semaphore then the thread can be preempted before the semaphore is actually acquired.

Please let me know if writing a class like this is possible and how to do it?

This problem came to me from a comment in a book called "The Little Book of Semaphores" By Allen B. Downey where it is mentioned that:

"Semaphores can also be used to represent a queue. In this case, the initial value is 0, and usually the code is written so that it is not possible to signal unless there is a thread waiting, so the value of the semaphore is never positive."

multithreading semaphore java
1 Answers

You can exploit Object.notify() which frees exactly one waiting thread, if any:

public class QueueOfThreads {

  public synchronized void acquire() throws InterruptedException {
    wait();
  }

  public synchronized void release() {
    notify();
  }
}

However, this works only on JVM without spurious wakeups. If spurious wakeup can happen, then the implementation is more complex:

public class QueueOfThreads {
  int threadCount = 0;
  boolean notified = false;

  public synchronized void acquire() throws InterruptedException {
    threadCount++;
    do {
      wait();
    } while (!notified);
    threadCount--;
    notified = false;
  }

  public synchronized void release() {
    if (threadCount==0) {
      return;
    }
    notified = true;
    notify();
  }
}
user_12063010
Related