2
\$\begingroup\$

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();
    }
}
\$\endgroup\$
  • \$\begingroup\$ The unfair part is easy, I would like to know if you can see any bugs in the fair part, it was an academic assignment in some course(not mine, so I cannot ask for help), there are some uni-tests supplied, all were past 100%, but they are clearly not good enough to test all cases. \$\endgroup\$ – user3580937 Mar 28 '16 at 21:00
1
\$\begingroup\$

When a thread is interrupted it needs no regenerate the notification, so other threads are able to proceed on the waiting condition. This means that for example your acquire should be written like this:

protected synchronized void acquire() throws InterruptedException {
    try{
        while (mAvailablePermits < 1){
            this.wait();
        }

        mAvailablePermits--;
    }catch(InterruptedException e){
        this.notify();
        throw e;
    }
}

On Java there exists the Lock and the Condition classes when you need multiple conditions to lock on. I suggest you to use those instead of creating objects, and lock on them, to simulate this behaviour. The reason being that are plenty of problems that I am not able to explain, I only know that they exist (sorry for this).

I also think that you were trying to maintain a reasonable indentation on your implementation and that's why you introduced should_wait variable. The same effect could be achieved by returning on the first if making the code a little bit cleaner.

Talking about should_wait you should follow Java conditions and rename it to shouldWait. The same goes for other variables.

It also seems that you forgot the while to wait on the condition this time and to decrement the number of permits. As I will explain later, there is no need to check tmp for null, on the catch block, because the object will always be on the list. However you may still want to check for the scenario, where the thread is interrupted but there are conditions to proceed normally.

Again do not forget to regenerate the notification

