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
 - Copyright (c) 2014, HerongYang.com, All Rights Reserved.
 */
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 TransferThread[] threadList =
      new TransferThread[numberOfThreads];
   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;
      ThreadGroup g = new ThreadGroup("The Group");
      for (int i=0; i<numberOfThreads; i++) {
         TransferThread t = new TransferThread(g,String.valueOf(i));
         t.start();
         threadList[i] = t;
      }
      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++)
            System.out.print(threadList[i].counts+" ");
         try {
            Thread.sleep(200); 
         } 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 accout balance going negative
            try {
               Thread.sleep(0,1); // slow down the process
            } catch (InterruptedException e) {
               Thread.currentThread().interrupt(); // re-set the flag
            }
            synchronized (lockList[j]) {
               long d = balance[j]; // get balance of the to-account
               ok = d+a>=0;
               if (ok) { // stop accout 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;
      public TransferThread(ThreadGroup g, String n) {
         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.

Last update: 2014.

Table of Contents

 About This Book

 Installing JDK 1.8 on Windows

 Execution Process, Entry Point, Input and Output

 Primitive Data Types and Literals

 Bits, Bytes, Bitwise and Shift Operations

 Managing Bit Strings in Byte Arrays

 Reference Data Types and Variables

 StringBuffer - The String Buffer Class

 System Properties and Runtime Object Methods

 Generic Classes and Parameterized Types

 Generic Methods and Type Inference

 Lambda Expressions and Method References

 Execution Threads and Multi-Threading Java Programs

 ThreadGroup Class and "system" ThreadGroup Tree

 Synchronization Technique and Synchronized Code Blocks

Deadlock Condition Example Programs

 What Is Deadlock?

 Deadlock Example - 5 Dining Philosophers

Deadlock Example - Transferring Funds

 Garbage Collection and the gc() Method

 Outdated Tutorials

 References

 PDF Printing Version