Reader Writer Lock支持低优先级编写器(Reader Writer Lock supporting low priority writers)

Reader Writer Lock支持低优先级编写器(Reader Writer Lock supporting low priority writers)

我试图找到（或实现）支持低优先级写入器的读取器/写入器锁，但是在研究任何现有解决方案方面都没有成功。

我对低优先级作家的意思是：“将会对即将到来的读者或普通作家产生影响。”

如果有一个恒定的读者流，肯定会导致饥饿，但这可以通过定时锁定变量（“尝试定时低优先级写入程序锁定”然后切换到超时时的正常锁定）或通过改变读者的方式来解决发布（可能会定期暂停读取短窗口）。

如果有任何文献描述这些方面的东西，我还没有找到它。

如果有一个已知的（正确！）解决方案利用常规锁，我将不胜感激。

I am trying to find (or implement) a Reader/Writer Lock which supports low-priority writers, but have been unsuccessful in researching any existing solutions.

What I mean by low-priority writer is: "will yield its place in line" to incoming readers or normal writers.

Certainly will lead to starvation if there is a constant stream of readers, but this could be solved either with a timed lock variant ("try timed low priority writer lock" and then switching to a normal lock on timeout) or by changing the way readers are issued (perhaps periodically halting reads for a short window).

If there is any literature describing something along these lines, I have not found it.

If there is a known (correct!) solution leveraging regular locks, I would would appreciate a description.

最满意答案

我不知道任何100％喜欢你的提议，但有一些现有的接口是接近的：

许多现有的r / w锁API都有一个“try lock”接口，比如UN * X系统上的pthread_rwlock_trywrlock() 。 这些都是无等待的，如果没有人拥有它也不会获得锁定，也不会等待它。

您通常使用此旋转来锁定，和/或人为地延迟尝试代码（退出）。 即具有以下代码：

for (count = 0; count < MAX_SPINS && (locked = trywrlock(lock)); count++); if (locked) { delay(some_backoff); wrlock(lock); /* or try spinning loop above again ? */ }

不幸的是，这并不是你要求的; 它会让锁定得更晚，但是由于（可能没有必要的）退避，低价的作家会在CPU上旋转和/或以延迟的方式获得它。

Solaris内核有一个接口rw_tryupgrade(9f) ，可用于测试当前线程是否是锁上唯一没有编写器等待的读取器，如果是，则将锁升级为exclusive / write，即你的代码如下：

if (!rw_tryenter(lock, RW_WRITER)) { rw_enter(lock, RW_READER); /* this might wait for a writer */ if (!rw_tryupgrade(lock)) { /* this fails if >1 reader / writer waiting */ /* do what you must to if you couldn't get in immediately */ } }

哪个更接近你要求的但仍然不完全相同 - 如果它失败了，你必须放弃读锁定，可能退回（等待），重新获得readlock，尝试升级。 这个过程再次成为旋转。

此外，许多UNIX系统至少实际按照调度优先级执行服务员唤醒; 因此在尝试普通的等待的wrlock()调用之前，你必须让你的线程具有最低优先级（如果必要的话，人为地）; 根据调度程序的工作原理，当你的线程在等待时，其他人想要相同的writelock将在此之前得到它。 虽然在多处理器/核心系统上不一定能得到保证......

最后，SymbianOS（Symbian ^ 3版本）有一个RRWlock类，可以使读者优先于作者，因此如果有读者等待/进入，它会故意使作者饿死。再次，不完全是你想要的行为，因为它会影响给定锁上的所有作者，而不仅仅是特定锁。

我担心你必须编写自己的优先锁定，有两个写入唤醒队列。

I don't know anything 100% like your proposal, but there's some existing interfaces that are close:

Many existing r/w lock APIs have a "try lock" interface, like pthread_rwlock_trywrlock() on UN*X systems. These are wait-free and will only acquire the lock if noone owns it nor waits for it already.

You'd normally use this spinning for the lock, and/or artificially delaying the try code (back off). I.e. have code like:

for (count = 0; count < MAX_SPINS && (locked = trywrlock(lock)); count++); if (locked) { delay(some_backoff); wrlock(lock); /* or try spinning loop above again ? */ }

Unfortunately this isn't exactly what you ask for; it'll get the lock late alright, but the low-prio writer will spin on CPU and/or get it in a delayed fashion due to the (possibly unnecessary) backoff.

The Solaris kernel has an interface rw_tryupgrade(9f) that can be used to test if the current thread is the only reader on the lock with no writer waiting and if so, upgrade the lock to exclusive/write, i.e. you'd code like:

if (!rw_tryenter(lock, RW_WRITER)) { rw_enter(lock, RW_READER); /* this might wait for a writer */ if (!rw_tryupgrade(lock)) { /* this fails if >1 reader / writer waiting */ /* do what you must to if you couldn't get in immediately */ } }

Which is a bit closer to what you ask for but still not quite the same - if it fails, you'd have to drop the readlock, possibly back off (wait), reaquire the readlock, try to upgrade. That process again amounts to spinning.

Also, many UNIX systems at least actually perform waiter wakeups in order of scheduling priority; so you'd have to make your thread lowest priority (if necessarily, artificially) before attempting an ordinary, waiting wrlock() call; whoever else wants the same writelock while your thread is waiting will get it before that, by virtue of how the scheduler works. Though on multiprocessor/core systems that's not necessarily guaranteed ...

Finally, SymbianOS (the Symbian^3 version) has a RRWlock class that can be made to prioritize readers over writers, so that it will deliberately starve writers if there are readers waiting / coming in. Again, not quite exactly the behaviour you want, as it affects all writers on a given lock, not just a specific one.

I'm afraid you'd have to write your own prioritized lock, with two writer wakeup queues.