Here is is a fixed code, taking in to account Spurious wakeup issue.Thanks to Costa for bringing that up.
ISemaphore:
package edu.vandy.utils;
/**
* This interface provides a simple counting semaphore to manage
* concurrent access to a set of resources. A semaphore may implement
* "Fair" or "Unfair" policies.
*/
public interface ISemaphore {
/**
* Acquire one permit from the semaphore in a manner that can be
* interrupted.
*/
public void acquire() throws InterruptedException;
/**
* Acquire one permit from the semaphore in a manner that cannot
* be interrupted.
*/
public void acquireUninterruptibly();
/**
* Return one permit to the semaphore.
*/
public void release();
/**
* Return the number of permits available.
*/
public int availablePermits();
}
**SimpleSemaphore:**
package edu.vandy.utils;
import java.util.ArrayList;
/**
* Implements a counting semaphore that uses Java built-in monitor
* objects to provide "fair" and "non-fair" semantics. Fair semantics
* are implemented via the Specific Notification pattern at
* www.dre.vanderbilt.edu/~schmidt/PDF/specific-notification.pdf.
*/
public class SimpleSemaphore
implements ISemaphore {
/**
* Keeps track of whether "fair" or "non-fair" semantics are
* requested. Plays the role of the Implementator class in the
* Bridge pattern.
*/
private SemaphoreBase mSemaphoreBase;
/**
* @class SemaphoreBase
*
* @brief This class abstracts the behavior of the fair/nonfair
* semaphore using the bridge pattern.
*/
private abstract static class SemaphoreBase {
/**
* Define a count of the number of available permits.
*/
protected volatile int mAvailablePermits;
/**
* Initialize the mAvailablePermits data member.
*/
SemaphoreBase (int availablePermits) {
mAvailablePermits = availablePermits;
}
/**
* Return the number of available permits.
*/
protected int availablePermits() {
return mAvailablePermits;
}
/**
* Acquire one permit from the semaphore in a manner that can
* be interrupted. Must be implemented by a subclass.
*/
abstract protected void acquire() throws InterruptedException;
/**
* Return one permit to the semaphore. Must be implemented by
* a subclass.
*/
abstract protected void release();
/**
* Acquire one permit from the semaphore in a manner that
* cannot be interrupted. It a template method that calls the
* acquire() hook method.
* Impotent note! if exception occurs this thread will go to the and of the wait
* line hence it will loose fairness.
*/
protected void acquireUninterruptibly() {
// TODO -- you fill in here, using a loop to ignore
// InterruptedExceptions.
try {
acquire();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
acquireUninterruptibly();
}
}
}
/**
* Initialize the SimpleSemaphore.
* @param Initialpermits Initial number of permits assigned to the
* semaphore, which can be < 0
* @parame Fair {@code true} if this lock should use a fair
* ordering policy.
*/
public SimpleSemaphore(int initialPermits,
boolean fair) {
// TODO - you fill in here.
if (!fair) mSemaphoreBase = new NonFairSemaphore(initialPermits);
else mSemaphoreBase = new FairSemaphore(initialPermits);
}
/**
* @class NonFairSemaphore
*
* @brief Implements the non-fair Semaphore using a Java
* built-in monitor object.
*/
static final class NonFairSemaphore extends SemaphoreBase {
/**
* Initialize the superclass.
*/
NonFairSemaphore (int availablePermits) {
// TODO -- you fill in here.
super(availablePermits);
}
/**
* Acquire one permit from the semaphore in a manner that can
* be interrupted.
*/
@Override
protected synchronized void acquire() throws InterruptedException {
// TODO -- you fill in here by waiting while no permit is
// available and then decrement the number of permits by
// one.
while (mAvailablePermits<1)
try {
this.wait();
} catch (InterruptedException e) {
if (mAvailablePermits>0) notify();//allways notify after Interrupt.
throw e;
}
mAvailablePermits--;
}
/**
* Return one permit to the semaphore.
*/
@Override
protected synchronized void release() {
// TODO -- you fill in here by incrementing the number of
// permits by one and then notifying some thread waiting
// on this object.
mAvailablePermits++;
notify();//we have only one condition, so each release we only wake-up
//a single thread
}
}
/**
* @class FairSemaphore
*
* @brief Implements the fair Semaphore using a Java built-in
* monitor object and the Specific Notification pattern.
*/
private static final class FairSemaphore extends SemaphoreBase {
/**
* Keep track of the waiters in FIFO order for "fair" semantics.
*/
// TODO - you fill in here.
/**
* Initialize the superclass.
*/
final ArrayList<WaitObject> wait_list = new ArrayList<>();
FairSemaphore (int availablePermits) {
// TODO - you fill in here.
super(availablePermits);
}
/**
* Acquire one permit from the semaphore in a manner that can
* be interrupted.
*/
@Override
protected void acquire() throws InterruptedException {
// TODO -- implement "fair" semaphore acquire semantics
// using the Specific Notification pattern.
boolean should_wait = false;
final WaitObject obj= new WaitObject();
synchronized(obj){
synchronized(this){
if (mAvailablePermits>0 && wait_list.isEmpty()){
mAvailablePermits--;
}
else{
should_wait = true;
wait_list.add(obj);
}
}
//!!!In case of an exception we will loose some of the fairness!!!
while (should_wait){
try {
obj.wait();
should_wait = obj.shouldWait;//test against spurious wakeups!!
} catch (InterruptedException e) {
synchronized(this){
Object tmp = wait_list.remove(obj);
if (tmp!=null) throw e;//if tmp is null we have
// acquired the semaphore after all.
}
}
}
}
}
/**
* Return one permit to the semaphore.
*/
@Override
public void release() {
// TODO -- implement "fair" semaphore release semantics
// using the Specific Notification pattern.
synchronized(this){
mAvailablePermits++;
if (mAvailablePermits>0 && !wait_list.isEmpty()){
WaitObject obj = wait_list.remove(0);
synchronized(obj){
obj.shouldWait = false;
obj.notify();
}
mAvailablePermits--;
}
}
}
private class WaitObject{
boolean shouldWait = true;
}
}
/**
* Acquire one permit from the semaphore in a manner that can be
* interrupted. Simply forwards to the concrete implementator
* object.
*/
@Override
public void acquire() throws InterruptedException {
// TODO - you fill in here.
mSemaphoreBase.acquire();
}
/**
* Acquire one permit from the semaphore in a manner that cannot
* be interrupted. Simply forwards to the concrete implementator
* object.
*/
@Override
public void acquireUninterruptibly() {
// TODO - you fill in here.
mSemaphoreBase.acquireUninterruptibly();
}
/**
* Return one permit to the semaphore. Simply forwards to the
* concrete implementator object.
*/
@Override
public void release() {
// TODO - you fill in here.
mSemaphoreBase.release();
}
/**
* Return the number of permits available. Simply forwards to the
* concrete implementator object.
*/
@Override
public int availablePermits() {
// TODO - you fill in here.
return mSemaphoreBase.availablePermits();
}
}
