Spinlock and lockfree and waitfree...

[aminer]

Hello,

I have come to an interresting subject, and you have
to be smart to understand it more...

If you take a look at the following FIFO queue that is
waitfree on the push() side and lockfree on the pop()
side, here it's:

http://pastebin.com/f72cc3cc1

as i said before , there is a weaknesses with this FIFO queue, first
the lockfree side on the pop() is not FIFO fair , so it's not
starvation-free on the pop() side, and there is a second weakness:
it doesn't minimizes the cache-coherence traffic ,
but there is also a third weakness with this algorithm: since
you can not use an exponential backoff on the waitfree pop() side
you can not make it 4 times or 6 times faster under contention on the
push() side,
the Spinlock() with an exponential backoff mechanism on the pop()
and the push() is 4 times to 6 times faster than the lockfree
version and the waitfree version without a backoff mechanism and
i have just explain it to you,
but you can add an exponential backoff on the pop() lockfree side of
this FIFO que,
and this will make it 6 times faster under contention on the pop() side.


So in my opinion , since the Spinlock with an exponential backoff is
6 times faster under contention , so the risk of a stavartion will
be lowered, and since it minimizes the cache-coherence traffic, so this
will make the Spinlock with an exponential backoff
a better alternative if you want better speed and to minimize
cache-coherence traffic.



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,


This 6X times faster is just for the pop() method, but
for the push() the Spinlock with backoff gives the same
performance as the lockfree, so this is why they both have
the same performance under contention.

[Chris M. Thomasson]

"aminer" wrote in message news:l3kl4m$ioi$1...@news.albasani.net...

[...]

> So in my opinion , since the Spinlock with an exponential backoff is
> 6 times faster under contention , so the risk of a stavartion will
> be lowered, and since it minimizes the cache-coherence traffic, so this
> will make the Spinlock with an exponential backoff
> a better alternative if you want better speed and to minimize
> cache-coherence traffic.

One tiny point:

A lockfree algorithm can make progress on every failure of the condition.

A spinlock cannot.

;^/