Re: spin locks and starvation

On Mon, 3 Apr 2017 11:40:29 +0200, Tom DalPozzo <t(dot)dalpozzo(at)gmail(dot)com>
wrote:

>I saw that postgresql implementation makes big use of spin locks.
>I was wondering if I should be concerned about possible starvation problem
>because I looked around and couldn't find an absolute answer about if linux
>spinlocks guarantee protection about starvation or not. I'm using ubuntu
>16.04.
>
>I've noticed no problem so far, I'm just wondering.

No form of locking can guarantee progress - starvation avoidance
requires use of a wait-free arbitration method.

Note that "wait-free" is not the same as "lock-less". Lock-less
methods guarantee only that *some* thread can make progress, not that
all threads will make progress. Any particular thread may starve
under lock-less arbitration.

There are a number of lock-less algorithms to choose from, but truely
wait-free algorithms are complex and difficult to implement correctly.
Outside of hard real-time systems they are quite rare.
http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf

Spin locking is the optimal *locking* technique to use when conflicts
are expected to occur relatively often, but the period of locking is
relatively short [wrt to the unlocked period and for some respective
definitions of "relatively"].

YMMV,
George