//...
synchronized(obj){
    synchronized(this){
        if (mAvailablePermits>0 && wait_list.isEmpty()){
            mAvailablePermits--;
            return;
        }

        wait_list.add(obj);
        try {
            while(mAvailablePermits == 0 || wait_list.get(0) != condition){
                obj.wait();
            }
            --mAvailablePermits;
        } catch (InterruptedException e) {
            synchronized(this){  
                wait_list.remove(condition);
                if(wait_list.get(0) == condition && mAvailablePermits > 0){
                    //I am the first thread on the list and there are conditions to proceed
                    --mAvailablePermits;
                    return;
                }
                //regenerate notification
                wait_list.get(0).signal();
                throw e;
            }
        } 
    }
//...  

So let's now recode your acquire using Lock and Condition:

protected void acquire() throws InterruptedException {
    try{
        lock.lock();
        if (mAvailablePermits>0 && wait_list.isEmpty()){
            mAvailablePermits--;
            return;
        }
        Condition condition = lock.newCondition();
        wait_list.add(condition);
        try{
            while(mAvailablePermits == 0 || wait_list.get(0) != condition){
                condition.await();
            }
            --mAvailablePermits;
            wait_list.remove(condition);
            if(wait_list.size() > 0 && mAvailablePermits > 0){
               //A thread released units in bulk, we need notify at least the next thread in the list
               wait_list.get(0).signal();
            }
        }catch(InterruptedException e){
            if(wait_list.get(0) == condition && mAvailablePermits > 0){
                //I am the first thread on the list and there are conditions to proceed
                --mAvailablePermits;
                return;
            }
            wait_list.remove(condition);  
            //regenerate the notification
            if(wait_list.size() > 0){
                wait_list.get(0).signal();
            }
            throw e;
        }
    }finally{
        lock.unlock();
    }
}

I do not know why your release decrements the number of permits, it should only increment and notify.

acquire Should be responsible for both adding and removing the condition from the list. If the release removes the condition from the list, the condition is no longer on the list and there is no way to know if the current thread is the first or not.

Here is the corrected version with Lock and Condition.

public  void release() {
    try{
        lock.lock();
        mAvailablePermits++;
        if(!wait_list.isEmpty()){
            wait_list.get(0).signal();
        }
    }finally{
        lock.unlock();
    }
}

Addressing comments.

My previous statement:

The reason being that are plenty of problems that I am not able to explain, I only know that they exist (sorry for this).

There are a couple of things that I know:

Specific notifications is not the only reason for why you need Conditions. For instance, for monitors to work, the wait and release must be done on the same object that is being locked on. When you have multiple conditions like you have in your FairSemaphore behind the scenes two objects are being locked, the Lock and the Condition. (I do not know if this statement is true for Java but I know it is true for C#). And there is a lot of trouble when you are trying to lock on multiple conditions like you are here (and this is the trouble that I am not able to explain).

I do not know why your release decrements the number of permits, it should only increment" - this is called " the Specific Notification pattern" - if you inc, and release, new thread can then acquire the semaphore, without waiting.

You are doing specific notifications because you have an object(which represents a thread), and you always notify only the correct thread. That is a specific notification, and you were using it mostly correctly.

Decrementing mAvailablePermits does not have anything to do with specific notification and does not grant any kind of gain on the acquire.

If those words are not enough let's state a scenario were your old implementation would fail:

  • Thread A acquires
  • Thread B releases and mAvailablePermits remains 0 because it increments and decrements
  • Thread A evaluates mAvailablePermits (you forgot to verify this in the while like I mentioned), it verifies it is 0 and will be blocked.

The same goes if you remove the object from the list on release. When thread A wakes up it will evaluate the condition and it won't be able to tell if it is the first from the list (because it was removed).


When a thread is interrupted it needs no regenerate the notification, so other threads are able to proceed on the waiting condition.

Again let's describe a scenario to explain this better.

  • Thread A acquires
  • Thread B acquires
  • Thread C releases the notification goes to thread A.
  • Thread A is interrupted
  • Thread B has conditions to proceed but notification was not regenerated and therefore it can't proceed.

If Thread A regenerated the notification thread B would be able to proceed.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I know about locks, and conditions, the ass was about java monitors. " The reason being that are plenty of problems that I am not able to explain, I only know that they exist (sorry for this)." well that is easy, it is simply not possible without locks and conditions to wait for two different events without waking up everybody, witch is not efficient. "I do not know why your release decrements the number of permits, it should only increment" - this is called " the Specific Notification pattern" - if you inc, and release, new thread can then acquire the semaphore, without waiting. \$\endgroup\$ – user3580937 Mar 31 '16 at 14:00
  • \$\begingroup\$ "When a thread is interrupted and is in a waiting state it needs no regenerate the notification, so other threads are able to proceed on the waiting condition. " I am sorry, could you explain this point, maybe in other words? here is link about the cpecific-notification. www.dre.vanderbilt.edu/~schmidt/PDF/specific-notification.pdf \$\endgroup\$ – user3580937 Mar 31 '16 at 14:04
  • \$\begingroup\$ " because the object will always be on the list" - lets say thread A wants to notify thread B, so A locks this, and removes As Object from the list. then A needs to lock on As Object, mean while A could be interrupted.(small windows, bat it is exists). then A notifies B(witch at this point could be interrupted), this is why I check if !=null... I hope now you see my logic :) \$\endgroup\$ – user3580937 Mar 31 '16 at 14:21
  • \$\begingroup\$ @user3580937 I hope the edit addresses your questions \$\endgroup\$ – Bruno Costa Mar 31 '16 at 15:02
  • \$\begingroup\$ I see the problem now - but the fix only needed in the not fair semaphore. lets take a look at your examples Thread A acquires Thread B releases and mAvailablePermits remains 0 because it increments and decrements (yes - and he wakes-up A) Thread A evaluates mAvailablePermits (you forgot to verify this in the while like I mentioned), it verifies it is 0 and will be blocked. - i did not forget... this is the point :) if you wake up - you are good to go... if you get exception.. comes the !null test... \$\endgroup\$ – user3580937 Mar 31 '16 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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