Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to test AtomicBoolean atomicity?

I'm writing unit tests for AtomicInteger and AtomicBoolean. They are going to be used as reference tests for testing emulations of these classes in objective-c, for use in translated projects.

The AtomicInteger test worked out well I think, basically by performing a predictable number of increment, decrement, add and subtract operations in a large number of for loops, each running in their own thread (and many threads per operation type). The actual operations start simultaneously using a CountDownLatch.

When all threads are done I assert by comparing the atomic integer with the expected integer value based on the number of threads, iterations per thread and the expected increase/decrease per iteration. This test passes.

But how to test AtomicBoolean? The basic operations are get and set so calling that many times in many threads and expecting the final result to be either true or false doesn't seem to make sense. The direction I'm thinking is to use two AtomicBooleans that should always have opposite values. Like this:

@Test
public void testAtomicity() throws Exception {

    // ====  SETUP  ====
    final AtomicBoolean booleanA = new AtomicBoolean(true);
    final AtomicBoolean booleanB = new AtomicBoolean(false);

    final int threadCount = 50;

    final int iterationsPerThread = 5000;

    final CountDownLatch startSignalLatch = new CountDownLatch(1);
    final CountDownLatch threadsFinishedLatch = new CountDownLatch(threadCount);

    final AtomicBoolean assertFailed = new AtomicBoolean(false);

    // ====  EXECUTE: start all threads ====
    for (int i = 0; i < threadCount; i++) {

        // ====  Create the thread  =====
        AtomicOperationsThread thread;
        thread = new AtomicOperationsThread("Thread #" + i, booleanA, booleanB, startSignalLatch, threadsFinishedLatch, iterationsPerThread, assertFailed);
        System.out.println("Creating Thread #" + i);

        // ====  Start the thread (each thread will wait until the startSignalLatch is triggered)  =====
        thread.start();
    }

    startSignalLatch.countDown();

    // ====  VERIFY: that the AtomicInteger has the expected value after all threads have finished  ====
    final boolean allThreadsFinished;
    allThreadsFinished = threadsFinishedLatch.await(60, TimeUnit.SECONDS);

    assertTrue("Not all threads have finished before reaching the timeout", allThreadsFinished);
    assertFalse(assertFailed.get());

}

private static class AtomicOperationsThread extends Thread {

    // #####  Instance variables  #####

    private final CountDownLatch startSignalLatch;
    private final CountDownLatch threadsFinishedLatch;

    private final int iterations;

    private final AtomicBoolean booleanA, booleanB;

    private final AtomicBoolean assertFailed;

    // #####  Constructor  #####

    private AtomicOperationsThread(final String name, final AtomicBoolean booleanA, final AtomicBoolean booleanB, final CountDownLatch startSignalLatch, final CountDownLatch threadsFinishedLatch, final int iterations, final AtomicBoolean assertFailed) {

        super(name);
        this.booleanA = booleanA;
        this.booleanB = booleanB;
        this.startSignalLatch = startSignalLatch;
        this.threadsFinishedLatch = threadsFinishedLatch;
        this.iterations = iterations;
        this.assertFailed = assertFailed;
    }

    // #####  Thread implementation  #####

    @Override
    public void run() {

        super.run();

        // ====  Wait for the signal to start (so all threads are executed simultaneously)  =====
        try {
            System.out.println(this.getName() + " has started. Awaiting startSignal.");
            startSignalLatch.await();  /* Awaiting start signal */
        } catch (InterruptedException e) {
            throw new RuntimeException("The startSignalLatch got interrupted.", e);
        }

        // ====  Perform the atomic operations  =====
        for (int i = 0; i < iterations; i++) {

            final boolean booleanAChanged;
            booleanAChanged = booleanA.compareAndSet(!booleanB.get(), booleanB.getAndSet(booleanA.get()));  /* Set A to the current value of B if A is currently the opposite of B, then set B to the current value of A */

            if (!booleanAChanged){
                assertFailed.set(true);
                System.out.println("Assert failed in thread: " + this.getName());
            }
        }

        // ====  Mark this thread as finished  =====
        threadsFinishedLatch.countDown();
    }
}

This works with one thread but fails with multiple. I guess this is because booleanAChanged = booleanA.compareAndSet(!booleanB.get(), booleanB.getAndSet(booleanA.get())); is not one atomic operation.

Any suggestions?

like image 415
Rolf W. Avatar asked Jul 01 '13 22:07

Rolf W.


3 Answers

I would concentrate on compareAndSet, which is the real difference between an AtomicBoolean and an ordinary boolean.

For example, use compareAndSet(false, true) to control a critical region. Loop doing it until it returns false, then enter the critical region. In the critical region, do something that is very likely to fail if two or more threads run it at the same time. For example, increment a counter with a short sleep between reading the old value and writing the new value. At the end of the critical region, set the AtomicBoolean to false.

Initialize the AtomicBoolean to false, and globalCounter to zero before starting the threads.

for(int i=0; i<iterations; i++) {
  while (!AtomicBooleanTest.atomic.compareAndSet(false, true));
  int oldValue = AtomicBooleanTest.globalCounter;
  Thread.sleep(1);
  AtomicBooleanTest.globalCounter = oldValue + 1;
  AtomicBooleanTest.atomic.set(false);
}

At the end, the globalCounter value should be t*iterations where t is the number of threads.

The number of threads should be similar to the number the hardware can run simultaneously - and this is far more likely to fail on a multiprocessor than on a single processor. The highest risk of failure is immediately after the AtomicBoolean becomes false. All available processors should be simultaneously trying to get exclusive access to it, see it to be false, and atomically change it to true.

like image 129
Patricia Shanahan Avatar answered Nov 15 '22 22:11

Patricia Shanahan


I think it's going to be harder to test this than an AtomicInteger, as you point out. The space of possible values is much smaller, and thus the space of possible things-that-can-go-wrong is much smaller. Since tests like this basically come down to luck (with lots of looping to increase your chances), it's going to be harder to hit that smaller target.

My recommendation would be to launch a lot of threads that have access to a single AtomicBoolean. Have each one of them do a CAS, and only if they succeed, atomically increment an AtomicInteger. When all the threads have finished, you should see just a single increment to that AtomicInteger. Then just rinse, lather, repeat.

like image 39
yshavit Avatar answered Nov 16 '22 00:11

yshavit


It is four atomic operations. Given you just want one boolean to be the inverse of the other, just have one boolean and keep toggling that. You can calculate the other from this value.

like image 1
Peter Lawrey Avatar answered Nov 15 '22 22:11

Peter Lawrey