Producer-consumer with interval partitioning

Question

I have an interesting producer-consumer spin-off to implement and I cannot wrap my head around its algorithm. So, every producer will "produce" numbers between the given range (min, max) which give the same reminder to the division by the given "quotient". Same goes for the consumer.

Extra requirement: finite buffer.

My thoughts on this:

• a coarse-grained queue which uses a lock and two conditions for push and pop, alongside a number of expected parties and arrived parties, used to determine of the queue is still available for the consumers. (one considers that a queue is available if there are still items in it or there are active writers (arrived != expected))
• a "Producer class" which contains minimum, maximum, a quotient and the shared queue as fields and has a method which produces and returns values based on the given fields.
• a "Consumer" class which contains the same fields as the "Producer" class and has the method "consume" which pops an item from the queue and "consumes" (prints it out) it. A consumer will consume as long as the queue is available.

My problems:

• How would one ensure that all numbers between a given workload interval (start, end) would be produced and consumed by x producers and y consumers (x != y) ?
• How would one implement the consume mechanism ?
• How would one perform the partitioning of values of producers and consumers so all the values of workload interval are used?

I was thinking about using an array list for the "buffer" and every consumer would perform a lock-free lookup for a "compatible" element to consume, removing an element if one available or trying again if none available. I think this would be inefficient because of wasted CPU cycles on "tries".

PS: I am using java for this, but pseudo-code is really good as well.

Thanks in advance!

Answer 1

To be sure that producer produces all numbers from given range that have the same remainder you can use the following pseudo-code

int current = start;
while (current++ <= end) { //assuming your ranges are inclusive
  if (current % quotient == 0) {
    publish(current);
  }
}

To support partitioning you basically need some kind of Map<YourKey, Queue>. Each producer and consumer will be associated with a key and producer will publish to the queue associated with his key and consumer will consume from a queue associated with its key. You can use your range as a key for a queue.