# Algorithm: spreading out jobs/events in time

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on

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

--
pkent 77 at yahoo dot, er... what's the last bit, oh yes, com

## Re: Algorithm: spreading out jobs/events in time

....

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
--
(reverse each component and remove .invalid for email address)

comp.lang.perl.misc guidelines on the WWW:

## Re: Algorithm: spreading out jobs/events in time

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?

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

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

--
Usenet Newsgroup Service                        \$9.95/Month 30GB

## Re: Algorithm: spreading out jobs/events in time

[...]

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

## Re: Algorithm: spreading out jobs/events in time

In article

very similar to that of scheduling a set of real-time tasks that have
different desired frequencies, but only one can run at a time on a
single-processor system. The two basic scheduling algorithms are 'rate
monotonic scheduling' and 'earliest deadline first'. The second is
probably easier to implement. For each task, calculate the time of next
execution. Execute or schedule whichever one has the earliest next
execution time.

http://www.mega-tokyo.com/osfaq2/index.php/Scheduling%20Algorithms

----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+
Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

## Re: Algorithm: spreading out jobs/events in time

If you're running UNIX, or cygwin on Wintel, why cant you use cron

## Re: Algorithm: spreading out jobs/events in time

gimme_this_gimme_that@yahoo.com wrote in news:1119373539.860470.116800

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
--
(reverse each component and remove .invalid for email address)

comp.lang.perl.misc guidelines on the WWW:

## Re: Algorithm: spreading out jobs/events in time

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

## Re: Algorithm: spreading out jobs/events in time

pkent wrote:

[---]

[---]

Hi pkent,

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

use Win32::Semaphore;
.....
if(\$Sem) {
\$Sem->wait();
##semaphore is now UP....
...
##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