Thread Deadlock:
A special
type of error that you need to avoid that relates specifically to multitasking
is deadlock, which occurs when two threads have a circular dependency on a pair
of synchronized objects.
For
example, suppose one thread enters the monitor on object X and another thread
enters the monitor on object Y. If the thread in X tries to call any
synchronized method on Y, it will block as expected. However, if the thread in
Y, in turn, tries to call any synchronized method on X, the thread waits forever,
because to access X, it would have to release its own lock on Y so that the
first thread could complete.
Example:
To
understand deadlock fully, it is useful to see it in action. The next example
creates two classes, A and B, with methods foo ( ) and bar ( ), respectively,
which pause briefly before trying to call a method in the other class.
The main
class, named Deadlock, creates an A and a B instance, and then starts a second
thread to set up the deadlock condition. The foo ( ) and bar ( ) methods use sleep
( ) as a way to force the deadlock condition to occur.
|
class A {
synchronized void foo(B b) {
String name =
Thread.currentThread().getName();
System.out.println(name + "
entered A.foo");
try {
Thread.sleep(1000);
} catch(Exception e) {
System.out.println("A
Interrupted");
}
System.out.println(name + " trying
to call B.last()");
b.last();
}
synchronized void last() {
System.out.println("Inside
A.last");
}
}
class B {
synchronized void bar(A a) {
String name =
Thread.currentThread().getName();
System.out.println(name + "
entered B.bar");
try {
Thread.sleep(1000);
} catch(Exception e) {
System.out.println("B
Interrupted");
}
System.out.println(name + " trying
to call A.last()");
a.last();
}
synchronized void last() {
System.out.println("Inside
A.last");
}
}
class Deadlock
implements Runnable {
A a = new A();
B b = new B();
Deadlock() {
Thread.currentThread().setName("MainThread");
Thread t = new Thread(this,
"RacingThread");
t.start();
a.foo(b); // get lock on a in this
thread.
System.out.println("Back in main
thread");
}
public void run() {
b.bar(a); // get lock on b in other
thread.
System.out.println("Back in other
thread");
}
public static void main(String args[]) {
new Deadlock();
}
}
|
Here is
some output from this program:
|
MainThread entered
A.foo
RacingThread entered
B.bar
MainThread trying to
call B.last()
RacingThread trying
to call A.last()
|
Because the
program has deadlocked, you need to press CTRL-C to end the program. You can
see a full thread and monitor cache dump by pressing CTRL-BREAK on a PC.
You will
see that RacingThread owns the monitor on b, while it is waiting for the
monitor on a. At the same time, MainThread owns a and is waiting
to get b. This program will never complete.
As this
example illustrates, if your multithreaded program locks up occasionally,
deadlock is one of the first conditions that you should check for.
Ordering
Locks:
A common
threading trick to avoid the deadlock is to order the locks. By ordering the
locks, it gives threads a specific order to obtain multiple locks.
Deadlock
Example:
Following
is the depiction of a dead lock:
|
// File Name
ThreadSafeBankAccount.java
public class
ThreadSafeBankAccount
{
private double balance;
private int number;
public ThreadSafeBankAccount(int num,
double initialBalance)
{
balance = initialBalance;
number = num;
}
public int getNumber()
{
return number;
}
public double getBalance()
{
return balance;
}
public void deposit(double amount)
{
synchronized(this)
{
double prevBalance = balance;
try
{
Thread.sleep(4000);
}catch(InterruptedException e)
{}
balance = prevBalance + amount;
}
}
public void withdraw(double amount)
{
synchronized(this)
{
double prevBalance = balance;
try
{
Thread.sleep(4000);
}catch(InterruptedException e)
{}
balance = prevBalance - amount;
}
}
}
// File Name
LazyTeller.java
public class
LazyTeller extends Thread
{
private ThreadSafeBankAccount source,
dest;
public LazyTeller(ThreadSafeBankAccount a,
ThreadSafeBankAccount b)
{
source = a;
dest = b;
}
public void run()
{
transfer(250.00);
}
public void transfer(double amount)
{
System.out.println("Transferring
from "
+ source.getNumber() + " to
" + dest.getNumber());
synchronized(source)
{
Thread.yield();
synchronized(dest)
{
System.out.println("Withdrawing
from "
+ source.getNumber());
source.withdraw(amount);
System.out.println("Depositing into "
+ dest.getNumber());
dest.deposit(amount);
}
}
}
}
public class
DeadlockDemo
{
public static void main(String [] args)
{
System.out.println("Creating two
bank accounts...");
ThreadSafeBankAccount checking =
new
ThreadSafeBankAccount(101, 1000.00);
ThreadSafeBankAccount savings =
new
ThreadSafeBankAccount(102, 5000.00);
System.out.println("Creating two
teller threads...");
Thread teller1 = new LazyTeller(checking,
savings);
Thread teller2 = new
LazyTeller(savings, checking);
System.out.println("Starting both
threads...");
teller1.start();
teller2.start();
}
}
|
This would
produce following result:
|
Creating two bank
accounts...
Creating two teller
threads...
Starting both
threads...
Transferring from
101 to 102
Transferring from
102 to 101
|
The problem
with the LazyTeller class is that it does not consider the possibility of a
race condition, a common occurrence in multithreaded programming.
After the
two threads are started, teller1 grabs the checking lock and teller2 grabs the
savings lock. When teller1 tries to obtain the savings lock, it is not
available. Therefore, teller1 blocks until the savings lock becomes available.
When the teller1 thread blocks, teller1 still has the checking lock and does
not let it go.
Similarly,
teller2 is waiting for the checking lock, so teller2 blocks but does not let go
of the savings lock. This leads to one result: deadlock!
Deadlock
Solution Example:
Here
transfer() method, in a class named OrderedTeller, in stead of arbitrarily
synchronizing on locks, this transfer() method obtains locks in a specified
order based on the number of the bank account.
|
// File Name
ThreadSafeBankAccount.java
public class
ThreadSafeBankAccount
{
private double balance;
private int number;
public ThreadSafeBankAccount(int num,
double initialBalance)
{
balance = initialBalance;
number = num;
}
public int getNumber()
{
return number;
}
public double getBalance()
{
return balance;
}
public void deposit(double amount)
{
synchronized(this)
{
double prevBalance = balance;
try
{
Thread.sleep(4000);
}catch(InterruptedException e)
{}
balance = prevBalance + amount;
}
}
public void withdraw(double amount)
{
synchronized(this)
{
double prevBalance = balance;
try
{
Thread.sleep(4000);
}catch(InterruptedException e)
{}
balance = prevBalance - amount;
}
}
}
// File Name
OrderedTeller.java
public class
OrderedTeller extends Thread
{
private ThreadSafeBankAccount source,
dest;
public OrderedTeller(ThreadSafeBankAccount
a,
ThreadSafeBankAccount
b)
{
source = a;
dest = b;
}
public void run()
{
transfer(250.00);
}
public void transfer(double amount)
{
System.out.println("Transferring
from " + source.getNumber()
+ " to " +
dest.getNumber());
ThreadSafeBankAccount first, second;
if(source.getNumber() <
dest.getNumber())
{
first = source;
second = dest;
}
else
{
first = dest;
second = source;
}
synchronized(first)
{
Thread.yield();
synchronized(second)
{
System.out.println("Withdrawing from "
+ source.getNumber());
source.withdraw(amount);
System.out.println("Depositing into "
+ dest.getNumber());
dest.deposit(amount);
}
}
}
}
// File Name
DeadlockDemo.java
public class
DeadlockDemo
{
public static void main(String [] args)
{
System.out.println("Creating two
bank accounts...");
ThreadSafeBankAccount checking =
new
ThreadSafeBankAccount(101, 1000.00);
ThreadSafeBankAccount savings =
new
ThreadSafeBankAccount(102, 5000.00);
System.out.println("Creating two
teller threads...");
Thread teller1 = new
OrderedTeller(checking, savings);
Thread teller2 = new OrderedTeller(savings,
checking);
System.out.println("Starting both
threads...");
teller1.start();
teller2.start();
}
}
|
This would
remove deadlock problem and would produce following result:
|
Creating two bank
accounts...
Creating two teller threads...
Starting both
threads...
Transferring from
101 to 102
Transferring from
102 to 101
Withdrawing from 101
Depositing into 102
Withdrawing from 102
Depositing into 101
|
