读者/写者锁...没有读者锁？

Question

我感觉这可能是一种非常普遍和常见的情况，对此有一个众所周知的无锁解决方案。

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

相反，对于读取器来说会有一些原子操作（128 位 CAS），对于写入器来说会有一个互斥锁。我有数据结构的两个副本，一个用于正常成功查询的只读副本，以及一个要在互斥锁保护下更新的相同副本。将数据插入可写副本后，我们将其设为新的可读副本。一旦所有待处理的读取器都读完它，旧的可读副本就会被依次插入，写入器会旋转剩余的读取器数量，直到其为零，然后依次修改它，最后释放互斥体。

或类似的东西。

存在这样的东西吗？

Answer 1

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

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

理想情况下，只是通过指针（RCU）进行额外的间接访问atomic<T*>，或者只是额外的加载+比较和分支（SeqLock）；没有比 acq/rel 或读取端的其他任何内容更强的原子 RMW 或内存屏障。

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

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

注 1：更新：x86 供应商最终决定保证 128 位 SSE/AVX 加载/存储在具有 AVX 的 CPU 上是原子的，因此，如果幸运的话，std::atomic<16-byte-struct>在启用 AVX 的 CPU 上运行时可以便宜地加载。例如，在 Ice Lake 之前不是 Pentium/Celeron。GCC 一段时间以来一直在间接调用 libgccatomic_load_16函数来进行 16 字节操作，因此它的运行时调度可以lock cmpxchg16b在支持它的 CPU 上选择一种策略。现在，它在某些 CPU 上有更好的选择。

远程控制单元

听起来您发明 RCU（读取复制更新）的工作已完成一半，您可以在其中更新指向新版本的指针。

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

对于 RCU，更改越不频繁，可以复制的数据结构就越大。 例如，即使是中等大小的树，如果仅由管理员交互更改，也是可行的，而读取器在数十个内核上运行，所有内核都并行检查某些内容。例如，内核配置设置是 RCU 在 Linux 中非常有用的一件事。

顺序锁

如果您的数据很小（例如 32 位机器上的 64 位时间戳），另一个不错的选择是 SeqLock。读取器在将数据非原子复制到专用缓冲区之前/之后检查序列计数器。如果序列计数器匹配，我们就知道没有撕裂。（编写者使用单独的互斥体相互排除）。 使用 32 位原子实现 64 位原子计数器/如何使用 c++11 原子库实现 seqlock 锁。

在 C++ 中编写一些可以有效编译为可能会撕裂的非原子副本的东西有点像黑客，因为不可避免地会出现数据争用 UB。（除非你分别对每个块使用std::atomic<long>with mo_relaxed，但是这样你就会阻止编译器使用movdquor 来一次复制 16 个字节。）

SeqLock 使读取器在每次读取时复制整个内容（或者理想情况下只是将其加载到寄存器中），因此它只适用于小型结构或 128 位整数或其他内容。 但对于少于 64 字节的数据来说，它可能非常好，lock cmpxchg16b如果您有很多读取器且写入不频繁，则比让读取器使用 128 位数据要好。

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

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

Answer 2

您所描述的与双实例锁定和左右并发控制非常相似。

在进度保证方面，两者的区别在于前者对读者来说是无锁的，而后者是无等待的。两者都对作家造成阻碍。