Testing concurrent code

Code in:JavaC#PythonJavaScript

In short: Concurrent code is tested with a stress test of many runs, a start barrier, forced interleavings and an invariant check, because one green run proves nothing.

Problem

It passes on my machine

The sales counter from the lesson on race conditions has no lock. A colleague writes a test: four threads sell 1000 times each, and at the end the number sold must be 4000:

int sold = 0;

bool LostSales()
{
    sold = 0;
    var threads = new List<Thread>();
    for (int i = 0; i < 4; i++)
    {
        var t = new Thread(() =>
        {
            for (int k = 0; k < 1_000; k++)
            {
                sold++;
            }
        });
        t.Start();
        threads.Add(t);
    }
    foreach (var t in threads)
    {
        t.Join();
    }
    return sold != 4_000;
}

LostSales();
Console.WriteLine("Sold (expected 4000):");
Console.WriteLine(sold);

Output

Sold (expected 4000):
4000

For them the test passes. It passes in CI too. The code goes into the sale, and in the first hour the shop has sold more items than the counter shows.

Creating a thread takes longer than 1000 increments. The first thread has often finished before the last one has started, and the threads do not overlap at all.

One green test of concurrent code proves almost nothing: in this run the threads just did not meet exactly between the read and the write. How do you write a test that catches such a bug?

The idea

A stress test: many runs and a barrier

Three things make the bug visible:

• Many runs. The test is not one run but 20 (or 1000 in a nightly CI job). You count how many are red.
• Many threads at once. More threads than cores, so that they switch in the middle of the work.
• A barrier at the start. Each thread waits until all have arrived, and they start together. That way they overlap the whole time, not only at the end.

int sold = 0;

bool LostSales()
{
    sold = 0;
    var threads = new List<Thread>();
    for (int i = 0; i < 4; i++)
    {
        var t = new Thread(() =>
        {
            for (int k = 0; k < 1_000; k++)
            {
                sold++;
            }
        });
        t.Start();
        threads.Add(t);
    }
    foreach (var t in threads)
    {
        t.Join();
    }
    return sold != 4_000;
}

Step by step, in words

1. The test starts 4 threads, each sells 1000 times without a lock. Without a barrier, each thread starts as soon as it is created.
2. 20 runs: in this example 0 of 20 red. A thread often finishes its 1000 sales before the next one has started.
3. A barrier: each thread waits at the start until all four have arrived. Then they run together.
4. 20 runs with the barrier: 13 of 20 red. The same broken counter, but now the test catches it again and again.

The test with a barrier:

int sold = 0;

bool LostSales()
{
    sold = 0;
    var start = new Barrier(4);
    var threads = new List<Thread>();
    for (int i = 0; i < 4; i++)
    {
        var t = new Thread(() =>
        {
            start.SignalAndWait(TimeSpan.FromSeconds(1));
            for (int k = 0; k < 1_000; k++)
            {
                sold++;
            }
        });
        t.Start();
        threads.Add(t);
    }
    foreach (var t in threads)
    {
        t.Join();
    }
    return sold != 4_000;
}

int failed = 0;
for (int run = 0; run < 20; run++)
{
    if (LostSales())
    {
        failed++;
    }
}
Console.WriteLine("Runs that lost sales (of 20):");
Console.WriteLine(failed);

Output

Runs that lost sales (of 20):
20

The output is "at most 20": how many runs turn red depends on the machine. On my machine (in the container where the programs are checked) without a barrier it is 0 of 20, with a barrier about 13.

Barrier(4): SignalAndWait waits until 4 threads have called it, then lets them all go. The 1 second timeout keeps the test from hanging if a thread never arrives.

The same test against the counter with a lock:

int sold = 0;
object sync = new object();

