c++ - 读者/作者锁...没有读者锁？

Question

我觉得这可能是一种非常普遍和常见的情况，存在众所周知的无锁解决方案。

简而言之，我希望有像读者/作者锁这样的方法，但这不需要读者获取锁，因此可以获得更好的平均性能。

相反，读者需要一些原子操作(128 位 CAS)，而编写者需要互斥。我有数据结构的两个拷贝，一个用于正常成功查询的只读拷贝，以及一个在互斥保护下更新的相同拷贝。将数据插入可写拷贝后，我们将其设为新的可读拷贝。旧的可读拷贝然后依次插入，一旦所有挂起的读取器都完成了读取，并且写入器旋转剩余的读取器数量直到其为零，然后依次修改它，最后释放互斥锁。

或类似的东西。

任何沿着这些路线的东西存在吗？

Answer 1

如果您的数据适合 64 位值，大多数系统可以廉价地以原子方式读取/写入，因此只需使用 std::atomic<my_struct> .

对于较小和/或不常写入的数据 ，有几种方法可以让读者真正对共享数据只读，而不必对共享计数器或任何东西进行任何原子 RMW 操作。这允许读取端扩展到多个线程，而无需读取器相互竞争(与 x86 上使用 lock cmpxchg16b 或采用 RWlock 的 128 位原子读取不同)。

理想情况下只是通过 atomic<T*> 额外的间接级别指针(RCU)，或者只是一个额外的负载+比较和分支(SeqLock)；在读取端没有比 acq/rel 或其他任何东西更强的原子 RMW 或内存屏障。

这适用于许多线程非常频繁地读取的数据，例如由定时器中断更新但到处读取的时间戳。或者一个通常永远不会改变的配置设置。

如果您的数据更大和/或更频繁地更改，其他答案中建议的策略之一 要求读者仍然对某事采取 RWlock 或以原子方式递增计数器将更合适。这不会完美扩展，因为每个读取器仍然需要获得包含锁或计数器的共享缓存行的独占所有权，以便它可以修改它，但没有免费午餐这样的东西。

区域控制单元

听起来像 您已经完成了 RCU 的发明 (Read Copy Update) 在其中更新指向新版本的指针。

但是请记住，无锁读取器在加载指针后可能会停止，因此您会遇到释放问题。这是 RCU 的难点。在内核中，它可以通过设置同步点来解决，在那里你知道没有比某个时间 t 更旧的读者，因此可以释放旧版本。有一些用户空间实现。 https://en.wikipedia.org/wiki/Read-copy-update和 https://lwn.net/Articles/262464/ .

对于 RCU，更改的频率越低，您可以证明复制的数据结构就越大。 例如如果只有管理员以交互方式更改它，即使是中等大小的树也是可行的，而读者在数十个内核上运行，所有内核都在并行检查某些内容。例如内核配置设置是 RCU 在 Linux 中很棒的一件事。

序列锁

如果您的数据很小(例如 32 位机器上的 64 位时间戳)，另一个不错的选择是 SeqLock。读取器在将数据非原子复制到私有(private)缓冲区之前/之后检查序列计数器。如果序列计数器匹配，我们就知道没有撕裂。 (作家用单独的互斥体相互排斥)。 Implementing 64 bit atomic counter with 32 bit atomics/how to implement a seqlock lock using c++11 atomic library .

在 C++ 中编写一些可以有效编译为可能会撕裂的非原子拷贝的东西有点小技巧，因为不可避免地会出现数据竞争 UB。 (除非您将 std::atomic<long> 和 mo_relaxed 分别用于每个块，但是这样您就无法使用 movdqu 或其他东西一次复制 16 个字节。)

SeqLock 使读取器在每次读取时都复制整个内容(或者理想情况下只是将其加载到寄存器中)，因此它仅适用于小型结构或 128 位整数或其他内容。 但是对于少于 64 字节的数据，它可以相当好，比让读者使用 lock cmpxchg16b 更好。对于 128 位数据，如果您有很多读者并且很少写入。

但是，它不是无锁的:在修改 SeqLock 时休眠的写入器可能会使读取器无限期地重试。对于一个小的 SeqLock，窗口很小，很明显，您希望在进行第一次序列计数器更新之前准备好所有数据，以最大限度地减少中断在更新过程中暂停编写器的机会。

最好的情况是只有 1 个编写器，因此它不必进行任何锁定；它知道没有其他东西会修改序列计数器。