ananonymous:

You've already gotten a few responses, but I can't keep from adding a couple things ;^)

For the question "is there time to insert another event?", I'd take a look at how much time is consumed in total:

$ cat pogo.pl
#!/usr/bin/perl
use strict;
use warnings;
use Number::Fraction;

my %tasks = (
    a=>4, b=>4, c=>4, d=>24, e=>24, f=>24, g=>100, h=>150, i=>150, j=>
+150, k=>600
);

my $time = 0;
for my $k (sort keys %tasks) {
    my $time_used = Number::Fraction->new( 1, $tasks{$k});
    $time = $time + $time_used;
    print $time->to_string(), "\n";
}
$ ./pogo.pl
1/4
1/2
3/4
19/24
5/6
7/8
177/200
107/120
539/600
181/200
68/75
[download]

So you definitely have time for 7 one-second events every 75 seconds, or 14 every 150 seconds, etc. Play with the factors, and you can figure out what's available.

Next comes the task of arranging them. Your task is perhaps a bit too "clean and academic" sounding. In your case, you can play with the factors and write a program to schedule all of them.

Back in a former life, when I did real-time systems, we'd just keep the tasks in a priority queue (implemented as a heap). Then, as we'd have time, we'd just pick off the next ready task. It's pretty simple, and a bit more flexible when your tasks have: (a) variable run times, and (b) a range of acceptable execution intervals. After you execute the task, just add its minimum interval to the current time and requeue it. When you pick off a task whose maximum interval has already been exceeded, generate a fault.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

I guess the classic story of a real-time priority based system ignoring lower priority tasks is described under: Apollo 11 Guidance Computer, look at the section titled "PGNCS trouble".

The systems in use were very crude but thank goodness, there were some very smart folks programming this primitive stuff!

You are correct, this is quite 'clean and academic'. This actually refers to a broadcast datastream with different message timing requirements of 6 second chunks and I have simplified it greatly to get to the core of the problem, though the problem is definitely still intact.

The tasks are all of equal length and can occur as frequently as I like, as long as that rule of max time interval between like events remains valid and true. The problem is that the system CAN'T (think dire consequences) exceed the maximum interval (ie, generating a vault), and it has to anticipate the sequence in advance to ensure the rules are ALWAYS met.

A valid start would be "a, b, c, d, a, b, c, e, a, b, c, f, a, b, c, g, a, b, c, h, a, b, c, d..." etc, though 'd' was forced to be refreshed on the 21st second because of upcoming 'a' 'b' and 'c's.

What does "refreshed" mean ? And 21st?

Some observations

Hmm, it seems obvious you should give priority to shortest max, and give priority to anything approaching max/2

Graph theory comes to mind ... and tetris , no, PONG , tk widget demo , Balls bouncing in a cavity

Keeps the balls from touching down by smacking them up, a,b,c would be very heavy, the hardest hit you can deliver only keeps them airborne 4 seconds, where k is a hot air baloon ,

I think you're on the right track with hitting balls up for 4 sec, etc ... a good way to visualize and think through it.

If you count out the letters from the example above of "a, b, c, d, a, b, c, e..." etc, the second 'd' event comes prematurely after 21 seconds instead of after 24 to abide by the rule and still allow the a, b, c to still occur at the right interval, otherwise it would have been 25 seconds if a, b, c repeated again prior to the 2nd 'd'. Does that explain it?

Does that explain it?

Yes, it makes sense now, after playing with this. You say refreshed, I say reset/reinitialized.

#!/usr/bin/perl --
use strict; use warnings;
use Tk;

my %in = (
    a => 4,    # HEAVY
    b => 4, 
    c => 4, 
    d => 24, 
    e => 24, 
    f => 24, 
    g => 1000, 
    h => 150, 
    i => 150, 
    j => 150, 
    k => 600,  # hot air baloon
);

my @ev11 = map {[$_, $in{$_}, 0, $in{$_}, undef ]} sort keys %in;

my $mw = tkinit;
my $fr = $mw->Frame( -background => 'red', )->pack;#( qw/ -expand x -f
+ill x -anchor n -side top / );
$fr->Label( -text => 'NUMHITS:')->grid( qw/ -stick ew -row 1 -column 1
+ /);
$fr->Label( -text => 'letter(interval):')->grid( qw/ -stick ew -row 2 
+-column 1 /);
$fr->Label( -text => 'time remaining:')->grid( qw/ -stick ew -row 3 -c
+olumn 1 /);
my %butt;
{
#~ $one->[0] letter
#~ $one->[1] interval
#~ $one->[2] number hits
#~ $one->[3] time remaining
#~ $one->[4] button
    use constant INTERVAL => 1;
    use constant NUMHITS => 2;
    use constant TIMEREM => 3;
    use constant BUTTON => 4;
    my $col = 2;
    for my $one ( @ev11 ){
        $fr->Label(
             -relief      => 'groove',
            -text => $one->[0] . ' (' . $one->[1] . ')',
        )->grid(
            qw/ -sticky ew -row 2 /,
            -column => $col
        );
        $fr->Label(
             -relief      => 'groove',
            -textvariable => \$one->[NUMHITS]
        )->grid(
            qw/ -sticky ew -row 1 /,
            -column => $col
        );
        $one->[BUTTON] = $fr->Button(
            -command => \&Fooo,
            -textvariable => \$one->[TIMEREM],
        )->grid(
            qw/ -sticky ew -row 3 /,
            -column => $col
        );
        $col++;
        $butt{ $one->[BUTTON] } = $one;
    }
}
my $tx = $mw->ROText->pack(qw/ -expand 1 -fill both -anchor n -side to
+p / );
MainLoop;
sub Fooo {
    my $b = $Tk::event->W;
    $tx->insert(
        'end',
        sprintf '%s(%d/%d), ', 
            $butt{ $b }->[0] ,
            $butt{ $b }->[NUMHITS] ,
            $butt{ $b }->[TIMEREM],
    );
    for my $one ( @ev11 ){
        $one->[TIMEREM]--;
        $one->[BUTTON]->configure( qw/ -state normal /);
    }
    $butt{ $b }->[NUMHITS]++;
    $butt{ $b }->[TIMEREM] = $butt{ $b }->[INTERVAL];
    $b->configure( qw/ -state disabled /) ;
}
__END__
[download]

a(0/4), b(0/3), c(0/2), a(1/2), b(1/2), c(1/2), d(0/18), a(2/1), b(2/1), c(2/1), e(0/14), a(3/1), b(3/1), c(3/1), f(0/10), a(4/1), b(4/1), c(4/1),

Looks like you could have four 4-second repeaters max without dropping one ( or five 4 second repeaters and nothing else).

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...
[download]

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
[download]

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
[download]

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!