Concurrent Programming in Java: State Dependence

This chapter is from the book 

3.2 Guarded Methods

Conservative check-and-act methods refuse to perform actions unless they can ensure that these actions will succeed, in part by first checking their preconditions. The three basic flavors reflect policy decisions surrounding failed preconditions:

Balking. Throwing an exception if the precondition fails. The exceptions thrown are conceptually different from those seen in optimistic methods: here, an exception indicates refusal, not failure. But these exceptions usually have the same consequences to clients.

Guarded suspension. Suspending the current method invocation (and its associated thread) until the precondition becomes true.

Time-outs. The range of cases falling between balking and suspension, where an upper bound is placed on how long to wait for the precondition to become true.

There is no universally best policy choice among these options. As illustrated in 3.4.1, it is often possible to create multiple methods that support multiple policies among which clients may choose.

Balking is common in both sequential and concurrent programs. Refusal is the only sensible strategy when there is no reason to believe that a precondition will ever become true if it is not true already. For example, Thread.start throws IllegalThreadStateException if a thread is already started (see 1.1.2), since it can never again enter an unstarted state once started. Refusal is also the best choice for nearly all argument-based preconditions. For example, a graphics method might throw an IllegalArgumentException when asked to draw something with a negative size. Balking is also useful whenever a method is intended to have now-or-never semantics associated with the availability of resources. When refusal is not considered to be exceptional, a balking method need not throw an exception. This is seen for example in the ParticleApplet.stop method in 1.1.1.3, that quietly ignores attempts to stop the applet if it is not running.

3.2.1 Guarded Suspension

Guarded suspension and time-outs have no analog in sequential programs, but play central roles in concurrent software. This is reflected in the wide range of approaches to conceptualizing guards and in the many different notations and constructs available for designing concurrent software using guards. Before delving into implementation matters, it is worth stepping back to consider higher-level approaches and constructs that help organize designs relying on guarded suspension.

As fodder, consider the following toy BoundedCounter example, expressed for now only as an interface. The idea here is that implementations of BoundedCounter are obligated to maintain a count between MIN and MAX:

interface BoundedCounter {
 static final long MIN = 0;  // minimum allowed value
 static final long MAX = 10; // maximum allowed value


 long count();       // INV:  MIN <= count() <= MAX
                     // INIT: count() == MIN

 void inc();         // only allowed when count() < MAX

 void dec();         // only allowed when count() > MIN

}

3.2.1.1 Guards

In one sense, guarded methods are customizable extensions of synchronized methods, providing extended forms of exclusion. The “guard” for a plain synchronized method is just that an object is in the Ready execution state; i.e., is not engaged in any activity. At the implementation level, this means that the current thread is in possession of the object's synchronization lock. Guarded methods further partition the Ready state by adding state- based conditions (for example that count() < MAX) that are logically necessary for an action to proceed.

Guards may also be considered as special forms of conditionals. In sequential programs, an if statement can check whether a condition holds upon entry to a method. When the condition is false, there is no point in waiting for it to be true; it can never become true since no other concurrent activities could cause the condition to change. But in concurrent programs, asynchronous state changes can happen all the time.

Guarded methods thus pose liveness issues that simple conditionals do not encounter. Any guard implicitly asserts that, eventually, some other thread(s) will cause the required state changes to occur, or, if they do not, that it would be best never to proceed with the current activity. Time-outs are a way of softening such assertions, using a balking policy as a backup if the wait continues too long.

Some high-level design methods express conditional waits using an if-like construct called WHEN (also known as AWAIT) that can be useful in designing guarded methods. For example, here is a pseudocode version of the counter class using WHEN:

pseudoclass
BoundedCounterWithWhen {        // Pseudocode
 protected long count = MIN;

 public long count() { return count; }

 public void inc() {
  WHEN (count < MAX) {
   ++count;
  }
 }

 public void dec()
  WHEN (count > MIN) {
   --count;
  }
 }
}

The WHEN constructs here express the idea that the BoundedCounter is obligated to keep the count between MIN and MAX. If a dec message is received but the count cannot be decremented because it is already at MIN, the thread is blocked, resuming sometime later if and when the count becomes greater than MIN via an inc message invoked by some method running in some other thread.

3.2.1.2 State-based message acceptance

