Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #3907 > unrolled thread

Lockfree or not to lockfree..

Back to article view | Back to comp.programming

Contents

  Lockfree or not to lockfree.. aminer <aminer@toto.net> - 2013-10-10 15:33 -0700
    Re: Lockfree or not to lockfree.. aminer <aminer@toto.net> - 2013-10-10 15:45 -0700
    Re: Lockfree or not to lockfree.. aminer <aminer@toto.net> - 2013-10-10 16:09 -0700
    Re: Lockfree or not to lockfree.. "Chris M. Thomasson" <no@spam.invalid> - 2013-10-10 14:35 -0700

#3907 — Lockfree or not to lockfree..

Hello,

Lockfree or not to lockfree , that's the question ...

I have read here and there that lockfree algorithms are hard,
but that's not always the case, if you take a look at the following
FIFO queue that is waitfree on the push() and Lockfree on the pop()

http://pastebin.com/f72cc3cc1

You will read this:

===
public bool pop(out T state) {
       node cmp, cmptmp = m_tail;
       do {
         cmp = cmptmp;
         node next = cmp.m_next;
         if (next == null) {
           state = default(T);
           return false;
         }
         state = next.m_state;
         cmptmp = System.Threading.Interlocked.CompareExchange(ref 
m_tail, next, cmp);
       } while (cmp != cmptmp);
       return true;
     }
   };

===


Lockfree is easy, you will notice that between the

the "cmp = cmptmp;"

and the:

"cmptmp = System.Threading.Interlocked.CompareExchange(ref m_tail, next, 
cmp);"

It's as we had a critical section, cause if for example  two threads
crossed the "cmp = cmptmp;"  , one of them will succeed and another
will retry and loop again, hence this lockfree mechanism is the same as 
a critical section,
but the difference between Lockfree and Lock algorithms is that
there can be no context switches inside the "cmptmp = 
System.Threading.Interlocked.CompareExchange(ref m_tail, next, cmp);"
but in lock algorithms you can have a context switch inside the critical 
section, other than that in lockfree algorithms if you have a problem 
with a thread and it has stopped right on "cmptmp = 
System.Threading.Interlocked.CompareExchange(ref m_tail, next, cmp);"
there will be still progress of the other threads , that's not the case
in Lock based algorithms , other than that Lockfree algorithms are
immune to  priority inversion, cause if a lower priority thread
is doing "System.Threading.Interlocked.CompareExchange(ref m_tail, next, 
cmp);" there will be no context switch , that's not the case with lock 
based algorithms , lock based algorithms are not immune to priority 
inversion, so as you have noticed Lockfree algorithms are more 
resiliente than Lock based algorithms, but this is not the end of the
story , Lockfree algorithms on the other hand can have too much 
cache-cohency traffic, much more than Lockfre based algorithms that uses 
scalable Locks, and more than that scalable Locks
are FIFO fair, and this is not the case with Lockfree algorithms , they
are not FIFO fair, hence they can  have starvation, so Lockfree algorithms
are not silver bullet.




Hope you have understood.



Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#3908

On 10/10/2013 3:33 PM, aminer wrote:
> Lockfree algorithms on the other hand can have too much cache-cohency
> traffic, much more than Lockfre based algorithms that uses scalable Locks

I mean:

Lockfree algorithms on the other hand can have too much cache-cohence
traffic, much more than Lock based algorithms that uses scalable Locks.


Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#3910

On 10/10/2013 3:33 PM, aminer wrote:
> and more than that scalable Locks
> are FIFO fair, and this is not the case with Lockfree algorithms


I mean scalable Locks such us the scalable Anderson Lock or
the scalable MCS Lock or my scalable distributed fair Lock are
FIFO fair.




Thank you,
Amine Moulay Ramdane,

[toc] | [prev] | [next] | [standalone]

#3912

> "aminer"  wrote in message news:l36ve6$pdq$1@news.albasani.net...

> Hello,

> Lockfree or not to lockfree , that's the question ...

[...]

https://groups.google.com/forum/#!original/comp.programming.threads/H24OfsoEttA/zT0vqAOMMrwJ
(you know this one)


https://groups.google.com/forum/#!original/comp.programming.threads/V2rTfDTdZzo/zm0XFuZlxv0J
(read this, and the whole damn thread!) 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web