选择生产者消费者问题变体的数据结构 [英] Choosing a data structure for a variant of producer consumer problem

问题描述

现在，我有一个队列，有多个生产者和单个消费者。

Right now, I have a queue, with multiple producers and single consumer.

消费者线程运行缓慢。此外，消费者通过窥视操作从队列中获取元素，直到消费操作完成，元素不能从队列中删除。这是因为生产者线程作为一个侧面操作也会捕获在该时间点未完全处理的所有元素的快照。

Consumer thread operation is slow. Also, consumer takes element from queue through a peek operation, and until the consumption operation is complete, the element cannot be removed from the queue. This is because the producer thread as a side operation also takes a snapshot of all elements that are not fully processed at that point in time.

现在，我想更改我的代码来支持多个消费者。所以说，我有三个线程，一个线程将采取第一个元素，可以通过窥视操作读取。
第二个消费者线程可以去第二个元素，但是我无法检索，因为队列不支持检索第二个元素。

Now, I want to change my code to support multiple consumers. So, lets say I have three threads, one thread will take the first element, which can be read through a peek operation. The second consumer thread can go for the second element, but I have no way of retrieving that since queue dosn't support retrieving the second element.

所以我使用标准的ConcurrentLinkedQueue（现在我正在使用的）的选项是out。

So, the option to use a standard ConcurrentLinkedQueue (which I am using right now) is out.

我正在考虑使用优先级队列，但是我将不得不关联每个元素都有一个标志，告诉我这个元素是否已被一些线程使用。

I am thinking of using a priority queue, but then I will have to associate with each element a flag that tells me if this element is already being used by some thread or not.

哪个数据结构最适合这个问题？

Which data structure is most suited to this problem?

推荐答案

听起来你应该真的有两个队列：

It sounds like you should really have two queues:

• 未处理


• 正在进行

消费者将以原子一个锁）从未处理的队列中拉出并添加到正在进行的队列。这样，多个消费者可以同时工作，但是制造商在需要时仍然可以拍摄两个队列的快照。消费者完成任务后，将其从正在进行的队列中删除。 （这不是真的需要排队，因为没有任何东西从它拉，只是一些集合，你可以轻松添加和删除。）

A consumer would atomically (via a lock) pull from the unprocessed queue and add to the in-progress queue. That way multiple consumers can work concurrently... but the producer can still take a snapshot of both queues when it needs to. When the consumer is finished with a task, it removes it from the in-progress queue. (That doesn't really need to be a queue, as nothing's "pulling" from it as such. Just some collection you can easily add to and remove from.)

鉴于您需要锁定才能将转移原子化，您可能不需要底层队列作为并发的队列 - 您将保护所有共享访问权。

Given that you'll need locking to make the transfer atomic, you probably don't need the underlying queues to be the concurrent ones - you'll be guarding all shared access already.

这篇关于选择生产者消费者问题变体的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！