我发现 Windows 实现了一个纤薄的读写器锁(参见https://msdn.microsoft.com/en-us/library/windows/desktop/aa904937%28v=vs.85%29.aspx)。不幸的是(对我来说)这个 rw-lock 既不是先进先出也不公平(在任何意义上)。是否有可能通过一些解决方法公平或先进先出使 Windows rw-lock?如果不是,您会在哪些情况下使用 windows slim rw-lock?
2 回答
您不太可能将苗条锁本身更改为公平的,特别是因为文档没有说明这样做的任何方法,而且今天大多数锁出于性能原因是不公平的。
也就是说,使用 Windows事件滚动您自己的近似 FIFO 锁是相当简单的,并且您可以通过比较和交换操作的 64 位控制字仍然非常小。这是一个大纲:
锁的状态反映在控制字被原子操作以在状态之间转换,并允许线程通过单个原子操作和没有内核切换(这是“slim”的性能部分)进入锁(如果允许) . 重置事件用于通知等待线程,当线程需要阻塞并且可以按需分配时(这是 slim 的低内存占用)。
锁定控制字具有以下状态:
免费 - 没有读者或作家,也没有服务员。任何线程都可以通过原子地将锁转换为状态 (2) 或 (3) 来获取用于读取或写入的锁。
N 个读卡器在锁中。目前锁中有N个读卡器。新读者可以通过将计数加 1 来立即获得锁——在控制字中使用一个 30 位左右的字段来表示这个计数。作家必须阻止(也许在旋转之后)。当读者离开锁时,他们会减少计数,当最后一个读者离开时,它可能会转换到状态 (1)(尽管他们不需要在 (2) -> (1) 转换中做任何特殊的事情)。
状态 (2) + 等待写入者 + 0 个或更多等待读取者。在这种状态下,还有 1 个或多个读者仍处于锁中,但至少有一个正在等待的写者。编写器应等待手动重置事件,该事件被设计为(尽管不能保证)为 FIFO。控制字中有一个字段来指示有多少写入器正在等待。在这种状态下,想要进入锁的新读者不能,而是设置一个读者等待位,并阻止读者等待事件。新写入者增加等待写入者计数并阻止写入者等待事件。当最后一个读者离开时(将 reader-count 字段设置为 0),它会发出writer-waiting 事件的信号,释放等待时间最长的 writer 进入锁。
锁中的作家。当写入者处于锁定状态时,所有读取者都会排队等待读取者等待事件。所有传入的写入者都会增加等待写入者的计数,并像往常一样在写入者等待事件中排队。由于上面的状态(3),写入者在获取锁时甚至可能有一些等待的读取者,这些被同等对待。当写入者离开锁时,它会检查等待的写入者和读取者,并根据策略解除对写入者或所有读取者的阻塞,如下所述。
上面讨论的所有状态转换都是使用比较和交换以原子方式完成的。典型的模式是任何lock()
orunlock()
调用查看控制字,确定它们处于什么状态以及需要发生什么转换(遵循上面的规则),临时计算新的控制字然后尝试交换新的控制字具有比较和交换的控制字。有时该尝试会失败,因为另一个线程同时修改了控制字(例如,另一个读取器进入了锁,增加了读取器计数)。没问题,从“确定状态...”重新开始,然后再试一次。这种竞争在实践中很少见,因为状态字计算非常短,而这正是基于 CAS 的复杂锁的工作方式。
这种锁设计“纤薄”几乎是每一种感觉。在性能方面,它接近通用设计所能达到的最高水平。特别是,常见的快速路径(a)读取器进入锁,0 个或多个读取器已经在块中(b)读取器离开锁,0 或多个读取器仍在锁中,(c)写入器进入/离开一个在通常情况下,非竞争锁都尽可能快:单个原子操作。此外,读卡器进入和退出路径是“无锁的”,因为传入的读卡器不会临时获取 rwlock 内部的互斥锁,操纵状态,然后在进入/离开锁时解锁它。这种方法很慢,并且每当读取器线程在持有内部锁的关键时刻执行上下文切换时都会出现问题。
它也是轻量级的,因为它只需要几个 Windows Event 对象,并且可以按需分配这些对象——它们仅在发生争用并且需要阻塞的状态转换即将发生时才需要。这就是CRITICAL_SECTION对象的工作方式。
从某种意义上说,上面的锁是公平的,读者不会阻塞写者,写者按 FIFO 顺序提供服务。写者如何与等待的读者交互取决于你的策略,即当写者解锁后锁变为空闲并且有等待的读者和写者时,谁来解除阻塞。简单的策略是解除所有等待的读者的阻塞。
在此设计中,写入器将按 FIFO 顺序与 FIFO 批次的读取器交替。writers 相对于其他 writers 是 FIFO,reader batches 是 FIFO 相对于其他 reader batches,但是 writers 和 reader 之间的关系并不完全是FIFO:因为所有传入的 reader 都被添加到同一个 reader-waiting set 中,在这种情况下已经有几个等待的作家,到达的读者都进入下一个要发布的“批次”,这实际上使他们领先于已经在等待的作家。不过,这很合理:读者都同时去了,因此向批处理中添加更多读取器不需要太多成本,并且可能会提高效率,并且如果您确实以严格的 FIFO 顺序为所有线程提供服务,那么锁的行为将减少为争用下的简单互斥锁。
另一种可能的设计是,如果有正在等待的写入器,则始终解除对写入器的阻止。这以牺牲读者为代价有利于作家,并且确实意味着永无止境的作家流可能会无限期地阻止读者。如果您知道写入对延迟敏感很重要,并且您不担心读取器饥饿,或者您知道由于应用程序的设计而不会发生这种情况(例如,因为只有一个可能的写入器在一次)。
除此之外,还有许多其他可能的策略,例如在读者等待一段时间之前偏爱作者,或者限制读者批量大小等。它们最有可能有效地实现,因为簿记通常仅限于线程无论如何都会阻塞的慢速路径。
我在这里忽略了一些实现细节和陷阱(特别是在进行涉及阻塞的转换时需要小心以避免“错过唤醒”问题)——但这绝对有效。在超薄 rwlock 出现之前,我已经编写了这样一个锁来满足对快速高性能 rwlock 的需求,并且它的性能非常好。其他折衷也是可能的,例如,对于预期读取占主导地位的设计,可以通过在高速缓存行之间拆分控制字来减少争用,但代价是更昂贵的写入操作。
最后一点 - 在内存使用方面,这个锁比在竞争情况下的 Windows 锁要胖一些 - 因为它为每个锁分配一个或两个 windows 事件,而纤细的锁避免了这种情况。slim lock 很可能是通过直接支持内核中的 slim lock 行为来实现的,因此控制字可以直接用作内核端等待列表的一部分。您无法准确地重现这一点,但您仍然可以通过另一种方式消除每个锁的开销:使用线程本地存储来为每个线程而不是每个锁分配两个事件。由于一个线程一次只能等待一个锁,因此每个线程只需要一个这个结构。这使它与内存使用中的小锁保持一致(除非你有很少的锁和大量的线程)。
这个 rw-lock 既不是先进先出也不公平
我不希望线程是“公平”或“先进先出”的,除非它明确表示。在这种情况下,我希望写锁优先,因为如果有很多读取线程,它可能永远无法获得锁,但我也不会假设是这种情况,我没有读过MS 文档以便更好地理解。
也就是说,听起来您的问题是由于写线程引起的锁争用很多;因为否则您的读者将始终能够共享锁。您可能应该检查为什么您的编写线程试图保持锁定这么长时间;例如,缓冲添加将有助于缓解这种情况。