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

Question

假设我在一个没有 multiple-reader/single-writer mutexes 的线程框架中编程.我可以通过以下方式实现它们的功能吗:

创建两个互斥锁:一个递归(锁计数)一个用于读者，一个二进制一个用于作者。

写:

获取二进制互斥锁

等到递归互斥锁的锁计数为零

实际写

释放二进制互斥锁

读:

获取二进制互斥锁(所以我知道作者不活跃)

递归互斥的增量计数

释放二进制互斥锁

实际阅读

递减递归互斥的计数

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

Answer 1

以下直接摘自The Art of Multiprocessor Programming这是一本了解这些东西的好书。实际上有两个实现:一个简单的版本和一个公平的版本。我会继续复制公平的版本。

此实现的要求之一是您有一个条件变量原语。我会想办法把它删除，但这可能需要我一点时间。在那之前，这应该还是比没有好。请注意，也可以仅使用锁来实现此原语。

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

在我解释算法之前的最后一个注释。使用锁初始化条件变量。这意味着当一个线程调用 condition.await() 时，它放弃了对锁的所有权。一旦它被调用 condition.signalAll() 唤醒一旦重新获得锁，线程将恢复。

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

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

算法的写锁部分并不复杂。要锁定，线程必须首先检查是否有任何其他编写器处于事件状态。如果是，则必须等到其他编写器完成。然后它通过设置 writer 来表明它需要锁。为真(请注意，它还没有保存它)。然后等待直到没有更多的读者才继续。要解锁，它只需设置变量 writer为 false 并通知可能正在等待的任何其他线程。

这个算法是公平的，因为读者不能无限期地阻止作者。一旦写者表示它想要获取锁，就没有更多的读者可以获取锁。之后，作者只是等待最后剩下的读者完成后再继续。请注意，一个作者仍然有可能无限期地阻止另一个作者。这是一个相当罕见的情况，但可以改进算法以将其考虑在内。

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

您描述的算法与我提到的书中介绍的简单版本非常相似。唯一的问题是 A) 这不公平 B) 我不确定您将如何实现 wait until recursive mutex has lock count zero .对于 A)，请参见上文和对于 B)，本书使用单个 int 来跟踪读者，并使用一个条件变量来发出信号。