2
\$\begingroup\$

I'm tutor for a university operating systems course, and part of my work is creating exercises for them. Those exercises are mostly about concurrency and synchronization issues. For the next exercise I intend to show them the finished implementation of an unfair counting semaphore, and their job is to make a fair one. Because of a lot of factors I'm constrained to using Java as implementation language.

Though I'm fully capable of writing Java programs, it's not exactly my "mother tongue". As such, I'm probably unaware of some idioms and best practices.

As I want to give my students not just something that "works", but code that could actually be found in a production system, I hope you can give me suggestions for my implementation:

/** Simple, unfair counting semaphore.

    This class implements a simple and unfair counting semaphore.
*/
public class UnfairSemaphore implements Semaphore {
    /** Count of available permits.
     */
    protected int count;

    /** Object used to communicate with waiting threads.

        A distinct object is used herefore (and not the semaphore itself)
        to keep any signals from notify() behind the abstraction.
     */
    protected Object wire = new Object();

    /** Construct a semaphore with the given initial count.

        Sets the initial count of the newly constructed semaphore to the
        given value, which may be negative.
    */
    public UnfairSemaphore(int initial) {
        count = initial;
    }

    /** Construct a semaphore with 1 initial permit.
     */
    public UnfairSemaphore() {
        this(1);
    }

    // Implementation
    public void acquire() throws InterruptedException {
        synchronized (wire) {
            while (count <= 0) {
                wire.wait();
            }
            --count;
        }
    }

    // Implementation
    public void release() {
        synchronized (wire) {
            ++count;
            if (count > 0) {
                wire.notifyAll();
            }
        }
    }
}

Semaphore is an interface with just the two methods acquire and release.

I'm using the member wire to synchronize on and to call notifyAll and wait in order to keep the signals resulting from these "behind the abstraction", that is to make them invisible to the code using the semaphore. (I could use just notify here, couldn't I?)

I'm neither interested in making this code faster or to use different, possibly better classes (Atomic* or whatever) to implement this.

What I do want is code that correctly handles all cases. (I just don't want to give them "educational code" which shows the idea, but fails to reliably work in practice)

\$\endgroup\$
7
  • \$\begingroup\$ As I want to give my students ... code that could actually be found in a production system and I'm neither interested in making this ... use different, possibly better classes (AtomicXXX or whatever) to implement this. - These are opposing requests because production code would not take the approach you are taking as a first or even second best choice. In pretty much every case, there are more production worthy ways to write idiomatic concurrent code in Java that is production worthy. \$\endgroup\$
    – user4619
    Dec 11, 2015 at 10:40
  • \$\begingroup\$ Hm, I see. Though I'm limited to using synchronized and wait/notify, as these have been explained to students. That means I'm looking for production quality in a hypothetically setting, which is kind of a difficult quest. \$\endgroup\$ Dec 11, 2015 at 21:20
  • 1
    \$\begingroup\$ In theory there is no difference between theory and practice, in practice there is \$\endgroup\$
    – user4619
    Dec 11, 2015 at 22:13
  • \$\begingroup\$ java.util.concurrent exists for a reason and that is what employers want to see people have experience in. As someone who interviewed hundreds of Java devs for a multimillion dollar company in just a few months. Anything else is a disservice to them. \$\endgroup\$
    – user4619
    Dec 11, 2015 at 22:17
  • \$\begingroup\$ I fully agree with you, but I'd guess unfortunately about 80% of my students are lacking even more fundamental programming skills (some of them just started programming a year ago, using IMO questionable, outdated and in some parts just wrong resources). None of those 80% would have (currently) any chance in an interview for a Java developer position. \$\endgroup\$ Dec 11, 2015 at 23:25

1 Answer 1

2
\$\begingroup\$

I don't like using the object as a mutex and Condition variable. Doing that would let another programmer spin up a thread to lock and never release the Semaphore.

Instead you should either provide a private Object lock = new Object(); and sync on that or use the java.util.concurrent.locks.ReentrantLock and its condition:

private final Lock mutex = new ReentrantLock();
private final Condition condition = mutex.newCondition();

public void acquire() throws InterruptedException {
    mutex.lockInterruptibly();//let interrupt throw as soon as possible
    try{
        while (count <= 0) {
            condition.await();
        }
        --count;
    } finally {
        mutex.unlock();
    }
}

// Implementation
public void release() {
    mutex.lock();
    try{
        ++count;
        if (count > 0) {
            condition.signal();
        }
    } finally {
        mutex.unlock();
    }
}

This makes it easy to change the semaphore to a fair one by passing true to the constructor.

Though I expect you will want to implement the wait queue yourself as an example.

If you want to go a step lower and no use the pre-implemented locks can instead use LockSupport which lets to park the current thread and unpark it from another thread safely.

\$\endgroup\$
4
  • \$\begingroup\$ "you will want to implement the wait queue yourself as an example" Exactly, that's the idea behind the exercise. That LockSupport link is pretty awesome, I'm possibly using this next term to get away from the current hypothetical situation of only having synchronized and wait/notify at hand. What do you mean with using a private Object lock = ... ? Would that be any different from the code I'm currently having? Apart from not being idiomatic in the sense that one better uses the Lock/Condition classes, do you see any issues with my code? \$\endgroup\$ Dec 11, 2015 at 21:24
  • \$\begingroup\$ Because your current code let random code grab a reference to your semaphore and synchronize on it and deny any other thread from being able to do any operation. \$\endgroup\$ Dec 11, 2015 at 21:31
  • \$\begingroup\$ Hm, I still don't get what you mean. Could you elaborate with a small example? \$\endgroup\$ Dec 11, 2015 at 23:51
  • \$\begingroup\$ spawn a new thread with synchronized(semaphore)Thread.sleep(Long.MAX_VALUE); and no one can access it anymore. Not something you want to allow in a production library. \$\endgroup\$ Dec 12, 2015 at 0:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.