Handle millis()/micros() overflow in task manager

[logan893]

I'm using a task manager adapted from the one found in this post by Alan
http://bleaklow.com/2010/07/20/a_very_simple_arduino_task_manager.html.

After looking into the issue with millis()/micros() overflow, many posts seem to disregard this as being a problem.
Example:
http://forum.arduino.cc/index.php?topic=122413.15

Arduino: How do you reset millis() ? - Bald Engineer

The gist of the task manager is a "now" variable being continuously updated with millis() and passed on to a "Tasks" function call that checks if the task is scheduled to run. The check is as follows:

...
    uint32_t runTime;
...

bool TimedTask::canRun(uint32_t now) {
    return now >= runTime;
}

The overflow issue is never really addressed here.

Consider a task scheduled to run, near the end of the "unsigned long" reach.

now = 2^32-10; runTime = 2^32-12; // now >= runTime == true
now = 2^32-10; runTime = 2^32-2;  // now >= runTime == false
now = 2^32-10; runTime = 1;       // now >= runTime == true  -- INCORRECT -- this should NOT trigger the task to run, and may trigger the task to run very very many times more than intended
now = 10;      runTime = 2^32-12; // now >= runTime == false -- INCORRECT -- if runTime is not incremented externally, the task will not run for a very very long time

There are thus two problems with this.

1. A task may run when it's not supposed to, potentially near-infinite number of times.
2. A task which should run regularly may not run for close to 49 days.

The general approach, "subtract old time from new time and compare with interval", does not translate directly to this situation. However we can adapt it to suit our needs.

now = 2^32-10; runTime = 2^32-12; // now-runTime == 2       -- direct comparison >= 0 WILL work here
now = 2^32-10; runTime = 2^32-2;  // now-runTime == 2^32-8  -- direct comparison >= 0 will NOT work here
now = 2^32-10; runTime = 1;       // now-runTime == 2^32-11 -- direct comparison >= 0 will NOT work here
now = 10;      runTime = 2^32-12; // now-runTime == 22      -- direct comparison >= 0 WILL work here

What we see from this comparison is that the two scenarios which should execute (first and last), are very close to the positive side of the variable space, and the two scenarios which should NOT execute (second and third), are just "below" the maximum.

The simplest way then is to cast the result of now-runTime to a signed long, for which the very high values will end up on the negative end of the scale. In essence by casting the result we say that half the spectrum is in the past, and half is in the future.

What we may also want is to establish a limit for when a task is considered "in the past" and should be executed, and a task which is "in the future". In my opinion, the future should hold the majority of the scheduled time, seeing as if a task was supposed to have run for even one day (~2% of the total millis() space), but was unable to due to other tasks taking up all processing power, then we have a greater issue with starved tasks.

Simplest solution - divide the total time in half by casting the result as a signed long.

now = 2^32-10; runTime = 2^32-12; // (long)(now-runTime) == 2   -- direct comparison >= 0 WILL work here
now = 2^32-10; runTime = 2^32-2;  // (long)(now-runTime) == -8  -- direct comparison >= 0 WILL work here
now = 2^32-10; runTime = 1;       // (long)(now-runTime) == -11 -- direct comparison >= 0 WILL work here
now = 10;      runTime = 2^32-12; // (long)(now-runTime) == 22  -- direct comparison >= 0 WILL work here

If we want to establish this "future" limit we do not need to cast the result, we only need to define what we consider "the future".
"Most time in the future" solution.

const uint32_t future = ((uint32_t)-1)/100*20; // 858993440

...
bool ... canRun(uint32_t now) {
return now-runTime+future >= future;
}

This will make sure that, regardless of whether you are using millis() or micros(), 80% of your schedulable time will be in the future, and only 20% is in the past.

[Peter_n]

I think you are right, comparing two unsigned longs with ">=" causes a problem.

Perhaps the original code was with seconds since 1970 (the unix time). But the Arduino has milliseconds.

Substracting unsigned longs can avoid the rollover problem.
http://playground.arduino.cc/Code/TimingRollover#arithmetic
In this code, the value of "now" can be less or greater than "runTime", and so the substracting won't work.

You use signed long, but it can also be solved with unsigned long. I agree that some decision has to be made for what is in the past or in the future. The 20% for the past seems a good number to me.

[michinyon]

now = 2^32-10; runTime = 2^32-12;

Does this code even compile ?

[logan893]

michinyon:

now = 2^32-10; runTime = 2^32-12;

Does this code even compile ?

No, I assume it will not. They were not intended as code, only as examples for how the variables may be valued. Using the code block is for formatting purposes. I'm sorry for the confusion.

[michinyon]

Two to the power of 32 is not going to be able to be evaluated as a long. Not even an unsigned long.

