Home > algorithm - Producer consumer model with uniform load distribution with N1 : N2 : .... : NM

## algorithm - Producer consumer model with uniform load distribution with N1 : N2 : .... : NM

I have to implement a producer consumer scenario, where there is one producer (say P) and N (say N=3) number of consumers (say C1, C2, C3). Now the requirement is that the load should be
d among the consumers such that `C1 : C2 : C3 = 1 : 3 : 6`. Which means P should supply `10% to C1, 30% to C2 and 60% to C3` and this distribution should be uniform.

e.g. say P produces 10 items. if counter method is applied along with round robin then the scenario will look like below

``````items 1,2,3 goes to C1, C2, C3,  // C1 is done here with its 10%
items 4,5,6 goes to C2, C3, C2,  // C2 is done here with its 30%
items 7,8,9 goes to C3, C3, C3,  // C3 is bearing continuous load
item  10    goes to C3
``````

But here the distribution was not uniform, C3 is bearing continuous load which fails the purpose.

Ideal distribution would have something like

``````items 1,2,3 goes to C3, C2, C3,
items 4,5,6 goes to C3, C2, C3,
items 7,8,9 goes to C3, C1, C3,
item  10    goes to C2
``````

I have tried to provide a hypothetical example here. In real scenario the count won't be predefined unlike 10 in the above example. In real scenario the producer will keep on producing and is a never ending process. for example imagine a toll booth having 3 toll gates C1, C2, C3 where number of vehicles passing by the gates should be in the ratio of `1 : 3 : 6` and the distribution should be uniform. Please suggest an efficient algorithm to implement this.

algorithm data-structures logic
|
this question
asked Mar 29 '16 at 13:20 paper.plane 644 5 12

|

## 2 Answers 2

One way to do it would be for the producer to generate a random number from 1 to 10, inclusive. If the number is 1, the item goes to C1. If the number is 2, 3, or 4, it goes to C2. If the number is in the range 5-10, then the item goes to C3.

Note that this doesn't guarantee that the distribution will be perfect over every 10 items, but assuming a reasonably good random number generator, the distributions will be very close to your 1:3:6 over a large number (thousands) of items.

|
this answer
answered Mar 29 '16 at 14:16 Jim Mischel 94.2k 9 105 211      Looks good and easy to implement. –  paper.plane Mar 30 '16 at 12:36

|

I'd suggest you use a variant of topological sorting.

c3 starts;c2 waits till c2=c3+1; similarly, c1 waits till c1=c2+1;

That way, the distribution will be like:

c3 c3 c2
c1 c3 c2
c3 c2 c3
c3

This is just an example I provided. You can choose to release the consumers based on similar logic

|
this answer
answered Mar 29 '16 at 15:01 attaboy182 1,131 2 11 20      this is good method, I have to check the feasibility. –  paper.plane Mar 30 '16 at 12:36      Can you explain this in more detail? I don't see how this is going to maintain that distribution over a long period of time. Are you proposing that the consumers start and stop periodically? –  Jim Mischel Mar 30 '16 at 12:44

|
------splitte line----------------------------