Coder's block: How to fire timer at intervals, compensating for early/late firing

Question

I'm having a silly-yet-serious case of coder's block. Please help me work through it so my brain stops hurting and refusing to answer my questions.

I want to fire a timer at intervals up to a final time. For example, if t = 0, my goal is 100, and my interval is 20, I want to fire at 0, 20, 40, 60, 80, and 100.

The timer is not precise, and may fire early or late. If it first fires at 22, I want to fire again in 18. If it first fires at 19, I want to fire in 21. All I know when the timer fires is the current time, goal time, and firing interval. What do I do?

Edit: Sorry, I wasn't too specific about what the heck I'm actually asking. I'm trying to figure out what kind of math (probably involving taking the modulus of something) needs to be done to calculate the delay until the next firing. Ideally, I also want the timer to by matched to the end time — so if I start the timer initially at 47, it schedules itself to fire at 60 and not at 67, so the last firing will still be at 100.

Answer 1

I would use the system clock to check your interval. For example if you know that your interval is every 20 minutes, fire off the first interval, check what the time was, and adjust the next interval start time.

Answer 2

If the primitive functionality you have is "schedule X to fire once at time T", then your procedure handling X should know the time T0 at which it was supposed to fire (the time T1 at which it actually fired is not needed) as well as the desired firing interval DT and schedule itself for time T0+DT. If the primitive is "fire D from now", then it should schedule for D = T0+DT-T1 (if that's negative then it needs to schedule itself immediately again but record that the scheduled time and the "was supposed to fire at" time are different so it can keep compensating on following firings).

Somebody already mentioned that .NET's Timer does this for you; so does Python's sched stdlib module; so, I'm sure, do many other languages / frameworks / libraries. But in the end you can build it if needed on top of either of the single-scheduling primitives above (one for an absolute time or one for a relative delta from now) as long as you keep track of desired as well as actual firing times!_)

Answer 3

Build a table listing the desired fire times, say 10:00, 10:20, 10:40, 11:00, and 11:20.

If your timer function takes an absolute time, the rest is trivial. Set it to fire at each of the desired times. If for whatever reason you can only set one timer at a time, okay, set it to fire at the first desired time. When that event happens, set it to fire again at the next time in the table, without regard to what time it is now. Each time through, pick up the next time until you're done.

If your timer function only accepts an interval, no big deal either. Find the difference between the desired time and the current time, and set it to fire at that interval. Like if the first time is 10:00 and it's now 9:23, set it to fire in 10:00 minus 9:23 equal 37 minutes. Then when that happens, set the interval to the next desired time minus the current time. If it really fired at 10:02, then the interval is 10:20 minus 10:02 equals 18 minutes. Etc.

You probably should check for the possibility that the next fire time has already passed. If the process can take longer than the interval you might run past it, and even if not, the system might have been down. If a fire time is missed, you may want to do catch up runs, or just skip it and go to the next desired time, depending on the details of your app.

If you can't keep the entire table -- like it goes on to infinity -- then just keep the next fire time. Each time through the process, add a fixed amount to the next fire time, without regard to when the current process ran. Then calculate the interval based on the current time. Like if you have a desired interval of 20 minutes going on forever starting at 10:00, and it's now 9:23, you set the first interval to 37 minutes. Say that actually happens at 9:59. You set the next fire time to 10:00 plus 20 minutes equals 10:20, i.e. base it on the goal time rather than the actual time. Then calculate the interval to the next fire time based on the current time, i.e. 10:20 minus 9:59 equals 21 minutes. Etc.

Answer 4

If your language/platform's underlying timers don't do what you want, then it's usually best to implement timers in terms of "target times", which means the absolute time at which you want the timer to fire next. If you platform asks for an "absolute time", then you give it the target time. If it asks for a "relative time" (or, like sleep, a duration), then it is of course target_time - current_time.

The quick way to calculate each target time in turn is:

• When you first set up the timer, calculate the "interval" (which might have to be a floating-point value, assuming that won't cripple performance) and also the "target time" of the first timer fire (again, you might need fractions). Record both, and set your underlying timer mechanism, whatever that is.
• When the timer fires, work out the next target time by adding the interval to the previous target time.

The problem with that approach is that you might get some very tiny accumulating errors as you add the interval to the target time (or not so tiny, if you haven't used floats).

So the longer and more accurate way is to store the very first start time, the target finishing time, and the number of firings (n). Then you recalculate the target time for each new firing in turn, which makes sure that you don't get cumulative rounding errors. The formula for that is:

target(k) = start + ((target_end - start) * k) / n

Of if you prefer:

target(k) = (k/n) * end + (1-k/n) * start

Where the firings of the timer are k=1, 2, 3, ... n. I was going to make it 0-based, then realised that was daft ;-)

The last thing you have to wrestle with when implementing timers is the difference between "wall clock" time, and real elapsed time as measured by your hardware clock. Wall clock time can suddenly jump forwards or backwards (either by an hour if your wall clock is affected by daylight savings, or by any amount if the system's clock is adjusted or corrected). Real time always increases (as long as it doesn't wrap). Which you want your timer to respect depends on the intended purpose. If you want to know when your last bus leaves, you want a timer firing daily according to wall clock time, but most commonly you care about real time elapsed. A good timer API has options for these kinds of things.