Deadlock Example - Transferring Funds

This section provides a Java program that simulates the deadlock example - Transferring Funds.

Another illustration of the deadlock problem is the following program, which simulates multiple threads taking transactions to transfer funds among different accounts.

```/* FundTransfer.java
*/
import java.util.*;
public class FundTransfer {
public static final int numberOfAccounts = 50; // number of accounts
public static long[] balance = new long[numberOfAccounts];
public static Random randomGenerator = new Random();
private static final int numberOfThreads = 10;
private static Object[] lockList = new Object[numberOfAccounts];
public static void main(String[] a) {
for (int i=0; i<numberOfAccounts; i++)
lockList[i] = new Object();
for (int i=0; i<numberOfAccounts; i++)
balance[i] = 100000;
for (int i=0; i<numberOfThreads; i++) {
t.start();
}
System.out.print("\nNumber of transactions performed per thread:");
long steps = 0;
while (true) {
steps++;
System.out.print("\nStep="+steps+": ");
for (int i=0; i<numberOfThreads; i++)
try {
} catch (InterruptedException e) {
System.out.println("Interrupted.");
}
}
}
public static boolean doTransfer(int i, int j, long a) {
boolean ok = false;
synchronized (lockList[i]) {
long c = balance[i]; // get balance of the from-account
ok = c-a>=0;
if (ok) { // stop account balance going negative
try {
Thread.sleep(0,1); // slow down the process
} catch (InterruptedException e) {
}
synchronized (lockList[j]) {
long d = balance[j]; // get balance of the to-account
ok = d+a>=0;
if (ok) { // stop account balance going negative
balance[i] = c-a; // update the from-account
balance[j] = d+a; // update the to-account
}
}
}
}
return ok;
}
public static class TransferThread extends Thread {
public long counts;
super(g,n);
counts = 0;
}
public void run() {
while (!isInterrupted()) {
counts++;
Random r = randomGenerator;
int m = numberOfAccounts;
int i = r.nextInt(m); // from-account number
int j = r.nextInt(m); // to-account number
int t = 2*r.nextInt(2)-1; // type of transaction
long a = (long) t*r.nextInt(10000);
if (i!=j) doTransfer(i,j,a);
try {
sleep(r.nextInt(200)); // pause between transactions
} catch (InterruptedException e) {
break;
}
}
}
}
}
```

The logic of the program is simple. The main thread launches 10 sub threads at the beginning, and allows each thread to repeatedly transfer some fund from a randomly selected account to another randomly selected account. The main thread keeps checking the number of transactions each thread has performed so far.

If it happens that one thread is transferring fund from account A to B, and another thread is transferring fund from account B to A at the same time, the two threads will become deadlock to each other. Then, if another thread is trying to transfer fund from account C to A or B, it will be put on hold also, because A and B are both locked. Account C will be locked also in this case. If another thread is trying to transfer fund from A or B to D, it will also be put on hold, but account D will not be locked. Slowly, all threads will be put on hold, because of the two deadlocked threads.

Execute the program several times. You will see that it behaves differently each time. But soon or later, the all threads will be put on hold as predicted. One of my executions gave the following output:

```Number of transactions performed per thread:
Step=1: 0 0 0 0 0 0 1 1 1 1
Step=2: 2 2 2 4 3 3 2 2 6 2
Step=3: 5 3 4 6 4 6 3 4 10 4
Step=4: 6 5 5 8 6 11 4 6 13 6
Step=5: 8 8 8 11 8 14 5 7 14 7
Step=6: 9 10 10 13 9 16 7 10 15 8
Step=7: 11 12 12 14 12 18 10 12 18 11
Step=8: 14 14 15 17 13 20 12 14 21 12
Step=9: 15 15 17 19 17 22 14 17 23 15
Step=10: 18 16 19 20 18 23 16 21 24 18
......
Step=813: 1613 1652 1607 1605 1627 1606 1613 1623 1601 1647
Step=814: 1616 1653 1611 1606 1630 1608 1615 1624 1604 1649
Step=815: 1617 1656 1615 1608 1631 1610 1616 1626 1607 1651
Step=816: 1619 1658 1617 1613 1633 1611 1619 1627 1608 1653
Step=817: 1621 1660 1617 1614 1633 1613 1621 1629 1610 1655
^1        ^2
Step=818: 1622 1660 1617 1615 1633 1614 1623 1632 1612 1656
^3
Step=819: 1623 1660 1617 1615 1633 1615 1625 1634 1613 1657
^4
Step=820: 1624 1660 1617 1615 1633 1617 1627 1636 1615 1659
Step=821: 1624 1660 1617 1615 1633 1617 1629 1638 1617 1662
^5                       ^6
Step=822: 1624 1660 1617 1615 1633 1617 1630 1640 1621 1664
Step=823: 1624 1660 1617 1615 1633 1617 1631 1641 1624 1666
Step=824: 1624 1660 1617 1615 1633 1617 1632 1643 1626 1667
Step=825: 1624 1660 1617 1615 1633 1617 1632 1645 1627 1668
^7
Step=826: 1624 1660 1617 1615 1633 1617 1632 1647 1628 1668
^8
Step=827: 1624 1660 1617 1615 1633 1617 1632 1647 1628 1668
^9   ^10
```

As you can see, threads 3 and 5 became deadlocked at step 817. Then within 10 steps, all other 8 threads were stopped.