Actions in guarded methods trigger only when both a certain message is received and the object is in a certain state. Because neither the message nor the state is necessarily primary, you can design abstract versions of methods with the two parts inverted. This state-based style can be easier to use when designing classes in which several different methods are all triggered in the same states, for example when the object is assuming a particular role. This form also more clearly reflects state-based notations used in several popular high-level OO analysis and design methods.

Ada concurrency constructs can be used to define methods in this fashion. Expressed in Ada-like pseudocode, the BoundedCounter is:

pseudoclass
BoundedCounterWithAccept {        //
Pseudocode
 protected long count = MIN;

 WHEN (true) ACCEPT public long
 count() {
  return count;
 }

 WHEN (count < MAX) ACCEPT
 public void inc()  {
  ++count;
 }

 WHEN (count > MIN) ACCEPT
 public void dec()  {
  --count;
 }
}

Going to the extreme, some designs are easier to reason about if you think of actions as always being requested, but triggered only when the object makes a particular state transition. Some looping methods take this form. For example, you might design a special counter with a continuously enabled mechanism that resets the count to zero whenever it reaches a threshold. This style is sometimes called concurrent constraint programming, where actions can be triggered only by state changes since there are no messages.

3.2.1.3 Defining logical control state

Many objects maintain attributes that together constitute a very large (or for all practical purposes infinite) state space, but maintain only a small logical state space for purposes of guarding actions. For example, for purposes of inc and dec, BoundedCounters have only three logical states, not one state per value of their count:

State		inc	dec
top	count == MAX	no	yes
middle	MIN < count < MAX	yes	yes
bottom	count == MIN	yes	no

A bit of care is needed in characterizing these states. For example, if MAX is equal to MIN+1, then there is no distinct middle state. And if MIN is equal to MAX, then there is no way to distinguish top from bottom: neither method should ever fire.

As seen in the table, logical states are normally defined in terms of predicates — boolean expressions that distinguish particular ranges, values and/or other computable properties of fields. They can be coded either as free-standing internal boolean methods or simply as boolean conditions written inside methods relying on them. When state analysis becomes too big and unwieldy for such techniques, you can design and encode states using StateCharts, tables, decision trees, automata, and related tools of the trade for dealing with state machines (see the Further Readings in 1.3.5).

Instead of relying on predicate expressions, you can represent logical state explicitly in a variable. Each distinct state can be labeled as an integer or any other discrete data type. The field representing state must be re-evaluated upon each update so that it is always accurate (see 3.3.1). It is not strictly necessary to use a single variable — multiple variables can be used if object state can be partitioned on several independent dimensions. Special cases include:

• Role variables control responses to all of a related set of methods (often those declared in a single interface). When objects may alternate among roles, a single variable suffices to direct appropriate behavior. For example, an object may alternate between being a Producer and a Consumer. When in one role, it may ignore or delay responses to messages associated with the other.

• Rather than coding state as a value, you can code it as a reference to a state-object. For each state, you can write a class describing the behavior of the object when it is in that state. The main class then contains a reference field, say stateObject, that is always bound to the appropriate delegate. This is an application of the States as Objects pattern in the Design Patterns book; a variant is described in 3.7.2.

3.2.2 Monitor Mechanics

There are at least as many ways to implement guarded methods as there are ways to design them. But nearly all these techniques can be considered specializations of the following strategy employing methods Object.wait, Object.notify, and Object.notifyAll:

• For each condition that needs to be waited on, write a guarded wait loop that causes the current thread to block if the guard condition is false.

• Ensure that every method causing state changes that affect the truth value of any waited-for condition notifies threads waiting for state changes, causing them to wake up and recheck their guard conditions.

As a preliminary to discussing such techniques, here is a summary of the properties of waiting and notification methods.

In the same way that every Object has a lock (see 2.2.1), every Object has a wait set that is manipulated only by methods wait, notify, notifyAll, and Thread.interrupt. Entities possessing both locks and wait sets are generally called monitors (although almost every language defines details somewhat differently). Any Object can serve as a monitor.

The wait set for each object is maintained internally by the JVM. Each set holds threads blocked by wait on the object until corresponding notifications are invoked or the waits are otherwise released.

Because of the way in which wait sets interact with locks, the methods wait, notify, and notifyAll may be invoked only when the synchronization lock is held on their targets. Compliance generally cannot be verified at compile time. Failure to comply causes these operations to throw an IllegalMonitorStateException at run time.

The actions of these methods are as follows:

