Rust 类型系统可以防止死锁吗？

在您最意想不到的时候，死锁潜伏在每个角落。我们可以使用 Rust 类型系统在编译时避免它们吗？也就是说，在编译时能证明没有死锁吗？

假设我们有两个互斥体（或互斥体，如果你喜欢的话）M1 和 M2。

如果线程 T1 持有 M1 但希望声明 M2，则会发生死锁；同时线程 T2 拥有 M2 并希望声明 M1。
有几种模式可以避免这种情况：

切勿同时申请M1和M2中的一个以上的锁定。
永远不要锁定 M2，除非我们已经锁定 M1（反之亦然）

让我们来看看这两种模式。在每种情况下，让我们假设我们正在为Mutex和MutexGuard制作一个新的包装器。

切勿同时申请M1和M2中的一个以上的锁定：
要做到这一点，我们需要确保每个线程正好有一个这样的 "mutex权限令牌 "存在。
在同一个文件中：

thread_local! {
   pub static MUTEX_PERMISSION_TOKEN: Cell<Option<MutexPermissionToken>> 
     = Cell::new(Some(MutexPermissionToken(PhantomData));
}

调用者可以得到MutexPermissionToken--每个线程正好一次。调用者应该期望把它储存在某个地方，因为它将经常需要它。但这并不重要！它是零大小的！- 它是零大小的，所以这只是记账，而不是实际的代码。

我们的新mutex包装器有一个修改过的lock()方法，它接收MutexPermissionToken并将其存储在修改过的MutexGuard中：

impl<T> DeadlockProofMutex<T> {
  fn lock(&self, permission: MutexPermissionToken) -> LockResult<DeadlockProofMutexGuard<T>> {
    // calls through to underlying mutex.lock()
    // wraps the result in a newtype wrapper containing the
    // (zero-sized) MutexPermissionToken
  }
}

MutexGuard需要更多的工作。目前，它在其Drop植入中解锁。我们希望添加一个显式的unlock()方法，检索MutexPermissionToken：

impl<T> DeadlockProofMutexGuard<T> {
  fn unlock(self) -> MutexPermissionToken {
    // unlock the underlying mutex
    // return the MutexPermissionToken
  }
}

就这样，我们有了它。如果M1和M2都是DeadlockProofMutex类型，编译器会阻止调用者同时索取这两个东西，因此没有死锁。

理论上，由于MutexPermissionToken是零大小的，这些都不会对编译后的代码或运行时活动产生任何影响。

这对调用者来说是否符合人体工程学？好吧，照顾珍贵的MutexPermissionToken可能需要调用者建立一个状态机--但我们知道使用Rust枚举是很省力的，尤其是在编译时防止死锁。

永远不要锁定 M2，除非我们已经锁定 M1（反之亦然）
为了简单起见，我们假设有两种互斥类型--DeadlockProofMutex和DeadlockProofOuterMutex。前者与我们已经描述过的完全一样--它要求你拥有一个MutexPermissionToken，以便能够要求它的锁。

但是这一次，MutexPermissionToken是由外层mutex发出的。(我们删除了之前的MUTEX_PERMISSION_TOKEN）。具体来说，当你锁定它时得到一个，而当你解锁它时返回它。

impl<T> DeadlockProofOuterMutex<T> {
  fn lock(&self) -> LockResult<(DeadlockProofOuterMutexGuard<T>, MutexPermissionToken> {
     // returns the thread's MutexPermissionToken if lock succeeds.
  }
}

impl<T> DeadlockProofOuterMutexGuard<T> {
  fn unlock(self, token: MutexPermissionToken) {
    // ...
  }
}

我们不需要在这里做任何花哨的跟踪。由于互斥的性质，任何时候都只能有一个MutexPermissionToken存在。

只有当外部突变体mutex 被锁定时，任何人都可以尝试索取内部突变体mutex 。防止了死锁。

我在这里试验了其中的一些想法（这里是示例客户端代码）。

当然，在实践中可能有比使用一堆互斥体更好的方式来表达你的程序。尽管如此，令我感兴趣的是，Rust 的类型系统可用于解决与内存安全完全无关的棘手错误（死锁）类。这里的一般理论是，其中一些 Rust 设施可以充当子结构类型系统。