152The Law of the Corrupt Politician

Author: Dr. Heinz M. KabutzDate: 2007-11-12Java Version: 5Category: Concurrency

Abstract: Corruption has a habit of creeping into system that do not have adequate controls over their threads. In this law, we look at how we can detect data races and some ideas to avoid and fix them.

Welcome to the 152nd issue of The Java(tm) Specialists' Newsletter, sent from a cold and windy island in the Mediterranean. We drove down to our favourite beach today, to let the children climb the trees and go wild on the sand. A lone Greek, Apostolis, who of his own accord keeps the beach spotlessly clean, was the only one brave enough to go for a swim. When the rain started to come down, we decided to rather head for our dry house, so here I am putting the finishing touches to this newsletter :-)

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

The Law of the Corrupt Politician

We are looking at a series of laws to make sense of Java concurrency. Just to remind you, here they are again. In this newsletter, we will look at the Law of the Corrupt Politician.

1. The Law of the Sabotaged Doorbell
2. The Law of the Distracted Spearfisherman
3. The Law of the Overstocked Haberdashery
4. The Law of the Blind Spot
5. The Law of the Leaked Memo
6. The Law of the Corrupt Politician
7. The Law of the Micromanager
8. The Law of Cretan Driving
9. The Law of Sudden Riches
10. The Law of the Uneaten Lutefisk
11. The Law of the Xerox Copier

The Law of the Corrupt Politician

In a letter written in 1887, Lord Acton, famous historian, wrote: "Power tends to corrupt, and absolute power corrupts absolutely."

When we start programming threads, we wield a lot of power, perhaps more than is good for us. We need to make sure that we put controls in the right places to stop data races from corrupting our object state.

Here is one of my favourite examples for showing the effects of data races causing corrupted object state:

public class BankAccount {
  private int balance;
  public BankAccount(int balance) {
    this.balance = balance;
  }
  public void deposit(int amount) {
    balance += amount;
  }
  public void withdraw(int amount) {
    deposit(-amount);
  }
  public int getBalance() { return balance; }
}

One of the problems with this code is that the += operation is not atomic.

We start with a BankAccount containing $1000. Let us now imagine that two threads are calling deposit and withdraw at the same time. Thread 1 is scheduled to run first and adds $100 to the account, thus updating the balance to $1100. Thread 2 is then scheduled to run, it withdraws $100, and writes the final balance of $1000 back to balance.

However, there are also other effects that might become visible. Since we have no concurrency controls around our code, Thread 1 could start, get the balance field value, but before writing the new value, get swapped out. Thread 2 could now come in, read the old value of $1000, withdraw $100 and write the final value of $900 into the field. Thread 1 would now start up again, not realising that the value has changed, overwrite the value $900 with its own $1100.

You can see the effects of data races very quickly with this test class. Be careful however, since some of the effects seen could also be due to The Law of the Blind Spot or The Law of the Leaked Memo

import java.util.concurrent.CountDownLatch;
import java.util.*;

public class TestCorruption {
  private static final int THREADS = 2;
  private static final CountDownLatch latch =
      new CountDownLatch(THREADS);
  private static final BankAccount heinz =
      new BankAccount(1000);

  public static void main(String[] args) {
    for (int i = 0; i < THREADS; i++) {
      addThread();
    }
    Timer timer = new Timer(true);
    timer.schedule(new TimerTask() {
      public void run() {
        System.out.println(heinz.getBalance());
      }
    }, 100, 1000);
  }

  private static void addThread() {
    new Thread() {
      { start(); } 
      public void run() {
        latch.countDown();
        try {
          latch.await();
        } catch (InterruptedException e) {
          return;
        }
        while (true) {
          heinz.deposit(100);
          heinz.withdraw(100);
        }
      }
    };
  }
}

Before I propose a fix, I would like to discuss how you can detect data races. Unfortunately, I do not know of any easy solution. You could possibly instrument the JVM to detect when an object is modified from two threads, but this type of problem usually occurs in production under heavy load. It is not easy to diagnose. There are some tell-tale signs though:

• NullPointerException: when you see this in code that you would definitely not expect, have a look whether you might have encountered a race condition.
• Broken Assertions: when our postconditions fail, it could be a race condition.
• Corrupt Data Structures: a XML DOM tree that suddenly becomes corrupt, could quite possibly be a race condition on the nodes in the tree.

As a first step, we should perhaps add assertions to make sure that if it goes wrong, we know about it early on. I do not like the idea that you can switch off an assertion, but prefer the Pragmatic Programmer approach, where we leave them on, even in production. You need to then handle the assertion correctly if it fails:

