Choosing a data structure for a variant of producer consumer problem

Question

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.

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?

Answer 1

It sounds like you should really have two queues:

• Unprocessed
• In progress

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.