单个进程中有数千个读/写锁

Question

我目前正在设计一个跨平台的C++服务器应用程序(Linux/Windows)，它具有大规模同步模式。我在内部使用boost::thread作为操作系统特定线程的抽象。我的问题是保护一个数据数组，数组的每个元素都受到独立的读写锁的保护。

我的数组包含4096个元素。考虑到“写者优先读者-写者”问题的解决方案，该问题在“Little Book of Semaphores”(第85页)中提出，我的应用程序需要每个数组元素5个信号量。这总共需要约20000个信号量(或等效地，20000个互斥量+20000个条件变量)。

我的应用程序的另一个特点是，在给定时间内，大多数信号量都不活动(通常有约32个“客户端”线程在等待/信号上千个信号量)。请注意，由于整个服务器在单个进程中运行，我使用轻量级、基于线程的信号量(而不是进程间信号量)。

我的问题有两个方面:

1. 在Linux和Windows系统下，对于一个单一进程创建20000个信号量是不推荐的。但实际上，似乎也不需要这么多。
2. 如果不建议这种做法，可以使用哪些技术来减少实际信号量的数量呢？例如，在一个实际信号量的基础上创建一组N个“模拟信号量”。这可能是一个有趣的解决方案，因为在给定时间大部分信号量都是不活跃的。

提前感谢！

1. 使用成千上万个信号量不建议，特别是从跨平台的角度考虑。因此，即使它们不是进程间信号量（在Windows下仍然会消耗句柄）。
2. 解决我的问题的直接方法是将我的数组分成例如16个元素的64个子数组，并将每个子数组与一个读/写锁相关联。不幸的是，这会引入很多争用（1个写者将阻塞对15个元素的读取）。

3. 深入研究Boost源代码，我发现：

   • "boost::mutex"的实现在Windows下不包装CRITICAL_SECTION对象（而是CreateEvent和ReadWriteBarrier），
   • "boost::shared_mutex"在Windows下使用CreateSemaphore（它们是沉重的进程间对象），并且
   • "boost::shared_mutex"在Linux下不包装"pthread_rwlock_t"。

   这样做的原因对我来说似乎不太清楚。特别是，在Windows下使用进程间对象作为"boost::shared_mutex"的子优化。

到目前为止的问题总结

1. 如何在一个实际的信号量上创建一组N个“模拟信号量”，使得模拟信号量之间的争用尽可能小？
2. boost::mutex和boost::shared_mutex与它们的本机对应物（CRITICAL_SECTION和pthread_rwlock_t）相比如何？

- Tisys

---

请注意，我知道boost::shared_mutex的存在（我可以为数组的每个元素使用一个shared_mutex）。然而，底层实现仍然涉及数千个互斥锁和条件变量。 - Tisys

不知道您试图保护的实际数据，很难回答这个问题。由于我们对数据结构甚至您的问题领域一无所知，除了以下建议外，我没有更多可以说的：在过度锁定之前，您应认真考虑为什么和如何需要保护数据。您甚至可能根本不需要“信号量”或锁定数据。 - Travis Gockel

好的，我已经尝试以最一般的方式写出我的问题。更具体地说，我的应用程序是科学计算（在FEM领域）的缓存系统。数组的元素对应于缓存页面。每个缓存页面存储有关FEM网格部分的一个计算上下文。计算上下文可以存储到磁盘中。将其读回内存需要相当大的设置费用，因此我希望尽可能长时间地将其保留在内存中，因此需要缓存。 - Tisys

在我看来，只要你保持关键部分的短暂性，你也可以为数组使用单个关键部分。或者，如果你担心锁拥塞，可以将数组分成几个子数组。对于合理的并发，关键部分效果非常好。boost::asio基于完成端口（IIRC），因此并发线程数将是合理的（除非你搞砸了）。在我的机器上，使用4个并发读取器，完成端口每秒处理约500k个事件，这对于关键部分来说不是真正的挑战（可以轻松处理数千万个）。 - Damon

Answer 1

1. 这并不是推荐的做法。实际上，你不应该这样做，因为在Windows中，每个信号量将会消耗1个句柄对象。一个进程只能管理特定数量的句柄对象。线程/进程和其他Windows对象可能需要使用句柄对象，如果它们无法获取，则会崩溃。在Linux中也有类似的文件描述符概念。

2. 将你的4096个元素分成30组（例如），每组140个元素，并为每个140个元素的组分配一个信号量。然后30个（在本例中）线程将尝试访问这些30组，并且它们将根据每个140个元素的组信号量进行同步。

- Damiox

