TimingWheels

This structure implements scheme 6.2 thom the http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf

It supports several primitives: 1. schedule timer in the future. 2. cancel timer. 3. time step (advance) - all timers expired at current time tick are extracted from wheels. Each operation take O(1) time.

struct TimingWheels (

) {

import core.bitop : bsr;;

alias Ticks = ulong;

~this();

void schedule(T timer, ulong ticks);

void cancel(T timer);

int ticksUntilNextEvent();

Duration timeUntilNextEvent(Duration tick);

auto advance(ulong ticks);

}

Destructor

~this ~this(): Undocumented in source.

Members

Aliases

Ticks alias Ticks = ulong: Undocumented in source.

Functions

advance auto advance(ulong ticks): Adnvance wheel and return all timers expired during wheel turn.
cancel void cancel(T timer): Cancel timer
schedule void schedule(T timer, ulong ticks): Schedule timer to future
ticksUntilNextEvent int ticksUntilNextEvent(): count "empty" ticks - slots without events. If you have empty ticks it is safe to sleep - you will not miss anything, just wake up at the time when next timer have to be processed.
timeUntilNextEvent Duration timeUntilNextEvent(Duration tick): Time until next scheduled timer event.

Examples

1 import std;
2 globalLogLevel = LogLevel.info;
3 auto rnd = Random(142);
4 
5 /// track execution
6 int  counter;
7 SysTime last = Clock.currTime;
8 
9 /// this is our Timer
10 class Timer
11 {
12     static ulong __id;
13     private ulong _id;
14     private string _name;
15     this(string name)
16     {
17         _id = __id++;
18         _name = name;
19     }
20     /// must provide id() method
21     ulong id()
22     {
23         return _id;
24     }
25 }
26 
27 enum IOWakeUpInterval = 100; // to simulate random IO wakeups in interval 0 - 100.msecs
28 
29 // each tick span 5 msecs - this is our link with time in reality
30 enum Tick = 5.msecs;
31 TimingWheels!Timer w;
32 
33 auto durationToTicks(Duration d)
34 {
35     return d/Tick;
36 }
37 void process_timer(Timer t)
38 {
39     switch(t._name)
40     {
41         case "periodic":
42             writefln("@ %s - delta: %sms (should be 50ms)", t._name, (Clock.currTime - last).split!"msecs".msecs);
43             last = Clock.currTime;
44             counter++;
45             w.schedule(t, durationToTicks(50.msecs)); // rearm
46             break;
47         default:
48             writefln("@ %s", t._name);
49             break;
50     }
51 }
52 
53 //
54 // start one arbitrary timer and one periodic timer
55 //
56 auto some_timer = new Timer("some");
57 auto periodic_timer = new Timer("periodic");
58 w.schedule(some_timer, durationToTicks(32.msecs));
59 w.schedule(periodic_timer, durationToTicks(50.msecs));
60 
61 while(counter < 10)
62 {
63     auto randomIoInterval = uniform(0, IOWakeUpInterval, rnd).msecs;
64     auto nextTimerEvent = max(w.timeUntilNextEvent(Tick), 0.msecs);
65     // wait for what should happen earlier
66     auto time_to_sleep = min(randomIoInterval, nextTimerEvent);
67     writefln("* sleep until timer event or random I/O for %s", time_to_sleep);
68     Thread.sleep(time_to_sleep);
69     // if we waked up early by the IO event then timeUntilNextEvent will be positive
70     // otherwise it will be <= 0 and we have something to process.
71     while(w.timeUntilNextEvent(Tick) <= 0.msecs)
72     {
73         auto ticks = w.ticksUntilNextEvent();
74         auto wr = w.advance(ticks);
75         foreach(t; wr.timers)
76         {
77             process_timer(t);
78         }
79     }
80     // some random processing time
81     Thread.sleep(uniform(0, 5, rnd).msecs);
82 }