Wait. A wait invocation results in the following actions:

• If the current thread has been interrupted, then the method exits immediately, throwing an InterruptedException. Otherwise, the current thread is blocked.

• The JVM places the thread in the internal and otherwise inaccessible wait set associated with the target object.

• The synchronization lock for the target object is released, but all other locks held by the thread are retained. A full release is obtained even if the lock is re-entrantly held due to nested synchronized calls on the target object. Upon later resumption, the lock status is fully restored.

Notify. A notify invocation results in the following actions:

• If one exists, an arbitrarily chosen thread, say T, is removed by the JVM from the internal wait set associated with the target object. There is no guarantee about which waiting thread will be selected when the wait set contains more than one thread — see 3.4.1.5.

• T must re-obtain the synchronization lock for the target object, which will always cause it to block at least until the thread calling notify releases the lock. It will continue to block if some other thread obtains the lock first.

• T is then resumed from the point of its wait.

NotifyAll. A notifyAll works in the same way as notify except that the steps occur (in effect, simultaneously) for all threads in the wait set for the object. However, because they must acquire the lock, threads continue one at a time.

Interrupt. If Thread.interrupt is invoked for a thread suspended in a wait, the same notify mechanics apply, except that after re-acquiring the lock, the method throws an InterruptedException and the thread's interruption status is set to false. If an interrupt and a notify occur at about the same time, there is no guarantee about which action has precedence, so either result is possible. (Future revisions of JLS may introduce deterministic guarantees about these outcomes.)

Timed Waits. The timed versions of the wait method, wait(long msecs) and wait(long msecs, int nanosecs), take arguments specifying the desired maximum time to remain in the wait set. They operate in the same way as the untimed version except that if a wait has not been notified before its time bound, it is released automatically. There is no status indication differentiating waits that return via notifications versus time-outs. Counterintuitively, wait(0) and wait(0, 0) both have the special meaning of being equivalent to an ordinary untimed wait().

A timed wait may resume an arbitrary amount of time after the requested bound due to thread contention, scheduling policies, and timer granularities. (There is no guarantee about granularity. Most JVM implementations have observed response times in the 1-20ms range for arguments less than 1ms.)

The Thread.sleep(long msecs) method uses a timed wait, but does not tie up the current object's synchronization lock. It acts as if it were defined as:

  if (msecs != 0)  {
    Object s = new Object();
    synchronized(s) { s.wait(msecs); }
  }

Of course, a system need not implement sleep in exactly this way. Note that sleep(0) pauses for at least no time, whatever that means.

To illustrate some of the underlying mechanics, consider the following useless class that blindly issues wait and notifyAll:

class X {
 synchronized void w() throws InterruptedException {
  before(); wait(); after();
 }
 synchronized void n() { notifyAll(); }
 void before() {}
 void after() {}
}

Here is one possible outcome of three threads invoking methods on a common x. Notice that even though T1 began waiting before T2, T2 resumed before T1. It could have been otherwise; there are no guarantees.

3.2.3 Guarded Waits

The standard coding idiom for expressing guarded methods is a simple while loop invoking wait. For example, the inc method of a BoundedCounter implementation might start out as:

 synchronized void inc() throws InterruptedException {
  while (count >= MAX) wait();
  ++count;
  // ...
 }

To ensure that guards are implemented correctly, it is sometimes helpful to encapsulate each guard in its own method. For a generic example:

class GuardedClass {             // Generic code sketch
 protected boolean cond = false;

 // PRE: lock held
 protected void awaitCond() throws InterruptedException {
  while (!cond) wait();
 }

 public synchronized void guardedAction() {
  try {
   awaitCond();
  }
  catch (InterruptedException ie) {
   // fail
  }

  // actions
  }
}

Condition checks must be placed in while loops. When an action is resumed, the waiting task doesn't know whether the condition it is waiting for is actually true; it only knows that it has been woken up. So, in order to maintain safety properties, it must check again.

As a matter of programming practice, this style should be used even if the class contains only a single instance of wait that waits for a single condition. It is never acceptable to write code that assumes an object is in some particular state when it resumes after a given wait. One reason is that such code could fail just because some other unrelated object invoked notify or notifyAll on the target object by mistake. (These are public methods defined on all objects.) Additionally, it is wise to avoid breakage in the case of spurious wakeups in which waits are released by the system without any explicit call to a notification method⁴. However, a more important consideration is that without re-evaluation, such code will start failing in peculiar ways if people define additional methods (perhaps in subclasses of your class) that also use waits and notifications for other purposes.

