|
Java Q&A
Semaphore
Does Java support the semaphore mechanism?
By Java Q&A Experts
Printer-friendly version |  Mail this to a friend
 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?
 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--;
}
}
Printer-friendly version | Mail this to a friend
About the author
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.
|