---

你在Windows中混淆了不同的句柄类型。内核句柄没有隐含的限制。尝试创建10^6个事件，你会发现没问题。但是，如果使用太多的gdi/user句柄可能会遇到麻烦。 - valdo

P.S. 内核句柄的每个进程限制为2^24。来源：http://msdn.microsoft.com/en-us/library/ms724485%28v=vs.85%29.aspx - valdo

嗨Valdo，Windows中的句柄会消耗内存，你可以在以下页面上查看更多详细信息：http://msdn.microsoft.com/en-us/library/ms724517(v=vs.85).aspx（"系统中打开的句柄总数仅受可用内存的限制。某些对象类型支持每个会话或进程的有限句柄数量"） - Damiox

Valdo。你发的那个微软链接真的很好。请注意那篇文章所述：“然而，句柄被存储在分页池中，因此您可以创建的实际句柄数量基于可用内存。” 我会避免在我的系统中创建大量句柄。 - Damiox

@Damiox：非常感谢。我可能会遵循您的建议进行第一次粗略实现（将单个boost::shared_mutex与我的大型数组的多个单元格关联）。然而，这比所需的内容引入了更多争用（考虑到您的示例，对1个元素的写入将阻塞对139个元素的读取）。这是有问题的，因为在我的情况下，“写入”可能需要比“读取”更长的时间。 - Tisys

@Tisys：我认为这是一个很好的方式，你可以从中开始，并学习它的性能。你的问题帖子真的很有趣。祝你好运！ - Damiox

Answer 2

从Windows的角度来看，我会告诉你我的想法。我非常有经验地编写Windows服务器应用程序。

首先，为单个进程创建20k个信号量绝对没有问题。它是一个相当轻量级的内核对象。即使是“进程间”信号量也是如此。

然而，我认为你的设计还存在另一个问题。你应该知道，每个在内核对象（如信号量/互斥体）上执行的操作都涉及到重量级内核模式事务（也称为系统调用）。即使完全没有冲突，每次这样的调用可能会花费你约2k个CPU周期。

因此，你可能会发现大部分处理器时间都花费在同步方法的调用上。

相反，为了同步线程，可以使用交错操作。它们的成本要低得多（通常只有几十个CPU周期）。

还有一个名为临界区的对象。它是交错操作数和内核对象的混合体（如果实际上存在冲突，则使用内核对象）。你应该检查一下你通常锁定元素的时间长度。如果通常是短时间锁定，请使用临界区，忘记复杂的读写锁。

如果你仍然需要处理长时间锁，并且确实需要读写锁，而且你发现在内核模式事务中花费了大量的CPU资源 - 考虑创建自己的（或尝试找到现有的）混合式实现。

- valdo

---

感谢您的回答。然而，我正在使用boost::thread mutexes，它们是Win32的CRITICAL_SECTION对象的包装器（而不是内核mutex对象）：http://boost.2283326.n4.nabble.com/Thread-win32-msvc-Mutexes-td2577038.html。因此，我认为您提到的性能问题在我的情况下不会存在。 - Tisys

@Tisys：是的，使用boost::thread互斥锁可能不会出现性能问题。只需确保所有其他涉及的同步对象（至少那些始终涉及，而不管碰撞如何）也不是纯内核对象即可。 - valdo

在检查boost::thread源代码时，我发现boost::mutex的实现并不是像我一直以为的那样是CRITICAL_SECTION的包装器（http://www.boost.org/doc/libs/1_46_1/boost/thread/win32/basic_timed_mutex.hpp）。实际的实现混合了对"CreateEvent()"和"ReadWriteBarrier()"的调用。 - Tisys

Answer 3

在Linux上，您绝对不应该自己实现锁，而是使用posix_rwlock_t。

拥有一个包含4096个这样元素的数组不应该出现任何特殊问题。在Linux中，POSIX锁结构实现得非常高效。特别是在“快速路径”上尽可能使用原子操作，在特定锁上存在拥塞时才进入系统调用（特别是对于FUTEX）。因此，如果您相对谨慎地实现，使得任何线程一次只持有1或2个锁，则Linux上的限制仅由您的工作线程总数而不是对象本身的数量给出。

- Jens Gustedt

---

感谢您的建议！检查了boost::thread源代码后，我发现"boost::shared_mutex"确实不是我一直以为的"posix_rwlock_t"的包装器，而是一个自定义实现（http://www.boost.org/doc/libs/1_47_0/boost/thread/pthread/shared_mutex.hpp）。我不知道哪种实现更好，但在这一点上需要小心。 - Tisys