如何让Windows slim读写locking公平?

我发现窗口实现了一个苗条的读写器锁(请参阅https://msdn.microsoft.com/en-us/library/windows/desktop/aa904937%28v=vs.85%29.aspx )。 不幸的是(对于我来说)这个locking既不是fifo,也不是公平的(在任何意义上)。 是否有可能使一些解决方法公平或先锋的窗户locking? 如果没有,在哪种情况下你会使用Windows slim rw-lock?

Solutions Collecting From Web of "如何让Windows slim读写locking公平?"

你不可能把细长的锁本身改成公平的,尤其是因为文档没有说明这样做的方法,而且今天大多数锁定对于性能的原因是不公平的。

也就是说,使用Windows 事件处理自己的近似FIFO锁定以及使用比较和交换处理的64位控制字非常简单。 这是一个大纲:

锁的状态反映在控制字中被原子操纵以在状态之间转换,并且允许线程通过单个原子操作进入锁(如果允许的话)并且没有内核切换(这是“slim”的性能部分) 。 重置事件用于通知等待线程,当线程需要阻塞并且可以按需分配(这是slim的低内存占用)。

锁控制字具有以下状态:

  1. 免费 – 没有读者或作家,也没有服务员。 任何线程都可以通过原子地将锁转换到状态(2)或(3)来获取读或写锁。

  2. N位读者在锁定。 目前锁中有N个读卡器。 新读者可以通过在计数上加1来立即获得锁定 – 使用控制字中的30位左右的字段来表示该计数。 作家必须阻止(也许在转动之后)。 当读者离开锁时,他们递减计数,当最后一个读者离开时(尽管他们不需要在(2) – >(1)转换中做任何特殊的事情),计数可以转换到状态(1)。

  3. 状态(2)+等待作者+ 0或更多的等待阅读者。 在这种状态下,有一个或更多的读者仍然在锁,但至少有一个等待作家。 作者应该等待一个手动重置事件,虽然不能保证这个事件被设计成FIFO。 控制字中有一个字段表示有多少个作者正在等待。 在这种状态下,想要进入锁的新阅读器不能,而是设置一个阅读器等待位,并阻止阅读器等待事件。 新的写入器增加了等待写入器计数并阻止写入器等待事件。 当最后一个阅读器离开(将阅读器计数字段设置为0)时,它发出写入器等待事件的信号 ,释放等待时间最长的作者进入锁定。

  4. 作家在锁。 当一个作者在锁,所有的读者排队等候在读者等待事件。 所有传入的写入程序都会在写入程序等待事件中像往常一样递增等待写入程序计数并排队。 由于上面的状态(3),当作者获得锁时,甚至可能有一些等待的读者,并且这些都是一致的。 当作者离开锁定时,它会检查等待的作者和读者,并根据下面讨论的策略来取消对作者或所有读者的阻止。

上面讨论的所有状态转换都是使用比较和交换原子地完成的。 典型的模式是,任何lock()unlock()调用都会查看控制字,确定它们处于什么状态以及需要发生什么样的转换(遵循上述规则),然后暂时计算新的控制字尝试用比较和交换来交换新的控制字。 有时这种尝试失败是因为另一个线程同时修改了控制字(例如,另一个读者进入了锁,增加了读者的数量)。 没问题,从“确定状态…”重新开始,然后重试。 这种种族在实践中很少见,因为国家字的计算很短,这就是基于CAS的复杂锁的工作原理。

这种锁定设计“苗条”几乎是每个感觉。 在性能方面,它接近您可以获得的通用设计的顶端。 (a)读者进入锁的普通快速路径已经在(b)读者中的0个或更多的读者将锁留在锁中,0个或更多的读者仍然在锁中并且(c)写入者进入/离开通常情况下,无锁锁定的速度都是尽可能快的:单个原子操作。 此外,读者进入和退出路径是“锁定自由”的,即传入的读者不会暂时在rwlock内部获取互斥锁,操纵状态,然后在进入/离开锁时解锁它。 这种方法是缓慢的,每当读者线程在关键时刻执行上下文切换时,都会遇到问题。 这种方法不能通过一个短的临界区来扩展阅读器的活动:即使多个阅读器在理论上可以进入临界区,但它们都是进入和离开内部锁的瓶颈(每进入/退出操作会发生两次)和性能比正常的互斥体差!

它也是轻量级的,它只需要几个Windows事件对象,并且这些对象可以按需分配 – 只有在发生争用时才需要这些对象,并且即将发生需要阻塞的状态转换。 这就是CRITICAL_SECTION对象的工作方式。

上面的锁定是公平的,读者不会阻止作者,而作者是按先进先出的顺序进行的。 作家如何与等待的读者进行互动,取决于你的策略,即在作家解锁之后,当锁被释放并且有读者和作者等待的时候,谁来解锁。 简单的政策是打开所有等待的读者。

在这个设计中,作者将按先进先出的顺序与FIFO批次的阅读器交替。 编写者相对于其他编写者而言是FIFO,而读者批量是相对于其他读者批次而言的FIFO,但编写者和读者之间的关系并不完全是 FIFO:因为所有传入的读者被添加到相同的等待读取者集合,已经有好几个等待的作家,到达的读者都会进入下一个“批”发行,这实际上使他们领先于那些已经在等待的作家。 这是相当合理的:读者都马上去,所以在批处理中增加更多的读者并不需要花太多的钱,并且可能会提高效率,如果你按照严格的先进先出顺序为所有的东西提供服务,那么锁的行为就会减少到简单互斥之下的争夺。

另一种可能的设计是,如果任何人在等待,总是解除封锁。 这有利于作家牺牲读者的利益,这意味着一个永无止境的作家流可以无限期地阻止读者。 这种方法是有道理的,在这种情况下,你知道你的写入对延迟敏感很重要,或者你不担心读者的匮乏,或者你知道它不会发生,因为你的应用程序的设计(例如,因为只有一个可能的作者一次)。

除此之外,还有很多其他的政策是可能的,例如在读者等待一段时间之前支持作者,或限制读者批量大小等等。 他们大多可以有效地实现,因为簿记一般局限于线程阻塞的缓慢路径。

我已经在这里掩盖了一些实现细节和陷阱(特别是在进行涉及阻塞的转换时需要小心以避免“错过唤醒”问题) – 但是这一定是有效的。 我已经写出了这样一个锁,在这个超薄的rwlock之前存在,以满足一个快速的高性能rwlock的需要,它表现非常好。 其他的权衡也是可能的,例如,对于期望读取占主导地位的设计,可以通过跨越高速缓存行分割控制字来降低争用,代价是更昂贵的写入操作。

最后一个注意事项 – 在内存使用方面,这个锁比在Windows中被调用的情况下稍微胖一些 – 因为它为每个锁分配一个或两个窗口事件,而细长锁则避免这种情况。 细长锁定可能是通过直接支持内核中细长的锁定行为来实现的,所以控制字可以直接用作内核等待列表的一部分。 你不能完全重现,但是你仍然可以用另一种方式去除每个锁的开销:使用线程本地存储来为每个线程分配你的两个事件而不是每个锁。 由于线程一次只能等待一个锁,所以每个线程只需要一个这样的结构。 这使得它与内存使用中的细长锁定(除非你有很少的锁和大量的线程)。

这个锁是既不是fifo也不公平

除非它明确表示,否则我不会期望线程成为“公平的”或“fifo”。 在这种情况下,我希望编写锁优先,因为如果有大量的读线程,它可能永远无法获得锁,但是我也不会认为是这种情况,而且我还没有阅读MS文档有更好的理解。

这就是说,这听起来像你的问题是,你有锁的争论,由写入线程造成的; 因为否则你的读者将永远能够分享锁定。 你可能应该仔细研究一下为什么你的写作线索试图锁定这么长时间; 缓冲补充例如将有助于缓解这一点。