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

Question

假设我正在一个没有 multiple-reader/single 的线程框架中进行编程-编写器互斥体。我可以通过以下方式实现它们的功能吗：

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

写入：

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

读：

• 获取二进制互斥锁上的锁（因此我知道写入器不处于活动状态）
• 递归互斥锁的增量计数，
• 释放二进制互斥锁上的锁
• 实际 读取
• 递归互斥体的递减计数

这不是家庭作业。我没有接受过并发编程的正式培训，并且正在努力掌握这些问题。如果有人能够指出缺陷、阐明不变量或提供更好的算法，我会非常高兴。一个好的参考资料，无论是在线的还是死树上的，也将不胜感激。

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 实现，但仅将其用作伪代码。在进行实际实现时，您必须小心内存模型语言，否则你肯定会头痛。举个例子，我认为 readAcquires 和 readReleases 以及 writer 变量都必须在 Java 中声明为 volatile，否则编译器可以自由地在循环之外优化它们。这是因为在严格顺序的程序中，连续循环循环内从未更改的变量是没有意义的。请注意，我的 Java 有点生疏，所以我可能是错的。还有另一个问题是 readReleases 和 readAcquires 变量的整数溢出，该问题在算法中被忽略。

在解释算法之前，请注意最后一点。条件变量是使用锁来初始化的。这意味着当线程调用 condition.await() 时，它会放弃对锁的所有权。一旦通过调用 condition.signalAll() 将其唤醒，线程将在重新获取锁后恢复。

最后，这是它的工作原理和原因。 readReleases 和 readAcquires 变量跟踪已获取和释放读锁的线程数。当它们相等时，没有线程拥有读锁。 writer 变量指示线程正在尝试获取写锁或已经拥有写锁。

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

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

这个算法是公平的，因为读者不能无限期地阻止作者。一旦写入者表示想要获取锁，则不再有读取者可以获取该锁。之后，作者只需等待最后剩下的读者完成即可继续。请注意，一个作者仍然有可能无限期地阻止另一个作者。这是一种相当罕见的情况，但可以改进算法以考虑到这一点。

---

所以我重新阅读了你的问题，并意识到我用下面介绍的算法部分（糟糕地）回答了它。这是我的第二次尝试。

您描述的算法与我提到的书中提出的简单版本非常相似。唯一的问题是 A) 这不公平，B) 我不确定如何实现等待递归互斥锁的锁计数为零。对于 A）（请参阅上文）和 B），本书使用单个 int 来跟踪读者，并使用条件变量来发出信号。

Answer 2

1. 您可能想防止写饥饿，为了实现这一点，您可以优先考虑写入或使互斥体公平。
   ReadWriteLock Java 的接口文档 表示编写者偏好是常见的，
   ReentrantReadWriteLock类文档说
   此类不会对锁访问强加读取器或写入器优先顺序。但是，它确实支持可选的公平策略。

2. 注意 R.. 的评论

   <块引用>

   您无需锁定和解锁二进制互斥体以进行读取，而是
   可以在增加计数后检查二进制互斥状态
   递归互斥锁，如果是，则等待（spin/yield/futex_wait/whatever）
   锁定直至解锁

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