What is Slipped Conditions?

Slipped conditions means, that from the time a thread has checked a certain condition until it acts upon it, the condition has been changed by another thread so that it is errornous for the first thread to act. Here is a simple example:

public class Lock {

    private boolean isLocked = true;

    public void lock(){
      synchronized(this){
        while(isLocked){
          try{
            this.wait();
          } catch(InterruptedException e){
            //do nothing, keep waiting
          }
        }
      }

      synchronized(this){
        isLocked = true;
      }
    }

    public synchronized void unlock(){
      isLocked = false;
      this.notify();
    }

}

Notice how thelock()method contains two synchronized blocks. The first block waits untilisLockedis false. The second block setsisLockedto true, to lock theLockinstance for other threads.

Imagine thatisLockedis false, and two threads calllock()at the same time. If the first thread entering the first synchronized block is preempted right after the first synchronized block, this thread will have checkedisLockedand noted it to be false. If the second thread is now allowed to execute, and thus enter the first synchronized block, this thread too will seeisLockedas false. Now both threads have read the condition as false. Then both threads will enter the second synchronized block, setisLockedto true, and continue.

This situation is an example of slipped conditions. Both threads test the condition, then exit the synchronized block, thereby allowing other threads to test the condition, before any of the two first threads change the conditions for subsequent threads. In other words, the condition has slipped from the time the condition was checked until the threads change it for subsequent threads.

To avoid slipped conditions the testing and setting of the conditions must be done atomically by the thread doing it, meaning that no other thread can check the condition in between the testing and setting of the condition by the first thread.

The solution in the example above is simple. Just move the lineisLocked = true;up into the first synchronized block, right after the while loop. Here is how it looks:

public class Lock {

    private boolean isLocked = true;

    public void lock(){
      synchronized(this){
        while(isLocked){
          try{
            this.wait();
          } catch(InterruptedException e){
            //do nothing, keep waiting
          }
        }
        isLocked = true;
      }
    }

    public synchronized void unlock(){
      isLocked = false;
      this.notify();
    }

}

Now the testing and setting of theisLockedcondition is done atomically from inside the same synchronized block.

A More Realistic Example

You may rightfully argue that you would never implement a Lock like the first implementation shown in this text, and thus claim slipped conditions to be a rather theoretical problem. But the first example was kept rather simple to better convey the notion of slipped conditions.

A more realistic example would be during the implementation of a fair lock, as discussed in the text onStarvation and Fairness. If we look at the naive implementation from the textNested Monitor Lockout, and try to remove the nested monitor lock problem it, it is easy to arrive at an implementation that suffers from slipped conditions. First I'll show the example from the nested monitor lockout text:

//Fair Lock implementation with nested monitor lockout problem

public class FairLock {
  private boolean           isLocked       = false;
  private Thread            lockingThread  = null;
  private List<QueueObject> waitingThreads =
            new ArrayList<QueueObject>();

  public void lock() throws InterruptedException{
    QueueObject queueObject = new QueueObject();

    synchronized(this){
      waitingThreads.add(queueObject);

      while(isLocked || waitingThreads.get(0) != queueObject){

        synchronized(queueObject){
          try{
            queueObject.wait();
          }catch(InterruptedException e){
            waitingThreads.remove(queueObject);
            throw e;
          }
        }
      }
      waitingThreads.remove(queueObject);
      isLocked = true;
      lockingThread = Thread.currentThread();
    }
  }

  public synchronized void unlock(){
    if(this.lockingThread != Thread.currentThread()){
      throw new IllegalMonitorStateException(
        "Calling thread has not locked this lock");
    }
    isLocked      = false;
    lockingThread = null;
    if(waitingThreads.size() > 0){
      QueueObject queueObject = waitingThread.get(0);
      synchronized(queueObject){
        queueObject.notify();
      }
    }
  }
}

public class QueueObject {}

Notice how thesynchronized(queueObject)with itsqueueObject.wait()call is nested inside thesynchronized(this)block, resulting in the nested monitor lockout problem. To avoid this problem thesynchronized(queueObject)block must be moved outside thesynchronized(this)block. Here is how that could look:

//Fair Lock implementation with slipped conditions problem

public class FairLock {
  private boolean           isLocked       = false;
  private Thread            lockingThread  = null;
  private List<QueueObject> waitingThreads =
            new ArrayList<QueueObject>();

