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

Question

假设我在一个没有多读者/单作者互斥体的线程框架中进行编程.我可以使用以下方法实现其功能:

创建两个互斥锁:一个用于读者的递归(锁定计数)和一个用于编写器的二进制互斥锁.

写:

• 获取对二进制互斥锁的锁定
• 等到递归互斥锁具有锁定计数零
• 实际写
• 释放对二进制互斥锁的锁定

读:

• 获取对二进制互斥锁的锁定(所以我知道编写器不活动)
• 递归互斥的递增计数
• 释放对二进制互斥锁的锁定
• 实际阅读
• 减少递归互斥的计数

这不是功课.我没有正式的并发编程培训,我正在努力把握这些问题.如果有人可以指出一个缺陷,拼出不变量或提供更好的算法,我会非常高兴.在线或在死树上的好参考也将受到赞赏.

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)我不确定你将如何实施wait until recursive mutex has lock count zero.对于A),见上文和B),本书使用单个int来跟踪读者和条件变量来进行信号传递.