Proving the following code not thread safe

Question

Hi,

How can I quickly prove that the following class is not thread-safe (as it uses Lazy Initialization and not using synchronization) by writing some code ? In other words, if I am testing the following class for thread safety, how can I fail it?

public class LazyInitRace {
  private ExpensiveObject instance = null;

  public ExpensiveObject getInstance() {
     if (instance == null)
        instance = new ExpensiveObject();
    return instance;
  }
}

Answer 1

Can you force ExpensiveObject to take a long time to construct within your test? If so, just call getInstance() twice from two different threads, in a short enough time that the first constructor won't have completed before the second call is made. You will end up with two different instances being constructed, which is where you should fail.

Making naive double-checked locking fail will be harder, mind you... (even though it's not safe without specifying volatile for the variable).

Answer 2

Well, it is not thread safe. Proofing of thread safety is random but rather simple:

1. Make ExpensiveObject constructor fully safe:

   synchronized ExpensiveObject(){ ...

2. Place to constructor code that checks if another copy of object exists - then raise an exception.

3. Create thread safe method to clear 'instance' variable

4. Place sequential code of getInstance/clearInstance to loop for execution by multiple threads and wait exception from (2)

Answer 3

By definition, race conditions cannot be tested deterministically, unless you control the thread scheduler (which you don't). The closest thing you can do is either to add a configurable delay in the getInstance() method, or write code where the problem might manifest and run it thousands of times in a loop.

BTW, none of this really constitutes "proof". Formal Verification would, but is very, very hard to do, even for relatively small amounts of code.

Answer 4

Put a really long calculation in the constructor:

public ExpensiveObject()
{
    for(double i = 0.0; i < Double.MAX_VALUE; ++i)
    {
        Math.pow(2.0,i);
    }
}

You might want to decrease the termination condition to Double.MAX_VALUE/2.0 or divide by a larger number if MAX_VALUE is taking too long for your liking.

Answer 5

Well... The result of this code will be false, where you expect for a true.

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.FutureTask;

public class LazyInitRace {

    public class ExpensiveObject {
        public ExpensiveObject() {
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
            }
        }
    }

    private ExpensiveObject instance = null;

    public ExpensiveObject getInstance() {
        if (instance == null)
            instance = new ExpensiveObject();
        return instance;
    }

    public static void main(String[] args) {
        final LazyInitRace lazyInitRace = new LazyInitRace();

        FutureTask<ExpensiveObject> target1 = new FutureTask<ExpensiveObject>(
                new Callable<ExpensiveObject>() {

                    @Override
                    public ExpensiveObject call() throws Exception {
                        return lazyInitRace.getInstance();
                    }
                });
        new Thread(target1).start();

        FutureTask<ExpensiveObject> target2 = new FutureTask<ExpensiveObject>(
                new Callable<ExpensiveObject>() {

                    @Override
                    public ExpensiveObject call() throws Exception {
                        return lazyInitRace.getInstance();
                    }
                });
        new Thread(target2).start();

        try {
            System.out.println(target1.get() == target2.get());
        } catch (InterruptedException e) {
        } catch (ExecutionException e) {
        }
    }
}

Answer 6

Since this is Java, you can use the thread-weaver library to inject pauses or breaks into your code and control multiple threads of execution. This way you can get a slow ExpensiveObject constructor without having to modify the constructor code, as other have (correctly) suggested.

Answer 7

This isn't using code, but here's an example of how I'd prove it. I forget the standard format for execution diagrams like this, but the meaning should be obvious enough.

| Thread 1              | Thread 2              |
|-----------------------|-----------------------|
| **start**             |                       |
| getInstance()         |                       |
| if(instance == null)  |                       |
| new ExpensiveObject() |                       |
| **context switch ->** | **start**             |
|                       | getInstance()         |
|                       | if(instance == null)  | //instance hasn't been assigned, so this check doesn't do what you want
|                       | new ExpensiveObject() |
| **start**             | **<- context switch** |
| instance = result     |                       |
| **context switch ->** | **start**             |
|                       | instance = result     |
|                       | return instance       |
| **start**             | **<- context switch** |
| return instance       |                       |

Answer 8

You can prove it easily with the debugger.

1. Write a program that calls getInstance() on two separate threads.
2. Set a breakpoint on the construction of the ExpensiveObject. Make sure the debugger will only suspend the thread, not the VM.
3. Then when the first thread stops on the breakpoint, leave it suspended.
4. When the second thread stops, you simply continue.
5. If you check the the result of the getInstance() call for both threads, they will be referring to different instances.

The advantage of doing it this way, is that you don't actually need an ExpensiveObject, any Object will in fact produce the same results. You are simply using the debugger to schedule the execution of that particular line of code and thus creating a deterministic result.