bool LostSales()
{
    sold = 0;
    var start = new Barrier(4);
    var threads = new List<Thread>();
    for (int i = 0; i < 4; i++)
    {
        var t = new Thread(() =>
        {
            start.SignalAndWait(TimeSpan.FromSeconds(1));
            for (int k = 0; k < 1_000; k++)
            {
                lock (sync)
                {
                    sold++;
                }
            }
        });
        t.Start();
        threads.Add(t);
    }
    foreach (var t in threads)
    {
        t.Join();
    }
    return sold != 4_000;
}

Output

Runs that lost sales: 0 of 20

More precisely, if you are curious

A stress test finds bugs, but it does not prove there are none. "0 of 20" means "we did not see it this time". That is why in CI such tests run thousands of times, on machines with many cores, and code review asks separately: what is shared and which lock guards it.

How it is in the other languages: in Java the barrier is CyclicBarrier (or a CountDownLatch latch), in Python threading.Barrier, in Node you write it with Atomics.wait and Atomics.notify. Instead of a barrier, C# code often uses a latch: a ManualResetEventSlim that the main thread opens.

Try it

Find the bug

Another colleague wrote a stress test without a barrier. It passes 20 of 20 times, on every run, on every machine, even though the counter has no lock:

int sold = 0;

bool LostSales()
{
    sold = 0;
    for (int i = 0; i < 4; i++)
    {
        var t = new Thread(() =>
        {
            for (int k = 0; k < 1_000; k++)
            {
                sold++;
            }
        });
        t.Start();
        t.Join();
    }
    return sold != 4_000;
}

Output

Runs that lost sales: 0 of 20

Pick the line with the bug.

1int sold = 0;23bool LostSales()4{5 sold = 0;6 for (int i = 0; i < 4; i++)7 {8 var t = new Thread(() =>9 {10 for (int k = 0; k < 1_000; k++)11 {12 sold++;13 }14 });15 t.Start();16 t.Join();17 }18 return sold != 4_000;19}

Check

Try it

Fill in

Which line makes the threads start together?

int sold = 0;

bool LostSales()
{
    sold = 0;
    var start = new Barrier(4);
    var threads = new List<Thread>();
    for (int i = 0; i < 4; i++)
    {
        var t = new Thread(() =>
        {
            
            for (int k = 0; k < 1_000; k++)
            {
                sold++;
            }
        });
        t.Start();
        threads.Add(t);
    }
    foreach (var t in threads)
    {
        t.Join();
    }
    return sold != 4_000;
}

Check

The idea

Force the interleaving

A stress test finds the bug sometimes. For a test that fails every time, the test chooses the order of the threads itself. For that the code has a seam: a place where the test can stop the thread. In the real program the seam does nothing.

The scenario is the bug from the lesson on race conditions: 10 items are left, two buyers buy one each.

1. The first buyer reads 10 and stops at the seam.
2. The second buyer goes all the way: reads 10, writes 9.
3. The first one goes on and writes its 10 − 1 = 9.

string ForcedTest(Stock stock)
{
    var read = new ManualResetEventSlim();
    var go = new ManualResetEventSlim();
    stock.Pause = () =>
    {
        if (Thread.CurrentThread.Name == "first")
        {
            read.Set();
            go.Wait(TimeSpan.FromSeconds(1));
        }
    };
    var first = new Thread(stock.Buy) { Name = "first" };
    var second = new Thread(stock.Buy) { Name = "second" };
    first.Start();
    read.Wait(TimeSpan.FromSeconds(1));   // first has read 10 and waits
    second.Start();
    second.Join(200);   // second buys to the end or waits for the lock
    go.Set();           // first writes
    first.Join(1000);
    second.Join(1000);
    string verdict = stock.Count == 8 ? "PASS" : "FAIL";
    return $"Stock: {stock.Count} (expected 8): {verdict}";
}

class Stock
{
    public int Count;
    public Action Pause = () => { };

    public Stock(int count) => Count = count;

    public void Buy()
    {
        int left = Count;
        Pause();   // a seam for the test: here the test can stop the thread
        Count = left - 1;
    }
}

Output

