你将如何在 C++11 中实现你自己的读/写锁？

How would you implement your own reader/writer lock in C++11?

提问by Hyman

I have a set of data structures I need to protect with a readers/writer lock. I am aware of boost::shared_lock, but I would like to have a custom implementation using std::mutex, std::condition_variable and/or std::atomic so that I can better understand how it works (and tweak it later).

我有一组需要使用读取器/写入器锁保护的数据结构。我知道 boost::shared_lock，但我想有一个使用 std::mutex、std::condition_variable 和/或 std::atomic 的自定义实现，以便我可以更好地理解它是如何工作的（并在以后进行调整） .

Each data structure (moveable, but not copyable) will inherit from a class called Commons which encapsulates the locking. I'd like the public interface to look something like this:

每个数据结构（可移动，但不可复制）将从一个名为 Commons 的类继承，该类封装了锁定。我希望公共界面看起来像这样：

class Commons {
public:
    void read_lock();
    bool try_read_lock();
    void read_unlock();

    void write_lock();
    bool try_write_lock();
    void write_unlock();
};

...so that it can be publicly inherited by some:

...以便它可以被某些人公开继承：

class DataStructure : public Commons {};

I'm writing scientific code and can generally avoid data races; this lock is mostly a safeguard against the mistakes I'll probably make later. Thus my priority is low read overhead so I don't hamper a correctly-running program too much. Each thread will probably run on its own CPU core.

我正在编写科学代码，通常可以避免数据竞争；这个锁主要是为了防止我以后可能会犯的错误。因此，我的优先事项是低读取开销，所以我不会过多地妨碍正确运行的程序。每个线程可能会在自己的 CPU 内核上运行。

Could you please show me (pseudocode is ok) a readers/writer lock? What I have now is supposed to be the variant that prevents writer starvation. My main problem so far has been the gap in read_lock between checking if a read is safe to actually incrementing a reader count, after which write_lock knows to wait.

你能告诉我（伪代码是可以的）一个读者/作者锁吗？我现在拥有的应该是防止作家饥饿的变体。到目前为止，我的主要问题是 read_lock 在检查读取是否安全与实际增加读取器计数之间的差距，之后 write_lock 知道等待。

void Commons::write_lock() {
    write_mutex.lock();
    reading_mode.store(false);
    while(readers.load() > 0) {}
}

void Commons::try_read_lock() {
    if(reading_mode.load()) {
        //if another thread calls write_lock here, bad things can happen
        ++readers; 
        return true;
    } else return false;
}

I'm kind of new to multithreading, and I'd really like to understand it. Thanks in advance for your help!

我对多线程有点陌生，我真的很想了解它。在此先感谢您的帮助！

回答by fgp

Here's pseudo-code for a ver simply reader/writer lock using a mutex and a condition variable. The mutex API should be self-explanatory. Condition variables are assumed to have a member wait(Mutex&)which (atomically!) drops the mutex and waits for the condition to be signaled. The condition is signaled with either signal()which wakes up onewaiter, or signal_all()which wakes up all waiters.

这是使用互斥锁和条件变量的简单读/写锁的伪代码。互斥锁 API 应该是不言自明的。假设条件变量有一个成员wait(Mutex&)（原子地！）删除互斥锁并等待条件发出信号。该条件signal()由唤醒一个服务员或signal_all()唤醒所有服务员的信号发出。

read_lock() {
  mutex.lock();
  while (writer)
    unlocked.wait(mutex);
  readers++;
  mutex.unlock();
}

read_unlock() {
  mutex.lock();
  readers--;
  if (readers == 0)
    unlocked.signal_all();
  mutex.unlock();
}

write_lock() {
  mutex.lock();
  while (writer || (readers > 0))
    unlocked.wait(mutex);
  writer = true;
  mutex.unlock();
}

write_unlock() {
  mutex.lock();
  writer = false;
  unlocked.signal_all();
  mutex.unlock();
}

That implementation has quite a few drawbacks, though.

但是，该实现有很多缺点。

Wakes up all waiters whenever the lock becomes available

每当锁可用时唤醒所有服务员

If most of the waiters are waiting for a write lock, this is wastefull - most waiters will fail to acquire the lock, after all, and resume waiting. Simply using signal()doesn't work, because you dowant to wake up everyone waiting for a read lock unlocking. So to fix that, you need separate condition variables for readability and writability.

如果大多数等待者都在等待写锁，这是一种浪费——毕竟大多数等待者将无法获取锁，并继续等待。简单地使用signal()是行不通的，因为您确实想唤醒等待读锁解锁的每个人。所以为了解决这个问题，你需要单独的条件变量来实现可读性和可写性。

No fairness. Readers starve writers

没有公平。读者饿死作家

