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

Question

我有一组数据结构,我需要用读/写锁来保护.我知道boost :: shared_lock,但我想使用std :: mutex,std :: condition_variable和/或std :: atomic进行自定义实现,这样我就能更好地理解它是如何工作的(稍后再调整) .

每个数据结构(可移动但不可复制)将从一个名为Commons的类继承,该类封装了锁定.我希望公共接口看起来像这样:

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

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

...以便某些人可以公开继承:

class DataStructure : public Commons {};

我正在编写科学代码,通常可以避免数据争用; 这种锁定主要是为了防止我以后可能犯的错误.因此,我的优先级是低读取开销,所以我不会妨碍正确运行的程序太多.每个线程可能都在自己的CPU核心上运行.

你能告诉我(伪代码是好的)读者/作家锁吗？我现在所拥有的应该是防止作家饥饿的变种.到目前为止,我的主要问题是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;
}

我对多线程有点新意,我真的很想理解它.在此先感谢您的帮助!

Answer 1

这是使用互斥锁和条件变量的ver简单读取器/写入器锁的伪代码.互斥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();
}

但是,这种实现有很多缺点.

锁定可用时唤醒所有服务员

如果大多数服务员都在等待写锁定,那就太浪费了 - 毕竟大多数服务员都无法获得锁定,并且继续等待.简单地使用signal()不起作用,因为你确实想要唤醒所有人等待读锁解锁.因此,为了解决这个问题,您需要单独的条件变量来实现可读性和可写性.

没有公平.读者们饿死了作家

您可以修复,通过跟踪未决阅读次数和写锁,要么停止采集读锁曾经有一个挂起写锁(虽然你会饿死,然后读者!),或者随机醒来要么所有的读者或一个作家(假设您使用单独的条件变量,请参阅上面的部分).

锁不按请求的顺序处理

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

即使是纯读取工作负载也会因互斥锁而导致争用

这个很难解决.一种方法是使用原子指令来获取读或写锁(通常是比较和交换).如果由于锁定而导致采集失败,则必须回退到互斥锁.但是,正确地做到这一点非常困难.此外,仍然存在争用 - 原子指令远非免费,特别是在具有大量内核的机器上.

结论

正确实现同步原语很难.实现高效且公平的同步原语更加 困难.它几乎没有回报.在Linux并行线程,例如包含使用futexes的和原子操作指令的组合,并因此可能优于任何你可以在工作几天拿出一个读/写锁.

Answer 2

检查这个课程:

//
// Multi-reader Single-writer concurrency base class for Win32
//
// (c) 1999-2003 by Glenn Slayden (glenn@glennslayden.com)
//
//


#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);
    }
};

我没有机会尝试它,但代码看起来还不错.