读者/作家的锁...没有读者的锁? [英] A readers/writer lock... without having a lock for the readers?

问题描述

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

I get the feeling this may be a very general and common situation for which a well-known no-lock solution exists.

简而言之，我希望可以采用类似读/写器锁定的方法，但这并不需要读取器获得锁定，因此可以获得更好的平均性能.

In a nutshell, I'm hoping there's approach like a readers/writer lock, but that doesn't require the readers to acquire a lock and thus can be better average performance.

取而代之的是，阅读器需要进行一些原子操作(128位CAS)，而编写器则需要进行互斥操作.我将有两个数据结构副本，一个用于正常成功查询的只读副本，以及一个在互斥保护下进行更新的相同副本.将数据插入可写副本后，我们将其设为新的可读副本.一旦所有待处理的阅读器都读取完该旧可读副本，然后依次插入该副本，然后作者将剩余的阅读器数量旋转至零，然后对其进行修改，最后释放互斥锁.

Instead there'd be some atomic operations (128-bit CAS) for a reader, and a mutex for a writer. I'd have two copies of the data structure, a read-only one for the normally-successful queries, and an identical copy to be update under mutex protection. Once the data has been inserted into the writable copy, we make it the new readable copy. The old readable copy then gets inserted in turn, once all the pending readers have finished reading it, and the writer spins on the number of readers left until its zero, then modifies it in turn, and finally releases the mutex.

或者类似的东西.

有没有类似的东西存在?

Anything along these lines exist?

推荐答案

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

If your data fits in a 64-bit value, most systems can cheaply read/write that atomically, so just use std::atomic<my_struct>.

对于较小和/或不经常写入的数据，有两种方法可以使读者真正对共享数据进行只读操作，而不必在共享计数器上执行任何原子RMW操作或任何事物.这样一来，读取方就可以扩展到多个线程，而无需读者相互竞争(与使用lock cmpxchg16b或使用RWlock在x86上进行的128位原子读取不同).

For smallish and/or infrequently-written data, there are a couple ways to make readers truly read-only on the shared data, not having to do any atomic RMW operations on a shared counter or anything. This allows read-side scaling to many threads without readers contending with each other (unlike a 128-bit atomic read on x86 using lock cmpxchg16b, or taking a RWlock).

理想情况下，只是通过atomic<T*>指针(RCU)进行的间接间接访问，或者只是额外的负载+比较和分支(SeqLock)；在读取方面，没有比acq/rel或其他任何东西强大的原子RMW或内存屏障.

Ideally just an extra level of indirection via an atomic<T*> pointer (RCU), or just an extra load + compare-and-branch (SeqLock); no atomic RMWs or memory barriers stronger than acq/rel or anything else in the read side.

这可能适用于许多线程频繁读取的数据，例如由计时器中断更新的时间戳记，但可在各处读取.或通常不会更改的配置设置.

This can be appropriate for data that's read very frequently by many threads, e.g. a timestamp updated by a timer interrupt but read all over the place. Or a config setting that typically never changes.

如果您的数据更大和/或更频繁地更改，则其他答案中建议的一种策略要求读者仍然对某物进行RWlock或原子地递增计数器会更合适. .由于每个读者仍然需要获得包含锁或计数器的共享高速缓存行的专有所有权，以便可以对其进行修改，所以这并不能完美地实现，但是没有免费的午餐之类的东西.

If your data is larger and/or changes more frequently, one of the strategies suggested in other answers that requires a reader to still take a RWlock on something or atomically increment a counter will be more appropriate. This won't scale perfectly because each reader still needs to get exclusive ownership of the shared cache line containing lock or counter so it can modify it, but there's no such thing as a free lunch.

听起来您正在发明RCU的中途(读取副本更新)，在那里您将指针更新为新版本.

It sounds like you're half-way to inventing RCU (Read Copy Update) where you update a pointer to the new version.

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

But remember a lock-free reader might stall after loading the pointer, so you have a deallocation problem. This is the hard part of RCU. In a kernel it can be solved by having sync points where you know that there are no readers older than some time t, and thus can free old versions. There are some user-space implementations. https://en.wikipedia.org/wiki/Read-copy-update and https://lwn.net/Articles/262464/.

对于RCU，更改的频率越低，可以证明进行复制的数据结构就越大.如果读者只能在管理员交互地更改它的情况下，即使是中等大小的树也是可行的，而阅读器则在数十个内核上运行，并且全部并行地进行检查.例如内核配置设置是RCU在Linux中很棒的一件事.

For RCU, the less frequent the changes, the larger a data structure you can justify copying. e.g. even a moderate-sized tree could be doable if it's only ever changed interactively by an admin, while readers are running on dozens of cores all checking something in parallel. e.g. kernel config settings are one thing where RCU is great in Linux.

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

If your data is small (e.g. a 64-bit timestamp on a 32-bit machine), another good option is a SeqLock. Readers check a sequence counter before/after non-atomic copy of the data into a private buffer. If the sequence counters match, we know there wasn't tearing. (Writers mutually exclude each with a separate mutex). 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个字节的方法.)

It's a bit of a hack in C++ to write something that can compile efficiently to a non-atomic copy that might have tearing, because inevitably that's data-race UB. (Unless you use std::atomic<long> with mo_relaxed for each chunk separately, but then you're defeating the compiler from using movdqu or something to copy 16 bytes at once.)

SeqLock使读取器在每次读取时都复制整个内容(或理想地将其加载到寄存器中)，因此它仅适用于较小的结构或128位整数之类的东西.比64字节的数据要好得多，如果读者很多且不经常写入，则比让读者使用lock cmpxchg16b来处理128位数据要好.

A SeqLock makes the reader copy the whole thing (or ideally just load it into registers) every read so it's only ever appropriate for a small struct or 128-bit integer or something. But for less than 64 bytes of data it can be quite good, better than having readers use lock cmpxchg16b for a 128-bit datum if you have many readers and infrequent writes.

但是，它并非不是无锁的:编写器在修改SeqLock时处于休眠状态，可能会使读者无限期地重试.对于较小的SeqLock，窗口很小，显然，您希望在执行第一次序列计数器更新之前准备好所有数据，以最大程度地减少在中期更新期间中断编写器的中断机会.

It's not lock-free, though: a writer that sleeps while modifying the SeqLock could get readers stuck retrying indefinitely. For a small SeqLock the window is small, and obviously you want to have all the data ready before you do the first sequence-counter update to minimize the chance for an interrupt pausing the writer in mid update.

最好的情况是只有1个写程序，因此不必进行任何锁定.它不知道会修改序列计数器.

The best case is when there's only 1 writer so it doesn't have to do any locking; it knows nothing else will be modifying the sequence counter.

这篇关于读者/作家的锁...没有读者的锁?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！