2

I can see how a "standard" Semaphore Class can be implemented in Java. However, I cant see how to implement a Binary Semaphore Class in Java. How does such implementation work? When should I call the wake and notify methods to wake and stop the threads that are on the semaphores? I understand what binary semaphores are, but I have no idea of how to code them.

Edit Note: Realize that I said "BINARY" Semaphore class. The standard Semaphore class I already did and I know its correct so the standard Semaphore Class does not interest me.

2
  • Have you tried something; drawing on the source code of existing semaphore class, of how it would behave if it were to just have a permit of 1. Commented Nov 27, 2011 at 15:22
  • Have you read (e.g. on wikipedia) the definition of (binary) semaphore? Can you explain why the given answers (especially those of Vikas or the more extensive one of Alexander) are not sufficient? Otherwise you could try and explain the use case (for what purpose do you need the binary semaphore/mutex?) Commented Nov 29, 2011 at 23:45

8 Answers 8

4

I think you're talking about mutex (or mutual exclusion locks). If so, you can use intrinsic locks. This kind of locks in Java act as mutexes, which means that at most one thread may own the lock:

synchronized (lock) { 
    // Access or modify shared state guarded by lock 
}

Where lock is a mock object, used only for locking.


EDIT:

Here is an implementation for you — non-reentrant mutual exclusion lock class that uses the value zero to represent the unlocked state, and one to represent the locked state.

class Mutex implements Lock, java.io.Serializable {

    // Our internal helper class
    private static class Sync extends AbstractQueuedSynchronizer {
      // Report whether in locked state
      protected boolean isHeldExclusively() {
        return getState() == 1;
      }

      // Acquire the lock if state is zero
      public boolean tryAcquire(int acquires) {
        assert acquires == 1; // Otherwise unused
        if (compareAndSetState(0, 1)) {
          setExclusiveOwnerThread(Thread.currentThread());
          return true;
        }
        return false;
      }

      // Release the lock by setting state to zero
      protected boolean tryRelease(int releases) {
        assert releases == 1; // Otherwise unused
        if (getState() == 0) throw new IllegalMonitorStateException();
        setExclusiveOwnerThread(null);
        setState(0);
        return true;
      }

      // Provide a Condition
      Condition newCondition() { return new ConditionObject(); }

      // Deserialize properly
      private void readObject(ObjectInputStream s)
          throws IOException, ClassNotFoundException {
        s.defaultReadObject();
        setState(0); // reset to unlocked state
      }
    }

    // The sync object does all the hard work. We just forward to it.
    private final Sync sync = new Sync();

    public void lock()                { sync.acquire(1); }
    public boolean tryLock()          { return sync.tryAcquire(1); }
    public void unlock()              { sync.release(1); }
    public Condition newCondition()   { return sync.newCondition(); }
    public boolean isLocked()         { return sync.isHeldExclusively(); }
    public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); }
    public void lockInterruptibly() throws InterruptedException {
      sync.acquireInterruptibly(1);
    }
    public boolean tryLock(long timeout, TimeUnit unit)
        throws InterruptedException {
      return sync.tryAcquireNanos(1, unit.toNanos(timeout));
    }
  }

If you need to know where should you call wait() and notify(), have a look at sun.misc.Unsafe#park(). It is used within java.util.concurrent.locks package (AbstractQueuedSynchronizer <- LockSupport <- Unsafe).

Hope this helps.

Sign up to request clarification or add additional context in comments.

2 Comments

What you are saying is what I should put in the Binary Semaphore Class. I already Know that I should do that at some point, but I dont know where should I call the notify and wait calls.
You don't need to dig into such a level of detail (but if you want, have a look at sun.misc.Unsafe class, as I mentioned in the post). You can achieve your goal with derived convenience implementations.
4

Here is a simple implementation I did for a binary semaphore:

public class BinarySemaphore {

    private final Semaphore countingSemaphore;

    public BinarySemaphore(boolean available) {
        if (available) {
            countingSemaphore = new Semaphore(1, true);
        } else {
            countingSemaphore = new Semaphore(0, true);
        }
    }

    public void acquire() throws InterruptedException {
        countingSemaphore.acquire();
    }

    public synchronized void release() {
        if (countingSemaphore.availablePermits() != 1) {
            countingSemaphore.release();
        }
    }
}

This implementation has one property of binary semaphores that you cannot get with counting semaphores that only have one permit - multiple calls to release will still leave just one resource available. This property is mentioned here.

2 Comments

This isn't safe - only release() is synchronized, so if acquire runs concurrently to release, after your if(countingSemaphore.availablePermits() != 1), and before where you call release, you could end up with unexpected behaviour. Also, making acquire synchronzied would not work either as the lock is then locked stopping you releasing the binary semaphore, halting the application.
@SamHeather i'm just thinking about what you said, if the non-synchronized method acquire starts just like you said after the != 1 check, there would be no slot available and the inner acquire-call would stop and the thread would wait, context-switch, the other releasing thread could continue with the call of countingSemaphore.release(); Just thinking, if this would be a problem anyway? I think all the possible requesting threads would get stuck at the inner countingSemaphore.acquire();-call. Don't you think so? Sychronizing the release()-method simply avoids too much free slots..
3

Yes, you can. A semaphore with a single permit is a binary semaphore. They control access to a single resource. They can be viewed as some kind of a mutex/lock.

Semaphore binarySemaphore = new Semaphore(1);

4 Comments