Objects with guarded waits can be harder to think about than simple fully synchronized objects (2.2.2). Methods with guarded waits are not completely atomic. A waiting method suspends without retaining its synchronization lock, thus allowing any other thread to begin executing any synchronized method on that object. (And, as usual, other unsynchronized methods can still execute at any time.)

Guarded methods thus need to be written so that objects are in consistent states upon entering wait. The best strategy for ensuring this stems from the general idea of check-and-act policies. If you place a guarded wait as the first statement in a method and do not change state in the process of checking it, then you cannot have changed state in any inconsistent way when entering wait.

3.2.3.1 Interrupted waits

A wait will be broken (or will not start at all) if the waiting thread has been interrupted. This enables blocked threads to respond to thread cancellation. In this sense, guarded methods are similar to try-and-see methods — attempts to pass preconditions may themselves fail — and the failure policies and implementations described in 3.1 apply.

By far the most common policy applied in guarded methods is just to rethrow InterruptedException to denote failure to the client, which will then need to deal with it. Assuming that guarded waits appear at the beginnings of methods, no further local cleanup is necessary.

The routine practice of rethrowing InterruptedException (or, in the usual case, merely not catching it) and thus including throws InterruptedException in method signatures also serves as a simple declarative assertion that a method employs a guarded wait or derivative. This can be vital information for potential users of a class (see especially 3.3.4).

3.2.4 Notifications

Wait-based constructions make up the bulk of the safety side of guard implementation. To ensure liveness, classes must also contain code to wake up waiting threads when the conditions they are waiting for change. Every time the value of any field mentioned in a guard changes in a way that might affect the truth value of the condition, waiting tasks must be awakened so they can recheck guard conditions.

The simplest way to arrange that blocked threads eventually recheck conditions is to insert notifyAll in methods that cause relevant state changes. In turn, the simplest way to do this is to define utility methods that encapsulate assignment, issuing a notification upon any change in value. This may lead to useless signals and poor performance (due to context switching overhead) in classes that perform lots of assignments. However, as a design practice, it is occasionally a good idea to start out using blanket notifications within assignment methods, and then to minimize and reorganize them as discussed in later sections of this chapter. For example, here is a first pass at BoundedCounter:

class SimpleBoundedCounter {
 protected long count = MIN;

 public synchronized long count() { return count; }

 public synchronized void inc() throws InterruptedException {
  awaitUnderMax();
  setCount(count + 1);
 }

 public synchronized void dec() throws InterruptedException {
  awaitOverMin();
  setCount(count - 1);
 }

 protected void setCount(long newValue) { // PRE: lock held
  count = newValue;
  notifyAll(); // wake up any thread depending on new value
 }

 protected void awaitUnderMax() throws InterruptedException {
  while (count == MAX) wait();
 }

 protected void awaitOverMin() throws InterruptedException {
  while (count == MIN) wait();
 }
}

3.2.4.1 Slipped conditions and missed signals

In SimpleBoundedCounter, the calls to awaitUnderMax and setCount in method inc are performed under the same synchronized lock scope. It would not suffice to separately synchronize awaitUnderMax and setCount but not inc. This could encounter a safety violation. Expanding these out:

   void badInc() throws InterruptedException {  // Do not use
    synchronized(this) { while (count >= MAX) wait(); }
    // (*)
    synchronized(this) { ++count; notifyAll(); }
}

This version may encounter a slipped condition in which the condition changes due to the actions of some other thread executing at point (*) — between the time the lock is released after the wait and then reacquired before incrementing the count. This could result in the action being performed even if the guard is now false, possibly breaking the object by causing the required invariant to become false.

Additionally, a liveness failure could result if setCount were written in a non- atomic fashion, in particular as:

   void badSetCount(long newValue) {         // Do not use
    synchronized(this) { notifyAll(); }
    // (**)
    synchronized(this) { count = newValue; }
}

Here, the method first acquires the lock to perform notifyAll, then releases it, and then re-acquires it to change count. This could result in a missed signal: A thread executing at point (**) might start waiting after the signal intended to wake it up was issued but before the condition was changed. This thread will wait forever, or at least until the next notification is somehow produced.

