Re: significance of lock->__spinlock increment in spinlock.c?

[Kaz Kylheku <kaz at ashi dot footprints dot net>]

On Mon, 18 Dec 2000, Britton wrote:

> Date: Mon, 18 Dec 2000 14:33:16 -0900 (AKST)
> From: Britton <fsblk@aurora.uaf.edu>
> To: libc-alpha@sourceware.cygnus.com
> Subject: significance of lock->__spinlock increment in spinlock.c?
>
>
> I have been trying to understand the thread code.  On smp kernels, after a
> failed spin, lock->__spinlock gets incremented like this:

Yes. On SMP kernels we don't need the spinlock because we have the
compare-and-swap instruction. So we reuse the __spinlock field to store a
smoothed average of the measured spin count.

>     lock->__spinlock += (spin_count - lock->__spinlock) / 8;
>
> which amount to
>
>     lock->__spinlock += (lock->__spinlock * 2 + 10 - lock->__spinlock) / 8

The algebraic substitution you wrote here is only valid in the case that the
full spin occurs; that is to say, the lock is not acquired. It is expected that
the spincount will be actually far less than ``lock->__spinlock * 2 + 10''.

> I am just wondering what is the significance of the numbers used in this
> increment, or where can I find out?

Firstly, the division by eight is just a convergence factor. A larger
denominator means that the smoothed spin count will converge more slowly to the
measurements so it is more resistant to transient perturbations.  The
measurement are likely to fluctuate wildly, ranging from near zero, as the
owner is just coming out of the critical region, to around twice the average,
when the owner has just acquired the lock. The program may also have several
critical regions based on the same lock, and have many different execution
paths through the same critical region.  Without assuming anything about the
behavior of the program, the value eight seems to be a reasonable tradeoff
between convergence speed and resistance to fluctuation, so I decided to just
use that without doing too much analysis on it.

The maximum spin count is computed as 2 * average + 10. The extra 10 spins is
just a hack to make the algorithm self starting. The spin field is initally
zero, and so the maximum iterations would be two times zero, meaning that the
smoothed average would never get off the ground from zero.  This number could
be any reasonably small non-zero value. An alternative would be to initialize
the spinlock field to some non-zero value, but then the initialization would
have to differ for SMP versus non-SMP, which is only detected at run time.

The reason the factor 2 is used for the spin limit is because the critical
region duration is around twice the smoothed average, assuming random sampling.
random.  E.g. if the average indicates 1 microsecond, then the worst case wait
is probably around 2 microseconds. If the lock is not released in that time,
it's likely that the owner has been descheduled from its processor, making it
reasonable reasonable to give up and suspend. This is somewhat conservative,
erring on the side of trying not to burn too many cycles in the spin.