Stock: 9 (expected 8): FAIL

The seam is the field Pause. The test puts code in it that stops only the thread named first: it opens read and waits for go. A ManualResetEventSlim is a latch: Set() opens it, Wait waits for it to open, here at most 1 second.

The stock is 9 instead of 8, on every run. Now the fix: a lock around the read and the write:

class Stock
{
    public int Count;
    public Action Pause = () => { };
    private readonly object sync = new object();

    public Stock(int count) => Count = count;

    public void Buy()
    {
        lock (sync)
        {
            int left = Count;
            Pause();   // a seam for the test: here the test can stop the thread
            Count = left - 1;
        }
    }
}

Output

Stock: 8 (expected 8): PASS

The test is the same. The first buyer holds the lock while it is stopped at the seam. The second one waits for the lock, so second.Join(200) runs out before it has bought. Only when the first one writes 9 and releases the lock does the second one read 9 and write 8. A test that failed every time before the fix and passes every time after it is exactly what you want in CI.

Try it

Three at the seam

The same Stock without a lock. Now the seam waits until all three buyers have read the stock:

What will the program print?

var stock = new Stock(10);
var allRead = new CountdownEvent(3);
stock.Pause = () =>
{
    allRead.Signal();
    allRead.Wait(TimeSpan.FromSeconds(1));
};
var buyers = new List<Thread>();
for (int i = 0; i < 3; i++)
{
    var t = new Thread(stock.Buy);
    t.Start();
    buyers.Add(t);
}
foreach (var t in buyers)
{
    t.Join();
}
Console.WriteLine($"Stock: {stock.Count}");

Answer

Stock: 9

Stock: 7

Stock: 8

Check

The idea

Check the invariant, not the order

With 8 buyers, who bought what depends on the run. A test that expects "the first buyer bought 13" fails even with correct code. So the test checks an invariant: something that must be true in every order.

For the shop it is: the stock plus the number sold is what there was at the start, the stock is not below zero, and the buyers' purchases added up equal the number sold. 8 buyers make 50 attempts each for 100 items:

var shop = new Shop(100);
int[] bought = new int[8];
var start = new Barrier(8);
var buyers = new List<Thread>();
for (int i = 0; i < 8; i++)
{
    int me = i;
    var t = new Thread(() =>
    {
        start.SignalAndWait(TimeSpan.FromSeconds(1));
        for (int k = 0; k < 50; k++)
        {
            if (shop.TryBuy())
            {
                bought[me]++;
            }
        }
    });
    t.Start();
    buyers.Add(t);
}
foreach (var t in buyers)
{
    t.Join();
}
Console.WriteLine($"Stock: {shop.Stock}, sold: {shop.Sold}");
Console.WriteLine(Check("stock + sold = 100", shop.Stock + shop.Sold == 100));
Console.WriteLine(Check("stock >= 0", shop.Stock >= 0));
Console.WriteLine(Check("bought = sold", bought.Sum() == shop.Sold));

Output

Stock: 0, sold: 100
stock + sold = 100: PASS
stock >= 0: PASS
bought = sold: PASS

The shop:

class Shop
{
    private int stock;
    private int sold = 0;
    private readonly object sync = new object();

    public Shop(int stock) => this.stock = stock;

    public bool TryBuy()
    {
        lock (sync)
        {
            if (stock == 0) return false;
            stock--;
            sold++;
            return true;
        }
    }

    public int Stock { get { lock (sync) return stock; } }
    public int Sold { get { lock (sync) return sold; } }
}

Each thread writes to its own slot bought[me], so the array needs no lock. The total is right in every order; who bought how much is not fixed.

400 attempts for 100 items means the stock ends at 0 in every order. That is an invariant too, which is why the output is the same on every run.

The idea

A timeout: the deadlock fails the test

Two warehouses transfer goods to each other. Each transfer locks the warehouse it takes from, then the one it puts into, in opposite order. That is a deadlock: each thread holds one lock and waits for the other forever.

