HowToTimeout.txt - Dealing correctly with timeouts.
Version 2, Hugh Sparks


We have some iterative process that should not take longer
than "timeout" ticks.

We have a function "now" that returns the current unsigned
integer tick count.

The following code is often seen, even in published algorithms:

        then = now() + timeout
        while now() < then do
        {        Continue the process.
        }

This clearly fails when the initial computation of "then"
wraps around: The loop won't execute at all.

In order to timeout correctly, we need to test the interval,
not the absolute time.

First adjust the stop time:

        then = now() + timeout - 1 ;

Assuming your process is in a loop, the condition becomes:

        while (then - now()) < timeout do
        {        Continue the process.
        }

To see how this works, we will use a machine word size
of 4 bits. All variables must be unsigned and the math
must be done mod 16:

Case 1: Stop time does not wrap around:

        now() = 1
        timeout = 6
        then = 1 + 6 - 1 = 6

        then - now:
        6 - 1 =  5
        6 - 2 =  4
        6 - 3 =  3
        6 - 4 =  2
        6 - 5 =  1
        6 - 6 =  0
        6 - 7 = 15 Timeout
        6 - 8 = 14
        ...

Case 2: Stop time does wrap around:

        now() = 12
        timeout = 6
        then = 12 + 6 - 1 = 1 (mod 16)

        then - now:
        1 - 12 =  5
        1 - 13 =  4
        1 - 14 =  3
        1 - 15 =  2
        1 -  0 =  1
        1 -  1 =  0
        1 -  2 = 15 Timeout
        1 -  3 = 14
        ...

Another variation is to reverse the subtraction.
In this case, we don't need to subtract 1 in the calcuation
for "then". For some reason, this form of exit condition
reads a bit more "oddly":

        then = now() + timeout
        while (now() - then) > timeout do
        {        Continue the process.
        }

        now() = 12
        timeout = 6
        then = 12 + 6 = 2 mod 16

        now - then
        12 - 2 = 10
        13 - 2 = 11
        14 - 2 = 12
        15 - 2 = 13
         0 - 2 = 14
         1 - 2 = 15
         2 - 2 =  0 Timeout
         3 - 1 =  1
         ...

A related problem is to find out how much time has elapsed
in a process when we must use a wrap-around counter.

In this case, the obvious code works perfectly:

        t0 = now()
        while condition do
        {        time = now() - t0 ;
        }

We can use this result for our process timeout:

	time = t0 = now()
        while time < timeout do
        {        time = now() - t0 ;
        }

Example with wrap around:

        t0 = 12

        now() - t0
        12 - 12 =  0
        13 - 12 =  1
        14 - 12 =  2
        15 - 12 =  3
         0 - 12 =  4
         1 - 12 =  5
         2 - 12 =  6
         3 - 12 =  7
         4 - 12 =  8
         5 - 12 =  9
         6 - 12 = 10
         7 - 12 = 11
         8 - 12 = 12
         9 - 12 = 13
        10 - 12 = 14
        11 - 12 = 15
        12 - 12 = 0

No matter where we start with t0, the elapsed time
now() - t0 will be correct until we have counted
an elapsed time greater than the largest value the
word can represent.

**************************************************

If we prefer to use signed arithmetic for timeout very
little changes. Again, we will assume a 4-bit word size.

Case 1: Stop time does not wrap around:

        now() = 1
        timeout = 6
        then = 1 + 6 - 1 = 6

        then - now:
        6 - 1 =  5
        6 - 2 =  4
        6 - 3 =  3
        6 - 4 =  2
        6 - 5 =  1
        6 - 6 =  0
        6 - 7 = -1 Timeout
        6 - 8 = -2
	...

Case 2: Stop time does wrap around:

        now() = -4
        timeout = 6
        then = -4 + 6 - 1 = 1 
        then - now:
        1 - -4 =  5
        1 - -3 =  4
        1 - -2 =  3
        1 - -1 =  2
        1 -  0 =  1
        1 -  1 =  0
        1 -  2 = -1 Timeout
        1 -  3 = -2
        ...

You can see in either case that the test should be:

        while (then - now()) > 0 do
        {        Continue the process.
        }

With signed arithmetic, the elapsed time case looks
like this:

        t0 = -4

        now() - t0 =

        -4 - -4 =  0
        -3 - -4 =  1
        -2 - -4 =  2
        -1 - -4 =  3
         0 - -4 =  4
         1 - -4 =  5
         2 - -4 =  6
         3 - -4 =  7
         4 - -4 = -8
         5 - -4 = -7
         6 - -4 = -6
         7 - -4 = -5
         8 - -4 = -4
         9 - -4 = -3
        10 - -4 = -2
        11 - -4 = -1
        12 - -4 =  0

We see that everything works, but we only have half
the range for our elapsed time measurement before
we get the wrong answer.

-Hugh

