EDF scheduler

[Joshua Muskovitz]

I had a slightly different problem, but perhaps my solution can be applied
to your problem as well.  (If this comes out a bit obtuse, it is because I
can't really give away what the specific problem was to solve.  NDAs suck.)

In my case, I had a collection of objects to be monitored.  Each one
essentially had separate conditions which caused state changes over time.
So, for example, an object might change from state A to state B after 30
seconds, unless some intervening event caused the state to reset, etc.
Another might change from A to C after 10 seconds.  Now this would be easy
to solve by allocating a thread to each object, but in fact the number of
objects wasn't able to be bounded.  (There could have been thousands of
them.)  And since the conditions which caused state changes could vary from
object to object, you couldn't easily group them into common timers.

My solution was to use a single thread, and essentially poll each object,
allowing each one the opportunity to perform its state changing logic, if
necessary.  This function would return immediately if the object didn't need
to be handled at that time.  More importantly, though, is the fact that each
object *knows* when it needs to be handled next.  (It can compute this since
it knows when it last changed state.)  So this function always returns the
value of *when* this object will need to be handled again.  The minimum of
these return values is how long the single thread can sleep before repeating
the cycle.  (There are a variety of optimizations to this process, but you
hopefully get the idea.)  There does need to be a sufficient granularity to
the timing requirements, to deal with the overhead of polling, etc.)

The main loop then becomes something like this (typing off the top of my
head):

while 1:
    nextTime = reduce(min, [x.PollAndComputeNextTime() for x in
listOfObjects])
    now = time.time()
    sleep(nextTime - now)

God, I love Python.

--
# Joshua Muskovitz
# joshm at taconic.net
def lyyrs(sig): return '-'.join(sig.split()+["ly y'rs"])
lyyrs('Hire me!  I need the work!')




-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----