Note that within synchronized methods, the order in which a notifyAll is placed does not matter. No awakened threads will be able to continue until the synchronization lock is released. Just as a matter of style, most people put notifications last in method bodies.

The mistakes leading to missed signals and slipped conditions illustrated here may seem farfetched. But they can be common sources of error in designs making more extensive use of waiting and notification techniques (see for example 3.7.2).

3.2.4.2 Single notifications

The SimpleBoundedCounter class uses notifyAll because threads may be waiting for the count either to be greater than MIN or less than MAX. It would not suffice here to use notify, which wakes up only one thread (if one exists). The JVM might pick a thread waiting for a condition that does not hold without picking the possibly many that could continue. This might happen, for example, if there are several threads all trying to increment and several all trying to decrement. (Consider for example the case where MAX == MIN+1.)

However, in some other classes, you can reduce the context-switch overhead associated with notifications by using a single notify rather than notifyAll. Single notifications can be used to improve performance when you are sure that at most one thread needs to be woken. This applies when:

• All possible waiting threads are necessarily waiting for conditions relying on the same notifications, usually the exact same condition.

• Each notification intrinsically enables at most a single thread to continue. Thus it would be useless to wake up others.

• You can accommodate uncertainties surrounding the possibility that an interrupt and a notify may occur at about the same time. In this case, the one thread that was notified is about to terminate. You might want another thread to receive notification instead, but this is not automatically arranged. (The issue does not arise with notifyAll since all threads are woken.)

To illustrate the relation between notify and notifyAll, the following GuardedClassUsingNotify class uses notify to approximate the effects of notifyAll by adding instrumentation to helper methods that encapsulate guards. Here, adding an execution state variable to track the number of waiting threads allows construction of a loop that broadcasts a notification to all waiting threads, thus simulating notifyAll (although only approximately — notifyAll is a primitive built-in operation).

The odd-looking catch clause seen here ensures that if a cancelled thread receives a notify, it relays that notification to some other waiting thread (if one exists). This safeguard is not really needed here since all waiting threads are being awakened anyway, but the technique should be employed in any code using notify in which interruptions do not necessarily shut down an entire program.

Note that the extra call to notify inside the catch clause may cause the count of waiting threads to overestimate the number of notifications necessary to wake up all threads. This in turn may cause more than the minimal number of calls to notify to be issued. This fact underscores the need to place waits in guard loops, even when using notify.

class GuardedClassUsingNotify {
 protected boolean cond = false;
 protected int nWaiting = 0; // count waiting threads

 protected synchronized void awaitCond()
  throws InterruptedException {
   while (!cond) {
    ++nWaiting;    // record fact that a thread is waiting
    try {
      wait();
    }
    catch (InterruptedException ie) {
     notify();    // relay to non-cancelled thread
     throw ie;
    }
    finally {
     --nWaiting;  // no longer waiting
    }
   }
  }

  protected synchronized void signalCond() {
   if (cond) {          // simulate notifyAll
     for (int i = nWaiting; i > 0; --i) notify();
   }
  }
}

In open, extensible designs (see 1.3.4), the conditions under which notify apply are rather special and fragile. The use of notify, and optimizations of guarded constructions more generally, are common sources of error. As a general design tactic, it is a better idea to isolate uses of notify to concurrency control utility classes (see 3.4) that can be heavily optimized and carefully reviewed and tested. We adopt this approach throughout the remainder of this chapter.

The conditions for using notify hold much more frequently in closed designs, where you are in full control of all participating threads. For example, the following sketch of a closed-system two- player game uses waits for turn-taking. A single notify suffices to wake the only thread that can possibly be awaiting its turn. On the other hand, because there is only one thread waiting anyway, the performance differences between this version and one using notifyAll are probably too small to measure — the main overhead associated with notifyAll is context switching, not the call to notifyAll itself.

Note that giveTurn is invoked as an open call (see 2.4.1.3) in method GamePlayer.releaseTurn. It is good practice to release as much synchronization as possible when performing notifications (see 3.7.2).

class GamePlayer implements Runnable {     // Incomplete
 protected GamePlayer other;
 protected boolean myturn = false;

 protected synchronized void setOther(GamePlayer p) {
  other = p;
 }

 synchronized void giveTurn() { // called by other player
  myturn = true;
  notify();          // unblock thread
 }

 void releaseTurn() {
  GamePlayer p;
  synchronized(this) {
   myturn = false;
   p = other;
  }
  p.giveTurn(); // open call
 }

