How Nested Monitor Lockout Occurs

Nested monitor lockout is a problem similar to deadlock. A nested monitor lockout occurs like this:

Thread 1 synchronizes on A
Thread 1 synchronizes on B (while synchronized on A)
Thread 1 decides to wait for a signal from another thread before continuing
Thread 1 calls B.wait() thereby releasing the lock on B, but not A.

Thread 2 needs to lock both A and B (in that sequence)
        to send Thread 1 the signal.
Thread 2 cannot lock A, since Thread 1 still holds the lock on A.
Thread 2 remain blocked indefinately waiting for Thread1
        to release the lock on A

Thread 1 remain blocked indefinately waiting for the signal from
        Thread 2, thereby
        never releasing the lock on A, that must be released to make
        it possible for Thread 2 to send the signal to Thread 1, etc.

This may sound like a pretty theoretical situation, but look at the naiveLockimplemenation below:

//lock implementation with nested monitor lockout problem

public class Lock{
  protected MonitorObject monitorObject = new MonitorObject();
  protected boolean isLocked = false;

  public void lock() throws InterruptedException{
    synchronized(this){
      while(isLocked){
        synchronized(this.monitorObject){
            this.monitorObject.wait();
        }
      }
      isLocked = true;
    }
  }

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

Notice how thelock()method first synchronizes on "this", then synchronizes on themonitorObjectmember. IfisLockedis false there is no problem. The thread does not callmonitorObject.wait(). IfisLockedis true however, the thread callinglock()is parked waiting in themonitorObject.wait()call.

The problem with this is, that the call tomonitorObject.wait()only releases the synchronization monitor on themonitorObjectmember, and not the synchronization monitor associated with "this". In other words, the thread that was just parked waiting is still holding the synchronization lock on "this".

When the thread that locked theLockin the first place tries to unlock it by callingunlock()it will be blocked trying to enter thesynchronized(this)block in theunlock() method. It will remain blocked until the thread waiting inlock()leaves thesynchronized(this)block. But the thread waiting in thelock()method will not leave that block until theisLockedis set to false, and amonitorObject.notify()is executed, as it happens inunlock().

Put shortly, the thread waiting inlock()needs anunlock()call to execute successfully for it to exitlock()and the synchronized blocks inside it. But, no thread can actually executeunlock()until the thread waiting inlock()leaves the outer synchronized block.

This result is that any thread calling eitherlock()orunlock()will become blocked indefinately. This is called a nested monitor lockout.

A More Realistic Example

You may claim that you would never implement a lock like the one shown earlier. That you would not callwait()andnotify()on an internal monitor object, but rather on the This is probably true. But there are situations in which designs like the one above may arise. For instance, if you were to implementfairnessin a Lock. When doing so you want each thread to callwait()on each their own queue object, so that you can notify the threads one at a time.

Look at this naive implementation of a fair lock:

//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 {}

At first glance this implementation may look fine, but notice how thelock()method callsqueueObject.wait();from inside two synchronized blocks. One synchronized on "this", and nested inside that, a block synchronized on thequeueObjectlocal variable. When a thread callsqueueObject.wait()it releases the lock on theQueueObjectinstance, but not the lock associated with "this".

Notice too, that theunlock()method is declared synchronized which equals asynchronized(this)block. This means, that if a thread is waiting insidelock()the monitor object associated with "this" will be locked by the waiting thread. All threads callingunlock()will remain blocked indefinately, waiting for the waiting thread to release the lock on "this". But this will never happen, since this only happens if a thread succeeds in sending a signal to the waiting thread, and this can only be sent by executing theunlock()method.

And so, the FairLock implementation from above could lead to nested monitor lockout. A better implementation of a fair lock is described in the textStarvation and Fairness.

Nested Monitor Lockout vs. Deadlock

The result of nested monitor lockout and deadlock are pretty much the same: The threads involved end up blocked forever waiting for each other.

The two situations are not equal though. As explained in the text onDeadlocka deadlock occurs when two threads obtain locks in different order. Thread 1 locks A, waits for B. Thread 2 has locked B, and now waits for A. As explained in the text onDeadlock Preventiondeadlocks can be avoided by always locking the locks in the same order (Lock Ordering). However, a nested monitor lockout occurs exactly by two threads taking the locksin the same order. Thread 1 locks A and B, then releases B and waits for a signal from Thread 2. Thread 2 needs both A and B to send Thread 1 the signal. So, one thread is waiting for a signal, and another for a lock to be released.

The difference is summed up here:

In deadlock, two threads are waiting for each other to release locks.

In nested monitor lockout, Thread 1 is holding a lock A, and waits
for a signal from Thread 2. Thread 2 needs the lock A to send the
signal to Thread 1.