Algorithm: spreading out jobs/events in time

[pkent]

hi,

I'm sure someone must have solved this problem before, but I've
exhausted my searches of CPAN and the web - I bet there's a name for
this algorithm but I don't know what.

Imagine I have a program which has a number of independent, equally hard
(i.e. same CPU usage) jobs to do. Each job should be run every 5
minutes. What I want to do is spread those jobs out so that the "work"
is as evenly distributed as possible.

In that case it's obvious that I need to stagger each job by 5/n minutes
to spread them out most evenly. Easy.


But this is the hard part... what if some of my jobs have _different_
frequencies? I want to work out how to stagger each job so that, over
time, the work is still spread out on average and I minimize the number
of times when jobs occur together.



Visual example:

E.g. imagine 2 jobs that run every 4 minutes, and one that runs every 8.
One way of spreading them out would be this (each number is a different
job:

1...1...1...1...1...1...1...1...
...2...2...2...2...2...2...2...2.
....3.......3.......3.......3...

as opposed to

1...1...1...1...1...
2...2...2...2...2...
3.......3.......3...

I've been thinking about frequencies, harmonics, phases, highest common
factors, subsets of jobs with the highest common factor, differentials,
local minima, ... but is this soluble?

any help appreciated

P
P

 

[A. Sinan Unur]

But this is the hard part... what if some of my jobs have _different_
frequencies? I want to work out how to stagger each job so that, over
time, the work is still spread out on average and I minimize the
number of times when jobs occur together.
....

I've been thinking about frequencies, harmonics, phases, highest
common factors, subsets of jobs with the highest common factor,
differentials, local minima, ... but is this soluble?

Honestly, I do not know the answer. However, the solution (if one
exists) is going to be language independent. Maybe you could try
comp.programming?

Incidentally, the first hit returned by searching Google is

<URL:http://www.onjava.com/pub/a/onjava/2004/03/10/quartz.html>

and it might prove useful to you.

Here is a very naive approach:

1. Order jobs from shortest to longest.
2. Start the first job, set up a completion callback. The completion
callback just restarts the job.
3. Wait for a minute (or whatever granularity you want)
4. Start the next shortest job.

This is probably full of holes, and not optimal, but it easy easy to
implement and test.

On second thought, I know nothing, so don't listen to me

Sinan

 

[xhoster]

hi,

I'm sure someone must have solved this problem before, but I've
exhausted my searches of CPAN and the web - I bet there's a name for
this algorithm but I don't know what.

Imagine I have a program which has a number of independent, equally hard
(i.e. same CPU usage) jobs to do.

Are these jobs not entirely CPU bottlenecked? I.e. is there any reason
to think that running more than on at a time will have better performance
than running them serially? Or are you already supposing serial execution?

Each job should be run every 5
minutes.

What if it takes more than 5 minutes of runtime to complete each job
once?

What I want to do is spread those jobs out so that the "work"
is as evenly distributed as possible.

In that case it's obvious that I need to stagger each job by 5/n minutes
to spread them out most evenly. Easy.

But this is the hard part... what if some of my jobs have _different_
frequencies? I want to work out how to stagger each job so that, over
time, the work is still spread out on average and I minimize the number
of times when jobs occur together.

If there is no benefit to parallel execution, and if the timings are
somewhat flexible, then you can just run the jobs serially. Keep track of
the last time each job was started, and then whenever one job finishes just
start whichever job is most overdue. If no jobs are overdue or nearly due,
sleep.

(Alternatively, you could run the job which is most overdue relative to
it's desired frequency, rather than in absolute time)



while (1) {
# how long till each job is due?
my @due = map time() - $last[$_] - $interval[$_], 0..$#jobs;
# find index of soonest due (or most overdue) job
my $soon = (sort {$due[$a]<=>due[$b]} 0..$#due)[0];

if ($due[$soon]> 5) {
sleep $due[$soon]-5; # Don't run a job too much before it's time
};

$last[$soon]=time();
system $jobs[$soon] and die;

}




Xho

 

[Anno Siegel]

[...]

Visual example:

E.g. imagine 2 jobs that run every 4 minutes, and one that runs every 8.
One way of spreading them out would be this (each number is a different
job:

1...1...1...1...1...1...1...1...
..2...2...2...2...2...2...2...2.
...3.......3.......3.......3...

as opposed to

1...1...1...1...1...
2...2...2...2...2...
3.......3.......3...

I've been thinking about frequencies, harmonics, phases, highest common
factors, subsets of jobs with the highest common factor, differentials,
local minima, ... but is this soluble?

It should be solvable, once you provide another crucial parameter: how
long each job takes. In your image of frequencies, you can't say anything
about the overlap in a set of pulse trains when you know know only the
frequency but not the duration (or duty cycle) of each train.

The solution won't be trivial to find, and I'm not convinced it is
worth trying. Start the jobs when you want them to run and let the
OS sort it out.

Anno

 

[gimme_this_gimme_that]

If you're running UNIX, or cygwin on Wintel, why cant you use cron
to schedule your jobs?

 

[A. Sinan Unur]

(e-mail address removed) wrote in @o13g2000cwo.googlegroups.com:

If you're running UNIX, or cygwin on Wintel, why cant you use cron
to schedule your jobs?

I don't know. Why can't you?

The OP's question (which you omitted as usual) was about *optimal* or near
optimal scheduling of jobs according to a criterion.

Sinan

 

[kevindotcar]

hi,
[---]

1...1...1...1...1...1...1...1...
..2...2...2...2...2...2...2...2.
...3.......3.......3.......3...

as opposed to

1...1...1...1...1...
2...2...2...2...2...
3.......3.......3...

[---]

Hi pkent,

You could fire them all off, and have a semaphore for each task- kindof
like this;

use Win32::Semaphore;
.....
Win32::Semaphore::Create($Sem,1,1,"Task1Sem")||die &Error;
if($Sem) {
$Sem->wait();
##semaphore is now UP....
### do all Task1 work
...
##place semaphore flag down...
$Sem->Release(1,$last);
}
else {
die("ERROR Getting SEMAPHORE");
}

...Programmers typically use these for database operations, but it
should be applicable to your needs. You of course have to figure out
what the work-thresholds are for your needs; You might need to "hold"
on several semaphore-flags... in which case beware of deadlocks.

Do a perldoc on Win32::Semaphore for specs- Perl also has semaphores
for UNIX/Linux if that's your need, but I don't know what they're
called.

HTH-

kDot

 

[gimme_this_gimme_that]

Well, I could post an example chron schedule and then explain
the nuiances of staggering the scripts so they run at different times
and then I could explain how to write a perl script that looks for
a text file or a database entry to check for a status message from
a preceeding perl script, but then I could do all that,
basically write his code, and that still wouldn't be enough.

It's just better to pass along the tip that perl isn't the tool for
this
task, it's better to use a combination of cron and perl. I trust he
could man cron and get it.


True, this isn't optimal in the sense of scheduling jobs according
to a criterion, but this is a workable approach considering the
diagram in the original post and that the staggering phase in
that diagram is measured in minutes not microseconds.
An optimal schedule isn't what's being asked for and the
guy isn't building an operating system from scratch using Perl.

Funny how some "perl gurus" either aren't as smart as they think
they are, or that they just like to whine.

gees