| |
Java Tech: The ABCs of Synchronization, Part 2Last time, I began a two-part series that focuses on synchronization in a Java context. I introduced you to the monitor and lock synchronization concepts, for guarding critical sections of code from simultaneous execution by multiple threads. I then revealed Java's synchronized method and synchronized statement implementations of monitors and locks. Finally, I explained deadlock.
An exploration of Java's synchronization ABCs is not complete without coverage of thread communication, volatile variables, and synchronizer tools. This month, you'll learn how Java's waiting and notification mechanism supports thread communication, and explore a classic example of two threads communicating. You'll then discover volatile variables and find out how they are related to synchronization. Finally, you'll tour J2SE 5.0's high-level synchronizer tools.
Note: As with the previous article, this article assumes that you have a basic
understanding of threads and the java.lang.Thread class. It also
assumes you understand what is meant by multiple threads simultaneously
executing code. (Refer to the Note near the beginning of last month's article,
if you aren't sure.)
Synchronized methods and synchronized statements make it possible for threads to avoid conflicts while sharing a common resource (e.g., two threads sending data packets over a single network connection). But when coupled with Java's waiting and notification mechanism, synchronized methods and/or synchronized statements also allow threads to actively communicate, to cooperate on common goals.
The waiting and notification mechanism supports communication between threads,
as follows: a thread voluntarily waits until some condition (a
prerequisite for continued execution) occurs. At that time, another thread
notifies the waiting thread, to continue its execution. That communication is
made possible by five methods implemented in the Object class:
public final void notify() wakes up an arbitrary thread that is
waiting to enter the monitor associated with the current object. The thread
cannot proceed until the thread within the monitor exits and releases its
lock. The woken thread competes with any other threads that are competing to
obtain the monitor's lock.
public final void notifyAll() wakes up all threads that are
waiting to enter the monitor associated with the current object. The threads
cannot proceed until the thread within the monitor exits and releases its
lock. The woken threads compete with any other threads that are competing to
obtain the monitor's lock.
public final void wait() throws InterruptedException causes the
invoking thread to wait (and give up its lock) until another thread invokes a
notification method that wakes up the thread (which grabs the lock). This
method throws an InterruptedException object if another thread
previously set the thread's interrupted status.
public final void wait(long timeout) throws InterruptedException
causes the invoking thread to wait (and give up its lock) until another thread
calls a notification method that wakes up the thread (which grabs the lock),
or the invoking thread has waited for timeout milliseconds. This
method throws an InterruptedException object if another thread
previously set the thread's interrupted status.
public final void wait(long timeout, int nanos) throws
InterruptedException causes the invoking thread to wait (and give up
its lock) until another thread calls a notification method that wakes up the
thread (which grabs the lock), or the invoking thread has waited for
timeout milliseconds plus nanos nanoseconds. This
method throws an InterruptedException object if another thread previously set the thread's interrupted status.
Because the synchronization lock is integrated with waiting and notification,
each method above must be called from a synchronized method or a synchronized
statement. Otherwise, an IllegalMonitorStateException object is
thrown from the method.
Note: J2SE 5.0's java.util.concurrent.locks package includes Condition,
an interface that serves as a replacement for Object's wait and notify
methods. You can use Condition implementations to create multiple
condition variables that associate with one Lock object, so that a
thread can wait for multiple conditions to occur.
Now that you know how threads use the waiting and notification mechanism to communicate, let's examine how that mechanism is used in a practical way. The classic example of thread communication involves the relationship between two threads: a producer thread and a consumer thread.
The producer thread produces data items to be consumed by the consumer thread. For example, the producer obtains data items from a network connection and passes them to the consumer for processing. Each produced data item is stored in one shared variable.
Imagine a scenario where the threads do not communicate and run at mismatched speeds. It would be possible for the producer to produce a new data item and record it in the shared variable before the consumer has retrieved the previous data item for processing. It would also be possible for the consumer to retrieve the contents of the shared variable before a new data item is produced. The result is a chaotic mess. To overcome those problems, the producer must wait until it is notified that the previously produced data item has been consumed, and the consumer must wait until it is notified that a new data item has been produced. The waiting and notification mechanism supports this communication, and is demonstrated in the following PC.java application source code. See this article's code.zip file for that source file.
public class PC
{
public static void main (String [] args)
{
Shared s = new Shared ();
new Producer (s).start ();
new Consumer (s).start ();
}
}
class Shared
{
private char c = '\u0000';
private boolean writeable = true;
synchronized void setSharedChar (char c)
{
while (!writeable)
try
{
wait ();
}
catch (InterruptedException e) {}
this.c = c;
writeable = false;
notify ();
}
synchronized char getSharedChar ()
{
while (writeable)
try
{
wait ();
}
catch (InterruptedException e) { }
writeable = true;
notify ();
return c;
}
}
class Producer extends Thread
{
private Shared s;
Producer (Shared s)
{
this.s = s;
}
public void run ()
{
for (char ch = 'A'; ch <= 'Z'; ch++)
{
s.setSharedChar (ch);
System.out.println (ch + " produced by "
+ "producer.");
}
}
}
class Consumer extends Thread
{
private Shared s;
Consumer (Shared s)
{
this.s = s;
}
public void run ()
{
char ch;
do
{
ch = s.getSharedChar ();
System.out.println (ch + " consumed by "
+ "consumer.");
}
while (ch != 'Z');
}
}
The application creates a Shared object and two threads that get
a copy of that object's reference. The producer invokes the object's
setSharedChar() method to save each of 26 uppercase letters. The
consumer invokes that object's getSharedChar() method to acquire
each letter.
The waiting and notification mechanism is incorporated into both methods. The
introduction of a Boolean writeable instance field variable into
the same class tracks two conditions (the producer waiting on the consumer to
consume a data item and the consumer waiting on the producer to produce a new
data item) and helps to coordinate the execution of the producer and consumer.
The following scenario, where the consumer executes first, illustrates that
coordination:
s.getSharedChar() to retrieve a letter.
Inside of that synchronized method, the consumer calls wait()
because writeable contains true. The consumer now waits until it
receives notification from the producer.
The producer eventually executes s.setSharedChar(ch).
When the producer enters that synchronized method (which is possible because
the consumer released the lock inside of the wait() method prior to
waiting), the producer discovers writeable's value as true and
does not call wait().
The producer saves the character, sets writeable to false (which
will cause the producer to wait on the next setSharedChar()
invocation if the consumer has not consumed the character by that time), and
invokes notify() to waken the consumer (assuming the consumer is
waiting).
The producer exits setSharedChar(char c).
The consumer wakes up (and re-acquires the lock), sets writeable
to true (which will cause the consumer to wait on the next
getSharedChar() invocation if the producer has not produced a
character by that time), notifies the producer to awaken that thread (assuming
the producer is waiting), and returns the shared character.
When run, the application produces the following output (which I've shortened, for brevity):
A produced by producer.
A consumed by consumer.
B produced by producer.
B consumed by consumer.
C produced by producer.
C consumed by consumer.
D produced by producer.
D consumed by consumer.
E produced by producer.
E consumed by consumer.
F produced by producer.
F consumed by consumer.As you can see, the producer always produces a data item before the consumer consumes that data item. Furthermore, each data item is produced exactly once and each data item is consumed exactly once.
|
The assignment of a value to a variable that is not of type long or double is treated by Java as an indivisible operation. Retrieving that variable's value is also treated as an indivisible operation. In other words, Java guarantees that a variable write operation results in all bits being written as a unit, and guarantees that a variable read operation results in all bits being read as a unit. There is no need for synchronization.
Because synchronization isn't needed when reading/writing a non-long/non-double variable, one expects that two threads can communicate, via a single shared variable, without a problem. Thread A writes a value to the shared variable, and thread B retrieves the new value from that variable.
But a problem exists. Java's memory model permits threads to store the values of variables in local memory (e.g., machine registers or a processor's cache on a multiprocessor machine). This is done for performance reasons: it is faster to access local memory than main memory. On Java VMs with memory-model implementations that support local memory, other threads do not "see" the change when a thread modifies a cached value. This lack of visibility across threads is a major problem in loop scenarios. For example, one thread continually iterates a loop until a certain variable is set to a specific value. Another thread assigns this value to the variable at some specific moment, so that the loop can end. But if the loop's thread cannot "see" the new value, because the value is stored in the other thread's local memory, an infinite loop occurs.
Synchronization represses this caching behavior. According to the Java memory model, a thread's local memory is reset to the values stored in main memory when the thread acquires a lock. Furthermore, local memory values are written back to main memory when the thread releases that lock.
Unfortunately, excessive synchronization can cause a program's performance to
suffer. To balance the need to (occasionally) avoid local memory versus not
sacrificing performance, Java provides the volatile keyword. For
each variable marked with that keyword, Java reads that variable's value from
main memory, and writes that variable's value to main memory. Local memory is
avoided.
I have written an application that demonstrates a volatile variable. When you run that application, it starts two threads. One thread runs in a loop and continually outputs the value of an integer variable (which it also increments). The other thread sleeps for five seconds and then writes a value to another variable, to "tell" the loop thread to terminate. That application's Terminate.java source code, which is included in this article's attached code.zip file, appears below.
public class Terminate
{
public static void main (String [] args)
{
ThreadB tb = new ThreadB ();
ThreadA ta = new ThreadA (tb);
tb.start ();
ta.start ();
}
}
class ThreadA extends Thread
{
private ThreadB tb;
ThreadA (ThreadB tb)
{
this.tb = tb;
}
public void run ()
{
try
{
Thread.sleep (5000);
}
catch (InterruptedException e)
{
}
tb.finished = true;
}
}
class ThreadB extends Thread
{
public volatile boolean finished = false;
private int sum = 0;
public void run ()
{
while (!finished)
{
System.out.println ("sum = " + sum++);
Thread.yield ();
}
}
}
Notice that I've marked ThreadB's finished variable
with the volatile keyword. This guarantees that each thread will
always access the value of finished from main memory. For Java
VMs that are capable of caching variable values in local memory, threads will
be required to access the value of finished from main memory; no
infinite loop will occur when this program is run on those Java VMs, because
both threads work with the same main memory copy of finished.
Note: J2SE 5.0 introduces java.util.concurrent.atomic, a package
of classes that extends the notion of volatile variables to include an atomic
conditional update operation, which permits lock-free, thread-safe programming
on single variables.
J2SE 5.0 introduces four kinds of synchronizers, high-level tools that
let your code achieve different kinds of synchronization: countdown latches,
cyclic barriers, exchangers, and semaphores. These high-level synchronization
tools are implemented by five classes in the
java.util.concurrent package. This section identifies each class,
as it briefly explores the first three synchronizers and extensively explores
semaphores.
A countdown latch is a synchronizer that allows one or more threads to
wait until some collection of operations being performed in other threads
finishes. This synchronizer is implemented by the CountDownLatch
class.
A cyclic barrier is a synchronizer that allows a collection of threads
to wait for each other to reach a common barrier point. This synchronizer is
implemented by the CyclicBarrier class and also makes use of the
BrokenBarrierException class.
An exchanger is a synchronizer that allows a pair of threads to
exchange objects at a synchronization point. This synchronizer is implemented
by the Exchanger<V> class, where V is a placeholder
for the type of objects that may be exchanged.
A semaphore, as implemented in J2SE 5.0's Semaphore class,
is a synchronizer that uses a counter to limit the number of threads that can
access limited resources. Ironically, this high-level synchronization tool is
based on the same-named, low-level primitive that is often used to implement
monitors. The discussion that follows first explores this low-level primitive,
and then explores Semaphore.
In 1965, E. W. Dijkstra invented the semaphore concurrency construct. He used that construct to support mutual exclusion, the act of restricting shared resource access to one process at a time. Nowadays, we don't think about processes. Instead, we think about threads. That's why I refer to thread instead of process in the following paragraph.
Dijkstra's semaphore construct is a protected variable that initializes to a non-negative integer count, implements P (from the Dutch word "proberen," meaning "to test") and V (from the Dutch word "verhogen," meaning "to increment") operations, and has a wait queue. When a thread executes P on the semaphore, the count is tested to see if it is greater than 0. If that is the case, the semaphore decrements the count. But if the count is 0, the calling thread is made to wait in the queue. When a thread executes V on the semaphore, the semaphore determines if one or more threads are waiting in the queue. If so, the semaphore allows one of those threads to proceed. But if no threads are waiting, the count increments. Each one of the P and V operations is indivisible.
Semaphores classify as counting semaphores or binary semaphores. A semaphore
is a counting semaphore if it can assume any non-negative integer value.
The SDK documentation for J2SE 5.0's Semaphore class refers to
that class as a counting semaphore. But if the semaphore can only assume 0 or
1, it is known as a binary semaphore. Binary semaphores are a special
case of counting semaphores.
Semaphore uses the concept of permits to explain how it works. A
thread must acquire a permit, guaranteeing that an item is available for use,
before the thread can obtain the item from a pool of items. When a thread
finishes using the item, it returns that item back to the pool and the permit
back to the semaphore.
Use the public Semaphore(int permits, boolean fair) constructor
to create a semaphore: permits specifies the number of available
permits (hence resources that are available in a pool), and fair
indicates whether or not the semaphore guarantees a first-in first-out (FIFO)
granting of permits under contention (true, if this is the case). An example:
Semaphore sem = new Semaphore (1, false);creates a binary semaphore that does not guarantee FIFO granting of permits under contention.
The public void acquire() method acquires a permit from the
semaphore. The calling thread blocks until one is available or the thread is
interrupted. An example:
sem.acquire ();
The public void release() method returns a permit to the
semaphore. If any threads are waiting for a permit, one of those threads is
selected and given the just-released permit. The thread is then re-enabled for
thread scheduling. An example:
sem.release (); To demonstrate Semaphore, I've created an application that makes
use of the Pool class, shown in the SDK's Semaphore
documentation. Check out that application's SemDemo.java source
code, which locates in the article's code.zip
file.
An exploration of Java's synchronization fundamentals is not complete without an examination of thread communication, volatile variables, and synchronizers. You've learned how Java uses its waiting and notification mechanism to support thread communication, have seen that volatile variables serve as a special-purpose alternative to synchronization, and have acquired insight into J2SE 5.0's high-level synchronizer tools.
I have some homework for you to accomplish:
Create a Java application that simulates this behavior. Avoid deadlock and the problem of indefinite postponement, where one of more philosophers soon starve because philosophers adjacent to the starving philosophers are always eating. Make sure that mutual exclusion is enforced, so that two adjacent philosophers do not use the same chopstick at the same time.
Next time, Java Tech explores SANE and TWAIN.
The previous Java Tech article presented you with some challenging homework on locks, synchronized methods, and synchronized statements. Let's revisit that homework and investigate solutions.
The thread is allowed to enter the other critical section and execute its code without having to re-grab the same lock. Furthermore, the lock is not released when the thread leaves the inner critical section and returns to the outer critical section, because that lock must be held while the thread continues to execute within the outer critical section.
notifyClients() and make the entire method synchronized. What is
wrong with that idea?
We run the risk of deadlock if we make the entire method synchronized. How is this possible? Assume two threads: an event-notification thread that invokes each registered listener's event-handling method, and a listener thread that registers that object's interest in receiving event notifications. Assume the event-handling method is synchronized, to protect itself from simultaneous invocation by multiple threads. Now consider this scenario: the event-notification thread has just entered its synchronized method and enters the loop to begin sending event notifications to registered listeners. At the same time, the listener thread is executing within code that synchronizes via the same lock as the listener's synchronized event-handling method. Each thread holds its own lock. Suppose the listener thread invokes a synchronized method in the event notification object to deregister its listener object. Because the deregistration method is synchronized using the same lock as the event-notification synchronized method, the listener thread must wait because the event-notification thread holds that lock. When the event-notification thread attempts to invoke the listener's event-handling method, it is forced to wait when it attempts to acquire the listener's lock, because the listener thread holds that lock. Neither thread can proceed because each thread holds the other thread's required lock, and deadlock occurs.
this and the
synchronized statement in the example.
Consult the NoSync.java source code in this article's attached code.zip file.
Jeff Friesen is a freelance software developer and educator specializing in Java technology. Check out his site at javajeff.mb.ca.
 |
 java.net RSS Feeds
|
