Why should wait() always be called inside a loop

I have read that we should always call a wait() from within a loop:

while (!condition) { obj.wait(); }

It works fine without a loop so why is that?

You need not only to loop it but check your condition in the loop. Java does not guarantee that your thread will be woken up only by a notify()/notifyAll() call or the right notify()/notifyAll() call at all. Because of this property the loop-less version might work on your development environment and fail on the production environment unexpectedly.

For example, you are waiting for something:

synchronized (theObjectYouAreWaitingOn) {
   while (!carryOn) {
      theObjectYouAreWaitingOn.wait();
   }
}

An evil thread comes along and:

theObjectYouAreWaitingOn.notifyAll();

If the evil thread does not/can not mess with the carryOn you just continue to wait for the proper client.

Edit: Added some more samples. The wait can be interrupted. It throws InterruptedException and you might need to wrap the wait in a try-catch. Depending on your business needs, you can exit or suppress the exception and continue waiting.

It's answered in documentation for Object.wait(long milis)

> A thread can also wake up without being notified, interrupted, or timing out, a so-called spurious wakeup. While this will rarely occur in practice, applications must guard against it by testing for the condition that should have caused the thread to be awakened, and continuing to wait if the condition is not satisfied. In other words, waits should always occur in loops, like this one:

 synchronized (obj) {
     while (<condition does not hold>)
         obj.wait(timeout);
     ... // Perform action appropriate to condition
 }

