EDF scheduler

[Colin Brown]

Thanks Joshua for your reply. Unfortunately I do not think it handles the
problem I have which is the addition of new entries which should be actioned
before the currently timed event. Because your solution is waiting on a
sleep, an entry that comes in with a very short delay time may not be seen
before the current sleep has timed out.

Thanks Jeff for your reply. "sched" does priority sorting, that is not the
problem. See above.

I have implemented a scheduler on a mainframe that does exactly what I want.
I just did not want to re-invent another wheel in Python. My mainframe
solution had an (EDF "earliest-deadline-first") sorted queue with a single
timer on the head entry. However on every new entry, the head entry deadline
time was compared with the entry deadline time and if the new entry was
earlier than the current head, the current timer is cancelled and the next
head entry (ie the new entry) is put in the timer.

Unless someone can suggest a better way, I have decided that since I will
only be entering groups of entries on minute intervals and the longest
period should not exceed 3 hours then I will live with up to 180 threads,
see example code below (not elegant but it is simple).

Thanks again
Colin Brown
PyNZ

!---------------------------------------------------------------------------
------
'''
Multi-thread EDF scheduler

Notes:
1    use simple thread; it terminates after function completion
2    entries put into sched before it is run are EDF sorted
3    separate groups run in parallel and are thus EDF
4    use Queue for thread-safe result return to mainline
5    in practise new threads will probably be created once per
      minute in my application and not all at once as here but 3
      above applies anyway.
'''
import Queue
import sched
import thread
import time

def thdq(q,line):
    q.put(line)

def thd(q,entries):
    s=sched.scheduler(time.time,time.sleep)
    for item in entries:
        s.enter(item[0],1,thdq,(q,item[1]))
    s.run()

q=Queue.Queue()
for ii in range(20):
    a1='Thread '+str(ii)+' @'+str(37-ii)+' secs'
    a2='Thread '+str(ii)+' @'+str(30-ii)+' secs'
    a3='Thread '+str(ii)+' @'+str(34-ii)+' secs'
    thread.start_new_thread(thd,(q,[(37-ii,a1),(30-ii,a2),(34-ii,a3)]))

time.sleep(0.1)
for ii in range(50):
    time.sleep(1)
    print ii+1
    while q.empty()==0:
        print q.get()
!---------------------------------------------------------------------------
------
Python 2.1 on Win NT4 produces:
1
2
3
4
5
6
7
8
9
10
11
Thread 19 @11 secs
12
Thread 18 @12 secs
13
Thread 17 @13 secs
14
Thread 16 @14 secs
15
Thread 19 @15 secs
Thread 19 @15 secs
16
Thread 18 @16 secs
Thread 14 @16 secs
17
Thread 17 @17 secs
Thread 13 @17 secs
18
Thread 19 @18 secs
Thread 16 @18 secs
Thread 12 @18 secs
19
Thread 18 @19 secs
Thread 15 @19 secs
Thread 11 @19 secs
20
Thread 14 @20 secs
Thread 17 @20 secs
Thread 10 @20 secs
21
Thread 16 @21 secs
Thread 13 @21 secs
Thread 9 @21 secs
22
Thread 12 @22 secs
Thread 15 @22 secs
Thread 8 @22 secs
23
Thread 14 @23 secs
Thread 11 @23 secs
Thread 7 @23 secs
24
Thread 10 @24 secs
Thread 13 @24 secs
Thread 6 @24 secs
25
Thread 12 @25 secs
Thread 9 @25 secs
Thread 5 @25 secs
26
Thread 11 @26 secs
Thread 8 @26 secs
Thread 4 @26 secs
27
Thread 7 @27 secs
Thread 10 @27 secs
Thread 3 @27 secs
28
Thread 2 @28 secs
Thread 9 @28 secs
Thread 6 @28 secs
29
Thread 1 @29 secs
Thread 5 @29 secs
Thread 8 @29 secs
30
Thread 0 @30 secs
Thread 7 @30 secs
Thread 4 @30 secs
31
Thread 3 @31 secs
Thread 6 @31 secs
32
Thread 2 @32 secs
Thread 5 @32 secs
33
Thread 1 @33 secs
Thread 4 @33 secs
34
Thread 0 @34 secs
Thread 3 @34 secs
35
Thread 2 @35 secs
36
Thread 1 @36 secs
37
Thread 0 @37 secs
38
39
40
41
42
43
44
45
46
47
48
49
50
>>>