in reply to Time Allotments

Interesting problem.

If I understand this correctly, a 600 entry table won't quite work out. One way to build the sequence is to start with:

step 1: a b c x a b c x a b c x a b c x a b c x a b c x a b c x... step 2: d e f x x x d...
basically, cycle through the first sequence, leave a blank slot (x), repeat sequence. You can run one other thing every 4 seconds (an x), start filling in slots with the second sequence. This time skip 3 x's between cycles of the second "24 second sequence".

After this, every 24 seconds, there will be 3 x's left every 24 seconds, or in a total of 600 seconds there are 600/24 = 25 "24 second groups" each with 3 open slots or 24*3=75 total open slots left.

This doesn't quite work out for the other tasks in a 600 second table because the "time slot opportunities" are modulo 24 seconds. But it appears possible to set up a pattern based upon modulo 24 seconds for the others...

seconds task 4 a b c 24 d e f a group of 3 blank slots occur every 24 seconds There are 3 categories of other things. Even if they all land on the same 24 second "window", we can still run one of each of them. In other words, each of these 3 slots could be dedicated as "potential 96, 144 or 600 second thing". 96 g run once every 4th group 144 h i j run one of them every other group (pattern repeats after 6 groups) 600 k run once every 25th group
I think there are many ways to do this problem. I looked for a simple repetitive pattern to ensure that everything that has to get done will get done. The CPU loading is not optimally evenly distributed, but I guess you could interleave "x's with def in the 24 second "pattern" and that would help.

I'm not sure what the requirements are for this 12th, thing, but it could run in any slot not otherwise taken. Of course, the 100 second group runs every 96 seconds and the 150 second group runs every 144 seconds, but that sounded like that "tradeoff" was allowed by the rules.

Update:
For implementation, I might just hand code a 24 entry dispatch table. Something like this:

1 a 2 b 3 c 4 d 5 a 6 b 7 c 8 potentially run one of the every 96 second group 9 a 10 b 11 c 12 e 13 a 14 b 15 c 16 potentially run one of the every 144 second group 17 a 18 b 19 c 20 f 21 a 22 b 23 c 24 potentially run one of the every 600 second group
Where, for example, the "potentially run one of the every 600 second group" entry means that it will do something every 25 times that you call it. If this otherwise meets the requirements, I like it because everybody has a dedicated slot to run in and I can absolutely guarantee that the maximum timing requirements will be met. The 12th thing can run at any opportunity where "potentially" means "not right now". The "12th thing" would be more like the "idle loop" - nothing else to do, might as well run you!

Replies are listed 'Best First'.
Re^2: Time Allotments
by alanonymous (Sexton) on Feb 20, 2012 at 07:54 UTC
    Marshall,

    This is the approach I took when thinking through the problem as well (only I cheated and used excel to lay the events out nicely), by allotting the a,b,c triplet and filling in the 24 sec repeaters and so on. By strictly enforcing a repeating pattern, this does indeed guarantee that each event occurs within the constraints and gives some opportunities for the new event type to occur. The only problem I see with this approach is that it may not be 'optimal' in that the 100s time becomes 96s, the 150s to 144s, though for simplicity's sake this may be the best approach.

    And after writing that, I've now done some math and with the tradeoffs of optimization, I'm calculating that in each 24 second 'frame' there would be ~2.21 slots available for a new event type. Without the tradeoffs with a theoretical maximum, I'm calculating ~2.24. I think you've just proven to me that even if it isn't technically optimum, 2.24 and 2.21 are pretty close and this way there are guarantees.
      Reaching the absolute maximum efficiency requires more "brain power" and does introduce the possibility of "mistakes - or missed intervals". If you would have said, "hey this isn't close enough", then I would have challenged and asked questions about this "every task takes one second" stuff to try to get more leeway in the algorithm. More efficient algorithms are possible, but the complexity is at least an order of magnitude more and they wouldn't have this: "obviously will work and are guaranteed to work" attribute. If you are happy, then I am happy!
        <- happy.