读写锁/互斥锁是如何工作的？

Question

假设我在一个没有多读者/单写者互斥锁的线程框架中编程。我能用以下方法实现它们的功能吗：

创建两个互斥锁：一个递归（锁计数）用于读取，另一个二进制用于写入。

写入：

• 获取二进制互斥锁
• 等待递归互斥锁计数为零
• 实际写入
• 释放二进制互斥锁

阅读：

• 获取二进制互斥锁（以便我知道写入者未激活）
• 递增递归互斥锁计数
• 释放二进制互斥锁
• 实际读取
• 递减递归互斥锁计数

这不是作业。我没有并发编程的正式培训，正在努力掌握相关问题。如果有人能指出缺陷、明确不变量或提供更好的算法，我会非常高兴。也欢迎提供在线或纸质参考资料。

- Fred Foo

---

很好的问题！买些书来学习这方面的知识。我想推荐一些，但是我在这个领域已经有些生疏了。 - Marcin

与其为了读取而锁定和解锁二进制互斥量，您可以在递归互斥量上增加计数后仅检查二进制互斥量状态，并等待（自旋/让步/futex_wait/任何方式），直到它变为未锁定。 - R.. GitHub STOP HELPING ICE

Answer 1

下面的内容直接摘自多处理器编程艺术，这是一本学习这方面知识的好书。实际上，有两种实现方式：简单版本和公平版本。我将展示公平版本。

其中一个要求是必须拥有条件变量原语的实现。我会尝试找到一种方法来移除它，但这可能需要花费一些时间。在那之前，这仍然比没有好。请注意，也可以仅使用锁来实现此原语。

public class FifoReadWriteLock {
    int readAcquires = 0, readReleases = 0;
    boolean writer = false;
    ReentrantLock lock;
    Condition condition = lock.newCondition(); // This is the condition variable.

    void readLock () {
        lock.lock();
        try {
            while(writer)
                condition.await();
            readAcquires++;
        }
        finally {
            lock.unlock();
        }
    }

    void readUnlock () {
        lock.lock();
        try {
            readReleases++;
            if (readAcquires == readReleases)
                condition.signalAll();
        }
        finally {
            lock.unlock();
        }
    }

    void writeLock () {
        lock.lock();
        try {
            while (writer)
                condition.await();

            writer = true;

            while (readAcquires != readReleases)
                condition.await();
        }
        finally {
            lock.unlock();
        }
    }

    void writeUnlock() {
        writer = false;
        condition.signalAll();
    }
}

首先，我简化了代码，但算法保持不变。此算法在书中存在错误，已在勘误表中进行了更正。如果您打算阅读这本书，请随时准备好勘误表，否则您将会非常困惑（就像我几分钟前重新理解算法时那样）。请注意，好的一面是，这是一件好事，因为它让你保持警惕，而在处理并发时这是必须的。

其次，虽然这可能是Java实现，但只将其用作伪代码。在实际实现时，您必须小心语言的内存模型，否则肯定会头痛。例如，我认为Java中readAcquires、readReleases和writer变量都必须声明为易失性，否则编译器可以将它们优化出循环。这是因为在严格的顺序程序中，在循环中不断循环一个从未在循环内更改的变量是没有意义的。请注意，我的Java有点生疏，所以我可能是错的。此外，还有另一个问题，即忽略了readReleases和readAcquires变量的整数溢出问题。

在解释算法之前，有一个重要的注意事项。条件变量是使用锁进行初始化的，也就是说，当线程调用 condition.await() 时，它放弃了对锁的所有权。一旦通过调用 condition.signalAll() 醒来后，线程将会重新获取锁并继续执行。

最后，这里是它如何以及为什么起作用的描述：变量 readReleases 和 readAcquires记录已经获取和释放读锁的线程数量。当它们相等时，没有线程持有读锁。变量 writer 表示线程正在尝试获取写锁或者已经持有了它。

算法的读取锁部分非常简单。在尝试获取锁时，它首先检查是否有其他线程持有锁或正在尝试获取锁。如果是这样，它会等待直到其他线程完成，然后通过增加 readAcquires 变量来为读取器获取锁。在解除锁定时，线程将增加变量 readReleases，如果没有更多读取器，则通知可能正在等待的任何写入器。

写入锁部分的算法并不复杂。要锁定，线程必须首先检查是否有其他写入器处于活动状态。如果有，它必须等待直到其他写入器完成。然后，它通过将 writer 设置为 true 来表示想要锁定（请注意，它尚未持有锁）。然后，它等待直到没有更多读取器才继续执行。要解除锁定，它只需将变量 writer 设置为 false，并通知可能正在等待的任何其他线程即可。

这个算法是公平的，因为读者无法无限期地阻塞作者。一旦作者指示要获取锁定，就没有更多的读者可以获取锁定。此后，作者只需等待最后剩余的读者完成后继续。请注意，仍然存在一个作者无限期地阻止另一个作者的可能性。这是一个相当罕见的情况，但可以改进算法以考虑这一点。

---

我重新阅读了您的问题，意识到我在下面给出的算法中部分地（糟糕地）回答了它。所以这是我的第二次尝试。

你描述的算法与我提到的书中介绍的简单版本非常相似。唯一的问题是A）它不公平，B）我不确定如何实现wait until recursive mutex has lock count zero。关于A），请参见上文；关于B），该书使用一个整数来跟踪读取器，并使用条件变量进行信号处理。

- Ze Blob

---

不错的回答。然而，回答中的代码存在严重缺陷，例如变量未同步，存在饥饿风险等等...因此请遵循@Ze Blob的建议，仅将其用作伪代码。 - user454322

我只想提一下，“Ze Blob”算法并不公平。 假设你有活跃的读者。现在来了一个作者，增加了作者计数器（将其设置为1）。然后又来了另一个作者（并被阻塞在作者条件变量上）。现在1000个读者到达（也被阻塞在条件变量上）。现在活跃的读者完成了。 现在会发生什么？你会释放一个作者（可能是第二个作者而不是第一个）。此外，你还会释放所有读者。所以现在再次进入读者并等待作者的机会就更大了。 - user2515259

writeUnlock() 是否正确？我们能否在没有锁的情况下调用 condition.signalAll(); ？如果尝试这样做，可能会出现 java.lang.IllegalMonitorStateException。 - Miguel Gamboa

@MiguelGamboa 如前所述，代码应仅视为伪代码。某些条件变量的实现不要求在发出信号时保持锁定状态，而其他一些则需要。根据需要进行调整。 - Ze Blob

在我看来，这是书中例子的一个打字错误。如果一直使用 signalAll() 方法，我能理解伪代码的参数。然而，有些例子在保持锁定状态时使用它，而其他例子则没有。 - Miguel Gamboa

Answer 2

1. 您可能想要防止写入饥饿，为此您可以优先考虑写入或使互斥公平。
   ReadWriteLock Java的接口文档中说：“写入器优先是常见的”，
   ReentrantReadWriteLock类文档中说：“此类不强制执行锁定访问的读取器或写入器优先级排序。但是，它支持可选的公平性策略。”

2. 请注意R..的评论：

   与其对二元互斥锁进行读取和解锁操作，您可以在增加递归互斥锁计数后仅检查二元互斥锁状态，并等待（旋转/屈服/futex_wait/其他）如果被锁定，则等待其变为未锁定

3. 推荐阅读：
   使用POSIX线程进行编程
   Perl的RWLock
   Java的ReadWriteLock文档。

- user454322