  public void lock() throws InterruptedException{
    QueueObject queueObject = new QueueObject();

    synchronized(this){
      waitingThreads.add(queueObject);
    }

    boolean mustWait = true;
    while(mustWait){

      synchronized(this){
        mustWait = isLocked
      }

      synchronized(queueObject){
        if(mustWait){
          try{
            queueObject.wait();
          }catch(InterruptedException e){
            waitingThreads.remove(queueObject);
            throw e;
          }
        }
      }
    }

    synchronized(this){
      waitingThreads.remove(queueObject);
      isLocked = true;
      lockingThread = Thread.currentThread();
    }
  }
}

Note: Only thelock()method is shown, since it is the only method I have changed.

Notice how thelock()method now contains 3 synchronized blocks.

The firstsynchronized(this)block checks the condition by settingmustWait = isLocked || waitingThreads.get(0) != queueObject.

The secondsynchronized(queueObject)block checks if the thread is to wait or not. Already at this time another thread may have unlocked the lock, but lets forget that for the time being. Let's assume that the lock was unlocked, so the thread exits thesynchronized(queueObject)block right away.

The thirdsynchronized(this)block is only executed ifmustWait = false. This sets the conditionisLockedback totrueetc. and leaves thelock()method.

Imagine what will happen if two threads calllock()at the same time when the lock is unlocked. First thread 1 will check theisLockedconditition and see it false. Then thread 2 will do the same thing. Then neither of them will wait, and both will set the stateisLockedto true. This is a prime example of slipped conditions.

Removing the Slipped Conditions Problem

To remove the slipped conditions problem from the example above, the content of the lastsynchronized(this)block must be moved up into the first block. The code will naturally have to be changed a little bit too, to adapt to this move. Here is how it looks:

//Fair Lock implementation without nested monitor lockout problem,
//but with missed signals problem.

public class FairLock {
  private boolean           isLocked       = false;
  private Thread            lockingThread  = null;
  private List<QueueObject> waitingThreads =
            new ArrayList<QueueObject>();

  public void lock() throws InterruptedException{
    QueueObject queueObject = new QueueObject();

    synchronized(this){
      waitingThreads.add(queueObject);
    }

    boolean mustWait = true;
    while(mustWait){


        synchronized(this){
            mustWait = isLocked || waitingThreads.get(0) != queueObject;
            if(!mustWait){
                waitingThreads.remove(queueObject);
                isLocked = true;
                lockingThread = Thread.currentThread();
                return;
            }
        } 

      synchronized(queueObject){
        if(mustWait){
          try{
            queueObject.wait();
          }catch(InterruptedException e){
            waitingThreads.remove(queueObject);
            throw e;
          }
        }
      }
    }
  }
}

Notice how the local variablemustWaitis tested and set within the same synchronized code block now. Also notice, that even if themustWaitlocal variable is also checked outside thesynchronized(this)code block, in thewhile(mustWait)clause, the value of themustWaitvariable is never changed outside thesynchronized(this). A thread that evaluatesmustWaitto false will atomically also set the internal conditions (isLocked) so that any other thread checking the condition will evaluate it to true.

Thereturn;statement in thesynchronized(this)block is not necessary. It is just a small optimization. If the thread must not wait (mustWait == false), then there is no reason to enter thesynchronized(queueObject)block and execute theif(mustWait)clause.

The observant reader will notice that the above implementation of a fair lock still suffers from a missed signal problem. Imagine that the FairLock instance is locked when a thread callslock(). After the firstsynchronized(this)blockmustWaitis true. Then imagine that the thread callinglock()is preempted, and the thread that locked the lock calls unlock(). If you look at theunlock()implementation shown earlier, you will notice that it callsqueueObject.notify(). But, since the thread waiting inlock()has not yet calledqueueObject.wait(), the call toqueueObject.notify()passes into oblivion. The signal is missed. When the thread callinglock()right after callsqueueObject.wait()it will remain blocked until some other thread callsunlock(), which may never happen.

The missed signals problems is the reason that theFairLockimplementation shown in the textStarvation and Fairnesshas turned theQueueObjectclass into a semaphore with two methods:doWait()anddoNotify(). These methods store and react the signal internally in the QueueObject. That way the signal is not missed, even ifdoNotify()is called beforedoWait().