CODEWITHSUNDEEP
multithreadingalgorithmdata-structuresqueueproducer-consumer
sc_ray
sc_ray

Reputation: 8043

Queue entry broadcasted to multiple threads

I have a producer thread that generates objects and puts it in a shared queue.

I have spawned a bunch of consumer threads that can read from this queue.

In an ideal situation every one of my workers will pick up the next job from the queue. But for some of the objects(with a certain attribute), each and every one of my consumer threads would need a copy of the object(without any duplicates).

My first impulse was to check for that attribute of the object before every push to the queue. If the attribute is present, make n copies(here n is equal to the number of workers I have) and push those n copies on to the queue.

The queue will need to do some bookkeeping to prevent the same worker from gaining the object more than once.

One way to do this book-keeping would be to have a Map where the key is the object and the value is the set of worker-ids(it can be a thread-id).

For every pop request, the queue will check if the object has already been processed by the current thread-id. If the thread-id is present in the map, it will exit the critical section without popping the object from the queue, otherwise it will pop the object and update the map.

The problem with this approach is that its quite possible that a single thread might starve the other threads from accessing the queue.

Can somebody suggest an elegant way to solve this issue?

Thanks

Upvotes: 0

Views: 94

Answers (1)

moooeeeep
moooeeeep

Reputation: 32542

My suggestion:

  • have one queue for each consumer,
  • push new items that are to be processed by all consumers to all queues,
  • push the other items to the shortest queue, w.r.t. the number of objects (count semaphores up and down...)

If you want to go fancy, you could determine the shortest queue by some other metric, e.g. accumulated object size or some custom quality of service of the specific consumers.

Upvotes: 2

Related Questions