C++ <mutex> header 在强制并发时使用硬件支持还是纯粹基于算法的解决方案

Question

C++ 互斥量是如何在底层实现的？它只使用 Decker、Peterson 或其他算法来强制互斥，还是也使用硬件支持，例如中断广告比较和交换 (CAS)。

是否可以在没有任何硬件支持的情况下实现一个由互斥锁和条件变量组成的完整多线程库？

Answer 1

它要求操作系统来做。

在 Linux 上可能会使用 pthreads (How does pthread implemented in linux kernel 3.2?)。

在 Windows 上它与 Windows API 一起。您可以尝试向 Microsoft 询问该问题。

标准库实现不会直接访问硬件。这就是操作系统的用途。

Answer 2

在 Linux 上，当互斥锁无竞争时，锁定和解锁发生在 user-space 中，仅使用原子指令，例如比较和交换。在有争议的情况下，需要调用内核以等待互斥量直到它被解锁（锁定）或唤醒服务员（解锁）。锁定用户-space 互斥体不会禁用中断。

Here is the source code for low-level mutex primitives in glibc，评论有指导意义：

/* 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.  */

和pthread_mutex_lock code.

Mutex 实现需要多个线程就共享变量的值达成一致 - 互斥锁，无论它是锁定的还是未锁定的。这也称为 consensus problem，仅使用原子加载和存储无法解决它，需要进行比较和交换。

Answer 3

标准要求有原子操作。不一定是CAS，但至少是exchange。 std::atomic_flag 要求是真正的原子，虽然 CAS 对它来说是多余的，但简单的交换就可以了。

请注意，任何算法（例如 Decker 的、Peterson 的或其他算法）至少需要原子加载和原子存储，如果加载和存储是非原子的，它们将无法工作。此外，非原子类型不强制执行内存排序，这些算法暗示了这一点。

std::mutex并不是真的需要基于操作系统调用，而且根本不需要操作系统调用。

理论上，std::mutex 只能旋转互斥量。

它也可能只阻塞互斥量。

在实践中，一个好的实现会首先尝试用原子处理阻塞，但是当它诉诸等待时，它会做 OS 等待。

C++ <mutex> header 在强制并发时使用硬件支持还是纯粹基于算法的解决方案

Does C++ <mutex> header use hardware support when enforcing concurrency or is purely an algorithm based solution

c++

concurrency

multithreading

mutex