public class BankAccount {
  private int balance;
  public BankAccount(int balance) {
    this.balance = balance;
  }
  public void deposit(int amount) {
    int check = balance + amount;
    balance = check;
    if (balance != check) {
      throw new AssertionError("Data Race Detected");
    }
  }
  public void withdraw(int amount) {
    deposit(-amount);
  }
  public int getBalance() { return balance; }
}

Interestingly, the assertion never fires on my machine, though it might well happen on your machine. My suspicion is that this is due to the local caching of the balance field (The Law of the Blind Spot). Let's eliminate that possibility by making balance volatile.

public class BankAccount {
  private volatile int balance;
  public BankAccount(int balance) {
    this.balance = balance;
  }
  public void deposit(int amount) {
    int check = balance + amount;
    balance = check;
    if (balance != check) {
      throw new AssertionError("Data Race Detected");
    }
  }
  public void withdraw(int amount) {
    deposit(-amount);
  }
  public int getBalance() { return balance; }
}

Now I can see the assertion failing very quickly:

1000
1100
Exception in thread "Thread-1" AssertionError: Data Race Detected
	at BankAccount.deposit(BankAccount.java:10)
	at BankAccount.withdraw(BankAccount.java:14)
	at TestCorruption$2.run(TestCorruption.java:38)
1000
1000
1000
1100

We are now at the point where we can look at some solutions to solve this problem. If we are running in an application server, we could set appropriate transaction isolation levels to avoid multiple threads calling the method at the same time.

Pre-Java 5, we used the synchronized mechanism to mark the critical section. If we use any sort of locking, we do not need to make the field volatile. Unfortunately, programmers have fallen into the habit of synchronizing on this, which is usually a bad idea. There is at least one other place in your code with a reference to your object, otherwise it would get garbage collected. If that other place also synchronizes on your object, you could see all sorts of strange liveness issues. A much better approach is to synchronize on a private final object:

public class BankAccount {
  private int balance;
  private final  Object lock = new Object();
  public BankAccount(int balance) {
    this.balance = balance;
  }
  public void deposit(int amount) {
    synchronized(lock) {
      int check = balance + amount;
      balance = check;
      if (balance != check) {
        throw new AssertionError("Data Race Detected");
      }
    }
  }
  public void withdraw(int amount) {
    deposit(-amount);
  }
  public int getBalance() {
    synchronized(lock) {
      return balance;
    }
  }
}

To avoid visibility problems with balance, we synchronize the getBalance() method. Visibility problems could also be solved by keeping balance volatile.

The test class now prints either 1000, 1100 or 1200.

There are some issues with using standard Java locks. First off, you can never interrupt a thread that is blocked on a lock. This makes it impossible to shut down a deadlocked application cleanly.

To illustrate, we can use the Java 5 ReentrantLock to lock the critical section.

import java.util.concurrent.locks.*;

public class BankAccount {
  private int balance;
  private final Lock lock = new ReentrantLock();

  public BankAccount(int balance) {
    this.balance = balance;
  }

  public void deposit(int amount) throws InterruptedException {
    lock.lockInterruptibly();
    try {
      int check = balance + amount;
      balance = check;
      if (balance != check) {
        throw new AssertionError("Data Race Detected");
      }
    } finally {
      lock.unlock();
    }
  }

  public void withdraw(int amount) throws InterruptedException {
    deposit(-amount);
  }

  public int getBalance() throws InterruptedException {
    lock.lockInterruptibly();
    try {
      return balance;
    } finally {
      lock.unlock();
    }
  }
}

Another nice feature of the Java 5 locks is that you can differentiate between reads and writes. This is particularly useful when you have lots of threads reading concurrently, but only a few writing. The reads do not block each other, but the writes have exclusive access to the critical section. Here is how you could use it:

import java.util.concurrent.locks.*;

public class BankAccount {
  private int balance;
  private final ReadWriteLock lock =
      new ReentrantReadWriteLock();

  public BankAccount(int balance) {
    this.balance = balance;
  }

  public void deposit(int amount) throws InterruptedException {
    lock.writeLock().lockInterruptibly();
    try {
      int check = balance + amount;
      balance = check;
      if (balance != check) {
        throw new AssertionError("Data Race Detected");
      }
    } finally {
      lock.writeLock().unlock();
    }
  }

  public void withdraw(int amount) throws InterruptedException {
    deposit(-amount);
  }

  public int getBalance() throws InterruptedException {
    lock.readLock().lockInterruptibly();
    try {
      return balance;
    } finally {
      lock.readLock().unlock();
    }
  }
}

Note that it is easy to write a microbenchmark that shows that using the ReadWriteLock is slower than simply using the synchronized keyword. It is important to remember the effects that contention can have on system throughput.

Kind regards from Greece

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive