EDF scheduler

[Colin Brown]

Hi

I am trying to implement a simple scheduler in Python where the deadline
times of (non-prioritised) entries as entered are not necessarily in
chronological order. From what I see on the Web this is best described as an
"Earliest Deadline First" scheduler.

The "sched" module [using timefunc of time.time and delayfunc of time.sleep]
does not appear to do this since a subsequent entry at an earlier schedule
time does not replace the non-completed next entry but is activated after
it. There does not appear to be a (documented) way of finding the currently
active entry so it can be cancelled and requeued thus allowing the earlier
entry to action at the right time.

Here is a test script that demonstrates sched behaviour:
!---------------------------------------------------------------------
import Queue
import sched
import threading
import time

class skd(threading.Thread):

    def __init__(self,outq):
        self.outq=outq
        self.myq=Queue.Queue()
        self.schd=sched.scheduler(time.time,time.sleep)
        threading.Thread.__init__(self)
        self.start()

    def reply(self,arg):
        self.outq.put(arg)

    def enter(self,entry):
        return self.schd.enter(entry['secs'],1,self.reply,(entry['data'],))

    def run(self):
        while 1:
            self.schd.run()
            time.sleep(0.1)

oq=Queue.Queue()
bks=skd(oq)
bks.enter({'secs': 11, 'data': 'eleven'})
bks.enter({'secs': 5, 'data': 'five'})
bks.enter({'secs': 3, 'data': 'three'})
for sec in range(20):
    time.sleep(1)
    print sec+1
    if sec == 6:
        bks.enter({'secs': 2, 'data': 'nine'})
        bks.enter({'secs': 1, 'data': 'eight'})
        bks.enter({'secs': 8, 'data': 'fifteen'})
    if oq.empty() == 0:
        print oq.get()
!---------------------------------------------------------------------------
-

produces output:
1
2
3
three
4
5
five
6
7
8
9
10
11
eight
12
nine
13
eleven
14
15
fifteen
16
17
18
19
20
!---------------------------------------------------------------------------
--

Here is my understanding of the operation. After the thread is created, the
schedule queue is empty so the scheduler.run() falls through and the thread
hits the 100ms sleep. During this period the 3 sec, 5 sec, 11 sec entries
are inserted in non-chronological order. When scheduler.run() next executes
in the thread they are sorted so the 3 & 5 second entries are actioned.
After 7 seconds 3 more entries are added (for 8, 9 & 15 seconds) but the 11
second entry is currently being processed. However the internal queue
entries have been put in the sorted order of 8,9,11 & 15 seconds. At 11
seconds, the next scheduler queue entry, "8 secs" is returned. I would have
expected to have seen 9 & eleven occur in the next interval together but I
guess the time/scheduler function are rounding things up. The "15 secs"
appears as expected.

I would be obliged if someone can suggest an easy solution to my problem.
There may be hundreds of queue entries but I will be working to only 1
minute resolution so the implementation should not be too demanding of
resources.

Thanks
Colin Brown
PyNZ