[Robin2]

Seems like a great justification for just using the simple Blink Without Delay technique and not wasting time on complex task managers.

...R

[logan893]

Robin2:
Seems like a great justification for just using the simple Blink Without Delay technique and not wasting time on complex task managers.

...R

For simpler projects, then surely "Blink Without Delay" is sufficient, yes.
My project will be running too many tasks to not use a more complex task manager, which will only serve to make it easier.

Tasks such as

• TLC5940 LED control
• DHT22 temperature/humidity measurement
• nRF24L01+ communication
• AES encryption/decryption for wireless data
• Hashing data for validation purposes

Another option for how to schedule such a task manager is to store the current run time of a task in a variable, and use another variable to indicate the duration of the delay until next execution. That way you could use the same theory as with "Blink Without Delay", by subtracting and comparing, currentTime-previousTime >= interval.

I actually like this idea also...

[Robin2]

logan893:

Robin2:
For simpler projects, then surely "Blink Without Delay" is sufficient, yes.
My project will be running too many tasks to not use a more complex task manager, which will only serve to make it easier.

Interesting. My logic would be quite the opposite. The more complex the program the more simple and transparent the timing should be. The BWoD technique can easily control several things at a time.

Any Library has to involve more code to achieve the same thing which must impact on the "space" for other stuff in the limited Arduino environment.

But each to his own.

...R

[system]

Robin2:
Seems like a great justification for just using the simple Blink Without Delay technique and not wasting time on complex task managers.

Yes.

[MarkT]

The test here is simply miscoded

bool TimedTask::canRun(uint32_t now) {
    return now >= runTime;
}

As always you need to subtract before comparing with timestamps:

bool TimedTask::canRun(uint32_t now) {
    return now - runTime >= 0 ;
}

The result of the subtraction is a time delta and will be correct whether or not the
two absolute time values are wrapping or not. [So long as the runTime wasn't set too
far from the current time when it was last updated].

[Peter_n]

MarkT, that was what this discussion was about, see my Reply #1.
The value of 'runTime' can be higher or lower than 'now'.
Some extra checking is needed.

[system]

Peter_n:
Some extra checking is needed.

Not if you code it correctly - using unsigned arithmetic and using subtraction rather than addition.

[MarkT]

Oh yes! Oh well it can bear repeating.

I've never scheduled something >25 days in advance! I think if I would use
a RTC I think

Oh, while on the subject here's a little scheduler of mine, using heapsort
to maintain a small set of tasks:
http://sphinx.mythic-beasts.com/~markt/TaskManLong.zip

Unlike the task manager mentioned in the OP it can run alongside other
code as it does hog the processor with a while loop and its can-run testing
is properly optimized.

[logan893]

Robin2:
Interesting. My logic would be quite the opposite. The more complex the program the more simple and transparent the timing should be. The BWoD technique can easily control several things at a time.

Any Library has to involve more code to achieve the same thing which must impact on the "space" for other stuff in the limited Arduino environment.

But each to his own.

...R

By creating a class to handle the task execution, we can reuse much code between tasks and as such reduce the program space. The memory usage may be marginally higher though, but in my case I'm closer to running out of program space than RAM.

I took the liberty of converting your SeveralThingsAtTheSameTimeRev1.ino into using a class based task manager approach. The program storage space was slightly reduced, from 4,616 to 4,490 bytes, while memory usage went up from 315 to 407 bytes.

PeterH:

Peter_n:
Some extra checking is needed.

Not if you code it correctly - using unsigned arithmetic and using subtraction rather than addition.

To me it is quite clear that when you are close to the overflow point of the unsigned value space, the regular "subtract" approach will not work even if you know that one variable will be less (further in the past) than another.

How do we know what constitutes "future" and what is "past"? We will need to either involve a third variable, or cast as signed.

Perhaps an example with uint8_t is easier.

In this example, nextRun will always be 2 behind now.

uint8_t now = 2;
uint8_t nextRun = 0;

void setup() { Serial.begin(115200); }

void loop() {
  now++;
  nextRun++;
  Serial.print("now == ");
  Serial.print(now);
  Serial.print(",\tnextRun == ");
  Serial.print(nextRun);
  Serial.print(",\tnow-nextRun >= 0 ==");
  Serial.print(now-nextRun >= 0);
  Serial.println();
  
  delay(10);
}

And around the overflow point we see problems appear.

now == 254,	nextRun == 252,	now-nextRun >= 0 ==1
now == 255,	nextRun == 253,	now-nextRun >= 0 ==1
now == 0,	nextRun == 254,	now-nextRun >= 0 ==0
now == 1,	nextRun == 255,	now-nextRun >= 0 ==0
now == 2,	nextRun == 0,	now-nextRun >= 0 ==1
now == 3,	nextRun == 1,	now-nextRun >= 0 ==1

