list::empty() multi-threaded behavior?

user_620863 0
Viewed 547

I have a list that I want different threads to grab elements from. In order to avoid locking the mutex guarding the list when it's empty, I check empty() before locking.

It's okay if the call to list::empty() isn't right 100% of the time. I only want to avoid crashing or disrupting concurrent list::push() and list::pop() calls.

Am I safe to assume VC++ and Gnu GCC will only sometimes get empty() wrong and nothing worse?

if(list.empty() == false){ // unprotected by mutex, okay if incorrect sometimes
    mutex.lock();
    if(list.empty() == false){ // check again while locked to be certain
         element = list.back();
         list.pop_back();
    }
    mutex.unlock();
}
stdlist race-condition optimization multithreading c++
3 Answers

It's okay if the call to list::empty() isn't right 100% of the time.

No, it is not okay. If you check if the list is empty outside of some synchronization mechanism (locking the mutex) then you have a data race. Having a data race means you have undefined behavior. Having undefined behavior means we can no longer reason about the program and any output you get is "correct".

If you value your sanity, you'll take the performance hit and lock the mutex before checking. That said, the list might not even be the correct container for you. If you can let us know exactly what you are doing with it, we might be able to suggest a better container.

user_43424980

There is a read and a write (most probably to the size member of std::list, if we assume that it's named like that) that are not synchronized in reagard to each other. Imagine that one thread calls empty() (in your outer if()) while the other thread entered the inner if() and executes pop_back(). You are then reading a variable that is, possibly, being modified. This is undefined behaviour.

user_71514940

As an example of how things could go wrong:

A sufficiently smart compiler could see that mutex.lock() cannot possibly change the list.empty() return value and thus skip the inner if check completely, eventually leading to a pop_back on a list that had its last element removed after the first if.

Why can it do that? There is no synchronization in list.empty(), thus if it were changed concurrently that would constitute a data race. The standard says that programs shall not have data races, so the compiler will take that for granted (otherwise it could perform almost no optimizations whatsoever). Hence it can assume a single-threaded perspective on the unsynchronized list.empty() and conclude that it must remain constant.

This is only one of several optimizations (or hardware behaviors) that could break your code.

user_95287460
Related