A simple semaphore in Java

Question

It is a simple semaphore in Java. Although it passes all their tests with flying colors, I'm still not sure it's correct.

For example, the last thing I wasn't sure about was mLock.lockInterruptibly(); vs mLock.lock(); in the method called aquire(). And I ended up using lockInterruptibly() because if the thread calling lockInterruptibly() is interrupted, then InterruptedException is thrown.

package edu.vuum.mocca;

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;

/**
 * @class SimpleSemaphore
 * 
 * @brief This class provides a simple counting semaphore
 *        implementation using Java a ReentrantLock and a
 *        ConditionObject (which is accessed via a Condition). It must
 *        implement both "Fair" and "NonFair" semaphore semantics,
 *        just liked Java Semaphores.
 */
public class SimpleSemaphore {
    /**
     * Define a ReentrantLock to protect the critical section.
     */
    // TODO - you fill in here
    ReentrantLock mLock;

    /**
     * Define a Condition that waits while the number of permits is 0.
     */
    // TODO - you fill in here
    Condition mCondition;

    /**
     * Define a count of the number of available permits.
     */
    // TODO - you fill in here.  Make sure that this data member will
    // ensure its values aren't cached by multiple Threads..
    volatile int mAvailable;

    public SimpleSemaphore(int permits, boolean fair) {
        // TODO - you fill in here to initialize the SimpleSemaphore,
        // making sure to allow both fair and non-fair Semaphore
        // semantics.
        mAvailable = permits;
        mLock = new ReentrantLock(fair);
        mCondition = mLock.newCondition();
    }

    /**
     * Acquire one permit from the semaphore in a manner that can be
     * interrupted.
     */
    public void acquire() throws InterruptedException {
        // TODO - you fill in here.
        try {
            mLock.lockInterruptibly();
            while (mAvailable == 0) {
                mCondition.await();
            }
            mAvailable--;
            mCondition.signalAll();
        } finally {
            mLock.unlock();
        }
    }

    /**
     * Acquire one permit from the semaphore in a manner that cannot be
     * interrupted.
     */
    public void acquireUninterruptibly() {
        // TODO - you fill in here.
        try {
            mLock.lock();
            while (mAvailable == 0) {
                mCondition.awaitUninterruptibly();
            }
            mAvailable--;
            mCondition.signalAll();
        } finally {
            mLock.unlock();
        }
    }

    /**
     * Return one permit to the semaphore.
     */
    void release() {
        // TODO - you fill in here.
        try {
            mLock.lock();
            mAvailable++;
            mCondition.signalAll();
        } finally {
            mLock.unlock();
        }
    }

    /**
     * Return the number of permits available.
     */
    public int availablePermits() {
        // TODO - you fill in here by changing null to the appropriate
        // return value.
        return mAvailable;
    }
}

Answer 1

You should put the lock statements before the try{}finally.

For example if the thread is interrupted before your interruptible acquire then lockInterruptibly will throw and the finally will try to unlock a non-locked lock (which will throw a IllegalMonitorStateException).

There is no need for the signalAll in the acquire methods, as nothing happens that may require a waiting thread to awake (all that were waiting will still need to wait).

Similarly you only need a signal() call in the release to signal a single waiting thread to awake.

Only the first issue is a true bug the other 2 are performance issues (and invalidate the fairness)

Answer 2

There are a number of issues I see here related to the implementation.

try -> lock vs. lock -> try

ratchet freak has already pointed out that the lock.lock() should be outside the try:

mLock.lock();
try {
    .... do work here ....
} finally {
    mLock.unlock();
}

This needs to be said multiple times, so I am saying it again.

TODO

All those TODO items.... do they still need to be done?

When I see TODO's in the code I 'worry'. Either it means the code is not done yet, or it means you do not pay attention to details. The fact that you have TODO in your code probably means you use eclipse (or Netbeans, IntelliJ, whatever...), and those TODO's will all create flags in the margins of your program. Don't those flags irritate you? Multithreaded programming is 90% discipline. You have to follow the rules, and you have to be concerned about the details. All those TODOs are details you should not be missing.

Visibility

Your mLock and your mCondition are not private, and they are not final. They should be.

Right now, some other class in your package can access them, lock on them, trigger conditions, even replace them, and it will royally f*** up your program.

mAvailable should be private too.

The whole class should also probably be final.

Volatile

Your mAvailable is volatile. I think you think this is needed to keep the value consistent on all threads.

In this case, volatile is redundant. The lock is what keeps the memory model consistent, and it is why you are using locks. The volatile just makes additional overhead for Java to work around. Remove the volatile. Locking, unlocking, synchronization, and accessing a volatile member all create what is called a 'happens before' event in the Java memory model. Everything in the JVM that 'happened before' the event is guaranteed to be visible to your code. So, if you also lock your access to the mAvailable then any thread that ran before your lock 'happened before', and any thread that tries to run during your lock has to wait for you to complete, and when that thread acquires the lock, your thread 'happened before' that thread, so your memory model is copied to that thread's model.

In general, if you are using volatile, and you don't understand what I said above, then you are likely doing something wrong.

Signals

ratchetfreak has already pointed out the unnecessary signalAll's in the acquire methods. I am going to extend his comments in three ways:

1. You should never have an await and a signal in the same locked block of code. It means you are doing something wrong.
2. you should not be calling signalAll, but just plain signal. There is no need to wake up every waiting thread when only one of them will be able to acquire the lock. The whole point of the fair lock system is that it will signal the fair one first. Once that fair one has awoken, it gets the semaphore. If you wake them all, then only one thread gets the semaphore, and they all re-lock and re-await, and the 'fairness' order may change.

3. mCondition should not be called mCondition. The whole point of conditions is that you can name them something that documents what they do. Consider the name released, then your code reads like:

   public void acquire() throws InterruptedException {
       mLock.lockInterruptibly();
       try {
           while (mAvailable == 0) {
               released.await();
           }
           mAvailable--;
       } finally {
           mLock.unlock();
       }
   }
   
   void release() {
       mLock.lock();
       try {
           if (mAvailable++ == 0) {
               // only release one thread, (the fair one),
               // and no point in signalling things if nothing can be waiting
               released.signal();
           }
       } finally {
           mLock.unlock();
       }
   }
   

Uninterruptibly

My preference is to wrap interruptible calls with the uninteruptible caller. You have implemented the calls two ways, and that duplicates a lot of logic. Consider this instead:

public void acquire() throws InterruptedException {
    mLock.lockInterruptibly();
    try {
        while (mAvailable == 0) {
            released.await();
        }
        mAvailable--;
    } finally {
        mLock.unlock();
    }
}

public void acquireUninterruptibly() {
    boolean interrupted = false;
    try {
        while (true) {
            try {
                acquire();
                return;
            } catch (InterruptedException ie) {
                // propogate the state, but do not throw the exception
                interrupted = true;
            }
        }
    } finally {
        if (interrupted) {
            // mark the fact that an interrupt happened, but we will
            // not throw an exception.
            Thread.currentThread().interrupt();
        }
    }