The same is true when nextRun is always 2 ahead of now.

now == 252,	nextRun == 254,	now-nextRun >= 0 ==0
now == 253,	nextRun == 255,	now-nextRun >= 0 ==0
now == 254,	nextRun == 0,	now-nextRun >= 0 ==1
now == 255,	nextRun == 1,	now-nextRun >= 0 ==1
now == 0,	nextRun == 2,	now-nextRun >= 0 ==0
now == 1,	nextRun == 3,	now-nextRun >= 0 ==0

The larger the gap between now and runTime(nextRun), the larger the ambiguity if using the "traditional" approach.

[system]

logan893:
To me it is quite clear that when you are close to the overflow point of the unsigned value space, the regular "subtract" approach will not work even if you know that one variable will be less (further in the past) than another.

To me it is quite clear that you don't understand how unsigned arithmetic works. Using unsigned arithmetic and subtraction handles the rollover case correctly without needing any special code if you code it correctly.

If you subtract a previous time from the current time using unsigned arithmetic the result is the elapsed time.

unsigned long previousMillis;
unsigned long interval;

if(millis() - previousMillis >= interval)
{
    // the interval has elapsed
    previousMillis += interval; // note the start of the next interval
}

logan893:
We will need to either involve a third variable, or cast as signed.

No, and no. The times you hold are times in the past. Subtract that from the current time to calculate the elapsed time. The elapsed time is always positive. Working out when the elapsed time exceeds a threshold is then trivial.

[Robin2]

logan893:
I took the liberty of converting your SeveralThingsAtTheSameTimeRev1.ino into using a class based task manager approach. The program storage space was slightly reduced, from 4,616 to 4,490 bytes, while memory usage went up from 315 to 407 bytes.

Would you mind posting the revised code - I would be very interested to see it.

...R

[logan893]

PeterH:

logan893:
To me it is quite clear that when you are close to the overflow point of the unsigned value space, the regular "subtract" approach will not work even if you know that one variable will be less (further in the past) than another.

To me it is quite clear that you don't understand how unsigned arithmetic works. Using unsigned arithmetic and subtraction handles the rollover case correctly without needing any special code if you code it correctly.

If you subtract a previous time from the current time using unsigned arithmetic the result is the elapsed time.

unsigned long previousMillis;

unsigned long interval;

if(millis() - previousMillis >= interval)
{
   // the interval has elapsed
   previousMillis += interval; // note the start of the next interval
}

> logan893:
> We will need to either involve a third variable, or cast as signed.



No, and no. The times you hold are times in the past. Subtract that from the current time to calculate the elapsed time. The elapsed time is always positive. Working out when the elapsed time exceeds a threshold is then trivial.

You are correct that proper unsigned arithmetic will always give the elapsed time if one is lower than the other. I was tricked by my code above which seem to cast the value sent to Serial.print() to signed automatically, but only for negative values. This same behaviour holds true even when only involving unsigned variables.

uint8_t now = 2;
uint8_t nextRun = 4;
uint8_t check = 0;

void setup() { Serial.begin(115200); }

bool returnvalue(uint8_t n, uint8_t next) {
  return now-nextRun >= check;
}
void loop() {
  now++;
  nextRun++;
  Serial.print("now == ");
  Serial.print(now);
  Serial.print(",\tnextRun == ");
  Serial.print(nextRun);
  Serial.print(",\tnow-nextRun >= 0 ==");
  Serial.print(returnvalue(now,nextRun));
  Serial.println();
  
  delay(10);
}

now == 253,	nextRun == 255,	now-nextRun >= 0 ==0
now == 254,	nextRun == 0,	now-nextRun >= 0 ==1
now == 255,	nextRun == 1,	now-nextRun >= 0 ==1
now == 0,	nextRun == 2,	now-nextRun >= 0 ==0

The way around this is to cast the result to unsigned.
E.g. (uint8_t)(now-nextRun)

Back to the original problem however, it still stands to reason that for the way this task manager handles execution time, an additional element is needed on top of "now >= runTime".

"now-runTime >= 0" is not sufficient, unless the result is cast to the signed type of the variable. This problem is due to the fact that runTime can be both ahead of, or behind, "now".

Casting to signed and comparing with 0 should be a computationally fast method while also maintaining roughly 50% of all possible schedulable time in the future.

And as I mentioned previously, another way around this is the "future" variable. How much of the schedulable time do we want in the future vs the past.

[logan893]

Robin2:

logan893:
I took the liberty of converting your SeveralThingsAtTheSameTimeRev1.ino into using a class based task manager approach. The program storage space was slightly reduced, from 4,616 to 4,490 bytes, while memory usage went up from 315 to 407 bytes.

Would you mind posting the revised code - I would be very interested to see it.

...R

Sure! Here it is.

SeveralThingsAtTheSameTimeRev2.ino (11 KB)

[system]

logan893:
You are correct that proper unsigned arithmetic will always give the elapsed time if one is lower than the other

Your proviso is not required. The unsigned arithmetic using subtraction gives the correct behaviour regardless of overflow, without any special code to handle the overflow condition.

[logan893]

PeterH:

logan893:
You are correct that proper unsigned arithmetic will always give the elapsed time if one is lower than the other

Your proviso is not required. The unsigned arithmetic using subtraction gives the correct behaviour regardless of overflow, without any special code to handle the overflow condition.

If what you are after is not only the difference between now and last execution (which we are not, by the very nature of this task manager using "next" runTime instead of lastRun), then you have to use additional constructs.

One very interesting fact is that for the example you provide:
"millis() - previousMillis >= interval"
the compiler is automatically (at least when using Arduino IDE 1.5.7) casting the subtraction to a signed value, so you are comparing apples to oranges depending on the magnitude of the values returned by the function and variable. The comparison will sometimes be true, sometimes false, for the same time difference.

Example code and output.

  uint8_t ms = 0;
  uint8_t prevms = 127;
  uint8_t interval = 8;
  uint16_t d = 0;
  for (uint16_t c=0; c<35; c++)
  {
    if (ms - prevms >= interval) { d++; }
    else { Serial.print("================="); }
    Serial.print("c="); Serial.print(c);
    Serial.print("\tms="); Serial.print(ms);
    Serial.print("\tprevms="); Serial.print(prevms);
    Serial.print("\tms-prevms="); Serial.print((ms - prevms));
    Serial.println();
    ms += interval;
    prevms += interval;
  }
  Serial.print("d=");
  Serial.println(d);

Output

=================c=0	ms=0	prevms=127	ms-prevms=-127
=================c=1	ms=8	prevms=135	ms-prevms=-127
=================c=2	ms=16	prevms=143	ms-prevms=-127
=================c=3	ms=24	prevms=151	ms-prevms=-127
=================c=4	ms=32	prevms=159	ms-prevms=-127
=================c=5	ms=40	prevms=167	ms-prevms=-127
=================c=6	ms=48	prevms=175	ms-prevms=-127
=================c=7	ms=56	prevms=183	ms-prevms=-127
=================c=8	ms=64	prevms=191	ms-prevms=-127
=================c=9	ms=72	prevms=199	ms-prevms=-127
=================c=10	ms=80	prevms=207	ms-prevms=-127
=================c=11	ms=88	prevms=215	ms-prevms=-127
=================c=12	ms=96	prevms=223	ms-prevms=-127
=================c=13	ms=104	prevms=231	ms-prevms=-127
=================c=14	ms=112	prevms=239	ms-prevms=-127
=================c=15	ms=120	prevms=247	ms-prevms=-127
=================c=16	ms=128	prevms=255	ms-prevms=-127
c=17	ms=136	prevms=7	ms-prevms=129
c=18	ms=144	prevms=15	ms-prevms=129
c=19	ms=152	prevms=23	ms-prevms=129
c=20	ms=160	prevms=31	ms-prevms=129
c=21	ms=168	prevms=39	ms-prevms=129
c=22	ms=176	prevms=47	ms-prevms=129
c=23	ms=184	prevms=55	ms-prevms=129
c=24	ms=192	prevms=63	ms-prevms=129
c=25	ms=200	prevms=71	ms-prevms=129
c=26	ms=208	prevms=79	ms-prevms=129
c=27	ms=216	prevms=87	ms-prevms=129
c=28	ms=224	prevms=95	ms-prevms=129
c=29	ms=232	prevms=103	ms-prevms=129
c=30	ms=240	prevms=111	ms-prevms=129
c=31	ms=248	prevms=119	ms-prevms=129
=================c=32	ms=0	prevms=127	ms-prevms=-127
=================c=33	ms=8	prevms=135	ms-prevms=-127
=================c=34	ms=16	prevms=143	ms-prevms=-127
d=15

One more limitation of the paradigm "millis() - previousMillis >= interval" is that any difference greater than "interval" will trigger an execution. In a task manager such as this we want to be able to have a varying frequency of code execution. And as such we need to establish how far in the future the next trigger can be.

I do agree that this is one way of doing things, however it is not as simple as this when the variable we use tells us at what time to execute, and not how much time may elapse since last execution.

So either we use "(uint32_t)(millis() - previousMillis) >= interval", or we use "now-runTime >= 0" with the addition of

1. Explicit signed-ness or unsigned-ness declaration
   and possibly
2. Future time statement