A test without a timeout does not fail: it hangs. CI waits an hour until it kills it, and nobody knows which test it was. So a test with threads always waits with a timeout:

object sofia = new object();
object plovdiv = new object();

void Transfer(object from, object to)
{
    lock (from)
    {
        Thread.Sleep(50);
        lock (to)
        {
            // move the goods
        }
    }
}

bool FinishesWithin(int ms, params ThreadStart[] parts)
{
    var threads = parts.Select(part => new Thread(part) { IsBackground = true }).ToList();
    threads.ForEach(t => t.Start());
    var end = DateTime.Now.AddMilliseconds(ms);
    foreach (var t in threads)
    {
        var left = end - DateTime.Now;
        t.Join(left > TimeSpan.Zero ? left : TimeSpan.FromMilliseconds(1));
    }
    return threads.All(t => !t.IsAlive);
}

bool ok = FinishesWithin(1000,
    () => Transfer(sofia, plovdiv),
    () => Transfer(plovdiv, sofia));
Console.WriteLine("Test \"transfer between warehouses\": " + (ok ? "PASS" : "did not finish in 1 s: FAIL"));

Output

Test "transfer between warehouses": did not finish in 1 s: FAIL

Join(TimeSpan) waits at most that long and returns whether the thread finished. IsBackground = true lets the program end even though the two threads are locked forever.

More precisely, if you are curious

Test frameworks have the timeout ready: [Fact(Timeout = 1000)] in xUnit (for async tests) or [Timeout] in NUnit. How to write a test in the language, see the lesson on testing.

There are also tools that look for these bugs for you. Here we only name them, without using them:

• jcstress (Java): runs small pieces of code millions of times in every order the JVM allows and counts the results.
• ThreadSanitizer (C, C++, Go, Rust) and Go's race detector (go test -race): watch every read and write during the test and say "these two threads touch the same thing without a lock", even if this time the result was right.
• Microsoft.Coyote (.NET): runs async and multithreaded code under its own scheduler, tries many orders, and can replay the order that failed.
• faulthandler (Python): when a test is stuck, prints where every thread is.

Exercise

A stress test for the register

Solve it in your own editor.

The sale's register has Sell(int euros). Write a stress test:

• 20 runs. In each, 4 threads with a barrier at the start; each one sells 500 times for €2. The expected total is €4000.
• A run in which the threads do not finish within 1 second counts as a timeout, and the test goes on.
• At the end print how many runs had a wrong total and how many a timeout, and whether the register passes.

Output

Runs: 20
With a wrong total: 0
With a timeout: 0
The register: PASS

More tasks

• Break the register. Remove the lock and see how many runs turn red. Run it a few times: the number changes.
• A forced interleaving. Add a seam in sell and write a test that fails every time without the lock and passes with it.
• A deadlock in the register. Add a second lock (the register and the warehouse) in opposite order and check that your test reports a timeout instead of hanging.

Test

Check yourself

1. The test of the counter without a lock passes. What does that mean?

The counter is safe on this machineThe counter is safeAlmost nothing: in this run the threads did not overlap

2. What is the barrier at the start of the stress test for?

To make the test fasterSo that all threads start together and overlapSo that the threads run one after another

3. The stress test passes 20 of 20 times. Is the code safe?

Yes, if the barrier was onYes, 20 runs are enoughNot proven: the test shows bugs, it does not prove there are none

4. How do you make a test fail every time on the same race condition?

More runsLatches in a seam of the code: the first thread stops between the read and the write until the second one is throughThread.sleep with different pauses

5. Why must a test with threads have a timeout?

To make it fasterOtherwise a deadlock makes the test hang forever and stops the whole CIBecause threads do not finish on their own

Check

Start the lesson over

Related lessons

• Builds on: Atomic operations and immutable objects · Deadlock · A pool of threads and tasks · async is not a thread
• Tasks on this topic: Concurrency and race conditions