> (For more information on this topic, > see Section 3.2.3 in Doug Lea's > "Concurrent Programming in Java > (Second Edition)" (Addison-Wesley, > 2000), or Item 50 in Joshua Bloch's > "Effective Java Programming Language > Guide" (Addison-Wesley, 2001).

> Why should wait() always be called inside a loop

The primary reason why while loops are so important is race conditions between threads. Certainly spurious wakeups are real and for certain architectures they are common, but race conditions are a much more likely reason for the while loop.

For example:

synchronized (queue) {
    // this needs to be while
    while (queue.isEmpty()) {
       queue.wait();
    }
    queue.remove();
}

With the above code, there may be 2 consumer threads. When the producer locks the queue to add to it, consumer #1 may be blocked at the synchronized lock while consumer #2 is waiting on the queue. When the item is added to the queue and notify called by the producer, #2 is moved from the wait queue to be blocked on the queue lock, but it will be behind the #1 consumer which was already blocked on the lock. This means that the #1 consumer gets to go forward first to call remove() from the queue. If the while loop is just an if, then when consumer #2 gets the lock after #1 and calls remove(), an exception would occur because the queue is now empty -- the other consumer thread already removed the item. Even though it was notified, it needs to be make sure the queue is for sure not empty because of this race condition.

This well documented. Here's a web page I created a while back which explains the race condition in detail and has some sample code.

There might be more then just one worker waiting for a condition to become true.

If two or more worker get awake (notifyAll) they have to check the condition again. otherwise all workers would continue even though there might only be data for one of them.

I think I got @Gray 's answer.

Let me try to rephrase that for newbies like me and request the experts to correct me if I am wrong.

Consumer synchronized block::

synchronized (queue) {
    // this needs to be while
    while (queue.isEmpty()) {
       queue.wait();
    }
    queue.remove();
}

Producer synchronized block::

synchronized(queue) {
 // producer produces inside the queue
    queue.notify();
}

Assume the following happens in the given order:

1. consumer#2 gets inside the consumer synchronized block and is waiting since queue is empty.

2. Now, producer obtains the lock on queueand inserts inside the queue and calls notify().

Now,either consumer#1 can be chosen to run which is waiting for queue lock to enter the synchronized block for the first time

or

consumer#2 can be chosen to run.

3. say, consumer#1 is chosen to continue with the execution. When it checks the condition,it will be true and it will remove() from the queue.

4. say,consumer#2 is proceeding from where it halted its execution (the line after the wait() method). If 'while' condition is not there (instead an if condition), it will just proceed to call remove() which might result in an exception/unexpected behaviour.

Because wait and notify are used to implement [condition variables](http://en.wikipedia.org/wiki/Monitor_(synchronization\)#Blocking_condition_variables) and so you need to check whether the specific predicate you're waiting on is true before continuing.

Both safety and liveness are concerns when using the wait/notify mechanism. The safety property requires that all objects maintain consistent states in a multithreaded environment. The liveness property requires that every operation or method invocation execute to completion without interruption.

To guarantee liveness, programs must test the while loop condition before invoking the wait() method. This early test checks whether another thread has already satisfied the condition predicate and sent a notification. Invoking the wait() method after the notification has been sent results in indefinite blocking.

To guarantee safety, programs must test the while loop condition after returning from the wait() method. Although wait() is intended to block indefinitely until a notification is received, it still must be encased within a loop to prevent the following vulnerabilities:

Thread in the middle: A third thread can acquire the lock on the shared object during the interval between a notification being sent and the receiving thread resuming execution. This third thread can change the state of the object, leaving it inconsistent. This is a time-of-check, time-of-use (TOCTOU) race condition.

Malicious notification: A random or malicious notification can be received when the condition predicate is false. Such a notification would cancel the wait() method.

Misdelivered notification: The order in which threads execute after receipt of a notifyAll() signal is unspecified. Consequently, an unrelated thread could start executing and discover that its condition predicate is satisfied. Consequently, it could resume execution despite being required to remain dormant.

Spurious wakeups: Certain Java Virtual Machine (JVM) implementations are vulnerable to spurious wakeups that result in waiting threads waking up even without a notification.

For these reasons, programs must check the condition predicate after the wait() method returns. A while loop is the best choice for checking the condition predicate both before and after invoking wait().

Similarly, the await() method of the Condition interface also must be invoked inside a loop. According to the Java API, Interface Condition

> When waiting upon a Condition, a "spurious wakeup" is permitted to > occur, in general, as a concession to the underlying platform > semantics. This has little practical impact on most application > programs as a Condition should always be waited upon in a loop, > testing the state predicate that is being waited for. An > implementation is free to remove the possibility of spurious wakeups > but it is recommended that applications programmers always assume that > they can occur and so always wait in a loop.

New code should use the java.util.concurrent.locks concurrency utilities in place of the wait/notify mechanism. However, legacy code that complies with the other requirements of this rule is permitted to depend on the wait/notify mechanism.

Noncompliant Code Example This noncompliant code example invokes the wait() method inside a traditional if block and fails to check the postcondition after the notification is received. If the notification were accidental or malicious, the thread could wake up prematurely.

synchronized (object) {
  if (<condition does not hold>) {
    object.wait();
  }
  // Proceed when condition holds
}

Compliant Solution This compliant solution calls the wait() method from within a while loop to check the condition both before and after the call to wait():

synchronized (object) {
  while (<condition does not hold>) {
    object.wait();
  }
  // Proceed when condition holds
}

Invocations of the java.util.concurrent.locks.Condition.await() method also must be enclosed in a similar loop.

Before getting to the answer, lets see how wait is probably implemented.

wait(mutex) {
   // automatically release mutex
   // and go on wait queue

   // ... wait ... wait ... wait ...

   // remove from queue
   // re-acquire mutex
   // exit the wait operation
}

In your example mutex is the obj with the assumption that your code is running inside synchronized(obj) { } block.

> A mutex is called as monitor in Java [some subtle differences though]

A concurrency example using condition variable with if

synchronized(obj) {
  if (!condition) { 
    obj.wait(); 
  }
  // Do some stuff related to condition
  condition = false;
}

Lets say we have 2 threads. Thread 1 and Thread 2. Lets see some states along the timeline.

at t = x

Thread 1 state:

waiting on ... wait ... wait ... wait ..

Thread 2 state:

Just entered the synchronised section, since as per the thread 1's state, the mutex/monitor is released.

> You can read more about wait() here java.sun.com/javase/6/docs/api/java/lang/Object.html#wait(long).

This is the only thing that is tricky to understand. When 1 thread is inside the synchronized block. Another thread can still enter the synchronized block because wait() causes the monitor/mutex to be released.

Thread 2 is about to read if (!condition) statement.

at t = x + 1

notify() is triggered by some thread on this mutex/monitor.

condition becomes true

Thread 1 state:

Waiting at re-acquire mutex, [Since thread-2 has the lock now]

Thread 2 state:

Doesn't go inside if condition and marks the condition = false.

at t = x + 2

Thread 1 state:

Exits the wait operation and about to mark condition = false.

This state is inconsistent as condition is supposed to be true but is false already, because thread 2 marked it false previously.

And thats the reason, while is required instead of if. As while would trigger the condition to be checked again for thread 1 and thread 1 will begin waiting again.

Result

In order to avoid this inconsistency the correct code seems to be like this:

synchronized(obj) {
  while (!condition) { 
    obj.wait(); 
  }
  // Do some stuff related to condition
  condition = false;
}

From your Question:

>I have read that we should always called a wait() from within a loop:

Although wait( ) normally waits until notify( ) or notifyAll( ) is called, there is a possibility that in very rare cases the waiting thread could be awakened due to a spurious wakeup. In this case, a waiting thread resumes without notify( ) or notifyAll( ) having been called.

In essence, the thread resumes for no apparent reason.

Because of this remote possibility, Oracle recommends that calls to wait( ) should take place within a loop that checks the condition on which the thread is waiting.

Three things you will see people do:

• Using wait without checking anything (BROKEN)

• Using wait with a condition, using an if check first (BROKEN).

• Using wait in a loop, where the loop test checks the condition (NOT BROKEN).

Not appreciating these details about how wait and notify work leads people to choose the wrong approach:

• One is that a thread doesn't remember notifications that happened before it got around to waiting. The notify and notifyAll methods only effect threads that are already waiting, if a thread isn't waiting at the time it is out of luck.

• Another is that a thread releases the lock once it starts waiting. Once it gets a notification it re-acquires the lock and continues on where it left off. Releasing the lock means that thread does not know anything about the current state once it wakes back up, any number of other threads could have made changes since then. The check made before the thread started waiting doesn't tell you anything about what the state is currently.

So the first case, with no checking, lays your code vulnerable to race conditions. It might happen to work by accident if one thread has enough of a head start over another. Or you may have threads waiting forever. If you sprinkle in timeouts then you end up with slow code that sometimes doesn't do what you want.

Adding a condition to check apart from the notification itself protects your code from these race conditions and gives your code a way to know what the state is even if the thread wasn't waiting at the right time.

The second case, with if-checks, is likely to work if you have only 2 threads. That puts a limit on the number of states things can get into and when you made faulty assumptions you don't get burned so badly. This is the situation for lots of toy example code exercises. The result is people come away thinking they understand, when they really don't.

Protip: Real world code has more than two threads.

Using the loop lets you re-check the condition once you re-acquire the lock so that you're moving forward based on current state, not on stale state.

In simple words,

'if' is a conditional statement , once condition is satisfied remaining block of code will get executed.

'while' is a loop which going check the condition unless condition is not satisfied.