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