4

Let's we have the following simple mutex definition:

class Mutex {
private:
    bool lock;
public:
    void acquire();

    void release();

    Mutex() {
        lock = 0;
    }
};

And the following acquire() func realization (with using of compare and swap operation):

void Mutex::acquire() {
    bool oldValue;
    __atomic_load(&lock, &oldValue, 0);
    bool newValue = true;
    while (!__atomic_compare_exchange_n(&lock, &oldValue, newValue, true, 0, 0)) {
        sched_yield();
    }
}

In that case, we get the following assembly code:

movzx   eax, BYTE PTR [rsp+15]
lock cmpxchg    BYTE PTR [rbx], bpl
je      .L9

Or in the case of using __atomic_test_and_set :

void Mutex::acquire() {
    while (__atomic_test_and_set(&lock, 0)) {
        sched_yield();
    }
}

We get the following assembly code:

    mov     eax, ebp
    xchg    al, BYTE PTR [rbx]
    test    al, al
    jne     .L6

But, what if we don't have hardware support of atomic Test-and-Set and CAS-operations (xchg and lock cmpxchg on x86 and their equivalent ones on other architectures)? What solution will compiler use in this case?

P.S. - I used gcc 8.2 to produce assembly code, and here's __atomic_ built-in functions: https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

TwITe
  • 400
  • 2
  • 14
  • 3
    Voting to close as "too broad". Mutex can't be implemented unless the hardware has *some* atomic operations. Unless we know what those are, we can't tell how the compiler would implement it. – Martin Bonner supports Monica Oct 22 '18 at 05:48
  • 2
    C++11 *requires* that [`std::atomic_flag`](https://en.cppreference.com/w/cpp/atomic/atomic_flag) is lock-free, and a mutex can be built out of that (you don't need CAS for a spinlock, just TAS). [Why only std::atomic\_flag is guaranteed to be lock-free?](https://stackoverflow.com/q/30256472) On hardware where you can't implement a test-and-set and clear at some width so you can implement `std::atomic_flag`, you can't implement C++11, only some earlier version of the standard. You might still be able to implement a mutex, depending on what building blocks you do have. – Peter Cordes Oct 22 '18 at 07:14
  • 2
    The answer for C++ would depend on answer to question if it is possible at all. If the platform allows creating any mutexes at all then it could be discussed how C++ API could be implemented for them, and this would depend on how they could be implemented. If the platform does not allow creating mutexes then C++ cannot make them available. – max630 Oct 22 '18 at 12:53

0 Answers0