Java supports thread synchronization by means of monitor-like primitives. The weak semantics of Java’s signaling mechanism provides little control over the order in which threads acquire resources, which encourages the use of the Haphazard Notification pattern, in which an arbitrary thread is selected from a set of threads competing for a resource. For synchronization problems in which such arbitrary selection of threads is unacceptable, the Specific Notification pattern may be used to designate exactly which thread should proceed. Specific Notification provides an explicit mechanism for thread selection and scheduling.
To study Java’s threads, I first tackled some of the classic exercises, like the "Dining Philosophers” and the "Readers and Writers." The solutions that I obtained were reasonable, but I felt uncomfortable with the degree to which I had to depend on serendipitous treatment with respect to contention for locks and notifications. The solutions were free of deadlock, but were not fair in all circumstances. I thought I might have to resign myself to tolerating some unfairness in Java. Next, I built a multi-threaded NNTP (note 1) client, in which several threads could have active requests outstanding with an NNTP server. The fundamental correctness of this class depended on waiting threads being reactivated in exactly the right order to receive their responses from the server. In coding this class I applied the Specific Notification mechanism described below. With new insight, I returned to the earlier exercises and found that Specific Notification provided complete solutions to those problems. I therefore propose the Specific Notification pattern.
Section 1 summarizes the semantics of Java’s thread synchronization mechanisms, contrasting them with classical monitors; this section may be omitted by readers who have a detailed knowledge of Java. Section 2 summarizes Java’s conventional Haphazard Notification pattern, and discusses its limitations. Section 3 presents the Specific Notification pattern, and explains how it addresses those limitations. Section 4 offers additional examples of Specific Notification. Section 5 speculates that Specific Notification may be a member of a pattern language.
The semantics of Java’s thread
synchronization primitives(note 2)
approximate
those of
classical monitors(note 3).
A Java "lock" object corresponds to a monitor;
Java's
synchronized method(note 4)
corresponds to a monitor procedure;
Java’s wait and notify methods on a
lock object correspond to the wait and
signal operations of a monitor.
There are two significant differences
between Java’s semantics and classical
monitors. First, Java locks have no
associated condition variables. The
wait and notify methods operate on
the lock object itself, not on distinct
condition variables. (Alternatively, a
Java lock may be viewed as a monitor
with a single, implicit condition
variable.) Therefore, a waiting thread
cannot be notified that a specific
condition has been satisfied by another
thread. Second, context switching
between a notifying thread and a notified
thread is not fair. Among a set of
threads awaiting notification, the
selection of the thread that receives the
notification is arbitrary. Therefore, an
unlucky thread can starve forever while
waiting to acquire a resource, if there is
sufficient ongoing competition from
other threads. Moreover, between the
execution of a notify operation and
the acquisition of the lock by the waiting
thread that receives the notification,
another thread may intervene to acquire
the lock. The impact of these semantics
is that a thread resuming from a wait
operation cannot assume that it will find
a specific state as left by the notifying
thread. A thread continuing from a
wait can assume that the lock invariant
holds, but no more.
In general, thread priority has no bearing on Java’s weak notification semantics. For example, a higher priority thread is not favored over a lower priority one in the selection of which should receive a notification. To illustrate the consequence of this, consider that two lower priority threads might starve a higher priority thread, if notification always happens to pass from one of the lower priority threads to the other. Thread priorities may be used to control the relative progress of threads when they are not interacting, but not when the are. For this reason, thread priority is ignored until Section 5.
The semantics of Java locks naturally lead to patterns in which a synchronized method waits in a loop until a required guard condition is met:
synchronized void f() {
while( !guardCondition() )
wait(); // (note 6)
executeOperation();
notifyAll();
}
The notifyAll primitive is a
variation of notify in which all
threads currently waiting on the lock are
notified, and may start competing for the
lock. In general, the notifyAll form
must be used because there is no way to
guarantee that a notify operation
would resume a thread that is in a
position to make progress. The use of
notifyAll results in each waiting
thread eventually (note 7)
retesting its guard condition. Those threads that may
proceed to use the resource will in turn
notify all waiting threads.
Gosling et al. (note 8) recommend this form as "good practice." Arnold and Gosling (note 9) state that "The condition test should always be in a loop." Lea (note 10) describes it as the "standard coding idiom." The pattern has also been recommended for use in other languages. Lampson and Redell (note 11) state that, in Mesa, "The proper pattern of code for waiting is therefore:
WHILE NOT <OK to proceed> DO
WAIT c
ENDLOOP
Birrell
(note 12)
offers "... the following general
pattern, which I strongly recommend for
all your uses of condition variables.
WHILE NOT expression DO
Thread.Wait(m,c)
END;
Listing 1
shows a Java solution to
Dijkstra’s "Dining Philosophers"
problem
(note 13)
using Haphazard Notification.
The solution is deadlock-free, because
even-numbered philosophers pick up
their left fork first, and odd-numbered
philosophers pick up their right fork
first
(note 14).
A weakness of this solution is
that it does not guarantee fairness: a
philosopher may wait without bound to
acquire a given fork while another
philosopher repeatedly acquires and
releases that fork. The putDown
method of class Fork uses notify,
rather than notifyAll, as an
optimization, since there is no point in
notifying more that one waiting thread.
However, as discussed above, the use of
notify does not guarantee that the
notified thread will be the next thread to
acquire the lock. In particular, the thread
that performs the notification may
acquire the lock again for itself before
the notified thread manages to do so.
The solution would become fair if a mechanism can be found that forces competing threads to alternate in their acquisition of a fork. How should this be accomplished?
The Specific Notification pattern addresses the arbitrary scheduling of Haphazard Notification.
A family of threads must cooperate to synchronize their use of a shared resource. In general, a thread must defer its use of the resource until the resource achieves an appropriate state. Many threads may wait for the resource concurrently, and for diverse reasons.
Specific Notification is applicable when
the arbitrary selection of a thread by
notify, or the arbitrary scheduling of
threads following notify and
notifyAll provide insufficient
control with respect to the order in
which threads acquire a resource. The
lack of ordering may be unsatisfactory
merely because it is unfair, or because
an application-specific policy constrains
the order in which threads must acquire
the resource. (An application-specific
policy is illustrated in Section 4.)
Remove thread selection and scheduling
from the purview of the built-in
primitives, and place it explicitly under
program control. To do this, create a
separate lock object for each set of
threads that must be notified together.
Notification may then be applied to a
specific lock object, which results in the
activation of precisely the corresponding
set of threads. If the set of threads is
known to be a singleton, then exactly
one thread is activated, by the use of
notify. For an arbitrary set of threads,
notifyAll should be used.
In general, the only property shared by the threads waiting for a specific notification lock is that they are to be reactivated simultaneously. The number of lock objects is therefore determined by the number of such sets of threads. For some resources, a fixed set of locks may suffice; for other resources, the set of locks may be determined dynamically, and may even grow without bound.
Listing 2
shows the Fork class from
Listing 1
rewritten to use Specific
Notification. Each Fork object has a
Vector
(note 15)
of lock objects called snq
(specific notification queue). As a thread
enters the pickUp method (which is not
a synchronized method), it creates a
new object, snl (specific notification
lock), for exclusive use as its specific
notification lock. If the thread must
wait, it must leave itself holding the
lock on snl. It therefore locks snl
before locking this (the Fork object).
The thread cannot block when acquiring
snl, because the identity of snl is
local. The thread may block in trying to
acquire this, just as it might have
blocked when entering the
synchronized version of pickUp
(Listing 1). Having acquired the lock on
the Fork object, the thread determines
whether or not it may proceed to use the
Fork object. If any other thread has a
lock object in the specific notification
queue, this thread must wait. Before
waiting, the thread releases the lock on
the Fork object. The wait operation is
applied specifically to snl. Any snl
object is used at most once as a lock.
The putDown method, which remains
synchronized, is simpler. First, a
thread that is relinquishing the Fork
object removes its own specific
notification lock from the head of the
specific notification queue. If the queue
is non-empty, then there is at least one
thread waiting to acquire this Fork
object. Before notifying the thread at the
head of the queue, the active thread must
acquire the corresponding specific
notification lock. The notify
operation activates exactly the
designated thread. No other thread may
intervene ahead of the designated thread.
Specific Notification incurs a programming cost, which must not be overlooked. The programmer must assume greater responsibility in terms of maintaining the integrity of shared objects and the progress of threads. The benefits of increased control over threads are paid for with greater diligence in design and coding. If the behavior of Haphazard Notification is acceptable, there is no reason to introduce this burden.
The execution costs of Specific
Notification are hard to characterize, but
are generally better conditioned than
those of Haphazard Notification. Where
thread contention is low, Haphazard
Notification is efficient because
notifyAll operations act on queues
that are expected to be empty. Under
low contention, Specific Notification
goes further, by eliminating redundant
notifications entirely, usually at the cost
of more mechanism when notification is
required. Under high contention, the
performance of Haphazard Notification
degrades: in general, of a large set of
threads that are activated to re-evaluate
their guard conditions, only a few
(usually zero or one) actually make
useful progress. The performance of
Specific Notification does not degrade
under high contention: the notification
operations performed remain exactly
those that are required.
This section offers two further examples of Specific Notification.
Listing 3 shows part of a solution to the
"Readers and Writers" problem
(note 16).
Class Resource has methods
beforeRead, beforeWrite,
afterRead and afterWrite, which
must be called before and after their
respective operations. The integer fields
readers and writers record the
number of active readers and writers,
respectively, preserving the invariants
(readers==0 or writers==0)
and writers<=1. The
readersWaiting field records the
number of readers waiting to acquire the
resource. All reader threads wait on the
Resource object itself and are notified
collectively by notifyAll in method
afterWrite. This illustrates Specific
Notification of a set of threads. Note that
beforeRead does not use a while
loop to test its guard condition, as it
would under Haphazard Notification.
Exactly the set of threads notified from
afterWrite become the active
readers (possibly joined by later
arrivals). Fairness among writer threads
is achieved by using Specific
Notification to individual threads. Writer
threads wait on lock objects that are
enqueued in a Vector called
writerQ. The Specific Notification is
performed in the method
notifyWriter, which is called from
both afterRead and afterWrite,
when needed.
Listing 4 is abstracted from a multi-threaded
NNTP client, which uses
Specific Notification. Each thread that
enters the client object with a query for
the NNTP server calls sendAndWait
to transmit a sequence of commands to
the server. Responses from the server are
returned in the order they were
transmitted. Client threads must
therefore be directed to read their
responses in the same order that they
sent their requests. After transmitting its
request, if another thread is seen ahead,
the thread waits in sendAndWait on a
Specific Notification lock placed in a
queue. After waiting (if necessary) and
then reading a response from the server,
each thread calls afterReading to
notify exactly the thread behind it, if
there is one.
The Specific Notification pattern may be
a member of a pattern language that
addresses Java’s weak context switching
semantics in general. Another problem is
to arrange that a set of independent
threads, which have no intrinsic reason
to communicate, share a set of
processors such that all of the threads
make progress. A Java virtual machine
may timeslice the execution of threads at
the same priority, but is not obliged to
do so. The semantics of the
Thread.yield primitive are not
strong enough to guarantee that N (or
more) threads can share N-1 processors
fairly. As with Specific Notification, the
solution is to program explicitly with the
weak primitives such that the virtual
machine is forced to produce the desired
effect. The problem can be solved by
adding a high priority thread that
awakens periodically and adjusts the
relative priorities of the other threads, so
that each is guaranteed to dominate from
time to time, and therefore make
progress.
Using Specific Notification, a Java
program takes responsibility for
explicitly determining the set of threads
to be activated by a notify operation,
rather than subject itself to the arbitrary
built-in semantics. The additional
implementation complexity is warranted
in programs where correctness or
fairness considerations make haphazard
synchronization intolerable.
Discussions with Doug Lea helped to clarify my thinking on several topics addressed in this paper. Thanks also to Adam McClure and Hans Rohnert for their comments on earlier drafts.
class Fork {
private boolean free = true;
synchronized void pickUp(){
while( !free ) {
try {
wait();
}
catch(Exception exc) {
Thread.currentThread().stop();
}
}
free = false;
}
synchronized void putDown() {
free = true;
notify();
}
}
class Phil implements Runnable {
private Fork a, b;
Phil(Fork a, Fork b) {
this.a = a;
this.b = b;
}
public void run(){
while( true ){
// thinking
a.pickUp();
b.pickUp();
// eating
b.putDown();
a.putDown();
}
}
}
class Dining {
public static void main(String[] argv){
int size = 5;
Fork[] forks = new Fork[size];
for( int i=0; i<size; ++i )
forks[i] = new Fork();
for( int i=0; i<size; ++i ){
Fork a = forks[i];
Fork b = forks[(i+1)%size];
Phil p;
if( i%2==0 )
p = new Phil(a, b);
else
p = new Phil(b, a);
new Thread(p).start();
}
}
}
class Fork {
private Vector snq = new Vector();
void pickUp(){
Object snl = new Object();
boolean mustWait;
synchronized( snl ) {
synchronized( this ) {
mustWait = !snq.isEmpty();
snq.addElement(snl);
}
if( mustWait ) {
try {
snl.wait();
}
catch(Exception exc) {
Thread.currentThread().stop();
}
}
}
}
synchronized void putDown() {
snq.removeElementAt(0);
if( !snq.isEmpty() )
synchronized(snq.firstElement() ) {
snq.firstElement().notify();
}
}
}
class Resource {
private int writers = 0, readers = 0, readersWaiting = 0;
private Vector writerQ = new Vector();
synchronized void beforeRead() {
if( writerQ.size()==0 && writers==0 ) {
readers += 1;
return;
}
readersWaiting += 1;
try {
wait();
} catch(Exception e) { Thread.currentThread().stop(); }
}
void beforeWrite() {
Object snl = new Object();
synchronized(snl) {
synchronized(this) {
if( writerQ.size()==0 && writers+readers==0 ) {
writers += 1;
return;
}
writerQ.addElement(snl);
}
try {
snl.wait();
} catch(Exception e) { Thread.currentThread().stop(); }
}
}
synchronized void afterRead() {
readers -= 1;
if( readers==0 )
notifyWriter();
}
synchronized void afterWrite() {
writers -= 1;
readers = readersWaiting;
readersWaiting = 0;
if( readers > 0 )
notifyAll();
else
notifyWriter();
}
private void notifyWriter() {
if( writerQ.size() > 0 ) {
Object snl = writerQ.firstElement();
writerQ.removeElementAt(0);
synchronized(snl) {
snl.notify();
}
writers += 1;
}
}
private void sendAndWait(String groupName, String cmd) {
Object lock = new Object();
synchronized(lock){
boolean ready;
synchronized(this){
sendAsync("group "+groupName);
sendAsync(cmd);
ready = snq.isEmpty();
snq.addElement(lock);
}
if( !ready )
try {
lock.wait();
}
catch(Exception e) { fatal(e); }
}
}
private synchronized void afterReading() {
snq.removeElementAt(0); // remove me
if( !snq.isEmpty() )
synchronized(snq.elementAt(0)) {
snq.elementAt(0).notify();
}
}
1. B. Kantor, P. Lapsley, Network News Transfer Protocol, Internic RFC 977, 1986.
2. J. Gosling, et al., The Java Language Specification, Addison-Wesley, 1996
3. C.A.R Hoare, Monitors: An Operating System Structuring Concept. CACM 17:10, pp. 549–557, 1974.
4.
In fact, the synchronized method is merely
syntactic sugar for the true primitive: the
synchronized statement.
5. For a discussion of "fairness" see G. R. Andrews, Concurrent Programming, Addison-Wesley, 1991, pp. 83–86
6.
The exception that may be thrown by wait is
ignored in this code fragment.
7. Strictly, Java does not guarantee that every thread progresses. Relative thread priorities and the availability of processors determine which threads make progress.
8. J. Gosling, et al., The Java Language Specification, Addison-Wesley, 1996, Chapter 16.
9. K. Arnold, J. Gosling, The Java Programming Language, Addison-Wesley, 1996, Chapter 9.
10. D. Lea, Concurrent Programming in Java, Addision-Wesley.
11. B.W. Lampson, D.D. Redell, Experience with Processes and Monitors in Mesa, CACM 23:2, 105– 11, 1981.
12. A.D. Birrell, An Introduction to Programming with Threads, Tech. Report #35, Systems Research Center, Digital Equipment, Palo Alto, CA, 1989.
13. E.W. Dijsktra, Hierarchical Ordering of Sequential Processes, Acta Informatica, 1:2, 115–138, 1971.
14. T.A. Cargill, A Robust Distributed Solution to the Dining Philosophers Problem, Software — Practice and Experience, 12, 965–969, 1982.
15. Class Vector is a member of the standard java.util package.
16. Courtois, Heymans, Parnas, Concurrent Control with "readers" and "writers," CACM 14:10, 667–668, Oct., 1971.
tac 9/14/98