Lib/sched.py

   1 """A generally useful event scheduler class.
   2
   3 Each instance of this class manages its own queue.
   4 No multi-threading is implied; you are supposed to hack that
   5 yourself, or use a single instance per application.
   6
   7 Each instance is parametrized with two functions, one that is
   8 supposed to return the current time, one that is supposed to
   9 implement a delay.  You can implement real-time scheduling by
  10 substituting time and sleep from built-in module time, or you can
  11 implement simulated time by writing your own functions.  This can
  12 also be used to integrate scheduling with STDWIN events; the delay
  13 function is allowed to modify the queue.  Time can be expressed as
  14 integers or floating point numbers, as long as it is consistent.
  15
  16 Events are specified by tuples (time, priority, action, argument).
  17 As in UNIX, lower priority numbers mean higher priority; in this
  18 way the queue can be maintained as a priority queue.  Execution of the
  19 event means calling the action function, passing it the argument
  20 sequence in "argument" (remember that in Python, multiple function
  21 arguments are be packed in a sequence).
  22 The action function may be an instance method so it
  23 has another way to reference private data (besides global variables).
  24 """
  25
  26 # XXX The timefunc and delayfunc should have been defined as methods
  27 # XXX so you can define new kinds of schedulers using subclassing
  28 # XXX instead of having to define a module or class just to hold
  29 # XXX the global state of your particular time and delay functions.
  30
  31 import heapq
  32 from collections import namedtuple
  33
  34 __all__ = ["scheduler"]
  35
  36 class Event(namedtuple('Event', 'time, priority, action, argument')):
  37     def __eq__(s, o): return (s.time, s.priority) == (o.time, o.priority)
  38     def __ne__(s, o): return (s.time, s.priority) != (o.time, o.priority)
  39     def __lt__(s, o): return (s.time, s.priority) <  (o.time, o.priority)
  40     def __le__(s, o): return (s.time, s.priority) <= (o.time, o.priority)
  41     def __gt__(s, o): return (s.time, s.priority) >  (o.time, o.priority)
  42     def __ge__(s, o): return (s.time, s.priority) >= (o.time, o.priority)
  43
  44 class scheduler:
  45     def __init__(self, timefunc, delayfunc):
  46         """Initialize a new instance, passing the time and delay
  47         functions"""
  48         self._queue = []
  49         self.timefunc = timefunc
  50         self.delayfunc = delayfunc
  51
  52     def enterabs(self, time, priority, action, argument):
  53         """Enter a new event in the queue at an absolute time.
  54
  55         Returns an ID for the event which can be used to remove it,
  56         if necessary.
  57
  58         """
  59         event = Event(time, priority, action, argument)
  60         heapq.heappush(self._queue, event)
  61         return event # The ID
  62
  63     def enter(self, delay, priority, action, argument):
  64         """A variant that specifies the time as a relative time.
  65
  66         This is actually the more commonly used interface.
  67
  68         """
  69         time = self.timefunc() + delay
  70         return self.enterabs(time, priority, action, argument)
  71
  72     def cancel(self, event):
  73         """Remove an event from the queue.
  74
  75         This must be presented the ID as returned by enter().
  76         If the event is not in the queue, this raises ValueError.
  77
  78         """
  79         self._queue.remove(event)
  80         heapq.heapify(self._queue)
  81
  82     def empty(self):
  83         """Check whether the queue is empty."""
  84         return not self._queue
  85
  86     def run(self):
  87         """Execute events until the queue is empty.
  88
  89         When there is a positive delay until the first event, the
  90         delay function is called and the event is left in the queue;
  91         otherwise, the event is removed from the queue and executed
  92         (its action function is called, passing it the argument).  If
  93         the delay function returns prematurely, it is simply
  94         restarted.
  95
  96         It is legal for both the delay function and the action
  97         function to to modify the queue or to raise an exception;
  98         exceptions are not caught but the scheduler's state remains
  99         well-defined so run() may be called again.
 100
 101         A questionable hack is added to allow other threads to run:
 102         just after an event is executed, a delay of 0 is executed, to
 103         avoid monopolizing the CPU when other threads are also
 104         runnable.
 105
 106         """
 107         # localize variable access to minimize overhead
 108         # and to improve thread safety
 109         q = self._queue
 110         delayfunc = self.delayfunc
 111         timefunc = self.timefunc
 112         pop = heapq.heappop
 113         while q:
 114             time, priority, action, argument = checked_event = q[0]
 115             now = timefunc()
 116             if now < time:
 117                 delayfunc(time - now)
 118             else:
 119                 event = pop(q)
 120                 # Verify that the event was not removed or altered
 121                 # by another thread after we last looked at q[0].
 122                 if event is checked_event:
 123                     action(*argument)
 124                     delayfunc(0)   # Let other threads run
 125                 else:
 126                     heapq.heappush(q, event)
 127
 128     @property
 129     def queue(self):
 130         """An ordered list of upcoming events.
 131
 132         Events are named tuples with fields for:
 133             time, priority, action, arguments
 134
 135         """
 136         # Use heapq to sort the queue rather than using 'sorted(self._queue)'.
 137         # With heapq, two events scheduled at the same time will show in
 138         # the actual order they would be retrieved.
 139         events = self._queue[:]
 140         return map(heapq.heappop, [events]*len(events))