Sleeping just the right amount of time

,

When you go to bed at night, you have two possibilities regarding the next morning wakeup time:

  1. You decide that you will sleep for 8 hours regardless of the bed time. You will feel well-rested, but you risk getting up at 1PM if you went to bed at 3AM. And, the next day, your wakeup time may drift to 2PM if you had a 17 hour long day. You will never get tired, but your social life may suffer from not being necessarily awake at the same time as everyone else.
  2. You decide that you will wake up at 7AM regardless of the bed time. You may be a bit tired from time to time, but you will enjoy a rich social life.

When you develop an embedded system, those two choices still hold when you need to put a thread to sleep:

  1. You have to wait for some time: for example, you do not want to turn your video projector on less than one minute after it has been turned off to avoid damaging the light bulb.
  2. You have to wait until some future date: for example you want to increment your clock counter every millisecond to keep track of the current time.

Most real-time operating systems provide the programmer with two options to put a thread to sleep. The first one typically takes a number of system ticks during which the thread will stay asleep. It will then be woken up after the given time. In ChibiOS/RT, this is done with:

chThdSleep(delayInSystemTicks);

The second option takes an absolute date at which the thread should be woken up. Again, in ChibiOS/RT, a function allows the programmer to do that:

chThdSleepUntil(futureDate);

If you want to run a doSomething() function every 12 milliseconds, with a system tick being configured as 1 millisecond, you could want to write:

for (;;) {
  doSomething();
  chThdSleep(12);
}

but this would be improper, as you wait for 12 milliseconds between the end of the previous doSomething() call and the beginning of the next one. If, from time to time, doSomething() gets preempted by a high-priority task or an interrupt routine and takes a few milliseconds to run, you will slowly accumulate the drift.

A more proper way of writing it is to use absolute delays, as in:

systime_t time = chTimeGetNow();
for (;;) {
  doSomething();
  time += 12;
  chThdSleepUntil(time);
}

chTimeGetNow() returns the initial date at which we execute the first doSomething() call, and will use this basis and add 12 milliseconds at a time to this initial date. Even if sometimes doSomething() takes 5 milliseconds to run, then the subsequent chThdSleepUntil() will sleep for only 7 milliseconds instead of 12. No drift will ever get accumulated.

However, there is a caveat. What if, in your soft real-time system, where some deadlines can occasionally be missed, doSomething() takes more than 12 milliseconds to execute?

A disaster waiting to happen

Embedded systems are usually designed to run forever, or at least for long enough so that the internal variable used to represent the number of elapsed system ticks will wrap around 0 and restart from its lowest value. For example, if an unsigned 32 bits variable is used to represent the number of milliseconds elapsed since the system start time, then before 50 days it will start from 0 again because the highest representable value (231 − 1) will have been reached.

Let’s assume that doSomething() was last executed at time = t0. The current time is now t0 + 15, and we ask the system to wait until t0 + 12. That is in the past, so no sleeping should occur, right? Wrong, for ChibiOS/RT, this represents the future, as this value will be reached in about 49.7 days. Which means that you will not execute doSomething() for more than seven weeks just because your 12 milliseconds deadline has been missed by 3 milliseconds.

The author of ChibiOS/RT has ackowledged this issue and even included an article into the knowledge base. However, in his view, this function should only be used on hard real-time systems where deadlines will be met inconditionally. This is a perfectly reasonable position, and on some systems with 16 bits time counters, trying to guess if the user meant a past time rather than a future time would cut the maximum resolution in half and only let a maximum timespan of about 32 seconds.

A little help for other systems

Another operating system, FreeRTOS, uses a clever way of dealing with those situations by adding another parameter to the sleeping function representing the latest wakeup time. This way, by comparing three time values (the current time, the latest wakeup time and the latest wakeup time + the expected delay cycle), the system is able to determine whether the next wakeup time has been reached already (in which case it does not sleep), or if sleeping is still needed. As long as the time spent since the next wakeup is smaller than a full timer cycle (49.7 days for 32 bits, 65.5 seconds for 16 bits, all that with a milliseconds system tick), the result will be non-ambiguous.

The following snippet allows you to use a similar functionality in ChibiOS/RT:

void sleepUntil(systime_t *previous, systime_t period)
{
  systime_t future = *previous + period;
  chSysLock();
  systime_t now = chTimeNow();
  int mustDelay = now < *previous ?
    (now < future && future < *previous) :
    (now < future || future < *previous);
  if (mustDelay)
    chThdSleepS(future - now);
  chSysUnlock();
  *previous = future;
}

Like its FreeRTOS counterpart vTaskDelayUntil(), it takes care of incrementing the variable pointed onto by the previous parameter by the number of system ticks given in period. The logic to know if we have to sleep (captured in the mustDelay assignment) is the following:

  • If the current time (now) is smaller than the previous wakeup, it means that the time counter has wrapped around 0. In this case, we have to sleep if the future wakeup time is smaller than the previous one (otherwise, it means that the future value has not wrapped around 0 and has been passed by the current time) and if it is greater than the current time (otherwise, it means that the future value has wrapped around 0 as well but is still behind the current time).

  • If the current time is greater or equal than the previous wakeup, we have to sleep either if the future wakeup time is after the current time, or if the future wakeup time is before the previous time, meaning that the future wakeup time computation has wrapped around 0 while the current time still hasn’t.

This way, we get a safer, easier to use function which allows for occasional missed deadlines in a soft real-time system:

systime_t time = chTimeGetNow();
for (;;) {
  doSomething();
  sleepUntil(&time, 12);
}
If you like this post, you can send some bitcoin dust to 1Bo78aNzJvkmeLTw8aptaFipvRWyNQP2WF (or click here).
blog comments powered by Disqus