ItGo.me Focus on IT Recommend

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

2021腾讯云限时秒杀,爆款1核2G云服务器298元/3年!(领取2860元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1062

2021阿里云最低价产品入口+领取代金券(老用户3折起),
入口地址https://www.aliyun.com/minisite/goods

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----------------------------
Related