Simple counting fair semaphore implementation

Question

Here is my attempt to implement a simple counting semaphore in Java. Please share your comments.

/*
 * A simple counting semaphore implementation.
 * Acquire calls block until a resource is available.
 * Supports fairness option which serves Acquire calls 
 * in FIFO order.
 */

import java.util.Deque;
import java.util.ArrayDeque;

public class MySemaphore {
   private final int capacity;
   private int usedCount;
   private final boolean isFair;
   private Deque<Long> waitList;

   public MySemaphore(int capacity, boolean isFair) {
      this.capacity = capacity;
      this.isFair = isFair;

      if(isFair) {
         waitList = new ArrayDeque<>();
      }
   }

   public synchronized void acquire() {
      if(isFair)
         waitList.addLast(Thread.currentThread().getId());

      while(!(isResourceAvailable() && isEligibleToAcquire())) {
         try {
            wait();
         } catch(InterruptedException e) {
         }
      }

      usedCount++;

      if(isFair)
         waitList.removeFirst();
   }

   public synchronized void release() {
      if (usedCount > 0) {
         usedCount--;
         notifyAll();
      }
   }

   private boolean isResourceAvailable() {
      return usedCount < capacity;
   }

   private boolean isEligibleToAcquire() {
      if(!isFair)
         return true;

      // True only if current thread is at the head of the queue.
      return Thread.currentThread().getId() == waitList.getFirst();
   }
}

What happens to the intrinsic lock when interrupt is caught in the below block? My understanding is, the thread which catches the exception will still hold the lock. Please clarify.

  while(!(isResourceAvailable() && isEligibleToAcquire())) {
     try {
        wait();
     } catch(InterruptedException e) {
     }
  }

Answer 1

As for your question of what happens to the intrinsic lock when the InterruptedException is thrown: As soon as wait() is called, the thread relinquishes the lock, which is stated in the documentation of Object.wait(). Continuing to hold the lock would defeat the purpose of wait(), which is to wait for some other thread to do something for which it needs the lock and be notified when that thread is finished with the task and no longer needs the lock, so that the current thread can start trying to re-acquire the lock.

This means that, in order to return from wait() and, if needed, execute the catch block, the thread has to acquire the lock again first. Once the thread does have the lock, however, entering the catch block will have no effect on the thread's ownership of the monitor.

I found this question, which, along with the answer given there, might contain what you're interested in.

Update

Here's a test to demonstrate that, even if the catch block is not synchronized, it will still only be executed after the thread has re-acquired the lock, because the thread must first return from wait(), which will only happen when it has the lock it was waiting on.

static void testControlFlow() {
    final Object lock = new Object();

    final Thread threadA = new Thread(new Runnable() {
        @Override
        public void run() {
            try {
                synchronized (lock) {
                    while (!Thread.currentThread().isInterrupted()) {
                        lock.wait();
                        /* Theoretically, it is possible that threadA will
                           be spuriously woken up AND be interrupted by
                           threadB between this wake-up and the next loop
                           iteration. If this unlikely scenario happens,
                           then the catch block will never be executed because
                           no InterruptedException will ever be thrown */
                    }
                }
            } catch (InterruptedException e) {
                System.out.println("threadA has caught an InterruptedException");
            }
        }
    });

    Thread threadB = new Thread(new Runnable() {
        @Override
        public void run() {
            while (threadA.getState() != Thread.State.WAITING) {
                //ensure that threadA acquires the lock before threadB
            }
            synchronized (lock) {
                threadA.interrupt();
                while (threadA.getState() == Thread.State.WAITING) {
                    //wait for threadA to wake up
                }
                System.out.println("threadA has woken up");

                while (threadA.getState() == Thread.State.RUNNABLE) {
                    //see if threadA can catch the exception without holding the lock
                }

                if (threadA.getState() == Thread.State.BLOCKED) {
                    System.out.println("threadA is now blocked and trying to acquire the lock");
                } else {
                    assert threadA.getState() == Thread.State.TERMINATED;
                    System.out.println("threadA has terminated while threadB was still holding the lock");
                }
            }
        }
    });

    threadA.start();
    threadB.start();
}

Output is:

threadA has woken up
threadA is now blocked and trying to acquire the lock
threadA has caught an InterruptedException

Answer 2

I have not read Java Concurrency in Practice in awhile, so I won't risk trying to figure out if this is correctly thread-safe. You should really read that book if you have not done so. But I think the general advice was to never use wait and notify and instead use the constructs in java.util.concurrent, but I think the exception was for building concurrent libraries, which you are kind of doing.

It seems that having a separate subclass for the FairSemaphore would make the code much easier to read. I have not tried it, so maybe there is some issue that makes it impossible or overly complicated.

Answer 3

Revised the code to include base class for a simple semaphore and a subclass for FairSemaphore.

Simple unfair Semaphore:

/*
 * A simple counting semaphore implementation.
 * Acquire method blocks until a resource is available.
 */

public class SimpleSemaphore {
   private final int capacity;
   private int usedCount;

   public SimpleSemaphore(int capacity) {
      this.capacity = capacity;
   }

   public synchronized void acquire() {
      while(!(isResourceAvailable() && isEligibleToAcquire())) {
         try {
            wait();
         } catch(InterruptedException e) {
         }
      }

      usedCount++;
   }

   public synchronized void release() {
      if (usedCount > 0) {
         usedCount--;
         notifyAll();
      }
   }

   private boolean isResourceAvailable() {
      return usedCount < capacity;
   }

   protected boolean isEligibleToAcquire() {
      return true;
   }
}

Fair Semaphore:

This subclass implements fairness policy to the simple semaphore above. With this, threads that call Acquire will be served in FIFO order.

import java.util.ArrayDeque;
import java.util.Deque;

public class FairSemaphore extends SimpleSemaphore {
   private Deque<Long> waitList;

   public FairSemaphore(int capacity) {
      super(capacity);
      waitList = new ArrayDeque<>();
   }

   @Override
   public synchronized void acquire() {
      waitList.addLast(Thread.currentThread().getId());
      super.acquire();
      waitList.removeFirst();
   }

   @Override
   protected boolean isEligibleToAcquire() {
      // True only if current thread is at the head of the queue.
      return Thread.currentThread().getId() == waitList.getFirst();
   }
}