6

我们一直在寻找在我们的代码中使用无锁队列来减少当前实现中单个生产者和消费者之间的锁争用。那里有很多队列实现，但我还不太清楚如何最好地管理节点的内存管理。

例如，生产者看起来像这样：

queue.Add( new WorkUnit(...) );

消费者看起来像：

WorkUnit* unit = queue.RemoveFront();
unit->Execute();
delete unit;

我们目前使用内存池进行分配。您会注意到生产者分配内存而消费者删除它。由于我们使用的是池，因此我们需要向内存池添加另一个锁以正确保护它。这似乎首先否定了无锁队列的性能优势。

到目前为止，我认为我们的选择是：

  • 实现无锁内存池。
  • 转储内存池并依赖线程安全分配器。

还有其他我们可以探索的选择吗？我们试图避免实现无锁内存池，但我们可能会走这条路。

谢谢。

4

5 回答 5

4

只有生产者才能创建对象并在不再需要时销毁它们。消费者只能使用对象并将其标记为已使用。这才是重点。在这种情况下，您不需要共享内存。这是我知道的有效无锁队列实现的唯一方法。

阅读这篇详细描述此类算法的精彩文章。

于 2011-06-23T22:30:51.807 回答
1

另一种可能性是为每个线程拥有一个单独的内存池，因此只有一个线程在使用堆，并且您可以避免锁定分配。

这样你就可以管理一个无锁函数来释放一个块。幸运的是，这很容易管理：您为每个堆维护一个空闲块的链接列表。您将块自己的地址放入（您将用作的内存）链表的链接字段，然后与持有链表头部的指针进行原子交换。

于 2011-06-23T22:57:18.100 回答
0

你应该看看英特尔的 TBB。我不知道商业项目的成本是多少（如果有的话），但他们已经有了并发队列、并发内存分配器之类的东西。

你的队列接口看起来也很狡猾——例如，你的 RemoveFront() 调用——如果队列为空怎么办？newanddelete调用看起来也很多余。英特尔的 TBB 和微软的 PPL（包含在 VS2010 中）不会遇到这些问题。

于 2011-06-23T22:31:51.823 回答
0

我不确定您的具体要求是什么，但是如果您有生产者创建数据并将此数据推送到队列中的场景，并且您有单个消费者获取此数据并使用它然后销毁它，您只需要执行安全队列或您可以制作自己的单链表，在这种情况下是安全的。

  • 创建列表元素
  • 在列表元素中追加数据
  • 将下一个元素的指针从 null 更改为列表元素（或其他语言中的等效项）

消费者可以以任何方式实现，并且大多数链表默认情况下对于这种操作是安全的（但请检查 whit 实现）

在这种情况下，消费者应该释放这个内存，或者它可以以同样的方式将它返回给生产者设置预定义的标志。生产者不需要检查所有标志（如果它们超过 1000 个）来查找哪个桶是空闲的，但是这个标志可以像树一样实现，启用 log(n) 搜索可用池。我确信这可以在 O(1) 时间内完成而无需锁定，但不知道如何

于 2011-06-23T23:54:48.707 回答
0

我也有同样的担忧，所以我编写了自己的无锁队列（单生产者、单消费者）来为您管理内存分配（它分配一系列连续的块，有点像std::vector）。

我最近在 GitHub 上发布了代码。（另外，我在我的博客上发布了关于它的信息。）

如果您在堆栈上创建节点，将其入队，然后将其出队到堆栈上的另一个节点，则根本不需要使用指针/手动分配。此外，如果您的节点为构造和赋值实现了移动语义，它将自动移动而不是复制:-)

于 2013-02-08T23:31:04.177 回答