 synchronized void awaitTurn() throws InterruptedException {
  while (!myturn) wait();
 }

 void move() { /*... perform one move ... */ }

 public void run() {
  try {
    for (;;) {
     awaitTurn();
     move();
     releaseTurn();
    }
   }
   catch (InterruptedException ie) {} // die
  }

 public static void main(String[] args) {
  GamePlayer one = new GamePlayer();
  GamePlayer two = new GamePlayer();
  one.setOther(two);
  two.setOther(one);
  one.giveTurn();
  new Thread(one).start();
  new Thread(two).start();
 }
}

3.2.5 Timed Waits

Rather than waiting forever for a condition to become true in a guarded method, time-out designs place a bound on how long any given wait should remain suspended.

Responses to time-outs are of course situation-dependent. When time-outs are used heuristically, the fact that a predicate does not hold may be only of informational value. In other cases, time-outs force cancellation of attempted actions, in which case it is often appropriate to declare a TimeoutException as a subclass of InterruptedException.

Time-outs are typically more useful than other techniques that detect unanticipated liveness problems (such as deadlock⁵) because they make fewer assumptions about contexts — any stall that causes unacceptably long blockages can be detected by a time-out that then triggers failure responses (see 3.1.1). Since most responses to delays of any kind are the same, they can all be triggered by time- out exceptions or related notification techniques.

The parameters controlling wait time and condition re-evaluation are sometimes completely arbitrary, and often require some trial and error. Usually, it is not too hard to provide values that will catch true liveness problems without false-alarming on waits that just happen to be slow. Since many such failures will at some point require human intervention, policies can be backed up via mechanisms that query users about remedial actions.

Time-outs are somewhat awkward to express using wait(msec). In the following TimeoutBoundedCounter class, the wait is placed in a loop in order to deal with the fact that unrelated notifications may occur. This loop is slightly messy but has the identical rationale as versions without time-outs. The condition being waited on is always checked first after waking up from the wait, before checking for time-out. This helps avoid programming errors stemming from cases in which a wait is released by a time-out, but other contending threads execute before the timed-out thread gets a chance to resume. One of those other threads could have changed the condition, in which case it would not be necessary or appropriate to return a failure indication. If the condition does not hold, the time-out value is checked and adjusted for use in the next iteration.

You could change this code to make the opposite decision about ordering the condition check and time check if time-outs are always considered to denote failure, even if the condition does hold upon resumption from the time-out.

class TimeoutException extends InterruptedException { ... }

class TimeOutBoundedCounter {
 protected long count = 0;

 protected long TIMEOUT = 5000; // for illustration

 // ...
 synchronized void inc() throws InterruptedException {

  if (count >= MAX) {
    long start = System.currentTimeMillis();
    long waitTime = TIMEOUT;

    for (;;) {
     if (waitTime <= 0)
       throw new TimeoutException();
     else {
      try {
        wait(waitTime);
      }
      catch (InterruptedException ie) {
       throw ie;  // coded this way just for emphasis
      }
      if (count < MAX)
        break;
      else {
       long now = System.currentTimeMillis();
       waitTime = TIMEOUT - (now - start);
      }
     }
    }
   }

   ++count;
   notifyAll();
  }

  synchronized void dec() throws InterruptedException {
   // ... similar ...
  }

}

3.2.6 Busy Waits

Implementing guards via waiting and notification methods is nearly always superior to using an optimistic-retry-style busy-wait “spinloop” of the form:

  protected void busyWaitUntilCond() {
   while (!cond)
    Thread.yield();
  }

Busy-waits have drawbacks that make them poor choices for implementing most guarded actions. The contrasts between the two techniques help explain why suspension-based waiting and notification methods are defined as they are.

3.2.6.1 Efficiency

Busy-waits can waste an unbounded amount of CPU time spinning uselessly. The wait- based version rechecks conditions only when some other thread provides a notification that the object's state has changed, thus possibly affecting the guard condition. Even if notifications are sometimes sent when enabling conditions do not hold, conditions are likely to be unproductively rechecked far less often than in a spinloop that continually, blindly rechecks.

The main exceptions are those cases in which you somehow know that the condition must become true within some very short, bounded amount of time. In such cases, the time wasted spinning might be less than the time required to suspend and resume threads. This may apply to operations associated with device control. Bounded spins, followed by suspensions, are also sometimes used inside run-time systems as an optimization for “adaptive” locks that are usually held only briefly.

