C++ hand-made mutex

Question

I've made a hand-made mutex for my project, but I doubt if it is thread safe...

    bool blocked;

    while ( blocked )
    {

    }

    blocked = true;
    ...
    blocked = false;

Lets say, thread A passes the while loop and doesn't block the flag in time (doesn't have time to set the flag to false) and thread B passes the while loop too!

1. Is it possible? Why?

2. As I get it mutex has the very same principle of work. Why can not this occur in mutex? I've read about atomic operations which can not be interrupted... So the check-if-mutex-available and mutex-block can not be interrupted, right?

Answer 1

Your code is completely defunct!

The reason is that access to the variable blocked is not atomic. Two threads can read it si­mul­ta­ne­ous­ly and decide that the mutex is unlocked, if the two reads happen before the first thread writes out the true update and the update propagates to all CPUs.

You need atomic variables and atomic exchange to solve this. The atomic_flag type is exactly what you want:

#include <atomic>

std::atomic_flag blocked;

while (blocked.test_and_set()) { }  // spin while "true"

// critical work goes here

blocked.clear();                    // unlock

(Alternatively, you could use a std::atomic<bool> and exchange(true), but the atomic_flag is made especially for this purpose.)

Atomic variables do not only prevent the compiler from reordering code that appears to be unrelated if this were a single-threaded context, but they also make the compiler generate the necessary code to prevent the CPU itself from reordering instructions in a way that would allow inconsistent execution flow.

In fact, if you want to be slightly more efficient, you can demand a less expensive memory ordering on the set and clear operations, like so:

while (blocked.test_and_set(std::memory_order_acquire)) { }  // lock

// ...

blocked.clear(std::memory_order_release);                    // unlock

The reason is that you only care about the correct ordering in one direction: a delayed update in the other direction is not very expensive, but requiring sequential consistency (as is the default) may well be expensive.

---

Important: The above code is a so-called spin lock, because while the state is locked, we do a busy spin (the while loop). This is very bad in almost all situations. A kernel-provided mutex system call is a whole different kettle of fish, since it allows the thread to signal the kernel that it can go to sleep and let the kernel deschedule the entire thread. That is almost always the better behaviour.

Answer 2

1. It's possible because the processor can switch from the first thread to the second after entering the loop, but before locking the mutex.
2. It's possible because they use kernel-level operations to ensure that the thread is not switched until a certain operation is complete.

On Windows for instance, you could make a mutex look like this.

Answer 3

You've pretty much got it already.

1. Yes, it's very possible. For a single core, threads get executed by the OS via timeslicing. It runs thread A for a bit, then pauses it, and runs thread B for a bit. Thread A could get paused right after passing the while loop.

2. To solve problems like these, CPU's have implemented special instructions that CANNOT be interrupted by anything. These atomic operations are used by a mutex to check the flag, and set it in one operation.

Answer 4

Yes, the situation you described can happen. The reason for this is that the thread can be interrupted between testing blocked is false, and setting blocked to true. To get the behaviour you want you will need to use or emulate an atomic test-and-set operation.

Further information on test-and-set can be found here.

Answer 5

a mutex implementation must ensure mutual exclusivity (that's the meaning of it) and not obtained in your code. It requires some atomic variable and suitable memory order for its access. In C++11, best use std::mutex (ideally together with std::lock), for C++03 you can use boost::mutex etc.