HappyLock: 无死锁互斥锁

事实证明，Rust借用检查器非常强大，如果标准库支持它，我们就可以使死锁成为未定义的行为。这个库目前是一个概念验证，说明这样做的效果。

理论

死锁发生需要四个条件。为了防止死锁，我们需要防止以下之一

1. 互斥（这是互斥锁的全部意义，所以我们不能防止这一点）
2. 非抢占性分配（语言必须能够在任何时候从线程中取出互斥锁。这将非常麻烦。）
3. 循环等待（语言必须强制每个线程以完全相同的顺序锁定互斥锁）
4. 部分分配（语言必须强制完全分配）

这个库试图通过要求完全分配来解决问题 部分分配。线程需要的所有资源必须同时分配。为了请求新的资源，必须先丢弃旧资源。一次性请求多个资源是原子的。要么获取所有请求的资源，要么一个都不获取。

作为一个优化，这个库还经常防止 循环等待。许多集合按内存地址顺序排序锁。只要始终以该顺序获取锁，就不需要在失败后浪费时间去释放锁，然后在稍后重新获取它们。

示例

let data: Mutex<i32> = Mutex::new(0);

for _ in 0..N {
    thread::spawn(move || {
        // each thread gets one thread key
        let key = ThreadKey::get().unwrap();

        // unlocking a mutex requires a ThreadKey
        let mut data = data.lock(key);
        *data += 1;

        // the key is unlocked at the end of the scope
    });
}

let key = ThreadKey::get().unwrap();
let data = data.lock(&mut key);
println!("{}", *data);

解锁互斥锁需要 ThreadKey 或对 ThreadKey 的可变引用。每个线程一次只能有一个密钥，但不能超过这个数量。`ThreadKey` 类型不可克隆或复制。这意味着一次只能锁定一个东西。

要同时锁定多个互斥锁，请创建一个 LockCollection。

static DATA_1: Mutex<i32> = Mutex::new(0);
static DATA_2: Mutex<String> = Mutex::new(String::new());

for _ in 0..N {
    thread::spawn(move || {
        let key = ThreadKey::get().unwrap();

        // happylock ensures at runtime there are no duplicate locks
        let collection = LockCollection::try_new((&DATA_1, &DATA_2)).unwrap();
        let mut guard = collection.lock(key);

        *guard.1 = (100 - *guard.0).to_string();
        *guard.0 += 1;
    });
}

let key = ThreadKey::get().unwrap();
let data = (&DATA_1, &DATA_2);
let data = LockGuard::lock(&data, &mut key);
println!("{}", *data.0);
println!("{}", *data.1);

在许多情况下，可以使用 LockCollection::new 或 LockCollection::new_ref 方法，提高性能。

use std::thread;
use happylock::{LockCollection, Mutex, ThreadKey};

const N: usize = 100;

static DATA: [Mutex<i32>; 2] = [Mutex::new(0), Mutex::new(1)];

for _ in 0..N {
    thread::spawn(move || {
        let key = ThreadKey::get().unwrap();
        // a reference to a type that implements `OwnedLockable` will never
        // contain duplicates, so no duplicate checking is needed.
        let collection = LockCollection::new_ref(&DATA);
        let mut guard = collection.lock(key);
        let x = *guard[1];
        *guard[1] += *guard[0];
        *guard[0] = x;
    });
}

let key = ThreadKey::get().unwrap();
let data = LockCollection::new_ref(&DATA);
let data = data.lock(key);

println!("{}", data[0]);
println!("{}", data[1]);

性能

《ThreadKey》是一种几乎零成本的抽象。 它不使用任何内存，并且在运行时实际上并不存在。唯一的花费来自于调用 ThreadKey::get()，因为该函数必须在运行时确保该密钥尚未被取走。丢弃密钥也会有小的成本。

考虑使用 OwnedLockCollection。 这几乎总是最快的锁集合。它不会以不可变的方式暴露底层数据集合，这意味着它将始终以相同的顺序锁定，并且不需要任何排序。

