0
$\begingroup$

I have a requirement for which I am trying to write an algorithm and struggling a bit conceptually with. This seems like it should be a common-ish type problem so I imagine there is a name/standard solution for it but can't seem to find any material...

Basically say I have X consumers (lets say 4 for the example), and I have a target interval I want some operation to occur at (lets say every minute for the example), I need to split the interval so that all 4 of the consumers take turns hitting the interval. First part is simple - we set them all to do the operation in (Interval * # of Consumers) time, i.e. 4 minutes in this case. But now I need to stagger them, so that 1st consumers fires on 1 minute, 2nd on minute 2, 3rd on minute 3 and 4th on minute 4 - the cycle will then repeat.

I had a go at doing this and it works fine at start-up but I am struggling to deal with the case where a consumer is added or removed. The existing consumers should then 're-balance' themselves in this case. by waiting or speeding up to fit their new time-slice. How can I calculate the time they should delay themselves in order to fall into the new correct pattern.

I feel like this is a relatively simple synchronisation problem and should have been tackled before / written about but not sure what it would be called to research it. Anyone heard of this / done anything similar before?

$\endgroup$
  • $\begingroup$ I'd take a look at the scheduling algorithms used in operating systems for CPU assignments (in the single CPU case). Be warned, they have a good dose of heuristics built in, as there are at best rough estimates of time taken available; besides, you can view them as having as central objective to keep -- slow, limiting -- disks busy). $\endgroup$ – vonbrand Sep 13 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.