MCS 锁的一个简单且正确的实现

MCS 锁是一种基于列表的排队锁，通过让线程在本地内存位置自旋来避免网络竞争。该机制的主要特性包括：

• 保证锁定获取的 FIFO 顺序；
• 仅在本地可访问的标志变量上自旋；
• 每个锁只需要一个小常量空间；
• 在具有和没有一致性缓存的情况下，工作效果相同（每个锁获取只需要 O(1) 网络事务）。

此算法及其它一些算法由 Mellor-Crummey 和 Scott 的论文引入。Johnson 和 Harathi 提出了一个更简单的 MCS 锁正确性证明。

使用场景

值得注意的是，自旋锁通常不是你想要的。大多数用例都由基于操作系统的互斥锁，如 std::sync::Mutex 或 parking_lot::Mutex 良好地覆盖。这些实现将通知系统等待的线程应该被挂起，以便处理器可以处理其他事情。

自旋锁只有在上下文切换或进程重新调度开销大于非常短期的忙等待的很少情况下才是高效的。自旋锁可以在操作系统内核、嵌入式系统或甚至补充其他锁定设计中使用。作为一个参考用例，一些 Linux 内核互斥锁 在实际休眠之前运行一个定制的 MCS 锁，专门用于竞争前的乐观自旋。此实现默认为 no_std，因此在这些环境中很有用。

安装

在您的项目目录中运行以下 Cargo 命令

cargo add mcslock

或者在你项目的Cargo.toml文件中的[dependencies]部分添加条目

# Cargo.toml

[dependencies]
# Available features: `yield`, `barging`, `thread_local` and `lock_api`.
mcslock = { version = "0.3", features = ["barging"] }

文档

本项目文档托管在docs.rs。或者你可以使用以下命令本地构建

RUSTDOCFLAGS="--cfg docsrs" cargo +nightly doc --all-features --open

原始MCS锁

此实现采用FIFO模式。原始锁定API需要本地可访问队列节点的独占访问。该节点由MutexNode类型表示。[更多详情](https://docs.rs/mcslock/latest/mcslock/raw/struct.MutexNode.html)。调用者负责实例化队列节点。此实现与no_std兼容。有关更多信息，请参阅raw模块。[更多信息](https://docs.rs/mcslock/latest/mcslock/raw/index.html)

use std::sync::Arc;
use std::thread;

use mcslock::raw::{spins::Mutex, MutexNode};

fn main() {
    let mutex = Arc::new(Mutex::new(0));
    let c_mutex = Arc::clone(&mutex);

    thread::spawn(move || {
        // A queue node must be mutably accessible.
        let mut node = MutexNode::new();
        *c_mutex.lock(&mut node) = 10;
    })
    .join().expect("thread::spawn failed");

    // A queue node must be mutably accessible.
    let mut node = MutexNode::new();
    assert_eq!(*mutex.try_lock(&mut node).unwrap(), 10);
}

线程本地MCS队列节点

启用在线程本地存储中存储的队列节点的raw::Mutex锁定API。这些锁定API需要一个指向LocalMutexNode键的静态引用。键必须由thread_local_node!宏生成。线程本地节点与no_std不兼容，可以通过thread_local功能启用。

use std::sync::Arc;
use std::thread;

use mcslock::raw::spins::Mutex;

// Requires `thread_local` feature.
mcslock::thread_local_node!(static NODE);

fn main() {
    let mutex = Arc::new(Mutex::new(0));
    let c_mutex = Arc::clone(&mutex);

    thread::spawn(move || {
        // Local nodes handles are provided by reference.
        // Critical section must be defined as closure.
        c_mutex.lock_with_local(&NODE, |mut guard| *guard = 10);
    })
    .join().expect("thread::spawn failed");

    // Local nodes handles are provided by reference.
    // Critical section must be defined as closure.
    assert_eq!(mutex.try_lock_with_local(&NODE, |g| *g.unwrap()), 10);
}

闯入式MCS锁

此实现将使非等待线程与非等待队列线程的前端进行竞争，这意味着这是一个不公平的锁。此实现适用于no_std环境，并且锁定API与lock_api存储库兼容。[更多信息](https://docs.rs/mcslock/latest/mcslock/barging/index.html)和[更多信息](https://docs.rs/mcslock/latest/mcslock/barging/lock_api/index.html)

use std::sync::Arc;
use std::thread;

// Requires `barging` feature.
use mcslock::barging::spins::backoff::Mutex;

fn main() {
    let mutex = Arc::new(Mutex::new(0));
    let c_mutex = Arc::clone(&mutex);

    thread::spawn(move || {
        *c_mutex.lock() = 10;
    })
    .join().expect("thread::spawn failed");

    assert_eq!(*mutex.try_lock().unwrap(), 10);
}

特性

此存储库不提供任何默认特性。可以启用的特性有

yield

yield特性需要链接到标准库，因此不适合no_std环境。通过启用yield特性，在锁定获取和释放期间不再忙等，而是调用std::thread::yield_now，这会与合作地放弃一个时间片给操作系统调度器。这可能会引起上下文切换，所以如果你打算进行实际的乐观自旋，可能不希望启用此功能。默认实现调用core::hint::spin_loop，这实际上只是简单地忙等。此特性与no_std不兼容。

thread_local

《thread_local》功能启用了对存储在线程本地存储中的队列节点进行操作的 Mutex 锁定 API。这些锁定 API 需要一个指向 LocalMutexNode 键的静态引用。密钥必须由 thread_local_node! 宏生成。这个特性与 no_std 不兼容。

闯入

《barging》功能提供了与 lock_api 插件兼容的锁定 API。它不需要调用者进行节点分配，并且适用于 no_std 环境。这种实现不是公平的（不保证 FIFO），但可以在锁被高度竞争时提高吞吐量。

lock_api

此功能实现了 RawMutex 特性，用于 barging::Mutex。别名由 lock_api 模块提供。这个特性与 no_std 兼容。

最低支持 Rust 版本 (MSRV)

此插件确保在 1.65.0 及以上版本的最低支持 Rust 版本 (MSRV) 下编译。此版本将不会在没有小版本号增加的情况下更改。如果您打算使用此插件，但只能针对较旧的 Rust 版本进行目标定位，请随意打开一个针对您特定目标的问题，降低此插件 MSRV 的可能性很大，只是尚未进行探索。

相关项目

这些项目提供了具有略微不同 API、实现细节或编译器要求的 MCS 锁实现，您可以查看它们的存储库。

• mcs-rs: https://github.com/gereeter/mcs-rs
• libmcs: https://github.com/topecongiro/libmcs

许可证

根据以下之一进行许可

• Apache License，版本 2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

贡献

除非您明确表示，否则根据 Apache-2.0 许可证定义，您提交的任何有意包含在工作中的贡献，都应作为上述双重许可，没有附加条款或条件。

代码审查

建议始终使用 cargo-crev 验证每个依赖项的可信度，包括此依赖项。