[ Home ] [ Up ] [ A Steam Boiler ] [ Race Conditions ] [ Monitors ] [ Synchronization ] [ A Fixed Steam Boiler ] [ Deadlock ] [ Starvation & Livelock ]

We said that, for a given thread that has already acquired the lock on a monitor, monitors are reentrant. However, if two (or more) threads compete for the same two (or more) resources, there is the possibility of deadlock, unless measures are taken to prevent it.

For example, imagine that we're writing a program to transfer funds from one bank account to another, and we want to ensure that we have no problems when we are accessing accounts from different threads. Here's a possible program to do that:

package threads;

/**
*  This class will create a deadlock situation.
*/
public class Deadlock
{
    public static void main(String[] args)
    {
        Account a1 = new Account("Account 1", 10000);
        Account a2 = new Account("Account 2", 30000);
        Thread threadA = 
            new TransferFundsThread("Thread A", a1, a2, 5);
        Thread threadB = 
            new TransferFundsThread("Thread B", a2, a1, 20);
        threadA.start();
        threadB.start();
    }
}

class Account
{
    public Account(String name, int balance)
    {
        m_name = name;
        m_balance = balance;
    }
    
    public int getBalance()
    {
        return m_balance;
    }
    
    public void setBalance(int newBalance)
    {
        m_balance = newBalance;
    }
    
    public String getName()
    {
        return m_name;
    }
    
    private String m_name;
    private int    m_balance;
}

class TransferFundsThread extends Thread
{
    public TransferFundsThread(String name, 
                               Account from, 
                               Account to, 
                               int amount)
    {
        super(name);
        m_from   = from;
        m_to     = to;
        m_amount = amount;
    }
    
    public void run()
    {
        transferFunds();
    }
    
    /**
     *  In order to transfer funds safely, we need to be able 
     *  to hold a lock on both the m_from and the m_to accounts, 
     *  and not release the locks until the transfer is completed.
     *  NOTE: This version does not consider the possibility that 
     *  there may be insufficient funds available.  This has been 
     *  omitted to simplify the example, but would have to be done 
     *  in the real world.
     */
    private void transferFunds()
    {
        synchronized (m_from)
        {
            System.out.println(getName() + 
                               ": Getting balance from " + 
                               m_from.getName());
            int balance1 = m_from.getBalance();
            System.out.println(getName() + 
                               ": Balance from " + 
                               m_from.getName() + 
                               " = " + balance1);
                    
            try
            {
                sleep(100);         // insert delay
            }
            catch (InterruptedException e)
            {
                // ignore
            }
            
            synchronized (m_to)
            {
                System.out.println(getName() + 
                                   ": Getting balance from " + 
                                   m_to.getName());
                int balance2 = m_to.getBalance();
                System.out.println(getName() + 
                                   ": Balance from " + 
                                   m_to.getName() + 
                                   " = " + balance2);
                                   
                if (balance1 >= m_amount)
                {
                    System.out.println(getName() + 
                                       ": Withdrawing funds from " +
                                       m_from.getName());
                    m_from.setBalance(balance1 - m_amount);
                    System.out.println(getName() + 
                                       ": Depositing funds into " +
                                       m_to.getName());
                    m_to.setBalance(balance2 + m_amount);
                    
                    System.out.println(getName() + 
                                       ": New balances are:\n" +
                                       "  " + m_from.getName() + 
                                       " = " + 
                                       m_from.getBalance() + "\n" +
                                       "  " + m_to.getName() + " = " +
                                       m_to.getBalance() );
                }
            }
        }
    }
    
    /// Private data ///
    private Account m_from;
    private Account m_to;
    private int     m_amount;
}

But when you run the program, it outputs the following:

Thread A: Getting balance from Account 1
Thread B: Getting balance from Account 2
Thread A: Balance from Account 1 = 10000
Thread B: Balance from Account 2 = 30000

and then stops. What's happening? Well, if you're running the program from a regular console window (an MS-DOS window on Microsoft Windows), using the java program (not jre), you can force a stack dump if you set the keyboard focus to the console window and press the proper keystroke combination:

• On Microsoft Windows, press <CTRL>Break (that is, hold the CTRL key down and press Break)
• On UNIX, press <CTRL>\ (ths is, hold the CTRL key down and press the backslash key)

and you will get output that looks something like this (this one was generated on Microsoft Windows NT):

Full thread dump:
    "Thread B" (TID:0x133d0f0, sys_thread_t:0xd26150, Win32ID:0x14b, state:MW) prio=5
        threads.TransferFundsThread.transferFunds(Deadlock.java:70)
        threads.TransferFundsThread.run(Deadlock.java:55)
    "Thread A" (TID:0x133d110, sys_thread_t:0xd26210, Win32ID:0x15e, state:MW) prio=5
        threads.TransferFundsThread.transferFunds(Deadlock.java:70)
        threads.TransferFundsThread.run(Deadlock.java:55)
    "SymcJIT-LazyCompilation-0" (TID:0x133cf58, sys_thread_t:0xd269c0, Win32ID:0x141, state:CW) prio=2
        SymantecJITCompilationThread.run(JITcompilationthread.java, Compiled Code)
    "SymcJIT-LazyCompilation-PA" (TID:0x133cf20, sys_thread_t:0xd251f0, Win32ID:0x158, state:CW) prio=10
        java.lang.Object.wait(Object.java:307)
        SymantecJITCompilationThread.run(JITcompilationthread.java, Compiled Code)
    "Finalizer thread" (TID:0x1339088, sys_thread_t:0xd1c670, Win32ID:0x145, state:CW) prio=2
    "main" (TID:0x13390b0, sys_thread_t:0xd1b8b0, Win32ID:0x14f, state:CW) prio=5
Monitor Cache Dump:
    threads.Account@133D130/1429100: owner (0x7ffd9000, 1 entry)
    threads.Account@133D148/14290B8: owner (0x7ffda000, 1 entry)
Registered Monitor Dump:
    SymcJIT Method Monitor: <unowned>
    SymcJIT Method List Monitor: <unowned>
    SymcJIT Lock: <unowned>
    Thread queue lock: <unowned>
        Waiters: 1
    Name and type hash table lock: <unowned>
    String intern lock: <unowned>
    JNI pinning lock: <unowned>
    JNI global reference lock: <unowned>
    BinClass lock: <unowned>
    Class loading lock: <unowned>
    Java stack lock: <unowned>
    Code rewrite lock: <unowned>
    Heap lock: <unowned>
    Has finalization queue lock: <unowned>
    Finalize me queue lock: <unowned>
        Waiters: 1
    Monitor registry: owner (0x7ffd8000, 1 entry)

For a detailed explanation of this output, see An Introduction to Java Stack Traces. 

However, here's a quick synopsis:

The possible thread states are:

• R -- Running or runnable thread
• S -- Suspended thread
• CW -- Thread waiting on a condition variable
• MW -- Thread waiting on a monitor lock
• MS -- Thread suspended waiting on a monitor lock

and you'll note that Thread A and Thread B are both in state: MW -- monitor wait.

The thread stack trace shows where the threads are -- both threads are at the same point in their respective code -- both are attempting to acquire a lock on their respective m_to objects.

Can you explain what's happening? Where is the problem? How can we solve it?

As you can see, when you're dealing with multiple threads, you have to be aware of the possibility of deadlock, and try to avoid that.