How is C++ mutex implemented under the hood ? Does it only use Decker's, Peterson's or other algorithms to enforce mutual exclusion or does it also use hardware support such as interrupt ad compare-and-swap (CAS).
Is it possible to implement an entire multi-threading library consisting of mutex and condition variable without any hardware support ?
On Linux, when the mutex is uncontended, the lock and unlock happen in user-space only using atomic instructions, such as compare-and-swap. In a contended case a call into the kernel is required to wait on the mutex till it's been unlocked (on lock) or to wake up waiters (on unlock). Locking user-space mutexes does not disable interrupts.
Here is the source code for low-level mutex primitives in glibc, the comments are instructive:
/* Low-level locks use a combination of atomic operations (to acquire and
release lock ownership) and futex operations (to block until the state
of a lock changes). A lock can be in one of three states:
0: not acquired,
1: acquired with no waiters; no other threads are blocked or about to block
for changes to the lock state,
>1: acquired, possibly with waiters; there may be other threads blocked or
about to block for changes to the lock state.
We expect that the common case is an uncontended lock, so we just need
to transition the lock between states 0 and 1; releasing the lock does
not need to wake any other blocked threads. If the lock is contended
and a thread decides to block using a futex operation, then this thread
needs to first change the state to >1; if this state is observed during
lock release, the releasing thread will wake one of the potentially
blocked threads.
Much of this code takes a 'private' parameter. This may be:
LLL_PRIVATE: lock only shared within a process
LLL_SHARED: lock may be shared across processes.
Condition variables contain an optimization for broadcasts that requeues
waiting threads on a lock's futex. Therefore, there is a special
variant of the locks (whose name contains "cond") that makes sure to
always set the lock state to >1 and not just 1.
Robust locks set the lock to the id of the owner. This allows detection
of the case where the owner exits without releasing the lock. Flags are
OR'd with the owner id to record additional information about lock state.
Therefore the states of robust locks are:
0: not acquired
id: acquired (by user identified by id & FUTEX_TID_MASK)
The following flags may be set in the robust lock value:
FUTEX_WAITERS - possibly has waiters
FUTEX_OWNER_DIED - owning user has exited without releasing the futex. */
Mutex implementation requires multiple threads to agree on a value of a shared variable - the mutex, whether it is locked or unlocked. This is also known as consensus problem and it is not possible to solve it using only atomic loads and stores, a compare-and-swap is required.
Standard requires that there are atomic operations. Not necessarily CAS, but at least exchange. std::atomic_flag is required to be true atomic, although CAS is superfluous for it, simple exchange is satisfactory.
Note that any algorithm such as Decker's, Peterson's or other would at least require atomic load and atomic store, and they will not work if load and store are non-atomic. Also non-atomic types do not enforce memory ordering, which is implied by those algorithms.
It is not really required that std::mutex will be based on operating system calls, and that there are operating system calls at all.
In theory, std::mutex could be spinning only mutex.
It could also be blocking only mutex.
In practice a good implementation would first try to handle blocking with atomic, but when it is resorted to wait, it would do OS wait.
It asks the operating system to do it.
On Linux that'll probably be using pthreads (How does pthread implemented in linux kernel 3.2?).
On Windows it's with the Windows API. You can try asking Microsoft about that one.
The standard library implementation won't be making direct hardware access. This is what operating systems are for.