It doesnt help, I need a binary semaphore class, not the standard one.
If it just has one permit, it IS a binary semaphore. Your comment is like saying "this car does not fit: it can go up to 180 km/h, and I need to go at 90 km/h.
You can extend the standard semaphore and create your own binary semaphore class as below. public class BinarySemaphore extends Semaphore{ BinarySemaphore (){ super(1); } }
@JBNizet Setting the number of permits to one in a counting semaphore does not automatically produce a binary semaphore because by invoking release() multiple times, a thread could still increase the number of available permits to a value greater than one.
2

Here is straight from the Java site

The concurrency utility library, led by Doug Lea in JSR-166, is a special release of the popular concurrency package into the J2SE 5.0 platform. It provides powerful, high-level thread constructs, including executors, which are a thread task framework, thread safe queues, Timers, locks (including atomic ones), and other synchronization primitives.

One such lock is the well known semaphore. A semaphore can be used in the same way that wait is used now, to restrict access to a block of code. Semaphores are more flexible and can also allow a number of concurrent threads access, as well as allow you to test a lock before acquiring it. The following example uses just one semaphore, also known as a binary semaphore. See the java.util.concurrent package for more information.

final  private Semaphore s= new Semaphore(1, true);

    s.acquireUninterruptibly(); //for non-blocking version use s.acquire()

try {     
   balance=balance+10; //protected value
} finally {
  s.release(); //return semaphore token
}

I think, the whole reason of using higher-level abstracts such as Semaphore class is that you don't have to call low level wait/notify.

Comments

1

I have my own implementation of a Binary Semaphore in Java.

import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;

/**
 * A binary semaphore extending from the Java implementation {@link Semaphore}.
 * <p>
 * This semaphore acts similar to a mutex where only one permit is acquirable. Attempts to acquire or release more than one permit
 * are forbidden.
 * <p>
 * Has in {@link Semaphore}, there is no requirement that a thread that releases a permit must have acquired that permit. However,
 * no matter how many times a permit is released, only one permit can be acquired at a time. It is advised that the program flow
 * is such that the thread making the acquiring is the same thread making the release, otherwise you may end up having threads
 * constantly releasing this semaphore, thus rendering it ineffective.
 * 
 * @author Pedro Domingues
 */
public final class BinarySemaphore extends Semaphore {

    private static final long serialVersionUID = -927596707339500451L;

    private final Object lock = new Object();

    /**
     * Creates a {@code Semaphore} with the given number of permits between 0 and 1, and the given fairness setting.
     *
     * @param startReleased
     *            <code>true</code> if this semaphore starts with 1 permit or <code>false</code> to start with 0 permits.
     * @param fairMode
     *            {@code true} if this semaphore will guarantee first-in first-out granting of permits under contention, else
     *            {@code false}
     */
    public BinarySemaphore(boolean startReleased, boolean fairMode) {
        super((startReleased ? 1 : 0), fairMode);
    }

    @Override
    public void acquire(int permits) throws InterruptedException {
        if (permits > 1)
            throw new UnsupportedOperationException("Cannot acquire more than one permit!");
        else
            super.acquire(permits);
    }

    @Override
    public void acquireUninterruptibly(int permits) {
        if (permits > 1)
            throw new UnsupportedOperationException("Cannot acquire more than one permit!");
        else
            super.acquireUninterruptibly(permits);
    }

    @Override
    public void release() {
        synchronized (lock) {
            if (this.availablePermits() == 0)
                super.release();
        }
    }

    @Override
    public void release(int permits) {
        if (permits > 1)
            throw new UnsupportedOperationException("Cannot release more than one permit!");
        else
            this.release();
    }

    @Override
    public boolean tryAcquire(int permits) {
        if (permits > 1)
            throw new UnsupportedOperationException("Cannot acquire more than one permit!");
        else
            return super.tryAcquire(permits);
    }

    @Override
    public boolean tryAcquire(int permits, long timeout, TimeUnit unit) throws InterruptedException {
        if (permits > 1)
            throw new UnsupportedOperationException("Cannot release more than one permit!");
        else
            return super.tryAcquire(permits, timeout, unit);
    }
}

Tell me if you find any bug in the code please, but so far it always worked fine! :)

Comments

1

I would rather use the Lock class

Besides the naming matching, Java Semaphore is no way to implement a BinarySemaphore, and using Object wait/notify or synchronize is quite raw.

Instead, the Lock class provides almost the same locking semantics as a Semaphore with its lock/unlock (versus acquire/release by Semaphore), but it is specifically targeted to solve critical section functionality, where just one thread is expected to enter at once.

Worth noting Lock also provide try with timeout semantics thanks to tryLock method.

Comments

1

Maybe it's a good idea to use AtomicBoolean implement it. If it's not, please let me know.

import java.util.concurrent.atomic.AtomicBoolean;

public class BinarySemaphore {
    
    private final AtomicBoolean permit;
    
    public BinarySemaphore() {
        this(true);
    }
    
    /**
     * Creates a binary semaphore with a specified initial state
     */
    public BinarySemaphore(boolean permit) {
        this.permit = new AtomicBoolean(permit);
    }

    public void acquire() {
        boolean prev;
        do {
            prev = tryAcquire();
        } while (!prev);
    }

    public boolean tryAcquire() {
        return permit.compareAndSet(true, false);
    }

    /**
     * In any case, the permit was released
     */
    public void release() {
        permit.set(true);
    }

    public boolean available(){
        return permit.get();
    }
}

Comments

0

You could have a look at the source code for the Java implementation of the Semaphore class (or perhaps use it directly?)

1 Comment

I need the binary semaphore not that one.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.