避免使用 LockCollection::try_new。 此构造函数会检查集合中是否没有重复的锁。在大多数情况下，这的时间复杂度为 O(nlogn)，其中 n 是集合中锁的数量，但在 RetryingLockCollection 的情况下，它接近 O(n)。 LockCollection::new 和 LockCollection::new_ref 不需要这些检查，因为它们使用了 OwnedLockable，只要它可访问，就能保证其唯一性。作为最后的手段，LockCollection::new_unchecked 不进行此检查，但调用它是危险的。

了解如何使用 RetryingLockCollection。 此集合不会进行任何排序，但使用了一个低效的锁算法。它不能依赖于锁在各个线程中的顺序相同，所以如果它找到一个无法不阻塞即可获得的锁，它会首先释放它已经获得的全部锁，以避免阻塞其他线程。这是低效的，因为此算法可能最终会多次重新获得相同的锁。为了避免这种情况，请确保（1）集合中的第一个锁总是出现在任何包含它的集合中的第一个位置，以及（2）集合中的其他锁总是紧随第一个锁之后。这将防止重新获得锁所浪费的时间。如果您不确定，LockCollection 是一个合理的默认选择。

未来工作

通过让两个 crate 导入此 crate 并调用 ThreadKey::get，可能会破坏 ThreadKey 系统。我不太确定这是如何工作的，但 Rust 可能会决定给每个 crate 分配其自己的密钥，因此一个线程可能会获得两个密钥。我认为标准库不会有这个问题。在某个时刻，我必须认识到，有人也可以简单地导入标准库互斥锁，并通过这种方式获得死锁。

这里的用户体验是否良好？这是一个完全未知的领域。也许这里还有一些有用的辅助方法我们还尚未提供。也许 try_lock 应该返回一个 Result。也许 lock_api 或 spin 实现了一些有用的方法，我出于这个概念验证的目的将其排除在外。也许可以添加一些特定于锁的方法到 LockCollection 中。可能更多的类型可以通过锁集合进行锁定。

希望能够使用操作系统中内置的互斥锁，这样可以节省二进制文件的大小。使用 std::sync::Mutex 听起来很有前景，但它没有实现 RawMutex，并且实现它非常困难，如果不是不可能的话。也许我可以为操作系统互斥锁实现自己的抽象。我还可以简单地为标准库互斥锁实现 Lockable。

就我个人而言，我不喜欢互斥锁中毒，但如果你喜欢这类事情，也许它可以集成到库中。

添加一些方法，如 lock_clone 或 lock_swap 将很有趣。但这仍然需要一个线程键，以防互斥锁已被锁定。如果不使用线程键，唯一能这样做的方法是使用一个 &mut Mutex<T>，但我们已经有了 as_mut。一个类似 Cell 但实现 Sync 的特殊锁可以在没有线程键的情况下共享，因为锁会被立即释放（防止非抢占式分配）。这可能会使一些常见操作更容易。

现在我们有 Sharable 特性，表示集合中的所有锁都可以共享，我们可以在不允许访问 lock 和 try_lock 的集合周围实现一个 Readonly 包装器。这样做的想法是，如果你不是独占锁定集合，那么你不需要检查集合中的重复项。在同一个 RwLock 上两次调用 .read() 不会导致死锁。

我想在不使用标准库的情况下尝试使这工作。但这有几个问题。例如，这个包使用 thread_local 允许其他线程有自己的键。此外，唯一实际可用的互斥锁类型是自旋锁。尽管如此，还可以使用 RawMutex 特性实现更多功能。目前，Lockable 特性需要内存分配来检查重复的锁。

我一直在考虑添加 Condvar 和 Barrier，但我被两件事阻止了。我不经常使用它们，所以我可能不是尝试实现其中任何一个的正确人选。它们也有些奇怪，更难防止死锁。它们在某种程度上是互斥锁的对立面，因为互斥锁保证了至少有一个线程可以始终访问每个资源。

OnceLock 或 LazyLock 是否会死锁？我们可能不需要在这里添加它们。

我们可以为类似于 LockCollection<Vec<i32>> 的东西实现特殊方法，其中我们只锁定前三个项目。