Atomic thread counter

Question

I'm experimenting with the C++11 atomic primitives to implement an atomic "thread counter" of sorts. Basically, I have a single critical section of code. Within this code block, any thread is free to READ from memory. However, sometimes, I want to do a reset or clear operation, which resets all shared memory to a default initialized value.

This seems like a great opportunity to use a read-write lock. C++11 doesn't include read-write mutexes out of the box, but maybe something simpler will do. I thought this problem would be a great opportunity to become more familiar with C++11 atomic primitives.

So I thought through this problem for a while, and it seems to me that all I have to do is :

1. Whenever a thread enters the critical section, increment an atomic counter variable

2. Whenever a thread leaves the critical section, decrement the atomic counter variable

3. If a thread wishes to reset all variables to default values, it must atomically wait for the counter to be 0, then atomically set it to some special "clearing flag" value, perform the clear, then reset the counter to 0.

4. Of course, threads wishing to increment and decrement the counter must also check for the clearing flag.

So, the algorithm I just described can be implemented with three functions. The first function, increment_thread_counter() must ALWAYS be called before entering the critical section. The second function, decrement_thread_counter(), must ALWAYS be called right before leaving the critical section. Finally, the function clear() can be called from outside the critical section only iff the thread counter == 0.

This is what I came up with:

Given:

1. A thread counter variable, std::atomic<std::size_t> thread_counter
2. A constant clearing_flag set to std::numeric_limits<std::size_t>::max()

...

void increment_thread_counter()
{
    std::size_t expected = 0;
    while (!std::atomic_compare_exchange_strong(&thread_counter, &expected, 1))
    {
        if (expected != clearing_flag)
        {
            thread_counter.fetch_add(1);
            break;
        }
        expected = 0;
    }
}

void decrement_thread_counter()
{
    thread_counter.fetch_sub(1);
}

void clear()
{
    std::size_t expected = 0;
    while (!thread_counter.compare_exchange_strong(expected, clearing_flag)) expected = 0;

    /* PERFORM WRITES WHICH WRITE TO ALL SHARED VARIABLES */

    thread_counter.store(0);
}

As far as I can reason, this should be thread-safe. Note that the decrement_thread_counter function shouldn't require ANY synchronization logic, because it is a given that increment() is always called before decrement(). So, when we get to decrement(), thread_counter can never equal 0 or clearing_flag.

Regardless, since THREADING IS HARD™, and I'm not an expert at lockless algorithms, I'm not entirely sure this algorithm is race-condition free.

Question: Is this code thread safe? Are any race conditions possible here?

Palladium

Can you guarantee that only one thread wishes to reset the variables at a time? Otherwise you might have a deadlock. – Hoi

Multiple threads may wish to reset variables, but I'm not sure why you think a deadlock can occur. There are two "waiting" loops, and neither holds a resource that the other may need. – Palladium

You have just described the read-write lock in all its unimplementrd glory. – Webbed

Answer 1

You have a race condition; bad things happen if another thread changes the counter between increment_thread_counter()'s test for clearing_flag and the fetch_add.

I think this classic CAS loop should work better:

void increment_thread_counter()
{
    std::size_t expected = 0;
    std::size_t updated;
    do {
        if (expected == clearing_flag) {     // don't want to succeed while clearing, 
             expected = 0;      //take a chance that clearing completes before CMPEXC
        }

        updated = expected + 1;
        // if (updated == clearing_flag) TOO MANY READERS!
    } while (!std::atomic_compare_exchange_weak(&thread_counter, &expected, updated));
}

Caco

Can this be improved further by defaulting expected to thread_counter instead of 0? Or does that introduce yet another race condition I can't see? – Dna

@MarkB: You mean on the first iteration? Should be fine, as long as you use the appropriate interlocked read call (which is probably a simple read on most hardware). My answer is primarily concerned with correctness issue. – Caco

I was thinking first iteration and inside the loop in the if check (obviously using an interlocked read which might be optimized down to a simple read on most hardware as you noted). – Dna

@MarkB: Absolutely not. The primary purpose point of the if is to ensure that expected != clearing_flag, reading from thread_counter would defeat that. Also, if a clearing operation is in progress, 0 is the optimistic value for expected. – Caco

@MarkB: Plus, introducing another read to the contended variable thread_counter is no optimization. – Caco