You can fix that by tracking the number of pending read and write locks, and either stop acquiring read locks once there a pending write locks (though you'll then starve readers!), or randomly waking up either all readers or one writer (assuming you use separate condition variable, see section above).

您可以通过跟踪挂起的读和写锁的数量来解决这个问题，并且一旦有挂起的写锁就停止获取读锁（尽管你会饿死读者！），或者随机唤醒所有读者或一个作者（假设您使用单独的条件变量，请参阅上面的部分）。

Locks aren't dealt out in the order they are requested

锁不是按照请求的顺序处理的

To guarantee this, you'll need a real wait queue. You could e.g. create one condition variable for each waiter, and signal all readers or a single writer, both at the head of the queue, after releasing the lock.

为了保证这一点，您需要一个真正的等待队列。例如，您可以为每个服务员创建一个条件变量，并在释放锁后向队列头部的所有读取器或单个写入器发出信号。

Even pure read workloads cause contention due to the mutex

由于互斥锁，即使是纯读取工作负载也会引起争用

This one is hard to fix. One way is to use atomic instructions to acquire read or write locks (usually compare-and-exchange). If the acquisition fails because the lock is taken, you'll have to fall back to the mutex. Doing that correctly is quite hard, though. Plus, there'll still be contention - atomic instructions are far from free, especially on machines with lots of cores.

这个很难修。一种方法是使用原子指令来获取读或写锁（通常是比较和交换）。如果获取失败，因为锁定被占用，您将不得不回退到互斥锁。但是，正确地做到这一点非常困难。另外，仍然会有争论——原子指令远非免费，尤其是在有很多内核的机器上。

Conclusion

结论

Implementing synchronization primitives correctly is hard. Implementing efficient and fair synchronization primitives is evenharder. And it hardly ever pays off. pthreads on linux, e.g. contains a reader/writer lock which uses a combination of futexes and atomic instructions, and which thus probably outperforms anything you can come up with in a few days of work.

正确实现同步原语很困难。实现高效且公平的同步原语更加困难。它几乎没有回报。linux 上的 pthreads，例如包含一个读取器/写入器锁，它使用了 futexes 和原子指令的组合，因此它的性能可能比你在几天的工作中能想出的任何东西都要好。

回答by Khachatur

Check this class:

检查这个类：

//
// Multi-reader Single-writer concurrency base class for Win32
//
// (c) 1999-2003 by Glenn Slayden ([email protected])
//
//


#include "windows.h"

class MultiReaderSingleWriter
{
private:
    CRITICAL_SECTION m_csWrite;
    CRITICAL_SECTION m_csReaderCount;
    long m_cReaders;
    HANDLE m_hevReadersCleared;

public:
    MultiReaderSingleWriter()
    {
        m_cReaders = 0;
        InitializeCriticalSection(&m_csWrite);
        InitializeCriticalSection(&m_csReaderCount);
        m_hevReadersCleared = CreateEvent(NULL,TRUE,TRUE,NULL);
    }

    ~MultiReaderSingleWriter()
    {
        WaitForSingleObject(m_hevReadersCleared,INFINITE);
        CloseHandle(m_hevReadersCleared);
        DeleteCriticalSection(&m_csWrite);
        DeleteCriticalSection(&m_csReaderCount);
    }


    void EnterReader(void)
    {
        EnterCriticalSection(&m_csWrite);
        EnterCriticalSection(&m_csReaderCount);
        if (++m_cReaders == 1)
            ResetEvent(m_hevReadersCleared);
        LeaveCriticalSection(&m_csReaderCount);
        LeaveCriticalSection(&m_csWrite);
    }

    void LeaveReader(void)
    {
        EnterCriticalSection(&m_csReaderCount);
        if (--m_cReaders == 0)
            SetEvent(m_hevReadersCleared);
        LeaveCriticalSection(&m_csReaderCount);
    }

    void EnterWriter(void)
    {
        EnterCriticalSection(&m_csWrite);
        WaitForSingleObject(m_hevReadersCleared,INFINITE);
    }

    void LeaveWriter(void)
    {
        LeaveCriticalSection(&m_csWrite);
    }
};

I didn't have a chance to try it, but the code looks OK.

我没有机会尝试，但代码看起来不错。

回答by Nikos

You can implement a Readers-Writers lock following the exact Wikipedia algorithm from here(I wrote it):

您可以按照此处的确切 Wikipedia 算法实现 Readers-Writers 锁（我写的）：

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

int g_sharedData = 0;
int g_readersWaiting = 0;
std::mutex mu;
bool g_writerWaiting = false;
std::condition_variable cond;

void reader(int i)
{
    std::unique_lock<std::mutex> lg{mu};
    while(g_writerWaiting)
        cond.wait(lg);
    ++g_readersWaiting;
    // reading
    std::cout << "\n reader #" << i << " is reading data = " << g_sharedData << '\n';
    // end reading
    --g_readersWaiting;
    while(g_readersWaiting > 0)
        cond.wait(lg);
    cond.notify_one();
}

void writer(int i)
{
    std::unique_lock<std::mutex> lg{mu};
    while(g_writerWaiting)
        cond.wait(lg);
    // writing
    std::cout << "\n writer #" << i << " is writing\n";
    g_sharedData += i * 10;
    // end writing
    g_writerWaiting = true;
    while(g_readersWaiting > 0)
        cond.wait(lg);
    g_writerWaiting = false;
    cond.notify_all();
}//lg.unlock()


int main()
{
    std::thread reader1{reader, 1};
    std::thread reader2{reader, 2};
    std::thread reader3{reader, 3};
    std::thread reader4{reader, 4};
    std::thread writer1{writer, 1};
    std::thread writer2{writer, 2};
    std::thread writer3{writer, 3};
    std::thread writer4{reader, 4};

    reader1.join();
    reader2.join(); 
    reader3.join();
    reader4.join();
    writer1.join();
    writer2.join();
    writer3.join();
    writer4.join();

    return(0);
}