Semaphore

Does Java support the semaphore mechanism?

Q: Java uses the synchronized keyword and java.lang.Object 's wait() and notify() methods as synchronization mechanisms. Are there any other mechanisms, like semaphores, built in to Java?

A: The only synchronization primitives built in to Java are monitors and wait sets, which many programmers have never heard of because Java hides them behind synchronized, wait(), and notify(). Fortunately, Java allows you to implement all the familiar synchronization schemes on top of monitors and wait sets. At the end of this answer, we'll look at how to implement our own Semaphore class.

Before we get into that, though, let's go over a little bit of the theory behind it. Every multithreaded programming language needs to have some way for the threads to keep in synch. Take, for example, a program with a thread that produces objects and a thread that consumes them, as seen in the following code snippet:

    Object data = null;
    public void push(Object d) {
        data = d;
    }
    public Object pop() {
        Object d = data;
        data = null;
        return d;
    }
    class Producer implements Runnable {
        public void run() {
            while (true) {
                Object o = createNewObject();
                push(o);
            }
        }
    }
    class Consumer implements Runnable {
        public void run() {
            while (true) {
                Object o = pop();
                doSomethingWith(o);
            }
        }
    }
    public static void main(String args[]) {
        (new Thread(new Producer())).start();
        (new Thread(new Consumer())).start();
    }

The problem with these naive Producer and Consumer classes is that they have no way of cooperating with each other. If one thread is faster than the other, it should occasionally wait for the slower thread to catch up. We can change the push() and pop() methods to take turns, so that one thread will not outstrip the other:

    public void push(Object d) {
        while (data != null) { /* Empty while--eats CPU. */ }
        data = d;
    }
    public Object pop() {
        while (data == null) { /* Empty. */ }
        Object d = data;
        data = null;           /* Allow push() to break out of its loop.
*/
        return d;
    }

When one thread runs push() and another thread runs pop(), they keep in sync by means of the data field. push() waits for pop() by constantly checking the data field. When data becomes null, push() can assign a new object to it. pop() uses the same technique, sitting in a tight loop, waiting for data to change. When data becomes nonnull, pop() should return it and set it back to null.

That technique is called busy waiting, and it has a number of problems. One of the most serious drawbacks is that it can consume all the available CPU cycles. If the consume() thread has an equal or higher priority than the produce() thread, consume()'s busy waiting can even prevent produce() from running!

Java obviates the need for busy waiting with monitors and wait sets. A monitor is a data structure that can hold only one thread at a time. If a thread tries to enter a monitor that already holds a thread, the second thread will block until the first leaves the monitor. Every object has a monitor: a thread enters it by calling a synchronized method on that object or by entering a block of code that is synchronized on it. Every Java object also has a wait set -- a set of threads that sleep until another thread tells the object to wake one of them up. A thread enters an object's wait set by calling wait() on that object. It can leave the wait set when another thread calls the object's notify() method.

Here are implementations of push() and pop() that use monitors and wait sets:

    Object full  = new Object();
    Object empty = new Object();
    public void push(Object d) {
        synchronized(full) {
            if (data != null) full.wait();
        }
        data = d;
        synchronized(empty) {
            if (data != null) empty.notify();
        }
    }
    public Object pop() {
        synchronized(empty) {
            if (data == null) empty.wait();
        }
        Object o = data;
        data = null;
        synchronized(full) {
            if (data == null) full.notify();
        }
        return o;
    }

If data is not null, push() waits until pop() notifies it that data is no longer full. push() then assigns its parameter to data and notifies pop() that data is no longer empty. This solution is much more CPU-efficient than busy waiting. It is also easy to extend so that it handles multiple producers and consumers instead of just one of each: just declare push() and pop() to be synchronized!

Java's monitors and wait sets are versatile enough to solve any synchronization problem but safe enough to keep most programmers out of trouble. For those who like to live dangerously, though, here is the promised Java implementation of Semaphore:

/**
 * Semaphore is a straightforward implementation of the well-known
 * synchronization primitive. Its counter can be initialized to any
 * nonnegative value -- by default, it is zero.
 */
package com.randomwalk.library.sync;
public class Semaphore {
    private int counter;
    public Semaphore() {
        this(0);
    }
    public Semaphore(int i) {
        if (i < 0) throw new IllegalArgumentException(i + " < 0");
        counter = i;
    }
    /**
     * Increments internal counter, possibly awakening a thread
     * wait()ing in acquire().
     */
    public synchronized void release() {
        if (counter == 0) {
            this.notify();
        }
        counter++;
    }
    /**
     * Decrements internal counter, blocking if the counter is already
     * zero.
     *
     * @exception InterruptedException passed from this.wait().
     */
    public synchronized void acquire() throws InterruptedException {
        while (counter == 0) {
            this.wait();
        }
        counter--;
    }
}
Random Walk Computing is the largest Java/CORBA consulting boutique in New York, focusing on solutions for the financial enterprise. Known for their leading-edge Java expertise, Random Walk consultants publish and speak about Java in some of the most respected forums in the world.
Join the discussion
Be the first to comment on this article. Our Commenting Policies
See more