3.2.6.2 Scheduling

The yield in the spinloop version is only a hint (see 1.1.2) and is not guaranteed effective in allowing other threads to execute so they can change the condition. Thus the utility of busy-waits is more dependent on the policies of a particular JVM, and may interact with other aspects of scheduling. For example, if the spinning task is running at a high priority but the threads that change the condition run at low priority, the spinning task may still crowd the others out. In the wait-based version, the waiting task does not run at all, and thus cannot encounter such scheduling problems (although other scheduling problems can of course still arise).

Some of the most plausible situations for using spinloops are those in which some other action can be taken within the loop if the condition is not true, rather than just yielding. This helps limit CPU wastage and interacts better with common scheduling policies. If spinning is for some reason necessary and no other alternatives apply, you can reduce CPU costs and scheduling uncertainties by using the timed back-off techniques described in 3.1.1.5.

3.2.6.3 Triggering

Unlike wait-based constructions, methods with spinloops need not be paired with methods that provide notifications to trigger checks. Spinloops are sometimes used in desperation when no such signaling method exists or can be written. But busy waits can miss opportunities to fire if they happen not to be scheduled to execute during times when the condition is momentarily true.

Note however, that similar phenomena also occur in wait-based constructions: A condition signaled by a notify or notifyAll may later change due to the action of some other thread occurring before the notified thread gets a chance to continue. This is one reason to guard all forms of waits.

Additionally, neither technique alone automatically guarantees fairness — that each potentially enabled thread eventually proceeds. Even in wait-based constructions, it could happen that one particular looping thread that repeatedly encounters the guard is always the one that proceeds, starving out all others (see 3.4.1.5).

3.2.6.4 Synchronizing actions

It can be difficult to synchronize spinloops in the desired manner. For example, it wouldn't always work to declare the method busyWaitUntilCond as synchronized, since this does not allow any other synchronized method to change the condition. Minimally, cond needs to be declared as volatile and/or accessed and set in its own synchronized methods. However, without synchronization of an entire check-act sequence, you cannot in general ensure that an object remains in the same state between the condition test and the associated action.

As described in 3.4.2.1, reliable use of unsynchronized busy-waits in guarded methods is generally restricted to latching predicates that are somehow guaranteed to remain true forever once set. In contrast, the wait-based version automatically relinquishes the synchronization lock (for the host object only) upon wait and re-obtains the lock upon waking up. So long as both the guard and the action are enclosed within a common lock, and the guard references only variables protected by that lock, there is no danger of slipped conditions. This is one reason that wait statements can be used only under synchronization. However, the fact that waiting tasks hold any locks at all can be the source of logistical difficulties, including the nested monitor problem discussed in 3.3.4.

3.2.6.5 Implementations

In those rare cases in which you have no alternative to busy-waits, you can use a class such as the following SpinLock. There is never any reason to use this class for locking (see 2.5.1), but it is a simple vehicle for illustrating constructions that can be applied in other contexts.

The release method here is synchronized as an assurance that a memory synchronization occurs upon lock release, as would be necessary in nearly any use of this class (see 2.2.7). The escalation rules for failed checks are uncomfortably dependent on settings that are intrinsically platform- and application-specific (for example, the pure yield-less spin phase is plausible only on multiprocessors), and can be difficult to tune effectively even with empirical feedback.

class SpinLock {           // Avoid needing to use this

 private volatile boolean busy = false;

 synchronized void release() { busy = false; }

 void acquire() throws InterruptedException {
  int spinsBeforeYield = 100;   // 100 is arbitrary
  int spinsBeforeSleep = 200;   // 200 is arbitrary
  long sleepTime = 1;        // 1msec is arbitrary
  int spins = 0;
  for (;;) {
   if (!busy) {          // test-and-test-and-set
    synchronized(this) {
     if (!busy) {
       busy = true;
       return;
     }
    }
   }

    if (spins < spinsBeforeYield) {      // spin phase
     ++spins;
    }
    else if (spins < spinsBeforeSleep) {  // yield phase
     ++spins;
     Thread.yield();
    }
    else {                    // back-off phase
     Thread.sleep(sleepTime);
     sleepTime =  3 * sleepTime / 2 + 1; // 50% is arbitrary
    }
   }
  }
}